按：并不是独立做出来的......参考内容见附录。

HDU 1232 (并查集)

并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构： Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union：将两个子集合并成同一个集合。

本题要求并不复杂，仅需一个一位数组记录父节点即可。初始化将第 i 个元素的父节点设为 1，然后对每对连通的元素将它们的父节点统一即可（统一成祖先节点）。查找祖先节点需要递归，而在递归中将子节点的父节点升到祖先节点可以简化后面的查找操作。

2017/4/15 Update：本题与HDU1213几乎相同。

C 代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <string.h>

int father[1005];

int getfather(int v) {
        if (father[v]==v) return v;
        else {
                father[v]=getfather(father[v]);
                return father[v];
        }
}

void conjunction(int x, int y){
        int fx,fy;
        fx=getfather(x);
        fy=getfather(y);
        if (fy!=fx) father[fx]=fy;
}

int main(){
        int i,n,m,x,y,counter;
        while (scanf("%d",&n) && n!=0) {
                scanf("%d",&m);
                counter=0;
                memset(father,0,sizeof(father));
                for (i=1;i<=n;i++) father[i]=i;
                while (m--) {
                        scanf("%d%d",&x,&y);
                        conjunction(x,y);
                }
                for (i=1;i<=n;i++) if (father[i]==i) counter++;
                printf("%d\n",counter-1);
        }
        return 0;
}

HDU 5943 (二分匹配)

个人觉得一些 tricky 或者需要注意的点： 1. 连续 600 个数里必有 2 个质数（n 大于 600 直接 No，不用管大规模多么爽）。 2. s+1<=n 的情况，把 s 与 n 互换就没有了重叠项。

二分匹配 - 匈牙利算法

  1. 从左边第 1 个顶点开始，挑选未匹配点进行搜索，寻找增广路。如果经过一个未匹配点，说明寻找成功。更新路径信息，匹配边数 +1，停止搜索。如果一直没有找到增广路，则不再从这个点开始搜索。事实上，此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去，而不影响结果。
  2. 由于找到增广路之后需要沿着路径更新匹配，所以我们需要一个结构来记录路径上的点。DFS 版本通过函数调用隐式地使用一个栈，而 BFS 版本使用 prev 数组。

C++ 代码(是[3]的，自己写的 RE 了好几次:< )： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
using namespace std;

const int N = 615;
int used[N], vis[N], n, s;
vector<int> G[N];

bool Find(int u)
{
    int len=G[u].size();
    for(int i=0; i<len; i++)
    {
        int v = G[u][i];
        if(!vis[v])
        {
            vis[v] = 1;
            if(!used[v] || Find(used[v]))
            {
                used[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int T, t = 1;
    scanf("%d", &T);
    while(T --)
    {
        scanf("%d %d", &n, &s);
        if(s+1 <= n) //忽略中间重合的部分;
            swap(s, n);
        if(n > 600) //因为连续600个数中一定有>=2个素数, 1只有一个，所以结果都是No;
        {
            printf("Case #%d: No\n", t++);
            continue;
        }
        for(int i=0; i<=n; i++)
            G[i].clear();
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if((s+i)%j == 0) //说明s+i是j的倍数;
                    G[i].push_back(j);
            }
        }
        memset(used, 0, sizeof(used));
        int ans = 0;
        for(int i=1; i<=n; i++)
        {
            memset(vis, 0, sizeof(vis));
            ans += Find(i);
        }
        if(ans != n) //必须要找到所有与之对应的才可以;
            printf("Case #%d: No\n", t++);
        else
            printf("Case #%d: Yes\n", t++);
    }
    return 0;
}

SCU 4512 (DP)

C++ 代码(是[4]的)： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int dp[2][250010]; //前i个木块使得两份木块高度差为j的最大可达高度是多少

int main(){
    int t, n, h;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i = 0; i < 250010; ++i) dp[0][i] = dp[1][i] = -1;
        int now = 1;
        dp[now][0] = 0;
        for(int i = 0; i < n; i++){
            scanf("%d", &h);
            now = now^1; //换边
            for(int j = 0; j < 250010; j++){
                dp[now][j] = max(dp[now][j], dp[1-now][j]);
                if(dp[1-now][j] < j || h>=250010) continue;
                if(j+h<250010) dp[now][j+h] = max(dp[now][j+h],dp[1-now][j]+h); //积木放到较高的一方
                dp[now][abs(h-j)] = max(dp[now][abs(h-j)], max(dp[1-now][j]-j+h, dp[1-now][j])); //积木放到较低的一方
            }
        }
        if(dp[now][0] > 0) printf("%d\n",ans);
        else printf("GG\n");
    }
	return 0;
}

本文参考了： 1. http://blog.csdn.net/ebowtang/article/details/50515067 2. http://www.itdadao.com/articles/c15a669765p0.html 3. http://blog.csdn.net/abc13068938939/article/details/52966064 4. http://liangxianfeng.top/2016/05/23/Goozy%E6%90%AD%E7%A7%AF%E6%9C%A8/