SCUACM 2016集训 7.15【14/19】

ACM_集训

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

B - Infinite Go(并查集，模拟)

题意：

两个人下围棋，问最后黑白棋子各剩多少。

分析：

模拟，第一反应连通块可以用并查集搞，然后就顺着题意一直在纠结怎么判断联通块内部的空白区域的大小，其实转换个角度，我们可以看一个连通块周围是否有空白区域，如果一个连通块四周被相反颜色的包围，没有剩余空白区域，那么整个连通块都要被移走。这样我们只要维护连通块周围的空白部分即可。删除的时候dfs遇到颜色相同的就删除，否则该块所在连通块的空白区域加一。
然后就狂T不止，因为$map$常数太大，每次找颜色都访问一次$map$的话，太耗时，直接作为参数传进$Delete()$中

代码：

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
#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
#define sa(n) scanf("%d", &n)
typedef pair<int, int>p;
const int maxn = 1e4 + 5;
int pa[maxn], sz[maxn];
int ans[2];
map<p, int>id;
map<p, int>::iterator mi;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1,1, 0};
int _find(int a)
{
    if(pa[a] == a) return a;
    return pa[a] = _find(pa[a]);
}
void Delete(p a, int c)
{
    id.erase(a);
    int x = a.first, y = a.second;
    for(int j = 0; j < 4; j++){
        int xx = x + dx[j], yy = y + dy[j];
        if(xx < 1 || yy < 1) continue;
        p t = p(xx, yy);
        if(id.find(t) == id.end()) continue;
        if((id[t] & 1) == c) Delete(t, c);
        else sz[_find(id[t])]++;
    }
}
int tmp;
p a, t;
int main (void)
{
    int T;sa(T);
    while(T--){
        int n;sa(n);
        int x, y;
        id.clear();
        for(int i = 1; i <= n; i++){
                pa[i] = i;sz[i] = 0;
        }
        for(int i = 1; i <= n; i++){
            sa(x);sa(y);
            a = p(x, y);
            id[a] = i;
            for(int j = 0; j < 4; j++){
                int xx = x + dx[j], yy = y + dy[j];
                if(xx < 1|| yy < 1) continue;
                t = p(xx, yy);
                if(id.find(t) == id.end()) sz[i]++;
                else if((id[t] & 1) == (i & 1)){
                    tmp = _find(id[t]);
                    sz[tmp]--;
                    pa[tmp] = i;
                    sz[i] += sz[tmp];
                }
            }
             for(int j = 0; j < 4; j++){
                int xx = x + dx[j], yy = y + dy[j];
                if(xx < 1|| yy < 1) continue;
                t = p(xx, yy);
                if(id.find(t) == id.end()) continue;
                tmp = _find(id[t]);
                if((id[t] & 1) != (i & 1)){//different
                    sz[tmp]--;
                    if(!sz[tmp]) Delete(t, id[t] & 1);
                }
            }
            if(!sz[i]) Delete(a, i & 1);
        }
        ans[0] = ans[1] = 0;
        for(mi = id.begin(); mi != id.end(); mi++){
            if(mi->second != 0){
                ans[mi->second & 1]++;
            }
        }
        printf("%d %d\n", ans[1], ans[0]);
    }
    return 0;
}

C - Ants(01Trie树)

题意：

$n$个点组成一棵树，给定树边长度，定义任意两个不同点之间的距离为两点之间边的异或值(考虑顺序)，$m$个询问，求所有距离中第$k$大距离为多少。

分析：

首先利用异或的性质，我们可以随便找一点作为根节点，然后$dfs$求出每个点到该点之间边的异或值，那么求两点之间的距离就将两点的$dist$数组异或一下即可~
这样我们就可以将$dist$数组插入$01Trie$树中，那么对于单独的一个点，问题就可以转化为经典的求异或值第$k$大的问题了。
但是如何处理所有点的第$k$大呢？这里就开始想不清楚了。。。。
======= 我是智障的分界线 =====
我们将询问离线处理。。
直接得到第$k$大不好算，可以从第1大开始，依次计算。
首先将所有点的第$1$大进行比较，选出最大，然后将选出的最大值删除，并将其对应的点的第$2$大值，加进去再与那些第$1$大们进行比较选出第$2$大值。。。依次类推。。这样是可以保证我们每次取到的点时全局最大，第$2$大。。等等。。。而比较的过程我们可以使用优先级队列，每次取队首元素即可。。。。

