SCUACM 2016集训 7.6【17/20】

ACM_集训

集训期间完成15道，补题2道。
比赛链接：http://vjudge.net/contest/120875#overview

A.How far away ？(Tarjan LCA)

题意：

无向图，给定边及边权重，任意两点之间都有一条唯一的道路，道路上每个点只能出现一次。给定询问，求询问的结点之间的距离。

分析：

路上每个点只能出现一次，可以转化成有根树，问题也即为求最近公共祖先问题~~ 这里每条边加上了距离，求出LCA后，用u、v的距离根的距离和减去2倍的根到最近公共祖先的距离即可，然后就是tarjan LCA 模板题了。

代码：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define fuck cout<<"fuck"<<endl;
const int maxn = 40005, maxq = 205;
typedef pair<int, int>p;
vector<p>G[maxn];
#define fi first
#define se second
int pa[maxn];
bool vis[maxn];
bool in[maxn];
int ance[maxn];
int dist[maxn];
int n, tot;
int head[maxn];
int ans[maxn];
struct Query{int to, next, index;};
Query query[maxq * 2];
void add_query(int u, int v, int index)
{
    query[tot].to = v;
    query[tot].index = index;
    query[tot].next = head[u];
    head[u] = tot++;
    query[tot].to = u;
    query[tot].index = index;
    query[tot].next = head[v];
    head[v] = tot++;
}
int _find(int x)
{
    if(pa[x] != x) return pa[x] = _find(pa[x]);
    return x;
}
void unite(int x, int y)
{
    int rx = _find(x), ry = _find(y);
    if(rx == ry) return;
    pa[rx] = ry;
}
void init()
{
    tot = 0;
   for(int i = 1; i <= n; i++){
        G[i].clear();
        pa[i] = i;
   }
    mem(ance, 0);
    mem(vis, false);
    mem(head, -1);
    mem(dist, 0);
    mem(in, false);
    mem(ans, 0);
}
void LCA(int u)
{
    ance[u] = u;
    vis[u] = true;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i].fi;
        if(vis[v]) continue;
        dist[v] = dist[u] + G[u][i].se;
        LCA(v);
        unite(u, v);
        ance[_find(u)] = u;
    }
    for(int i = head[u]; i != -1; i = query[i].next){
        int v = query[i].to;
        if(vis[v])  ans[query[i].index] = dist[u] + dist[v] - 2 * dist[ance[_find(u)]];
    }
}
int main(void)
{
    int u, v, k;
    int a, b, c;
    int Q;
    int T;scanf("%d", &T);
    while(T--){
        init();
        scanf("%d%d", &n, &Q);
        for(int i = 0; i < n - 1; i++){
            scanf("%d%d%d",&a, &b, &c);
            G[a].push_back(p(b, c));
            G[b].push_back(p(a, c));
        }
        for(int i = 0; i < Q; i++){
           scanf("%d%d",&u,&v);
            add_query(u, v, i);
        }
        dist[1] = 0;
        LCA(1);
        for(int i = 0; i <Q; i++){
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}

B - Network(LCA + 并查集)

题意：

给定无向图，给定若干询问，每个询问加入一条边，问加入该边后图中桥的数目。

分析：

首先想是缩点，缩点之后形成的是棵树，树边均为桥，每加一条新边，就把他们所在集合并起来。这样就在树上形成了一个环，环中所有边都不再是桥。找环中的边的过程实际就是找最近公共祖先的过程，向上爬的过程中遇到的所有边都不再是桥。
集合并起来很自然的想到用并查集搞，而缩点过程我们也可以在tarjan求桥的同时求用并查集搞。对于每个询问在两个点向上爬的时候判断该点是否与父节点在同一集合中，若不是，说明连边为桥，删去，并将该点与其父节点并起来。
QAQ在缩点的时候我们用深度最低的点来代表他所处在的强连通分量中，利用这点就可以在求LCA时集合合并的同时让结点向上一步一步的跳。

代码：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/*************************************************************************
    > File Name: 3694.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/14 13:37:27
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5, maxm = 2e5 + 5;
int head[maxn], dfn[maxn], low[maxn];
struct EDGE{
	int to, next;
	bool vis;
};
EDGE edge[maxm * 2];
int tot, dfnum;
int btot;
int pa[maxn], fa[maxn];
int dep[maxn];
void init(int n)
{
    tot = 0;
	btot = 0;
    dfnum = 1;
    memset(head, -1, sizeof(head));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
	for(int i = 1; i <= n; i++) pa[i] = i;
}
int _find(int x)
{
	if(x == pa[x]) return x;
	return pa[x] = _find(pa[x]);
}
void unit(int x, int y)
{
	int rx = _find(x), ry = _find(y);
	if(rx == ry) return;
	pa[rx] = ry;
}
void addedge(int u, int v)
{
	edge[tot].vis = false;
	edge[tot].to = v;
	edge[tot].next = head[u];
	head[u] = tot++;
}
void dfs(int u, int depth)
{
    dfn[u] = low[u] = dfnum++;
	dep[u] = depth;
    for(int i = head[u]; i != -1; i = edge[i].next){
        if(edge[i].vis) continue;
		edge[i].vis = edge[i ^ 1].vis = true;
		int v = edge[i].to;
        if(!dfn[v]){
			fa[v] = u;
            dfs(v, depth + 1);
            low[u] = min(low[u], low[v]);
		}else low[u] = min(low[u], dfn[v]);
        if(low[v] <= dfn[u]) unit(v, u);
		else btot++;
    }
}
int LCA(int u, int v)
{
	int cnt = 0;
	while(dep[u] > dep[v]){
		if(_find(u) != _find(fa[u])) cnt++;
		unit(u, fa[u]);
		u = fa[u];
	}
	while(dep[v] > dep[u]){
		if(_find(v) != _find(fa[v])) cnt++;
		unit(v, fa[v]);
		v = fa[v];
	}
	while(u != v){
		if(_find(u) != _find(fa[u])) cnt++;
		unit(u, fa[u]);
		if(_find(v) != _find(fa[v])) cnt++;
		unit(v, fa[v]);
		u = fa[u];
		v = fa[v];
	}
	return cnt;
}
int main (void)
{
	int n, m;
	int a, b;
	int kas = 1;
	while(~scanf("%d%d", &n, &m) && (n + m)){
		init(n);
		for(int i = 0; i < m; i++){
			scanf("%d%d", &a, &b);
			addedge(a, b);
			addedge(b, a);
		}
		fa[1] = 1;
		dfs(1, 1);
		int q;scanf("%d", &q);
		printf("Case %d:\n", kas++);
		for(int i = 0; i < q; i++){
			scanf("%d%d", &a, &b);
			if(_find(a) != _find(b)) btot -= LCA(a, b);
			printf("%d\n", btot);
		}
		puts("");
	}
	return 0;
}

E.Crossing River(数学)

题意：

经典过河问题，一个船只能运两个人，每个人过河时间不同，船来回往返使得$n$个人全部通过，问如何安排使得总时间最小。

分析：

小学奥数题的感觉。。
决策如下：

  1. $n <= 2$，直接过河。
  2. $n = 3$，让最快的往返一次。
  3. $n >= 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*************************************************************************
	> File Name:
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef pair<int, int>p;
typedef long long ll;
const int maxn = 1e3 + 5;
int a[maxn];
int main (void)
{
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        for(int i = 0; i < n; i++) cin>>a[i];
        sort(a, a + n);
        int ans = 0;
        while(n){
            if(n == 1){
                ans += a[0];
                break;
            } else if(n == 2){
                ans += a[1];
                break;
            }else if(n == 3){
                ans += a[0] + a[1] + a[2];
                break;
            }else{
                int t1 = a[0] * 2 + a[n - 1] + a[n - 2];
                int t2 = a[1] * 2 + a[0] + a[n - 1];
                n -= 2;
                ans += min(t1, t2);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

G.Piotr’s Ants(找规律)

题意：

给定$n$个蚂蚁的初始位置及方向，两只蚂蚁相遇后同时掉头，速度均为$1m/s$，问$T$时间后，各个蚂蚁的位置。

分析：

可以将问题看成，两只蚂蚁相遇后交换速度和方向，那么本质就相当于相遇后直接穿过对方，继续原方向行走，而由于两只蚂蚁相遇后直接掉头，所以最后 所有蚂蚁的相对顺序保持不变，这样我们算出所有终态，排个序，按照对应初始位置的顺序输出即可。注意判断是否掉下去的优先级要比位置是否相同的高！

代码：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
/*************************************************************************
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
#define pr(x) cout<<#x<<":"<<x
#define pl(x) cout<<#x<<":"<<x<<endl
#define sa(n) scanf("%d", &(n))
#define sal(n) scanf("%I64d", &(n))
typedef long long ll;
const int maxn = 1e4 + 5, oo = 0x3f3f3f3f;
struct NODE{int x; int dir; int id;};
NODE node[maxn], nnode[maxn];
map<int, int>MAP;
bool cmp(NODE a, NODE b)
{
    return a.x < b.x;
}
int main (void)
{
    int N;sa(N);
    for(int kas = 1; kas <= N; kas++){
        int L, T, n;sa(L);sa(T);sa(n);
        int x;
        for(int i = 1; i <= n; i++){
            sa(x);getchar();
            if(getchar() == 'L'){
                node[i] = (NODE){x, 1, i};
                nnode[i] = (NODE){x - T, 1, 0};
            }else{
                node[i] = (NODE){x, 2, i};
                nnode[i] = (NODE){x + T, 2, 0};
            }
        }
        sort(node + 1, node + n + 1, cmp);
        for(int i = 1; i <= n; i++){
           MAP[node[i].id] = i;
        }
        sort(nnode + 1, nnode + n + 1, cmp);
        for(int i = 1; i <= n; i++){
            if(nnode[i].x < 0 || nnode[i].x > L)
                nnode[i].dir = -1;
            else if(i < n && nnode[i].x == nnode[i + 1].x){
                nnode[i].dir = 0;
                nnode[i + 1].dir = 0;
            }
        }
        printf("Case #%d:\n", kas);
        for(int j = 1; j <= n; j++){
            int i = MAP[j];
            if(nnode[i].dir == -1) {
                cout<<"Fell off"<<endl;
                continue;
            }
            cout<<nnode[i].x<<' ';
            if(nnode[i].dir == 1){
                cout<<'L'<<endl;
            }else if(nnode[i].dir == 2){
                cout<<'R'<<endl;
            }else if(nnode[i].dir == 0){
                cout<<"Turning"<<endl;
            }
        }
        cout<<endl;
        /*for(int i = 1; i <= n; i++){
            cout<<nnode[i].id<<' '<<nnode[i].x<<' '<<nnode[i].dir<<endl;
        }*/
    }
    return 0;
}

