最近题目记录

1，二分图染色法 hdu 5285 wyh2000 and pupil

　　题意：一共有 N 个人，有些人之间不认识（a不认识b则b不认识a），要分成两组，每组的人都相互认识，且每组至少一人，问是否能可以做到，若可以则输出每组人数

　　这是第一次接触二分图。。。写了好久一直TTTTTTT。。。无奈之下只好看题解了。。

　　

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 100005 ;
vector<int> G[maxn] ;
int vis[maxn] ;
int N, M ;

void init()
{
    scanf("%d%d",&N,&M) ;
    for (int i = 0; i <= N; ++ i) {
        G[i].clear() ;
        vis[i] = -1 ;
    }
}

int fi(int st)
{
    queue<int> Q;
    Q.push(st) ;
    int re[] = {0,1} , x , y , tmp ;
    vis[st] = 1 ;
    while (!Q.empty()) {
        x = Q.front() ;
        Q.pop() ;
        for (int i = 0; i < G[x].size(); ++ i) {
            y = G[x][i] ;
            if (vis[y] == -1) {
                Q.push(y) ;
                vis[y] = !vis[x] ;
                re[vis[y]] ++ ;
            }
            else if (vis[y] == vis[x]) return -1;
        }
    }
    tmp = (re[0] < re[1] ? re[0] : re[1]) ;
    return tmp ;
}