代码：

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
122
123
124
125
126
127
128
129
130
131
132
133
/*************************************************************************
    > File Name: 4776.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/8 14:41:18
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, int>pl;
const int maxn = 1e5 + 5, maxm = 6200005;
struct Trie {
    int a[2];
    int sz;
} f[maxm];
int cnt,  tot;
int head[maxn], _rank[maxn];
ll ans[maxn << 1];
void init(int n)
{
    cnt = 1;
    tot = 0;
    memset(ans, -1, sizeof(ans));
    memset(f, 0, sizeof(Trie) * maxm);
    for(int i = 1; i <= n; i++){
        _rank[i] = 1;
        head[i] = -1;
    }
}
void insert(ll x, int u, int num) 
{
	int k;
    for (int i = num; i >= 0; i--) {
        f[u].sz++;
        k = (x >> i) & 1;
        if (!f[u].a[k])  f[u].a[k] = ++cnt;
        u = f[u].a[k];
    }
    f[u].sz++;
}
ll query(ll x, int u, int num, int K) 
{
	int k;
    ll ans = 0;
    for (int i = num; i >= 0; i--) {
        k = (x >> i) & 1;
        ans <<= 1;
        if (f[u].a[k^1] && f[f[u].a[k^1]].sz >= K){
            u = f[u].a[k^1];
            ans |= k^1;
        }else{
            if(f[u].a[k^1]) K -= f[f[u].a[k^1]].sz;  
            u = f[u].a[k];
            ans |= k;
        }
    }
    ans ^= x;
    return ans;
}
struct EDGE{
    int to, next;
    ll val;
}edge[maxn << 1];
void addedge(int u, int v, ll val)
{
    edge[tot].to = v;
    edge[tot].val = val;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int q[maxn];
ll dist[maxn];
void dfs(int u, int fa)
{
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(v == fa) continue;
        dist[v] = dist[u] ^ edge[i].val;
        dfs(v, u);
    }
}
int main(void)
{
    int n;
    while(~scanf("%d", &n) && n){
        int root;
		priority_queue<pl>que;
        init(n);
        int x, y;
        ll z;
        for(int i = 0; i < n - 1; ++i){
            scanf("%d%d%I64d", &x, &y, &z);
            addedge(x, y, z); addedge(y, x, z);
        }
        dist[1] = 0;
        dfs(1, 1);
        for(int i = 1; i <= n; ++i){
            insert(dist[i], 1, 60);
        }
        for(int i = 1; i <= n; ++i){
            que.push(pl(query(dist[i], 1, 60, 1), i));
        }
        int maxq = 0;
        int m;scanf("%d", &m);
        for(int i = 0; i < m; ++i){
            scanf("%d", &q[i]);
            maxq = max(maxq, q[i]);
        }
        maxq = min((ll)maxq, n * 1ll * (n - 1));
        for(int i = 1; i <= maxq; ++i){
            if(que.empty()) break;
            pl t = que.top(); que.pop();
            ans[i] = t.first;
            if(_rank[t.second] >= n) continue;
            _rank[t.second]++;
            que.push(pl(query(dist[t.second], 1, 60, _rank[t.second]), t.second));
        }
        for(int i = 0; i < m; ++i){
            printf("%I64d\n", ans[q[i]]);
        }
    }
    return 0;
}

G - Matrix Decompressing(网络流)

题意：

给定各行各列的和，求出一个满足条件的矩阵。

分析：

最初没想到，听陈鹏说是网络流突然觉得好有道理，这样想来好像也是很裸的样子。各行各列相连，从超级源点到每行连线，流量为各行的和，从各列向超级汇点连线，流量为各列的和。这样跑一下网络流再往回找一各边的流量即为答案。注意此题有流量至少为1的下界， 所以初始就为每条边安排1的流量，那么行列之间边的容量为19，从源点流入和汇点流出的值要进行相应的减少。跑完网络流最后输出答案再加上一即可。

代码：

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
122
123
124
125
126
127
128
129
/*************************************************************************
    > File Name: G.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/16 23:01:48
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
struct edge{int to, cap, rev, flow;};
const int maxn = 100 + 5, maxm = maxn * maxn + 5, INF = 0x3f3f3f3f;
int d[maxm], iter[maxm];
int s, t;
vector<edge>G[maxm * 2];
void init()
{
	for(int i = 0; i < maxn; i++) G[i].clear();
}
void addedge(int from, int to, int cap)
{
    G[from].push_back((edge){to, cap, G[to].size(), 0});
    G[to].push_back((edge){from, 0, G[from].size()-1, 0});
}
void bfs()
{
    memset(d, -1, sizeof(d));
    queue<int>q;
    d[s] = 0;
    q.push(s);
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = 0; i < G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > e.flow && d[e.to] == -1){
                d[e.to] = d[v] + 1;
                q.push(e.to);
            }
        }
    }
}
int dfs(int v, int f)
{
    if(v == t) return f;
    for(int &i = iter[v]; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(e.cap > e.flow && d[v] == d[e.to] - 1){
            int tf = dfs(e.to, min(f, e.cap - e.flow));
            if(tf > 0){
				e.flow += tf;
                G[e.to][e.rev].flow -= tf;
                return tf;
            }
        }
    }
    return 0;
}
int max_flow()
{
    int flow = 0;
    for(;;){
        bfs();
        if(d[t]<0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while((f = dfs(s, INF))>0){
            flow += f;
        }
    }
}
int a[maxn], b[maxn];
int res[maxn][maxn];
int main (void)
{
	int T;scanf("%d", &T);
	for(int kas = 1; kas <= T; kas++){
		int n, m;
		init();
		scanf("%d%d", &n, &m);
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		int tmp1, tmp2 = 0;
		for(int i = 1; i <= n; i++){
			scanf("%d", &tmp1);
			a[i] = tmp1 - tmp2;
			tmp2 = tmp1;
		}
		tmp2 = 0;
		for(int i = 1; i <= m; i++){
			scanf("%d", &tmp1);
			b[i] = tmp1 - tmp2;
			tmp2 = tmp1;
		}
		s = 0, t = n + m + 1;
		for(int i = 1; i <= n; i++){
			addedge(s, i, a[i] - m);
		}
		for(int i = 1; i <= m; i++){
			addedge(i + n, t, b[i] - n);
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				addedge(i, j + n, 19);
			}
		}
		int ans = max_flow();
		memset(res, 0, sizeof(res));
		for(int i = 1; i <= n; i++){
			for(int j = 0; j < G[i].size(); j++){
				res[i][G[i][j].to - n] = G[i][j].flow;
			}
		}		
		printf("Matrix %d\n", kas);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				printf("%d%c", res[i][j] + 1, j == m?'\n':' ');
			}
		}
	    puts("");
	}
	return 0;
}

I. BerDonalds(图绝对中心)

题意：

求图的绝对中心，即在边上或者顶点中选一个点$X$，使得该点到图中顶点的最远距离$f(X)$最小。

分析：

参考非常透彻的讲解 见C题

=== 我是搬运工===

首先$floyd$求出任意两点之间的最短路。
其次，根据题意，对于某一点$X，设其在线段$u-v$上，与点$u$的距离为$x$，对于任意点$w$，我们有f(X)=max{min{d[u][w]+x, d[v][w]+L_{u,v}-x}}$。
下面来分析$f(X)$的性质，对于固定的线段$u-v$，我们可以画出$f(X)关于x$的函数图像，为方便比较，把$w$们放在一个坐标系中，由于我们要求的是到其他点的最大值，所以对于某个$x$，只要保留该$x$对应的最大的$f(x)$值即可，也就是函数图像中最上面的点，如资料中实线所示。
$f(X)$的最小值就是实线中的最低点，观察图可知，这个最小值必然在交叉点上，即$L_1，L_2，L_3…$。
根据函数图像，存在交叉点的前提是$d[u][w_j] > d[u][w_k] 并且 d[v][w_j] < d[v][w_k]$，且有$d[u][w_j] + L_{u,v} - x = d[v][w_k] + x$，而此时的$f(X)= \frac{d[u][w_j] + L_{u,v} - x + d[v][w_k]+ x}{2} = \frac{d[u][w_j] + L_{u,v} + d[v][w_k]}{2}$
这样我们枚举每一条边，然后对于$d[u][w]$从大到小排个序，扫一遍，按照上述式子答案就出来了。

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int, int>p;
const int maxn = 2e2 + 5, oo = 0x3f3f3f3f ;
int dist[maxn][maxn];
struct EDGE{
	int from, to, val;
}edge[maxn * maxn];
p node[maxn];
int tot;
int main (void)
{
	int n, m;scanf("%d%d", &n, &m);
	int a, b, w; 
	tot = 0;
	memset(dist, 0x3f, sizeof(dist));
	for(int i = 0; i < m; i++){
		scanf("%d%d%d", &a, &b, &w);
		a--;b--;
		dist[a][b] = dist[b][a] = w;
		edge[tot++] = (EDGE){a, b, w};
	}
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i == j)	dist[i][j] = 0;
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	int ans = oo;
	int tmp;
	for(int i = 0; i < tot; i++){
		int u = edge[i].from, v = edge[i].to;
		for(int j = 0; j < n; j++){
			node[j] = p(dist[j][u], dist[j][v]);
		}
		tmp = n - 1;
		sort(node, node + n);
		ans = min(ans, node[n - 1].first * 2);
		for(int j = n - 2; j >= 0; j--){
			if(node[j].second > node[tmp].second){
				ans = min(ans, node[tmp].second + node[j].first + edge[i].val);
				tmp = j;
			}
		}	
		ans = min(ans, node[tmp].second * 2);	
	}
	printf("%.10f\n", (double)ans / 2.0);
	return 0;
}

J - Runaway to a Shadow【计算几何】

题意：

给定小强初始位置，以及若干圆的圆心和半径。已知小强以均等概率选择前进方向，给定速度和时间，做匀速直线运动。问小强在给定时间内走进圆的概率。

分析：

建立坐标系，以小强初始位置为原点，只要求出以原点为圆心，半径为$T\times V$的圆$O$与其他每个圆相交的部分构成的弧度，再取个并集，那么概率即为$并集大小/2\pi$。
如何求弧度并集？利用余弦定理求出相交部分的弧度，注意弧度存在范围，当原点与交点的连线$L$与圆相切的时候，弧度到达最大，那么在计算的时候只要将$L$跟切线长取个最小值即可~
【沙茶如我以为这样就结束了。
注意！角弧度范围为$[0,2\pi]$，不要忘记对于$a-b \lt 0 和 a+b \gt 2\pi$的情况进行一下处理！orz

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<double, double> pd;
const int maxn = 1e5 + 5;
double pi = acos(-1.0), eps = 1e-8;
struct POINT{
	double x, y, r;
	double dist(){
		return x * x + y * y;
	}
	double angel(){
		double a = atan2(y, x);
		if(a < -eps) a += 2 * pi;
		return a;
	}
}p[maxn];
int main (void)
{
	double x0, y0, V, T;
	int n;
	scanf("%lf%lf%lf%lf%d", &x0, &y0, &V, &T, &n);
	double x, y, r;
	double mx = T * V;
	for(int i = 0; i < n; i++){
		scanf("%lf%lf%lf", &x, &y, &r);
		x -= x0; y -=y0;
		p[i] = (POINT){x, y, r};
	}
	vector<pd>v;
	for(int i = 0; i < n; i++){
		if(p[i].dist() - p[i].r * p[i].r < eps) return printf("1.000000000\n"), 0;
		if(sqrt(p[i].dist()) - eps > p[i].r + mx) continue;
		double d1 = min(sqrt(p[i].dist() - p[i].r * p[i].r), mx);
		double b = acos((p[i].dist() + d1 * d1 - p[i].r * p[i].r) / (2.0 * sqrt(p[i].dist()) * d1));
		double a = p[i].angel();
		if(a + b - eps > 2 * pi){
			v.push_back(pd(a - b, 2 * pi));
			v.push_back(pd(0, a + b - 2 * pi));
		}else if(a - b < -eps){
			v.push_back(pd(0, a + b));
			v.push_back(pd(a - b + 2 * pi, 2 * pi));
		}else{
			v.push_back(pd(a - b, a + b));
		}
	}
	if(!v.size()) return printf("0.000000000\n"), 0;
	sort(v.begin(), v.end());
	double ans = 0.0;
	double l = v[0].first;
	r = v[0].second;
	int sz = v.size();
	for(int i = 1; i < sz; i++){
		if(v[i].first + eps > r){
			ans += r - l;
			l = v[i].first;
		}
		if(v[i].second + eps > r){
			r = v[i].second;
		}
	}
	ans += r - l;
	printf("%.10f\n", ans / (2.0 * pi));
	return 0;
}

K - Puzzles (树形dp)

题意：

一棵树上，随机遍历子节点，求每个节点$dfs$序中第一次标号的值的期望。

分析：

首先可以明确，对于任意子节点$b$，设父节点为$a$，那么其期望为$a + 1 + p * (sz[a] - sz[b] - 1)$，下面只要求出所有兄弟节点排列在他前面的概率。我们写出所有兄弟节点的所有排列，发现其兄弟节点排列在$b$前面的概率加和起来正好为$0.5$，即每个结点都有$0.5$的概率排列在$b$前面，即$p=0.5$，那么两次dfs就可以解决问题了！

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int sz[maxn];
double dp[maxn];
vector<int>G[maxn];
int ans[maxn];
void dfs(int u)
{
	sz[u] = 1;
	for(int i = 0; i < G[u].size(); i++){
		dfs(G[u][i]);
		sz[u] += sz[G[u][i]];
	}
}
void dfs2(int u, int pa)
{
	if(u != pa) dp[u] = dp[pa] + 1 + (sz[pa] - sz[u] - 1) * 0.5;
	for(int i = 0; i < G[u].size(); i++){
		dfs2(G[u][i], u);
	}
}
int main (void)
{
	int n;scanf("%d", &n);
	int a;
	for(int i = 2; i <= n; i++){
		scanf("%d", &a);
		G[a].push_back(i);
	}
	dfs(1);
	dp[1] = 1;
	dfs2(1, 1);
	for(int i = 1; i <= n; i++){
		printf("%.8f ", dp[i]);
	}
	return 0;
}

L - PLEASE(概率dp，数学)

题意：

有三个杯子，最初在中间的杯子中放一张纸，然后进行$n$轮交换，每次交换等概率的将纸条放到其他任意两个杯子中，问$n$轮后纸条在中间杯子的概率，将概率用两个互质$p/q$的分数形式表示，其中$p,q为模1e9+7$的余数。

分析：

设$dp[i]:=第i轮纸条在中间杯子的概率$，那么我们有$dp[i] = (1 - dp[i - 1]) \times 0.5$，可是$n$特别大，首先第一反应矩阵快速幂，可是无法保证最后得到正确的$p,q$，然后我们观察这个式子，发现很像高中数学题= =。
我们试图构造等比序列，设$f[i] = dp[i] + x$，那么$f[i] = 0.5 \times f[i - 1]$，解得$f[i] = dp[i] - {1 \over 3}$，那么我们就利用等比数列的通项公式，其中初始项$dp[1] = 0, f[1] = -\frac{1}{3}$解得$dp[n] = -\frac{1}{3}*-\frac{1}{2}^{n-1}+\frac{1}{3}$，分$n$为奇数偶数讨论一下，得到$$dp[n] = { { { 2^{n-1}-1} \over 3} \over {2^{n-1 } } }, n为奇数$$
$$dp[n] = { { { 2^{n-1}+1} \over 3} \over {2^{n-1} } }, n为偶数$$
我们发现分母均为偶数，分子均为奇数，这样正好保证互质的条件！然后就出来啦~~

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, mod = 1e9 + 7;
ll a[maxn];
int quick_pow(int a, int b, int mod)
{
	int ans = 1;
	for(; b; b >>= 1, a = a * 1ll * a % mod){
		if(b & 1) ans = ans * 1ll * a % mod;
	}
	return ans;
}
int main (void)
{
	int n;scanf("%d", &n);
	bool flag1 = false, flag2 = false;
	int m = 1;
	for(int i = 0; i < n; i++){
		scanf("%I64d", &a[i]);
		if(a[i] != 1) flag1 = true;
		if(!(a[i] & 1)) flag2 = true;
		a[i] %= (mod - 1);
		m = m * 1ll * a[i] % (mod - 1);
	}
	m = (m - 1 + mod - 1) % (mod - 1);
	if(!flag1) return puts("0/1"),0;
	int up = quick_pow(2, m, mod);
	int down = up;
	if(flag2) up++;
	else up--;
	up = (up + mod) % mod;
	up = up * 1ll * quick_pow(3, mod - 2, mod) % mod;
	printf("%d/%d\n", up, down);
	return 0;
}

M.Legen…(AC自动机+floyd倍增)

题意：

给定若干字符串，及各个字符串的价值，求长度为$l$的字符串可以得到的最大价值。

分析：

首先建个AC自动机，然后在上面暴力，我们设$dp[i][j]$表示长度为$i$，以字符$j$结尾的字符串能得到的最大价值，由于$l$特别大， 我们将$l$拆成二进制数，即设状态$dp[i][j][k]$表示从节点$i$开始走$2^k$步到达结点$j$的最大价值，那么可以得到状态转移方程$dp[i][j][k] = max{dp[i][p][k-1]+dp[p][j][k-1]}$，这样我们直接矩阵快速幂一下即可！最后我们得到矩阵$A$，$A[0][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
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
122
123
124
125
126
127
128
129
130
131
/*************************************************************************
    > File Name: M.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/15 23:20:10
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
#define pr(x) cout << #x << ": " << x << "  "
#define pl(x) cout << #x << ": " << x << endl;
#define sa(x) scanf("%d",&(x))
#define sal(x) scanf("%I64d",&(x))
typedef long long ll;
const int maxn = 200 + 5, oo = 0x3f3f3f3f;
char s[maxn][maxn];
int a[maxn];
int n;
const int N = 205;
struct Matrix
{
    int row,cal;
    long long m[N][N];
};
Matrix init(Matrix a, long long t)
{
    for(int i = 0; i < a.row; i++)
        for(int j = 0; j < a.cal; j++)
            a.m[i][j] = t;
    return a;
}
Matrix operator * (const Matrix& a, const Matrix& b)
{
    Matrix ans;
    ans.row = a.row, ans.cal = b.cal;
    ans = init(ans,-oo);
    for(int i = 0; i < a.row; i++)
        for(int j = 0; j < b.cal; j++)
            for(int k = 0; k < a.cal; k++)
                ans.m[i][j] = max(ans.m[i][j], a.m[i][k] + b.m[k][j]);
    return ans;
}
Matrix quick_pow(long long k, Matrix A)
{
    Matrix I = A;
	for(; k; k >>= 1, A = A * A){
		if(k & 1) I = I * A;
	}
    return I;
}
int tot;
const int maxm = 4e4 + 5;
struct trie
{
    int fail, next[26 + 5];
	int val;
}ans[maxm];
int init(int x)
{
    for(int i = 0; i < 26; i++) ans[x].next[i] = 0;
    ans[x].fail = 0;
	ans[x].val = 0;
    return x;
}
void insert(char *s, int val)
{
    int now = 0;
    for(; *s; s++){
        int t = *s - 'a';
        if(ans[now].next[t] == 0) ans[now].next[t] = init(++tot);
        now = ans[now].next[t];
    }
    ans[now].val += val;
}
void ACbfs()
{
    queue<int>q;
    for(int i = 0; i < 26; i++){
        if(ans[0].next[i]) q.push(ans[0].next[i]);
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = 0; i < 26; i++){
            int &v = ans[u].next[i];
            if(v){
                q.push(v);
			    ans[v].val += ans[ans[ans[u].fail].next[i]].val;
				ans[v].fail = ans[ans[u].fail].next[i];
            }else{
                v = ans[ans[u].fail].next[i];
            }
        }
    }
}
int main (void)
{
	int n;sa(n);
	ll l;sal(l);
	tot = 0;
	init(0);
	for(int i = 0; i < n; i++){
		sa(a[i]);
	}
	for(int i = 0; i < n; i++){
		scanf("%s", s[i]);
		insert(s[i], a[i]);
	}
	ACbfs();
	Matrix A;
	A.row =  A.cal = tot + 1;
	A = init(A, -oo);
	for(int i = 0; i <= tot; i++){
		for(int j = 0; j < 26; j++){
			A.m[i][ans[i].next[j]] = ans[ans[i].next[j]].val;
		}
	}
	A = quick_pow(l - 1, A);
	ll anss = 0;
	for(int i = 0; i <= tot; i++){
		anss = max(anss, A.m[0][i]);
	}
	printf("%I64d\n", anss);
	return 0;
}

N - Fashion in Berland(水)

分析：

水题

代码：

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
/*************************************************************************
    > File Name: P.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/15 15:31:41
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define sa(n) scanf("%d", &(n))
using namespace std;
int main (void)
{
	int n;sa(n);
	int a;
	int cnt = 0;
	for(int i = 0; i < n; i++){
		sa(a);
		if(a == 0) cnt++;
	}
	if(cnt){
		if(n == 1) puts("NO");
		else if(cnt == 1) puts("YES");
		else puts("NO");
	}else{
		if(n == 1) puts("YES");
		else puts("NO");
	}
	return 0;
}

O - s-palindrome(模拟)

题意：

还是找镜面字符串

代码：

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
/*************************************************************************
    > File Name: O.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/15 12:06:02
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
map<int,int>m;
int main (void)
{
	m['q'] = 'p';m['p'] = 'q';m['A'] = 'A';m['d'] = 'b';m['H'] = 'H';m['I'] = 'I';m['M'] = 'M';
	m['O'] = 'O';m['o'] = 'o';m['T'] = 'T';m['U'] = 'U';m['V'] = 'V';m['v'] = 'v';m['W'] = 'W';
	m['w'] = 'w';m['x'] = 'x';m['X'] = 'X';m['Y'] = 'Y';m['b'] = 'd';
	string s;cin>>s;
	for(int i = 0, j = s.length() - 1; i <= j; i++, j--){
		if(m[s[i]] != s[j]) return cout<<"NIE"<<endl, 0;
	}
	cout<<"TAK"<<endl;
	return 0;
}

P - Exponential notation(模拟)

题意：

将数字表示为科学计数法

分析：

很无聊的码农题。。码力不足的哭了555

代码：

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
/*************************************************************************
    > File Name: N.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/15 15:47:18
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 5;
char str[maxn], t[maxn];
int main (void)
{
	scanf("%s", str);
	int len = strlen(str);
	int s = 0, t = len - 1;
	int pos = len - 1;
	bool flag = false;
	while(str[s] == '0'||str[s] == '.'){
		if(str[s] == '.'){
			pos = s;
			flag = true;
		}
		s++;
	}
	while(str[t] == '0'||str[t] == '.'){
		if(str[t] == '.'){
			pos = t - 1;
		}
		t--;
	}
	for(int i = s; i <= t; i++){
		if(str[i] == '.'){
			pos = i - 1;
			break;
		}
	}
	int npos = s;
	int add = pos - npos;
//	cout<<s<<' '<<t<<' '<<npos<<' '<<pos<<' '<<add<<endl;
	for(int i = s; i <= t; i++){
		if(i == pos + 1 && !flag) continue;
		printf("%c", str[i]);	
		if(i == npos && i != t) printf(".");
	}
	if(add) printf("E%d\n", add);
	else puts("");;
	return 0;
}

Q - Swaps in Permutation(并查集)

题意：

给定序列，给定几组交换的位置，该位置上的数可以进行交换无数次，问得到的字典序最大的序列。

分析：

看完样例我们发现会形成一个连通块，联通块内所有元素可以互相交换，那么我们用并查集处理连通块，将元素放进优先级队列，从大到小从头到尾放进去即可。

代码：

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
/*************************************************************************
    > File Name: Q.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/15 15:07:04
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
#define sa(n) scanf("%d", &(n))
const int maxn = 1e6 + 5;
int a[maxn];
int pa[maxn];
vector<int>v[maxn];
priority_queue<int>q[maxn];
int _find(int a)
{
	if(a == pa[a]) return a;
	return pa[a] = _find(pa[a]);
}
void unite(int a, int b)
{
	int ra = _find(a);
	int rb = _find(b);
	if(ra == rb) return;
	pa[ra] = rb;
}
int main (void)
{
	int n, m;sa(n);sa(m);
	for(int i = 1; i <= n; i++){
		sa(a[i]);
		pa[i] = i;
	}
	int u, v;
	for(int i = 0; i < m; i++){
		sa(u);sa(v);
		unite(u, v);
	}
	int ri;
	for(int i = 1; i <= n; i++){
		ri = _find(i);
		q[ri].push(a[i]);
	}
	for(int i = 1; i <= n; i++){
		ri = _find(i);
		printf("%d%c", q[ri].top(), i == n?'\n':' ');
		q[ri].pop();
	}
	return 0;
}

R - Xor-sequences(矩阵快速幂)

题意：

给定序列，从序列中选择$k(1 \le k \le 1e18)$个数（可以重复选择），使得得到的排列满足${x_i} 与{x_{i+1}}$异或的二进制表示中$1$的个数是$3$的倍数。问长度为$k$的满足条件的 序列有多少种？

分析：

首先每个元素自己构成一个长度为$1$的满足条件的序列。
其次我们可以预处理出满足条件的$v_i, v_j$，就可以得到一个横纵为$n$的$01$矩阵。这还是很显然的。此时我们得到了以$v_i$开头，$v_j$结尾的长度为$2$的序列个数。
接下来我们发现，两个矩阵相乘，矩阵$c$为新得到的矩阵，此时矩阵$a = b$,$c[i][j] = a[i][1] \times b[1][j] + a[i][2] \times b[2][j]+…+a[i][n]\times b[n][j]$，我们得到的即为以$a_i$开头，$a_J$结尾的长度为$3$的序列个数！
接下来用矩阵$c$更新矩阵$a$，再与最初的$01$矩阵，即$b$相乘，得到的又为开头元素为$a_i$，结尾元素为$a_j$的长度为$4$的序列个数！
依次乘$k-1$次即得到结果，这部分可以用矩阵快速幂进行优化。
最后把得到的矩阵中的每个元素的值加起来即为长度为$k$的满足条件的序列个数！
实质上就是$floyd$求长度为$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
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
/*************************************************************************
    > File Name: R.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/15 18:51:12
 ************************************************************************/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