H- Intellectual Inquiry【dp，构造】

题意：

给定字符串，要求用字母表前$k$个字母组成长度为$n$的字符串，并添加在已知字符串后面，使得不同子序列个数最多，求个数。

分析：

设$dp[i]:=前i个元素组成的子序列个数$，则有$dp[i] = dp[i - 1] * 2 - 重复序列个数$.
如何求得重复序列呢？首先对于每个$i$，我们都保证$dp$值中不存在重复序列，那么对于第$i$个元素，只需考虑$s[i]$对于序列的影响即可。而这重复部分即为$s[i]$上一个位置$last[s[i] - ‘a’ ]$之前的所有元素与$s[i]$形成的序列，即重复序列个数=$dp[last[s[i]-‘a’]-1]$。
为使最后得到的$dp$值最大，我们要尽量减小$dp[last[s[i]-‘a’]-1]$，而显然$dp$值是单调上升的，构造时每次选取last值最小的即可~~每次得到的$dp$都是最大的，这样累加起来最后得到的而$dp[n+m]$也一定是最大的。

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5, mod = 1e9 + 7;
char s[maxn];
int dp[maxn];
int last[26 + 5];
int main (void)
{
	int n, k;scanf("%d%d", &n, &k);
	scanf("%s", s + 1);
	int m = strlen(s + 1);
	memset(last, -1, sizeof(last));
	dp[0] = 1;
	int tmp, res;
	for(int i = 1; i <= n + m; i++){
		if(i <= m) tmp = s[i] - 'a';
		else{
			res = n + m + 1, tmp = 0;
			for(int j = 0; j < k; j++){
				if(res > last[j]){
					res = last[j];
					tmp = j;
					if(res == -1) break;
				}
			}
		}
		if(last[tmp] > 0) (dp[i] = dp[i - 1] * 2 % mod - dp[last[tmp] - 1] + mod) %= mod;
		else dp[i] = dp[i - 1]  * 2 % mod;
		last[tmp] = i;
	}
	printf("%d\n", dp[m + n]);
	return 0;
}