void solve()
{
    init() ;
    int i, j , a, b ;
    for (i = 0; i < M; ++ i) {
        scanf("%d%d",&a,&b) ;
        G[a].push_back(b) ;
        G[b].push_back(a) ;
    }
    if (N <= 1) {
        puts("Poor wyh") ;
        return ;
    }
    if (M == 0) {
        printf("%d 1
",N-1) ;
        return ;
    }
    int tmp, ans = 0 ;
    for (i = 1; i <= N; ++ i) {
        if (vis[i] == -1) {
            tmp = fi(i) ;
            if (tmp == -1) {
                puts("Poor wyh") ;
                return ;
            }
            else ans += tmp ;
        }
    }
    if (ans == N) {
        printf("%d 1
",ans-1) ;
    }
    else {
        if (ans > N - ans) printf("%d %d
",ans,N - ans) ;
        else printf("%d %d
",N-ans,ans) ;
    }
}

int main()
{
    int T ;
    scanf("%d",&T) ;
    while (T --) {
        solve() ;
    }
    return 0 ;
}
hdu 5285

2，简单动规 hdu 1087 Super Jumping! Jumping! Jumping!

　　题意：有N个台阶，每个台阶（假设从左往右编号为1到N）上面都有一个数字，只能从数字小的台阶跳到数字大的台阶（相等也不行），问从0号台阶跳到N+1号台阶最大的花费（落在的台阶上面的数字之和） ，

　　

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std ;
#define LL long long
const LL maxn = 1010 ;
LL N ;
LL dp[maxn] , a[maxn] ;

int main()
{
    while (scanf("%d",&N) == 1 && N) {
        for (LL i = 1; i <= N; ++ i) {
            scanf("%d",&a[i]) ;
        }
        memset(dp,0,sizeof(dp)) ;
        for (LL i = N-1; i >= 0; i --) {
            for (LL j = i + 1; j <= N; ++ j) {
                if (a[i] < a[j]) {
                    if (dp[i] < dp[j] + a[j]) dp[i] = dp[j] + a[j] ;
                }
            }
        }
        printf("%d
",dp[0]) ;
    }
    return 0 ;
}
hdu 1087

3，线段树成段更新 hdu 1698 Just a Hook

　　题意：　　　　有一个钩子长度是N，每单位的价值为1，或2，或3，初始时均为1，多次成段更新后问总价值。

　　

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
const int maxn = 100005 ;
struct Node
{
    int le;
    int ri;
    int sc;
    int xx;
    bool tag;
};
int N, M, flag = 1 ;
Node A[maxn<<2] ;

void build(int i,int le,int ri)
{
    A[i].le = le ;
    A[i].ri = ri ;
    A[i].sc = 1 ;
    A[i].xx = 0 ;
    A[i].tag = false ;
    if (le == ri) return ;
    int mid = (le + ri)/2 ;
    build(i<<1,le,mid) ;
    build(i<<1|1,mid+1,ri) ;
    A[i].sc = A[i<<1].sc + A[i<<1|1].sc ;
}

void pushdown(int i)
{
    A[i].tag = false ;
    A[i<<1].tag = A[i<<1|1].tag = true ;
    A[i<<1].xx = A[i<<1|1].xx = A[i].xx ;
    A[i<<1].sc = (A[i<<1].ri - A[i<<1].le + 1)*A[i].xx ;
    A[i<<1|1].sc = (A[i<<1|1].ri - A[i<<1|1].le + 1)*A[i].xx ;
}

void update(int i,int le,int ri,int xx)
{
    if (A[i].le == le && A[i].ri == ri) {
        A[i].tag = true ;
        A[i].xx = xx ;
        A[i].sc = (A[i].ri - A[i].le + 1)*xx ;
        i /= 2 ;
        while (i) {
            A[i].sc = A[i<<1].sc + A[i<<1|1].sc ;
            i /= 2 ;
        }
        return ;
    }
    if (A[i].tag) pushdown(i) ;
    int mid = (A[i].le + A[i].ri)/2 ;
    if (ri <= mid) update(i<<1,le,ri,xx) ;
    else if (le > mid) update(i<<1|1,le,ri,xx) ;
    else {
        update(i<<1,le,mid,xx) ;
        update(i<<1|1,mid+1,ri,xx) ;
    }
    A[i].sc = A[i<<1].sc + A[i<<1|1].sc ;
}


void sol()
{
    scanf("%d%d",&N,&M) ;
    build(1,1,N) ;
    int st, to, xx ;
    for (int i = 1; i <= M; ++ i) {
        scanf("%d%d%d",&st,&to,&xx) ;
        update(1,st,to,xx) ;
    }
    printf("Case %d: The total value of the hook is %d.
",flag++,A[1].sc) ;
}

int main()
{
    int T ;
    scanf("%d",&T) ;
    while (T --) {
        sol() ;
    }
    return 0 ;
}
hdu 1698

4，最短路 hdu 2544 最短路 （模板）

　　题意：裸题。。

　　

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define LL long long
const LL inf = 0x3f3f3f3f ;
const LL maxn = 110 ;
LL N, M ;
LL low[maxn] ;
LL G[maxn][maxn] ;
bool vis[maxn] ;
vector<LL> GG[maxn] ;

void init()
{
    memset(G,inf,sizeof(G)) ;
    memset(low,inf,sizeof(low)) ;
    memset(vis,false,sizeof(vis)) ;
    for (LL i = 1; i <= N; ++ i) {
        G[i][i] = 0 ;
        GG[i].clear() ;
    }
}

void spfa(LL st,LL to)
{
    low[st] = 0 ;
    vis[st] = true ;
    LL u, v ;
    queue<LL> X ;
    X.push(st) ;
    while (!X.empty()) {
        u = X.front() ;
        vis[u] = false ;
        X.pop() ;
        for (LL i = 0; i < GG[u].size(); ++ i) {
            v = GG[u][i] ;
            if (low[v] > low[u] + G[u][v]) {
                low[v] = low[u] + G[u][v] ;
                if (!vis[v]) {
                    vis[v] = true ;
                    X.push(v) ;
                }
            }
        }
    }
    printf("%d
",low[N]) ;
}

void sol()
{
    init() ;
    LL st, to, sc ;
    for (LL i = 0; i < M; ++ i) {
        scanf("%I64d%I64d%I64d",&st,&to,&sc) ;
        if (G[st][to] != inf) {
            GG[st].push_back(to) ;
            GG[to].push_back(st) ;
        }
        G[st][to] = (G[st][to] < sc ? G[st][to] : sc) ;
        G[to][st] = G[st][to] ;
    }
    spfa(1,N) ;
}

int main()
{
    while (scanf("%I64d%I64d",&N,&M) == 2 &&(N && M)) {
        sol() ;
    }
    return 0 ;
}
hdu 2544

5. 线段树求逆序数.hdu 1394 Minimum Inversion Number

　　线段树单点更新。

　　

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std ;
 7 const int maxn = 5010 ;
 8 struct Node
 9 {
10     int le , ri , sc , xx ;
11 };
12 Node A[maxn<<2] ;
13 int s[maxn] , a[maxn] ;
14 
15 void build(int i,int le,int ri)
16 {
17     A[i].le = le , A[i].ri = ri , A[i].sc = 0 ;
18     if (le == ri) {
19         s[le] = i ;
20         return ;
21     }
22     int mid = (le+ri)/2 ;
23     build(i<<1,le,mid) ;
24     build(i<<1|1,mid+1,ri) ;
25 }
26 
27 void ins(int x)
28 {
29     int i = s[x] ;
30     while (i) {
31         A[i].sc ++ ;
32         i /= 2 ;
33     }
34 }
35 
36 int GetSum(int i,int le,int ri)
37 {
38     if (le < A[i].le || A[i].ri < ri || ri < le) return 0 ;
39     if (A[i].le == le && A[i].ri == ri) return A[i].sc ;
40     int mid = (A[i].le + A[i].ri)/2 ;
41     if (ri <= mid) return GetSum(i<<1,le,ri) ;
42     else if (le > mid) return GetSum(i<<1|1,le,ri) ;
43     else return (GetSum(i<<1,le,mid) + GetSum(i<<1|1,mid+1,ri)) ;
44 }
45 
46 int main()
47 {
48     int N , x , ans ;
49     while (cin >> N) {
50         build(1,1,N) ;
51         ans = 0 ;
52         for (int i = 1 ; i <= N ; ++ i) {
53             scanf("%d",&x) ;
54             a[i] = x + 1 ;
55             ans += GetSum(1,x+2,N) ;
56             ins(1+x) ;
57         }
58         int sum = ans , tmp ;
59         for (int i = N ; i >= 1 ; i --) {
60             tmp = sum - N +2*a[i] - 1 ;
61             sum = tmp ;
62             ans = (ans < tmp ? ans : tmp) ;
63         }
64         cout << ans << endl ;
65     }
66     return 0 ;
67 }
hdu 1394

6.线段树~poj2528 Mayor's posters

成段更新加离散化（啊啊啊啊啊！！！map超时了大概是我的姿势不够优美）

  1 /*********************************************************************
  2     > File Name: poj2528.cpp
  3     > Author: CROSShh
  4     > Mail: smile_wen@foxmail.com 
  5     > Created Time: 2015年11月20日 星期五 21时55分08秒
  6  ********************************************************************/
  7 
  8 #include <iostream>
  9 #include <stdio.h>
 10 #include <stdlib.h>
 11 #include <cstring>
 12 #include <algorithm>
 13 #include <cmath>
 14 #include <map>
 15 #include <set>
 16 #include <list>
 17 using namespace std;
 18 #define LL long long
 19 const int maxn = 200010 ;
 20 int vis[maxn<<2] , s[maxn<<2] , N ;
 21 struct Node
 22 {
 23     int le , ri , mid , sc , tag ;
 24 }A[maxn<<2] ;
 25 
 26 void build(int i,int le,int ri)
 27 {
 28     A[i].le = le , A[i].ri = ri , A[i].mid = (le + ri)/2 ;
 29     A[i].sc = 0 , A[i].tag = 0 ;
 30     if (le == ri) {
 31         s[le] = i ;
 32         return ;
 33     }
 34     build(i<<1,le,A[i].mid) ;
 35     build(i<<1|1,A[i].mid+1,ri) ;
 36 }
 37 
 38 void pushdown(int i)
 39 {
 40     A[i].tag = 0 , A[i<<1].tag = A[i<<1|1].tag = 1 ;
 41     A[i<<1|1].sc = A[i<<1].sc = A[i].sc ;
 42 }
 43 
 44 void update(int i,int le,int ri,int id)
 45 {
 46     if (le < A[i].le || A[i].ri < ri) return ;
 47     if (A[i].le == le && A[i].ri == ri) {
 48         A[i].tag = 1 , A[i].sc = id ;
 49         return ;
 50     }
 51     if (A[i].tag) pushdown(i) ;
 52     if (ri <= A[i].mid) update(i<<1,le,ri,id) ;
 53     else if (le > A[i].mid) update(i<<1|1,le,ri,id) ;
 54     else {
 55         update(i<<1,le,A[i].mid,id) ;
 56         update(i<<1|1,A[i].mid+1,ri,id) ;
 57     }
 58 }
 59 
 60 void query(int i)
 61 {
 62     if (A[i].le == A[i].ri) return ;
 63     if (A[i].tag) pushdown(i) ;
 64     query(i<<1) ;
 65     query(i<<1|1) ;
 66 }
 67 
 68 int Aa[maxn] , cnt , xx , pp[10000005] ;
 69 struct node
 70 {
 71     int le , ri ;
 72 }AZ[maxn] ;
 73 
 74 void change()
 75 {
 76     sort(Aa,Aa+cnt) ;
 77     xx = pp[Aa[0]] = 1 ;
 78     for (int i = 1 ; i < cnt ; ++ i) {
 79         if (Aa[i] == Aa[i-1]) continue ;
 80         else if (Aa[i] == Aa[i-1] + 1) pp[Aa[i]] = xx + 1 ;
 81         else pp[Aa[i]] = xx + 2 ;
 82         xx = pp[Aa[i]] ;
 83     }
 84     xx = pp[Aa[cnt-1]] ;
 85     int le , ri ;
 86     build(1,1,xx) ;
 87     memset(vis,0,sizeof(vis)) ;
 88     for (int i = 1 ; i <= N ; ++ i) {
 89         le = pp[AZ[i].le] , ri = pp[AZ[i].ri] ;
 90         update(1,le,ri,i) ;
 91     }
 92     query(1) ;
 93 }
 94 
 95 int main()
 96 {
 97     // freopen("in","r",stdin) ;
 98     int T , le , ri ;
 99     scanf("%d",&T) ;
100     while (T --) {
101         scanf("%d",&N) ;
102         cnt = 0 ;
103         for (int i = 1 ; i <= N ; ++ i) {
104             scanf("%d%d",&le,&ri) ;
105             Aa[cnt++] = le , Aa[cnt++] = ri ;
106             AZ[i].le = le , AZ[i].ri = ri ;
107         }
108         change() ;
109         int x , ans = 0 ;
110         for (int i = 1 ; i <= xx ; ++ i) {
111             x = A[s[i]].sc ;
112             if (vis[x] || x == 0) continue ;
113             else {
114                 vis[x] = 1 ;
115                 ans ++ ;
116             }
117         }
118         printf("%d
",ans) ;
119     }
120     return 0 ;
121 }
poj2528

7. 最近公共祖先（裸） poj 1330 Nearest Common Ancestors

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/smile-0/p/4683529.html