#define pr(x) cout << #x << ": " << x << "  "
#define pl(x) cout << #x << ": " << x << endl;
#define sa(x) scanf("%d",&(x))
#define sal(x) scanf("%I64d",&(x))
typedef long long ll;
const int maxn = 105, mod = 1e9 + 7;
ll a[maxn];
int n;
const int N = 105;
struct Matrix
{
    int row,cal;
    long long m[N][N];
};
Matrix init(Matrix a, long long t)
{
    for(int i = 0; i < a.row; i++)
        for(int j = 0; j < a.cal; j++)
            a.m[i][j] = t;
    return a;
}
Matrix mul(Matrix a,Matrix b)
{
    Matrix ans;
    ans.row = a.row, ans.cal = b.cal;
    ans = init(ans,0);
    for(int i = 0; i < a.row; i++)
        for(int j = 0; j < b.cal; j++)
            for(int k = 0; k < a.cal; k++)
                ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j])%mod;
    return ans;
}
Matrix quick_pow(long long k, Matrix A)
{
    Matrix I;
    I.row = n, I.cal = n;
    I = init(I, 0);
	for(int i = 0; i < n; i++){
		I.m[i][i] = 1;
	}
    while(k){
        if(k & 1) I = mul(I, A);
        A = mul(A, A);
        k >>= 1;
    }
    return I;
}
int count(ll a)
{
	int ans = 0;
	while(a){
		if(a & 1) ans++;
		a >>= 1;
	}
	return ans;
}
int main(void)
{
	sa(n);
	ll k;sal(k);
	for(int i = 0; i < n; i++){
		sal(a[i]);
	}
	Matrix A;
	A.row = n, A.cal = n;
	A = init(A, 0);
	for(int i = 0 ; i < n; i++){
		for(int j = 0; j < n; j++){
			if(count(a[i] ^ a[j]) % 3 == 0){
				A.m[i][j] = 1;
			}
		}
	}
	ll ans = 0;
	A = quick_pow(k - 1, A); 
    for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			(ans += A.m[i][j]) %= mod;
		}
	}
	printf("%I64d\n", ans);
    return 0;
}