I.The Water Bowls(反转开关问题)

题意：

给定01序列，翻转一位其左右相邻两位也会被翻转，问使序列全部变为0的最小翻转次数。

分析：

简单线性排列，由于后面是否翻转由前面的决定，所以我们枚举第一个元素的状态，然后从头扫一遍即可。

代码：

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
/*************************************************************************
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
#define pr(x) cout<<#x<<":"<<x
#define pl(x) cout<<#x<<":"<<x<<endl
#define sa(n) scanf("%d", &(n))
#define sal(n) scanf("%I64d", &(n))
typedef long long ll;
const int maxn = 20 + 5, oo = 0x3f3f3f3f;
int f[maxn], a[maxn];
int main (void)
{
    for(int i = 0; i < 20; i++){
        cin>>a[i];
    }
    memset(f, 0, sizeof(f));
    int cnt = 0;
    for(int i = 1; i < 20; i++){
        if((a[i - 1] + f[i - 1]) & 1){
            cnt++;
             f[i]++;
             f[i + 1]++;
        }
    }
    memset(f, 0, sizeof(f));
    int cnt2 = 1;
    f[0] = f[1] = 1;
    for(int i = 1; i < 20; i++){
        if((a[i - 1] + f[i - 1]) & 1){
             cnt2++;
             f[i]++;
             f[i + 1]++;
        }
    }
    cout<<min(cnt, cnt2)<<endl;
    return 0;
}

J.Fliptile(反转开关问题)

题意：

有$m*n$个黑白块，黑块的背面是白块，白块背面是黑块，一头牛踩一块，则这个块的上下左右的方块都会转动，问至少踩多少块，才会使所有块都变成白色？

分析：

一个块的转动会影响其他块的状态，这里不是简单的线性排列，不能只踩黑块。
首先根据字典序，我们可以对第一排从$00…00$到$11..11$进行考虑(1表示踩)，再后续一排一排的考虑。因为踩一块四周的块都会转动，所以必须规定个踩的原则，发现对于某块来说，他一旦改变上方块的状态，那个块就再也不会改变了，而其他块还有他的下一列改变他的机会（如果存在），所以就以上一行块为原则，如果上方为黑，则踩。最后判断最后一行是否全白。
字典序，因为他说了是把整个排列当做字符串的字典序，所以肯定是越前面的越小越好，而且从第一个例子中也能看出来。

代码：

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<iostream>
#include<cstring>
using namespace std;
#define mem(s,a)  memset(s,a,sizeof(s));
int m, n;
const int maxn = 25, INF = 0x3fffffff;
int x[5]={-1,0,0,0,1};
int  y[5] = {0,1,0,-1,0};
int s[maxn][maxn], a[maxn][maxn], r[maxn][maxn], ans[maxn][maxn];
int cal()
{
    int cnt = 0;
    for(int i = 2; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if((a[i-1][j] + r[i-1][j]) % 2 == 1) {
                cnt++;
                s[i][j] = 1;
            }
            for(int k = 0; k < 5; k++){
                r[i + x[k]][j + y[k]] += s[i][j];
            }
        }
    }
    for(int i =1; i <= n; i++){
        if((r[m][i] + a[m][i]) % 2 == 1) return -1;
    }
    return cnt;
}
int main (void)
{
    cin>>m>>n;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            cin>>a[i][j];
        }
    }
    int res = INF;
    for(int i = 0; i <1<<n; i++){
        mem(s,0);mem(r,0);
        int t = 0;
        for(int j =n; j >= 1; j--){
            s[1][j] = i>>j&1;
            for(int k = 0; k < 5; k++){
                r[1 + x[k]][j + y[k]] += s[1][j];
            }
            t += s[1][j];
        }
       int tm = cal();
       if(tm> = 0 && t + tm < res){
            res = t + tm;
            memcpy(ans,s,sizeof(s));
       }
    }
    if(res == INF) {
            cout<<"IMPOSSIBLE"<<endl;
            return 0;
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
           cout<<ans[i][j];
           if(j != n)  cout<<' ';
           else cout<<endl;
        }
    }
    return 0;
}

K.Jessica’s Reading Problem(双指针)

题意：

给定$P$页书及每页的知识点，最少读多少个连续的页使得书中所有知识点都被覆盖。

分析：

最少，连续->双指针
挑战例题，双指针入门题

代码：

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
#include<cstdio>
#include<cstring>
#include<set>
#include<map>
#include<iostream>
using namespace std;
const int maxn = 1e6 + 5;
#define sa(n) scanf("%d", &n)
int a[maxn];
map<int, int>cnt;
int main (void)
{
    int P;sa(P);
    set<int>s;
    for(int i = 0; i < P; i++){
        sa(a[i]);
        s.insert(a[i]);
    }
    int n = s.size();
    int sz = 0;
    int r;
    for(r = 0; r < P; r++){
        if(!cnt[a[r]]) sz++;
        cnt[a[r]]++;
        if(sz == n) break;
    }
    int l = 0;
    int ans = r - l + 1;
    while(r < P){
        if(cnt[a[l]] == 1){
             while(r < P && a[r] != a[l]) {
                r++;
                cnt[a[r]]++;
            }
            if(r == P) break;
        }
        cnt[a[l]]--;
        ans = min(ans,  r - l);
        l++;
    }
    cout<<ans<<endl;
    return 0;
}

L.Bound Found(双指针，巧妙)

题意：

给定序列及target，求一个子序列使得该序列和的绝对值最接近target。

分析：

挑战上的习题
求子区间和问题，先预处理个前缀和。
前缀和有正有负且不单调。因为题目中说的是区间和的绝对值最接近target，所以我们将前缀和排个序，这样保证求出的值为正即为相应区间求出绝对值之后的结果，整个序列单调，这样舍和取的条件非常明确，直接在上面二指针以获取值最接近target的即可。
观察题目中的性质区间和的绝对值，巧妙的化简问题。
最初用的$long long$，姿势不太对一直CE，改回$int$就过了。。不是很理解。。
还有注意结果非空，即$l != r$

代码：

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 1e5 + 5, oo = 0x3f3f3f3f;
int a[maxn];
typedef pair<int, int>P;
P p[maxn];
int n, k;
int ans;
int L, R;
void gao(int t)
{
    int l = 0, r = 1;
    ans =  oo;
    int res = 0;
    while(l <= n && r <= n){
        if(abs(p[r].first - p[l].first- t)< ans){
            ans = abs(p[r].first - p[l].first - t);
            L = p[l].second;
            R = p[r].second;
            res = abs(p[r].first - p[l].first);
        }
        if(p[r].first - p[l].first <  t) r++;
        else if(p[r].first - p[l].first > t) l++;
        else break;
        if(l == r) r++;
    }
    cout<<res<<' '<<min(L, R) + 1<<' '<<max(L, R)<<endl;
}
int main (void)
{
    while(~scanf("%d%d", &n, &k) && (n + k)){
        int sum = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            sum += a[i];
            p[i] = P(sum, i);
        }
        p[0] = P(0, 0);
        sort(p, p + n + 1);
        int t;
        for(int i = 0; i < k; i++){
            scanf("%d", &t);
            gao(t);
        }
    }
    return 0;
}

M.The Values You Can Make(DP)

题意：

用$n$种钱币组成$k$元，问可以再用组成这$m$元的钱币组成多少种钱数？

分析：

可以把题意理解为向两个背包里面装东西，一个最后组成$m$，另一个最后组成我们待求的$x$，前提是放入第二个背包中的东西必须放入第一个背包中，也就是$m$必须包含$x$的钱币。
那么有$dp[i][j][k] := 前i个钱币，组成了j，其中的钱币还可以组成k的情况是否存在$
状态转移方程就很好写了。
滚动数组可以优化。。

代码：

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
#include<cstdio>
#include<cstring>
#include<set>
#include<iostream>
using namespace std;
const int maxn = 5e2 + 5;
bool dp[maxn][maxn][maxn];
int a[maxn];
int main (void)
{
    int n, m;scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    memset(dp, false, sizeof(dp));
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= 0; j--){
            for(int k = j; k >= 0; k--){
               dp[i][j][k] |= dp[i - 1][j][k];
               if(j - a[i] >= k) dp[i][j][k] |= dp[i - 1][j - a[i]][k];
               if(k >= a[i]){
                    dp[i][j][k] |= dp[i - 1][j - a[i]][k - a[i]];
               }
            }
        }
    }
    set<int>v;
    for(int j = 0; j <= m; j++){
        if(dp[n][m][j]) v.insert(j);
    }
    printf("%d\n", v.size());
    set<int>:: iterator s;
    for(s = v.begin(); s != v.end(); s++){
        printf("%d ", *s);
    }
    return 0;
}

N - Dividing Kingdom II(带权并查集，二分图)

题意：

给定$m$条边，若干询问，每次选择编号在$[l,r]$之间的边，将图分成两部分，问如何分才能使得端点在同一部分的最长边最小。

分析：

为使在端点在同一部分的最长边长度最小，我们可以将所有边从大到小排个序，然后每次都贪心的将两条边的端点放在两部分，这样便形成了一个二分图，不停加边直到不能形成二分图，即一条边的端点在同一部分，当前边就是最大值。使用带权并查集判断二分图。

代码：

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
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int, int>p;
const int maxn = 1e3 + 5, maxm = 1e6 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
int pa[maxn];
int kind[maxn];
struct Node{int x, y, val, id;}edge[maxm], nedge[maxm];
int MAP[maxn];
int n, m;
bool cmp(Node a, Node b)
{
    return a.val > b.val;
}
int _find(int a)
{
	int fa = pa[a];
	if(pa[a] == a) return a;
	pa[a] = _find(pa[a]);
	kind[a] = (kind[a] + kind[fa]) % 2;
	return pa[a];
}
void init()
{
    for(int i = 1; i <= n; i++){
        pa[i] = i;
        kind[i] = 0;
    }
}
int gao(int l, int r)
{
    init();
    for(int i = 1; i <= m; i++){
        if(edge[i].id > r || edge[i].id < l) continue;
        int x = edge[i].x, y = edge[i].y;
        int rx = _find(x);
        int ry = _find(y);
        //cout<<rx<<' '<<ry<<endl;
        if(rx != ry){
            pa[rx] = ry;
            // y根 -> y， y->x，x -> x根，即y根->x根
            kind[rx] = (kind[y] + 1 - kind[x] + 2) % 2;
        }
        if(rx == ry && kind[y] == kind[x] ){
            return edge[i].val;
        }
    }
    return -1;
}
int main (void)
{
    int q;
	scanf("%d%d%d", &n, &m, &q);
    int x, y, w;
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &x, &y, &w);
        edge[i].x = x , edge[i].y = y; edge[i].val = w;
        edge[i].id = i;
    }
    sort(edge + 1, edge + m + 1, cmp);
    for(int i = 1; i <= m; i++){
        MAP[edge[i].id] = i;
    }
    int l, r;
    for(int i = 0; i < q; i++){
        scanf("%d%d", &l, &r);
        printf("%d\n", gao(l, r));
	}
	return 0;
}

O. Collecting Bugs(概率DP)

题意：

一个软件有$s$个子系统，会产生$n$种bug，在一个系统中发现一个bug的概率保持不变，问发现$n$种bug，$s$子系统都发现bug的天数的期望。

分析：

有四种状态转移:

  1. 发现的bug在已经发现的$i$个分类和$j$个系统中。概率为$(i j) / (n s)$
  2. 发现的bug在已经发现的$i$个分类，但不属于已有的$j$个系统中。概率为$i (n - j) / (n s)$
  3. 发现的bug不在已有的$i$个分类中，但在已有的$j$个系统中。概率$(n - i) j /(n s)$
  4. 发现的bug不属于已有的$i$个分类也不属于已有的$j$个系统，概率$(n - i) (s - j) / (n s)$

状态转移方程：
$dp[i][j] = 1 + (i j) / (n s) dp[i][j] + i (n - j) / (n s) dp[i + 1][j]+ (n - i) j dp[i + 1][j] + (n - i) (s - j) / (n s) * dp[i + 1][j + 1]$
然后整理一下即可。

代码：

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
/************************************************************************
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
#define pr(x) cout<<#x<<":"<<x
#define pl(x) cout<<#x<<":"<<x<<endl
#define sa(n) scanf("%d", &(n))
#define sal(n) scanf("%I64d", &(n))
typedef long long ll;
const int maxn = 1e3 + 5, oo = 0x3f3f3f3f;
double dp[maxn][maxn];
int main (void)
{
    int n, s;
    while(~scanf("%d%d", &n, &s)){
        memset(dp, 0, sizeof(dp));
        for(int i = n; i >= 0; i--){
            for(int j = s; j >= 0; j--){
                if(i == n && j == s){
                    continue;
                }
                double a4 = 1.0 * n * s / (double)(n * s - i * j);
                double a1 = 1.0 * (n - i) * (s - j)  / (double) (n * s - i * j);
                double a2 = 1.0 * (n - i) * j  / (double)(n * s - i * j);
                double a3 = 1.0 *  i * (s - j) / (double) (n * s - i * j);
                dp[i][j] = a4 + dp[i + 1][j + 1] * a1 + dp[i + 1][j] * a2 + dp[i][j + 1] * a3;
            }
        }
        printf("%.4f\n", dp[0][0]);
    }
    return 0;
}

P.Wall(计算几何)

题意：

给定$n$个顶点，建一个围墙围住所有点，并且与所有点的距离至少为$L$，求墙最小的长度。

分析：

首先求个凸包，将凸包的边平移$L$个长度即组成墙的一部分，为了最小化墙的长度，我们用半径为$L$的圆弧将凸包平移后的边平滑的连接起来。
我们可以发现每个圆弧与其对应的凸包内角互补，凸边形内角和$180(n - 2)$，凸边形$n$个内角及对应的圆弧和$180n$，两者相减即为圆弧的角度和$360$度，即圆弧正好组成一个半径为$L$的大圆。
所以我们只要求个凸包周长+圆的周长即可。

代码：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*************************************************************************
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
#define pr(x) cout<<#x<<":"<<x
#define pl(x) cout<<#x<<":"<<x<<endl
#define sa(n) scanf("%d", &(n))
#define sal(n) scanf("%I64d", &(n))
const int maxn = 1e3 + 5;
const double Pi = acos(-1.0);
struct Point
{
    int x, y;
    Point(){}
    Point(int _x,int _y){
        x = _x; y = _y;
    }
    Point operator -(const Point &b)const{
        return Point(x - b.x, y - b.y);
    }
    int operator *(const Point &b)const{
        return x * b.x + y * b.y;
    }
    int operator ^(const Point &b)const{
        return x * b.y - y * b.x;
    }
};
Point node[maxn], Stack[maxn];
inline double dist(Point p1, Point p2)
{
    return sqrt((p2 - p1) * (p2 - p1));
}
int dot(Point p0, Point p1, Point p2)
{
    return (p1 - p0) ^ (p2 - p0);
}
int top;
bool cmp(Point a, Point b)
{
    if(a.x == b.x) return a.y < b.y;
    else return a.x < b.x;
}
void convexHull(int n)
{
    sort(node, node + n, cmp);
    top = -1;
    for(int i = 0; i < n; i++){
        while(top > 0 && dot(Stack[top - 1], Stack[top], node[i]) <= 0) top--;
            Stack[++top] = node[i];
    }
    int ttop = top;
    for(int i = n - 2; i >= 0; i--){
        while(top > ttop && dot(Stack[top - 1], Stack[top], node[i])  <= 0) top--;
            Stack[++top] = node[i];
    }
}
int main (void)
{
    int N, L;sa(N);sa(L);
    for(int i = 0; i < N; i++){
        sa(node[i].x);sa(node[i].y);
    }
    convexHull(N);
    double ans = 0;
    for(int i = 0; i < top; i++){
        ans += dist(Stack[i], Stack[i + 1]);
    }
    ans += 2 * Pi * L;
    printf("%.f\n", ans);
    return 0;
}

Q.Brackets(区间DP)

题意：

给定序列，由’(‘’)’’[‘’’]’’四个字符组成的字符串，求子序列最大匹配个数。

分析：

设$dp[i][j]$表示区间$[i,j]$之间的最大匹配数。
如果$s[i]$与$s[j]$匹配，那么dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
枚举区间长度，更新对应长度的区间的$dp[i][j]$，再将区间合并更新子结构即可。

代码：

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
/*************************************************************************
	> File Name: Q.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#include<stack>
using namespace std;
#define pr(x) cout<<#x<<":"<<x
#define pl(x) cout<<#x<<":"<<x<<endl
#define sa(n) scanf("%d", &(n))
#define sal(n) scanf("%lld", &(n))
typedef long long ll;
typedef pair<int, int>p;
const int maxn = 1e2 + 5;
int dp[maxn][maxn];
int main (void)
{
    string s;
    while(cin>>s){
        if(s == "end") break;
        memset(dp, 0, sizeof(dp));
        for(int len = 2; len <= s.length(); len++){
            for(int j = 0, k = len - 1; j < k - len + 2 && k < s.length(); j++, k++){
                if((s[j] == '('&& s[k] == ')') || (s[j] == '[' && s[k] == ']'))
                        dp[j][k] = max(dp[j][k], dp[j + 1][k - 1] + 2);
                for(int i = j; i < k; i++)
                    dp[j][k] = max(dp[j][k], dp[j][i] + dp[i + 1][k]);
            }
        }
        cout<<dp[0][s.length() - 1]<<endl;
    }
    return 0;
}

R.Bad Luck Island(概率DP)

题意：

给定剪刀、石头、布分别的人数，两种物种相遇，输的一方少一个人，问最后只剩下仅一种生物的概率。

分析：

概率$dp$，$maxn$最大只有100，容易想到状态$dp[i][j][k] := 第一种剩i人，第二种剩j人，第三张剩k人的概率$，然后乘上相遇的概率，转移一下就好。
！！！最初计算相遇概率的时候除以的是从剩下所有人中选择两个人的方案数，其实不对，因为只有不同物种相遇才能使当前状态发生改变，所以需要进行归一化处理，即直接除以$ij + jk + k * i$。

代码：

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 1e2 + 5, oo = 0x3f3f3f3f;
double dp[maxn][maxn][maxn];
int main (void)
{
     int r, s, p;cin>>r>>s>>p;
     dp[r][s][p] = 1;
     for(int i = r; i >= 0; i--){
        for(int j = s; j >= 0; j--){
            for(int k = p; k >= 0; k--){
                if(i == 0 && j == 0 || i == 0 && k == 0|| j == 0 && k == 0) continue;
                if(j >= 1) dp[i][j - 1][k] += dp[i][j][k] * i * j / (double)(i * j + j * k +  i * k)  ;
                if(i >= 1) dp[i - 1][j][k] += dp[i][j][k] * i * k / (double)(i * j + j * k +  i * k) ;
                if(k >= 1) dp[i][j][k - 1] += dp[i][j][k] * j * k/ (double)(i * j + j * k +  i * k)  ;
            }
        }
     }
     double ans = 0;
     for(int i = 1; i <= r; i++){
        ans += dp[i][0][0];
     }
     printf("%.12f ", ans);
     ans = 0;
     for(int i = 1; i <= s; i++){
        ans += dp[0][i][0];
     }
     printf("%.12f ", ans);
     ans = 0;
     for(int i = 1; i <= p; i++){
        ans += dp[0][0][i];
     }
     printf("%.12f\n", ans);
     return 0;
}

S.Not Equal on a Segment（线段树 Or DP）

题意：

给定序列，若干查询，每个查询给定区间和$t$，输出区间内任意一个不等于$t$的元素的位置。

分析：

最初没看样例直接钦定输出每个不等于$t$的元素位置，结果怎么想都是$n^2$复杂度的，后来看了样例才发现是输出任意一个。。
对于一个区间，如果区间最大值和最小值相等，那么该区间元素值全部相同，那么我们维护区间的最大最小值，然后判断是否均等于$t$，若不等，输出最大值或最小值的位置即可，若相等， 则该区间所有元素值均等于$t$。
区间最大最小值用线段树维护，最初使用map来保存最大最小值所在的位置，结果TLE，改成数组就过了，就是内存难看了一点。。
感觉自己姿势怪怪的上网搜了一发标程：设$dp[i]$表示不等于$a[i]$的最大的元素下标，这样每次看$t$是否等于区间最右端的值，若是，则判断$dp[t]$是否在区间内，若不是，则最右端的值即为答案。非常巧妙。

代码：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define sa(n) scanf("%d", &(n))
const int maxn = 6e5 + 5, maxm = 1e6 + 5, oo = 0x3f3f3f3f;
struct Node{int l;int r;int a; int b;int pa;int pb;}Tree[maxn];
int a[maxn];
int ans[maxm];
void build(int i, int l, int r)
{
    Tree[i].l = l;
    Tree[i].r = r;
    Tree[i].a = 0;
    Tree[i].b = oo;
    if(l == r) {
            Tree[i].pa =  Tree[i].pb = l;
            return;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build((i << 1) | 1, mid + 1, r);
}
void push_up(int i)
{
    if(Tree[i<<1].a > Tree[(i << 1)| 1].a){
        Tree[i].a = Tree[i<<1].a ;
        Tree[i].pa = Tree[i << 1].pa;
    }else{
        Tree[i].a = Tree[(i<<1) | 1].a ;
        Tree[i].pa = Tree[(i << 1) | 1].pa;
    }
    if(Tree[i<<1].b < Tree[(i << 1)| 1].b){
        Tree[i].b = Tree[i<<1].b ;
        Tree[i].pb = Tree[i << 1].pb;
    }else{
        Tree[i].b = Tree[(i<<1) | 1].b ;
        Tree[i].pb = Tree[(i << 1) | 1].pb;
    }
}
int querymax(int i, int l, int r)
{
    if(Tree[i].l == l && Tree[i].r == r){
        ans[Tree[i].a]  = Tree[i].pa;
        return Tree[i].a;
    }
    int mid = Tree[i].l + Tree[i].r >> 1;
    if(r <= mid) return querymax(i<<1, l, r);
    else if(l > mid) return querymax((i << 1)|1, l, r);
    else return max(querymax(i << 1, l, mid), querymax((i << 1)|1, mid + 1, r));
}
int querymin(int i, int l, int r)
{
    if(Tree[i].l == l && Tree[i].r == r){
        ans[Tree[i].b] = Tree[i].pb;
        return Tree[i].b;
    }
    int mid = Tree[i].l + Tree[i].r >> 1;
    if(r <= mid) return querymin(i<<1, l, r);
    else if(l > mid) return querymin((i << 1)|1, l, r);
    else return min(querymin(i << 1, l, mid), querymin((i << 1)|1, mid + 1, r));
}
void update(int i, int k, int x)
{
    if(Tree[i].l == k && Tree[i].r == k){
        Tree[i].a =  Tree[i].b = x;
        return;
    }
    int mid = Tree[i].l + Tree[i].r >> 1;
    if(k <= mid) update(i << 1, k, x);
    else update((i << 1) | 1, k, x);
    push_up(i);
}
int main (void)
{
    int n, m;sa(n);sa(m);
    build(1, 0, n - 1);
    for(int i = 0; i < n; i++){
        sa(a[i]);
        update(1, i, a[i]);
    }
    int l, r, x;
    int a, b;
    for(int i = 0; i < m; i++){
        sa(l);sa(r);sa(x);
        a = querymax(1, l - 1, r - 1);
        b = querymin(1, l - 1, r - 1);
        if(a == b && a == x) puts("-1");
        else if(a == x) printf("%d\n", ans[b] + 1);
        else printf("%d\n", ans[a] + 1);
    }
    return 0;
}

$DP$方法

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define sa(n) scanf("%d", &(n))
const int maxn = 6e5 + 5, maxm = 1e6 + 5, oo = 0x3f3f3f3f;
int dp[maxn];
int a[maxn];
int main (void)
{
    int n, m;sa(n);sa(m);
    memset(dp, -1, sizeof(dp));
    for(int  i = 1; i <= n; i++){
        sa(a[i]);
        if(a[i] == a[i - 1]) dp[i] = dp[i - 1];
        else dp[i] = i - 1;
    }
    int l, r, t;
    for(int i = 0; i < m; i++){
        sa(l);sa(r);sa(t);
        if(a[r] == t){
            if(dp[r] < l) cout<<-1<<endl;
            else cout<<dp[r]<<endl;
        }else cout<<r<<endl;
    }
    return 0;
}

T.Monkey and Banana(DAG)

题意：

一堆石头，给定长宽高，每种石头均可以使用无数次，问这堆石头可以叠放的最高高度，要求下面的石头的长和宽分别严格大于上面石头的长和宽。

分析：

采用DAG最长路算法，由于长宽较大，不能直接用于表示状态，因此采用$dp[i][x]$表示以第$i$块石头为最高点，以其第$x$个边为高所能达到的最大高度，x代表长/宽/高，然后根据长宽高要求构造DAG，最后记忆化搜索求出最长路。

代码：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*************************************************************************
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
#define pr(x) cout<<#x<<":"<<x
#define pl(x) cout<<#x<<":"<<x<<endl
#define sa(n) scanf("%d", &(n))
#define sal(n) scanf("%I64d", &(n))
typedef long long ll;
const int maxn = 30 + 5, oo = 0x3f3f3f3f;
int dp[maxn][maxn];
int p[maxn][3];
int u1, u2, l1, l2;
int n;
bool G[maxn][3][maxn][3];
bool check(int i, int k, int j, int q)// i 是否可以放在 j 上
{
   if(k == 1) u1 = 2, u2 = 0;
   if(k == 0) u1 = 2, u2 = 1;
   if(k == 2) u1 = 1, u2 = 0;
   if(q == 1) l1 = 2, l2 = 0;
   if(q == 2) l1 = 1, l2 = 0;
   if(q == 0) l1 = 1, l2 = 2;
    int a1 = max(p[i][u1], p[i][u2]);
    int a2 = min(p[i][u1], p[i][u2]);
    int b1 = max(p[j][l1], p[j][l2]);
    int b2 = min(p[j][l1], p[j][l2]);
    return a1 < b1 && a2 < b2;
}
int get(int i, int k)
{
    if(dp[i][k]) return dp[i][k];
    int &ans = dp[i][k];
    for(int a = 1; a <= n; a++){
        for(int b = 0; b < 3; b++){
            if(G[i][k][a][b])
                ans = max(ans, get(a, b));
        }
    }
    ans += p[i][k];
    return ans;
}
int main (void)
{
    int kas = 1;
    while(~scanf("%d", &n) && n){
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++){
            sa(p[i][0]);sa(p[i][1]);sa(p[i][2]);
        }
        memset(G, false, sizeof(G));
        for(int i = 1; i <= n; i++){
            for(int k = 0; k < 3; k ++){
                for(int j = 1; j <= n; j++){
                    for(int q = 0; q < 3; q++){
                        if(check(i, k, j, q)){
                            G[i][k][j][q] = true;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 3; j++){
                ans = max(ans, get(i, j));
            }
        }
        cout<<"Case "<<kas++<<": maximum height = "<<ans<<endl;
    }
    return 0;
}
文章目录
  1. 1. A.How far away ？(Tarjan LCA)
    1. 1.1. 题意：
    2. 1.2. 分析：
    3. 1.3. 代码：
  2. 2. B - Network(LCA + 并查集)
    1. 2.1. 题意：
    2. 2.2. 分析：
    3. 2.3. 代码：
  3. 3. E.Crossing River(数学)
    1. 3.1. 题意：
    2. 3.2. 分析：
    3. 3.3. 代码：
  4. 4. G.Piotr’s Ants(找规律)
    1. 4.1. 题意：
    2. 4.2. 分析：
    3. 4.3. 代码：
  5. 5. H- Intellectual Inquiry【dp，构造】
    1. 5.1. 题意：
    2. 5.2. 分析：
    3. 5.3. 代码：
  6. 6. I.The Water Bowls(反转开关问题)
    1. 6.1. 题意：
    2. 6.2. 分析：
    3. 6.3. 代码：
  7. 7. J.Fliptile(反转开关问题)
    1. 7.1. 题意：
    2. 7.2. 分析：
    3. 7.3. 代码：
  8. 8. K.Jessica’s Reading Problem(双指针)
    1. 8.1. 题意：
    2. 8.2. 分析：
    3. 8.3. 代码：
  9. 9. L.Bound Found(双指针，巧妙)
    1. 9.1. 题意：
    2. 9.2. 分析：
    3. 9.3. 代码：
  10. 10. M.The Values You Can Make(DP)
    1. 10.1. 题意：
    2. 10.2. 分析：
    3. 10.3. 代码：
  11. 11. N - Dividing Kingdom II(带权并查集，二分图)
    1. 11.1. 题意：
    2. 11.2. 分析：
    3. 11.3. 代码：
  12. 12. O. Collecting Bugs(概率DP)
    1. 12.1. 题意：
    2. 12.2. 分析：
    3. 12.3. 代码：
  13. 13. P.Wall(计算几何)
    1. 13.1. 题意：
    2. 13.2. 分析：
    3. 13.3. 代码：
  14. 14. Q.Brackets(区间DP)
    1. 14.1. 题意：
    2. 14.2. 分析：
    3. 14.3. 代码：
  15. 15. R.Bad Luck Island(概率DP)
    1. 15.1. 题意：
    2. 15.2. 分析：
    3. 15.3. 代码：
  16. 16. S.Not Equal on a Segment（线段树 Or DP）
    1. 16.1. 题意：
    2. 16.2. 分析：
    3. 16.3. 代码：
  17. 17. T.Monkey and Banana(DAG)
    1. 17.1. 题意：
    2. 17.2. 分析：
    3. 17.3. 代码：