2018-2019 ICPC Asia Nanjing Regional

比赛地址 ：Codeforces Gym 101981

还没补完：FHKLM

A - Adrien and Austin

给定数集 \(\{1,\dots, n\}\) ，每次只能删掉至多 \(k\) 个连续的数字，删空的人赢，问最终结果。

若 \(k=1\) 直接判解；否则奇数删掉中位数，偶数删掉两个中位数，然后对称操作，先手一定赢。

想出来放 \(n=0\) 的 corner case 的出题人真是人才。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;

int main() {
	int n, m; cin >> n >> m;
	if (n == 0) {puts("Austin"); return 0;}
	if (m == 1) {puts((n & 1) ? "Adrien" : "Austin"); return 0;}
	puts("Adrien");
	return 0;
}

B - Tournament

wqs 二分 + 凸优化。队友做过一摸一样的板子题。

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
#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=300000;

int n,m,a[maxn+5];
int que[maxn+5],l[maxn+5],r[maxn+5],p[maxn+5];
LL sum[maxn+5],f[maxn+5];int g[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
	static char buf[1<<16],*l=buf,*r=buf;
	return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
	T tot=0;char ch=readc(),lst='+';
	while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
	while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
	lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline LL Sum(int L,int R){
	int m=(L+R>>1),A=m-L+1,B=R-m;
	return (LL)(A-B)*a[m]-(sum[m]-sum[L-1])+(sum[R]-sum[m]);
}
#define val(j,i) (mp(f[j]+Sum((j)+1,(i))+c,g[j]+1))
bool check(LL c){
	f[0]=0;g[0]=0;
	int Head=1,Tail=0;
	p[++Tail]=0;l[Tail]=1;r[Tail]=n;
	for (int i=1;i<=n;i++){
		pair<LL,int> now=val(p[Head],i);
		f[i]=now.fr;g[i]=now.sc;
		int lst=-1;
		while (Head<=Tail)
			if (val(p[Tail],l[Tail])>val(i,l[Tail])) lst=l[Tail--]; else {
				int L=l[Tail],R=r[Tail];
				for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
					val(p[Tail],mid)>val(i,mid)?R=mid-1:L=mid+1;
				if (L<=r[Tail]) lst=L,r[Tail]=L-1;
				break;
			}
		if (~lst) p[++Tail]=i,l[Tail]=lst,r[Tail]=n;
		if (Head<=Tail) {l[Head]++;if (l[Head]>r[Head]) Head++;}
	}
	return g[n]<=m;
}
int main(){
	readi(n);readi(m);
	for (int i=1;i<=n;i++) readi(a[i]),sum[i]=sum[i-1]+a[i];
	LL L=0,R=3e14;
	for (LL mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
		check(mid)?R=mid-1:L=mid+1;
	check(L);
	printf("%lld\n",f[n]-L*m);
	return 0;
}

**C - Cherry and Chocolate

给一棵树，第一个人把某个点染成粉色，第二个人把另一个点染成棕色，第一个人再把另另一个点染成粉色。

定义树的权值为符合下述描述的节点 \(u\) 的个数：从 \(u\) 到棕色点的路径上经过某个粉色点。

第一个人想最大化权值，第二个人想最小化权值，问最终树的权值。

我们称第一个粉色点为 \(x\) ，棕色点为 \(y\) ，第二个粉色点为 \(z\) 。

我们以第一个人的视角，假设 \(x,y\) 已经确定，那么令 \(x\) 为根，所有子树里除掉 \(y\) 所在的子树以外的全部的点都已经被赚到了。

所以 \(z\) 一定会放在 \(y\) 所在的子树中。把这个子树拎成以 \(y\) 为根， \(z\) 能赚回来的是某个子树大小，因此一定选 \(y\) 的某个儿子。

因此如果 \(y\) 所在的子树已经选定，为了让 \(z\) 捞回去的点数最少， \(y\) 一定会选在这个子树的重心上。

所以 \(y\) 捞回来的值是 \(sz[\text{子树}]-mxs[\text{重心}]\) ，会把 \(y\) 选在使得这个权值最大的子树的重心上。

这样就可以 \(\mathcal{O}(n)\) 检查一个选定的 \(x\) 之后最终树的权值了。

那么考虑现在我们已经有了一个方案 \((x,y,z)\) ，那么把 \(x\) 朝远离 \(y\) 的方向移动不会使答案变优。

因此每次需检查的范围都是当前 \(x\) 的某个子树，那么每次都选这个范围的重心，就只需要检查 \(\mathcal{O}(\log 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
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
#include<bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

inline bool getmin(int &a, int b) {return a > b ? (a = b, true) : false;}
inline bool getmax(int &a, int b) {return a < b ? (a = b, true) : false;}

#define N 100007

bool tag[N]; // [tag[u] = true] : should be tested to be the first pink point

int sz[N], mxs[N];

vector<int> e[N];

int n, rt, tot, mn;

void getcentre(int u, int fa) {
	sz[u] = 1; mxs[u] = 0;
	for (auto v : e[u])
		if (tag[v] && v != fa) {getcentre(v, u); sz[u] += sz[v]; mxs[u] = max(mxs[u], sz[v]);}
	mxs[u] = max(mxs[u], tot - sz[u]);
	mn = min(mn, mxs[u]);
}

vector<int> subtree[N];

void getsz(int u, int fa, int top) {
	sz[u] = 1; mxs[u] = 0; 
	subtree[top].push_back(u);
	for (auto v : e[u])
		if (v != fa) {getsz(v, u, top); sz[u] += sz[v]; mxs[u] = max(mxs[u], sz[v]);}
}

int main() {
	n = tot = rd();
	for (int i = 1; i <= n; ++i) tag[i] = true;
	for (int i = 1; i < n; ++i) {
		int u = rd(), v = rd();
		e[u].push_back(v); e[v].push_back(u);
	} 
	int ans = 0;
	for (rt = 1; tag[rt]; ) {
		// find the centre
		mn = 1e9; getcentre(rt, rt);
		for (int u = 1; u <= n; ++u)
			if (tag[u] && mxs[u] == mn) {rt = u; break;}
		tag[rt] = false; --tot;
		// find the best brown point in the initial tree 
		// i.e. find a subtree whose centre maximize |subtree| - mxs[centre]
		int res = n, pos = rt;
		for (auto u : e[rt]) {
			subtree[u].clear();
			getsz(u, rt, u);
			int bst = u;
			for (auto v : subtree[u]) mxs[v] = max(mxs[v], sz[u] - sz[v]);
			for (auto v : subtree[u]) if (mxs[v] < mxs[bst]) bst = v;
			int cur = n - sz[u] + mxs[bst];
			if (getmin(res, cur)) pos = u;
		}
		ans = max(ans, res);
		for (auto u : e[rt])
			if (u != pos) for (auto v : subtree[u]) 
				if (tag[v]) {tag[v] = false; --tot;}
		rt = pos;
	} 
	printf("%d\n", ans);
	return 0;
}

D - Country Meow

求最小球覆盖的半径。

板子题。换一换估价函数类似的题目也可以考虑三分套三分套三分。

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
#include<bits/stdc++.h>
using namespace std;

int n, cnt, i;
double R, tmp;

const double eps = 1e-5;

struct P {
	double x, y, z;
	P(){}
	P(double _x, double _y, double _z) {x = _x; y = _y; z = _z;}
	P operator + (const P &b) {return P(x + b.x, y + b.y, z + b.z);}
	P operator - (const P &b) {return P(x - b.x, y - b.y, z - b.z);}
	P operator * (double b) {return P(x * b, y * b, z * b);}
	P operator / (double b) {return P(x / b, y / b, z / b);}
} a[200007], b[4], O;

double dis(const P &a, const P &b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z);
}
double dot(const P &a, const P &b) {
	return a.x * b.x + a.y * b.y + a.z * b.z;
}

void ball() {
	P q[3];
	double m[3][3], f[3], L[3], det;
	int i, j; O.x = O.y = O.z = R = 0;
	switch(cnt) {
		case 1 : O = b[0]; break;
		case 2 : O = (b[0] + b[1]) / 2; R = dis(O, b[0]); break;
		case 3 : 
			for (i = 0; i < 2; ++i) q[i] = b[i + 1] - b[0];
			for (i = 0; i < 2; ++i) for (j = 0; j < 2; ++j) m[i][j] = dot(q[i], q[j]) * 2;
			for (i = 0; i < 2; ++i) f[i] = dot(q[i], q[i]);
			if (fabs(det = m[0][0] * m[1][1] - m[0][1] * m[1][0]) < eps) return;
			L[0] = (f[0] * m[1][1] - f[1] * m[0][1]) / det;
			L[1] = (f[1] * m[0][0] - f[0] * m[1][0]) / det;
			O = b[0] + q[0] * L[0] + q[1] * L[1];
			R = dis(O, b[0]);
			break;
		case 4 : 
			for (i = 0; i < 3; ++i) q[i] = b[i + 1] - b[0 ], f[i] = dot(q[i], q[i]);
			for (i = 0; i < 3; ++i) for (j = 0; j < 3; ++j) m[i][j] = dot(q[i], q[j]) * 2;
			det = m[0][0] * m[1][1] * m[2][2]
				+ m[0][1] * m[1][2] * m[2][0]
				+ m[0][2] * m[2][1] * m[1][0]
				- m[0][2] * m[1][1] * m[2][0]
				- m[0][1] * m[1][0] * m[2][2]
				- m[0][0] * m[1][2] * m[2][1];
			if (fabs(det) < eps) return;
			for (j = 0; j < 3; ++j) {
				for (i = 0; i < 3; ++i) m[i][j] = f[i];
				L[j] = (m[0][0] * m[1][1] * m[2][2]
				+ m[0][1] * m[1][2] * m[2][0]
				+ m[0][2] * m[2][1] * m[1][0]
				- m[0][2] * m[1][1] * m[2][0]
				- m[0][1] * m[1][0] * m[2][2]
				- m[0][0] * m[1][2] * m[2][1]) / det;
				for (i = 0; i < 3; ++i) m[i][j] = dot(q[i], q[j]) * 2;
			}
			O = b[0];
			for (i = 0; i < 3; ++i) O = O + q[i] * L[i];
			R = dis(O, b[0]);
	}
}

void minball(int n) {
	ball();
	if (cnt < 4) for (int i = 0; i < n; ++i) if (dis(O, a[i]) - R > eps) {
		b[cnt++] = a[i]; minball(i); --cnt;
		if (i > 0) {
			P t = a[i];
			memmove(&a[1], &a[0], sizeof(P) * i);
			a[0] = t;
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z);
	random_shuffle(a, a + n); R = -1;
	for (i = 0; i < n; ++i) {
		if (dis(O, a[i]) - R > eps) cnt = 1, b[0] = a[i], minball(i);
		//printf("%.12lf %.12lf %.12lf %.12lf\n", O.x, O.y, O.z, R);
	}
	printf("%.12lf\n", sqrt(R));
	return 0;
}

*E - Eva and Euro coins

给定两个 \(01\) 序列 \(A,B\) ，每次可以把 \(A\) 中连续 \(k\) 个相同的位置一起翻转，问是否能把 \(A\) 变成 \(B\) 。

手玩一下发现：对于 \(k\) 个 \(x=0/1\) , \(xx\dots xxy\) 和 \(y x x\dots x\) 一定是可以互相转换的。

换言之， \(k\) 个相同的字符可以在序列里任意移动，而且与具体是 \(0/1\) 无关。

所以把尽可能多的 \(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
#include<bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 1000007

#define fr  first
#define sc  second
#define pci pair<char, int>

int na, nb;

pci a[N], b[N];

int main() {
	int n = rd(), k = rd();
	if (k == 1) {puts("Yes"); return 0;}
	for (int i = 1; i <= n; ++i) {
		char c = getchar();
		while (!isdigit(c)) c = getchar();
		if (na && a[na].fr == c) {
			++a[na].sc; if (a[na].sc == k) --na;
		} else a[++na] = mp(c, 1);
	}
	for (int i = 1; i <= n; ++i) {
		char c = getchar();
		while (!isdigit(c)) c = getchar();
		if (nb && b[nb].fr == c) {
			++b[nb].sc; if (b[nb].sc == k) --nb;
		} else b[++nb] = mp(c, 1);
	}
	if (na != nb) {puts("No"); return 0;}
	for (int i = 1; i <= na; ++i)
		if (a[i] != b[i]) {puts("No"); return 0;}
	puts("Yes");
	return 0;
}

**F - Frank

DAG 随机游走。

队友切了 貌似是 \(O(n^2)\) 支持修改一个方程并求解方程组。

一个相关套路题：连接1

G - Pyramid

打表插值/找规律/推式子，柴老师推出来是 \({n+3\choose 4}\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define mod 1000000007
#define inv24 41666667

int main(){
	for (int t = rd(); t; --t) {
		int n = rd();
		printf("%lld\n", 1ll * (n + 3) * (n + 2) % mod * (n + 1) % mod * n % mod * inv24 % mod);
	}
	return 0;
}

*H - Huge Discount

I - Magic Potion

最大流板子题。药水当作另一个源点。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

inline bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}
inline bool getmax(int &a, int b) {return (a < b ? (a = b, true) : false);}

// F is the type of flow
template<const int V, const int E, class F, const F flowInf>
struct Flow {

    int tot = 1, S, T, hd[V], cur[V], dis[V];
    struct edge{int to, nxt; F cap;} e[E << 1];

    void clear() {tot = 1; memset(hd, 0, sizeof(hd));}

    void add(int u, int v, F w) {
        e[++tot].nxt = hd[u], hd[u] = tot, e[tot].to = v, e[tot].cap = w;
        e[++tot].nxt = hd[v], hd[v] = tot, e[tot].to = u, e[tot].cap = 0;
    }

    inline bool bfs() {
        static int q[V], qhd, qtl; 
        memcpy(cur, hd, sizeof(hd));
        memset(dis, -1, sizeof(dis));
        q[qhd = qtl = 1] = S; dis[S] = 0;
        while (qhd <= qtl) {
            int u = q[qhd++];
            for (int i = hd[u], v; i; i = e[i].nxt)
                if (dis[v = e[i].to] == -1 && e[i].cap != 0) {
                    dis[v] = dis[u] + 1; q[++qtl] = v;
                }
        }
        return dis[T] != -1;
    }

    F dfs(int u, F rem) {
        if (u == T) return rem;
        F flow = 0;
        for (int i = cur[u], v; i && rem; i = e[i].nxt) {
            cur[u] = i; v = e[i].to;
            F nw = min(rem, e[i].cap);
            if (nw != 0 && dis[v] == dis[u] + 1) {
                int ret = dfs(v, nw);
                flow += ret; rem -= ret; 
                e[i].cap -= ret; e[i ^ 1].cap += ret;
            }
        }
        if (flow == 0) dis[u] = -1;
        return flow;
    }

    F dinic(int source, int sink) {
        S = source; T = sink; F flow = 0;
        while (bfs()) flow += dfs(S, flowInf);
        return flow;
    }
};

constexpr int N = 1007;
constexpr int M = 100007;
constexpr int inf = 1e9;

Flow<N, M, int, inf> f;

int main(){
	int n = rd(), m = rd(), k = rd();
	int S = 0, T = N - 1, P = N - 2;
	f.add(S, P, k);
	for (int i = 1; i <= m; ++i) f.add(i + n, T, 1);
	for (int i = 1; i <= n; ++i) {
		f.add(S, i, 1); f.add(P, i, 1);
		for (int j = rd(); j; --j) f.add(i, rd() + n, 1);
	}
	printf("%d\n", f.dinic(S, T));
	return 0;
}

J - Prime Game

给定一个数列，定义一个区间的权值为区间所有数的乘积的质因子集大小，求所有区间权值和。

对每个质数计算，用总区间数减掉不包含这个质数的区间数，复杂度 \(\mathcal{O}(n\log(\max a_i))\) 。分解质因数用线性筛出 mindiv 。

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
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=1000000;

int n,a[maxn+5];LL ans;
int p[maxn+5],D[maxn+5];bool pri[maxn+5];
int lst[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
	static char buf[1<<16],*l=buf,*r=buf;
	return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
	T tot=0;char ch=readc(),lst='+';
	while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
	while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
	lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Make(int n){
	for (int i=2;i<=n;i++){
		if (!pri[i]) p[++p[0]]=i,D[i]=i;
		for (int j=1,t;j<=p[0] && (t=i*p[j])<=n;j++)
			{pri[t]=true;D[t]=p[j];if (!(i%p[j])) break;}
	}
}
int main(){
	readi(n);Make(maxn);
	ans=(LL)n*(n+1)/2*p[0];
	for (int i=1,x;i<=n;i++){
		readi(x);
		for (int d=D[x];x>1;x/=d,d=D[x]){
			int len=i-lst[d]-1;
			ans-=(LL)len*(len+1)/2;
			lst[d]=i;
		}
	}
	for (int i=1;i<=p[0];i++){
		int len=n-lst[p[i]];
		ans-=(LL)len*(len+1)/2;
	}
	printf("%lld\n",ans);
	return 0;
}

K - Kangaroo Puzzle

给一个 \(20\times 20\) 的网格图，每个位置是袋鼠/墙，保证袋鼠联通，构造一个LURD序列使得所有的袋鼠走到一起。

网格太小想一想随机可过，输出 \(50000\) 个随机字符就过了。正解是考虑每次合并两个袋鼠，合在一起的肯定不会再分开了。

*L - Lagrange the Chef

M - Mediocre String Problem

Z 函数 + manacher。