S - Couple Cover(神题，暴力)

题意：

给定序列，给定询问，求序列中两个数的乘积大于等于询问的数的对数。顺序不同的两个数算两对。

分析：

神题啊。类似筛法的思想，复杂度$O(nlogn)$，
$$1/1+ 1/2+1/3+…+1/(n-1)+1/n=0.577ln(n)$$
求出小于某个询问的所有对数，用总对数减一下即可。

代码：

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
/*************************************************************************
    > File Name: S.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/16 15:20:54
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int>p;
typedef long long ll;
const int maxm = 3e6 + 1;
ll sum[maxm];
int cnt[maxm];
int main (void)
{
	int n;scanf("%d", &n);
	int a;
	for(int i = 0; i < n; i++){
		scanf("%d", &a);
		cnt[a]++;
	}
	int q;scanf("%d",&q);
	for(int i = 1; i <= maxm; i++){
		for(int j = 1; j * i < maxm; j++){
			sum[i * j] += cnt[i] * 1ll * (cnt[j] - (i == j));
		}
	}
	for(int i = 1; i <= maxm; i++) sum[i] += sum[i - 1];
	int b;
	for(int i = 0; i < q; i++){
		scanf("%d", &b);
		printf("%I64d\n", n * 1ll * (n - 1) - sum[b - 1]);
	}
	return 0;
}
文章目录
  1. 1. B - Infinite Go(并查集，模拟)
    1. 1.1. 题意：
    2. 1.2. 分析：
    3. 1.3. 代码：
  2. 2. C - Ants(01Trie树)
    1. 2.1. 题意：
    2. 2.2. 分析：
    3. 2.3. 代码：
  3. 3. G - Matrix Decompressing(网络流)
    1. 3.1. 题意：
    2. 3.2. 分析：
    3. 3.3. 代码：
  4. 4. I. BerDonalds(图绝对中心)
    1. 4.1. 题意：
    2. 4.2. 分析：
    3. 4.3. 代码：
  5. 5. J - Runaway to a Shadow【计算几何】
    1. 5.1. 题意：
    2. 5.2. 分析：
    3. 5.3. 代码：
  6. 6. K - Puzzles (树形dp)
    1. 6.1. 题意：
    2. 6.2. 分析：
    3. 6.3. 代码：
  7. 7. L - PLEASE(概率dp，数学)
    1. 7.1. 题意：
    2. 7.2. 分析：
    3. 7.3. 代码：
  8. 8. M.Legen…(AC自动机+floyd倍增)
    1. 8.1. 题意：
    2. 8.2. 分析：
    3. 8.3. 代码：
  9. 9. N - Fashion in Berland(水)
    1. 9.1. 分析：
    2. 9.2. 代码：
  10. 10. O - s-palindrome(模拟)
    1. 10.1. 题意：
    2. 10.2. 代码：
  11. 11. P - Exponential notation(模拟)
    1. 11.1. 题意：
    2. 11.2. 分析：
    3. 11.3. 代码：
  12. 12. Q - Swaps in Permutation(并查集)
    1. 12.1. 题意：
    2. 12.2. 分析：
    3. 12.3. 代码：
  13. 13. R - Xor-sequences(矩阵快速幂)
    1. 13.1. 题意：
    2. 13.2. 分析：
    3. 13.3. 代码：
  14. 14. S - Couple Cover(神题，暴力)
    1. 14.1. 题意：
    2. 14.2. 分析：
    3. 14.3. 代码：