2019 ICPC World Finals

比赛地址 ：Codeforces Gym 102511

A - Azulejos

两排雕像，每排 \(n\) 个，每个雕像都有一个高度 \(h_i\) 和权值 \(w_i\) 。

对每排重新排序，使得：1. 每排 \(w_i\) 从左到右严格降序；2. 第一排的每个位置的雕像都比第二排对应位置的高。

贪心，先按照 \(w_i\) 从大到小排序，显然只有相同权值之间的可以有位置变动。

从左到右依次考虑，每次都扩展一个相同权值的区间，然后用右端点更小的区间里的雕像去匹配右端点更大的区间里的雕像。

这样子我们的需求都是在必须满足的时候满足的，并且已经考虑到了所有的情况。合理使用 STL 即可。

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
#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 mp make_pair
#define mt make_tuple
#define pb push_back
#define pii pair<int, int>
#define tii tuple<int, int, int>

#define N 500007

int p[N], ansb[N], anss[N];

tii b[N], s[N];

set<pii> B, S;

int main() {
	int n = rd();
	for (int i = 1; i <= n; ++i) p[i] = rd();
	for (int i = 1; i <= n; ++i) b[i] = mt(p[i], rd(), i);
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; ++i) p[i] = rd();
	for (int i = 1; i <= n; ++i) s[i] = mt(p[i], rd(), i);
	sort(s + 1, s + 1 + n);
	int tot = 0;
	for (int ptrs = 0, ptrb = 0; ptrs < n || ptrb < n;) {
		if (ptrs > ptrb) {
			++ptrb; 
			B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
			while (ptrb < n && get<0>(b[ptrb]) == get<0>(b[ptrb + 1])) {
				++ptrb; B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
			}
		} else if (ptrs < ptrb) {
			++ptrs; 
			S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
			while (ptrs < n && get<0>(s[ptrs]) == get<0>(s[ptrs + 1])) {
				++ptrs; S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
			}
		} else {
			++ptrb; 
			B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
			while (ptrb < n && get<0>(b[ptrb]) == get<0>(b[ptrb + 1])) {
				++ptrb; B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
			}
			++ptrs; 
			S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
			while (ptrs < n && get<0>(s[ptrs]) == get<0>(s[ptrs + 1])) {
				++ptrs; S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
			}
		}
    
		if (ptrs <= ptrb) {
			for (auto [h, id] : S) {
				if (h >= (*--B.end()).first) {puts("impossible"); return 0;}
				anss[++tot] = id; ansb[tot] = (*B.upper_bound(mp(h, 1e9))).second;
				B.erase(B.upper_bound(mp(h, 1e9))); 
			}
			S.clear();
		} else {
			for (auto [h, id] : B) {
				if (h <= (*S.begin()).first) {puts("impossible"); return 0;}
				ansb[++tot] = id; anss[tot] = (*--S.lower_bound(mp(h, 0))).second;
				S.erase(--S.lower_bound(mp(h, 0)));
			}
			B.clear();
		}
	}
	for (int i = 1; i <= n; ++i) printf("%d ", ansb[i]); puts("");
	for (int i = 1; i <= n; ++i) printf("%d ", anss[i]);
	return 0;
}

*B - Beautiful Bridges

题面太麻烦了不再赘述，要求折线不能与上半圆外有交，最小化代价。

数据范围是允许 \(\mathcal{O}(n^2)\) 做的，因此设 \(f[i]\) 表示前 \(i\) 个，且 \(i\) 放了桥墩的最小代价，转移很直接。

问题就是如何判断可以转移，即：判断区间内的点是否在上半圆外。

我们考虑枚举左端点 \(i\) ，然后再枚举被更新的所有右端点 \(j\) ，那么可以注意到圆心的轨迹是 \((x_i+r,H-r),r\ge 0\) 。

考虑一个点到圆心的距离，其实就是从无穷远变成点到直线距离再变到无穷远，因此一个点的合法范围一定是一个区间。

考虑一个点 \((x_j,y_j)\) 带来的约束，临界值显然取在 \((x_j-(x_i+r))^2+(y_j-(H-r))^2=r^2\) 处：

  • 如果 \((x_j,y_j)\) 加入时处于圆心上方（ \(y_j\ge H-\frac{x_j-x_i}{2}\) ），那么约束就是 \(r\in\) 方程两根之间的区间。
  • 否则，只会对 \(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
#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 N 10007

ll x[N], y[N], f[N];

inline double sqr(double x) {return x * x;}

int main() {
	memset(f, 0x3f, sizeof(f));
	ll n = rd(), H = rd(), alpha = rd(), beta = rd();
	for (int i = 1; i <= n; ++i) {x[i] = rd(); y[i] = rd();}
	f[1] = alpha * (H - y[1]);
	ll inf = f[n];
	for (int i = 1; i <= n; ++i) {
		double l = 0, r = H - y[i];
		for (int j = i + 1; j <= n; ++j) {
			double b = 2 * (x[i] + y[j] - x[j] - H);
			double c = sqr(x[j] - x[i]) + sqr(y[j] - H);
			double dlt = sqrt(b * b - 4 * c);
			double L = (-b - dlt) / 2, R = (-b + dlt) / 2;
			r = min(r, R);
			if (1.0 * y[j] >= H - 1.0 * (x[j] - x[i]) / 2.0) l = max(l, L); 
			double nwpos = 1.0 * (x[j] - x[i]) / 2.0;
			if (nwpos >= l - 1e-8 && nwpos <= r + 1e-8)
				f[j] = min(f[j], f[i] + alpha * (H - y[j]) + beta * (x[j] - x[i]) * (x[j] - x[i]));
		}
	}
	if (f[n] == inf) {puts("impossible"); return 0;}
	printf("%lld\n", f[n]);
	return 0;
}

D - Circular DNA

给定一个环状括号序列，有 \(n\) 类括号分别记做 \((_i\) 和 \()_i\) ，每类左括号只能与同一类右括号匹配。

找一个断开的位置变成一个序列，最大化合法的括号类数，如果有多个位置找下标最小的。

定义一类括号合法，当且仅当仅考虑该类括号，当前序列是一个合法的括号序列。

对每类分开考虑，合法的位置一定是若干个区间，然后线段树支持区间加求最值即可。

一个比较好写的方法：假设开始的位置是 \(0\) ，左括号 \(-1\) ，右括号 \(+1\) ，记录前缀和。

那么合法区间的左端点一定是前缀和最小的那些位置，右端点就是对应的下一个位置。

upd on 2022/11/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
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
#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 fr first 
#define sc second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pii pair<int, int>
#define tii tuple<int, int, int>

#define N 1000007

vector<pii> s[N];

#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)

int n, tag[N << 2];

pii mx[N << 2];

void pushdown(int rt) {
	if (tag[rt]) {
		mx[ls].fr += tag[rt]; tag[ls] += tag[rt];
		mx[rs].fr += tag[rt]; tag[rs] += tag[rt];
		tag[rt] = 0;
	}
}

void pushup(int rt) {
	if (mx[ls].fr > mx[rs].fr) mx[rt] = mx[ls];
	else if (mx[ls].fr < mx[rs].fr) mx[rt] = mx[rs];
	else {mx[rt].fr = mx[ls].fr; mx[rt].sc = min(mx[ls].sc, mx[rs].sc);}
}

void build(int rt, int l, int r) {
	mx[rt].sc = l;
	if (l == r) return;
	build(ls, l, mid);
	build(rs, mid + 1, r);
}

void upd(int rt, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		++mx[rt].fr; ++tag[rt]; return;
	}
	pushdown(rt);
	if (L <= mid) upd(ls, l, mid, L, R);
	if (R > mid) upd(rs, mid + 1, r, L, R);
	pushup(rt);
}


void add(int l, int r) {
	if (l <= r) upd(1, 1, n, l, r);
	else {
		upd(1, 1, n, 1, r); 
		if (l <= n) upd(1, 1, n, l, n);
	}
}

int tmp[N], pos[N];

inline void work(int x) {
	tmp[0] = 0;
	int tot = 0, mn = 0;
	for (auto [v, p] : s[x]) {
		++tot; 
		tmp[tot] = tmp[tot - 1] + v;
		mn = min(mn, tmp[tot]);
		pos[tot] = p;
	}
	if (tmp[tot] != 0) return;
	for (int i = 1; i < tot; ++i)
		if (tmp[i] == mn) add(pos[i] + 1, pos[i + 1]);
	if (tmp[tot] == mn) add(pos[tot] + 1, pos[1]);
}

int main() {
	n = rd();
	for (int i = 1; i <= n; ++i) {
		char c = getchar();
		while (!isalpha(c)) c = getchar();
		int x = rd();
		s[x].pb(mp((c == 's' ? 1 : -1), i));
	}
	build(1, 1, n);
	for (int i = 1; i <= 1000000; ++i) 
		if (!s[i].empty()) work(i);
	printf("%d %d\n", mx[1].sc, mx[1].fr);
	return 0;
}

*E - Dead-End Detector

给定无向图，定义 \(E_i=(u_i,v_i)\) 在 \(u_i\) 端要放死路牌：从 \(u_i\) 经过 \(E_i\) 之后，如果想回 \(u_i\) 一定要在某个顶点原路返回。

但如果存在 \(x\) 经过 \(E_i\) 之后可以到达 \(y\) 再经过 \(E_j\) ，并且 \(E_i\) 在 \(x\) 端有死路牌、\(E_j\) 在 \(y\) 端有死路牌，那么后者可以省去。

构造最小放置死路牌数方案。

对每个连通块考虑。

如果是一棵树，每条边都是死路。发现只需要在所有的叶子端放置即可，其他路径必定可以反着找到一条从叶子出发的边。

如果是其他情况，一定存在回路。考虑先拎出来一棵生成树，每加一条边，原树上对应这两个端点之间的路径都不是死路。

我们称这些被覆盖的点为标记点。可以注意到，两个标记点之间的路径也不会是死路，因为一定会走到一个环上。

此外同理，剩下的边里指向标记点的路径都不是死路。只有从标记点走出来的路径，并且不能到另一个标记点的是死路。

根据题目的省略要求，发现只要把所有标记点的最小连通块找出来就可以了，考场上写的虚树，实际上按叶子拓扑即可。

要放置死路牌的位置就是从拓扑中未删除点指向被删除点的那些方向。

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
#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 fr     first 
#define sc     second
#define mp     make_pair
#define mt     make_tuple
#define pb     push_back
#define pii    pair<int, int>
#define tii    tuple<int, int, int>
#define all(x) (x).begin(), (x).end()

#define N 500007

bool tree[N], circ[N], not_tree[N];

vector<int> s[N];

int tot, hd[N], f[N], deg[N];

struct edge{int to, nxt;} e[N << 1];

inline void add(int u, int v) {
    e[++tot].to = v; e[tot].nxt = hd[u]; hd[u] = tot; ++deg[u];
    e[++tot].to = u; e[tot].nxt = hd[v]; hd[v] = tot; ++deg[v];
}

int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}

inline void merge(int x, int y) {
    x = find(x); y = find(y);
    f[x] = y; not_tree[y] |= not_tree[x];
}

vector<pii> ans;

queue<int> q;

void topo(int x) {
    for (auto u : s[x])
        if (deg[u] == 1 && !circ[u]) {tree[u] = true; q.push(u);}
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = hd[u], v; i; i = e[i].nxt) {
            --deg[v = e[i].to];
            if (deg[v] <= 1 && !circ[v] && !tree[v]) {
                q.push(v); tree[v] = true;
            }
        }
    }
    for (auto u : s[x])
        if (tree[u]) 
            for (int i = hd[u], v; i; i = e[i].nxt)
                if (!tree[v = e[i].to]) ans.pb(mp(v, u));
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) f[i] = i;
    for (int i = 1, u, v; i <= m; ++i) {
        u = rd(); v = rd(); 
        if (find(u) == find(v)) not_tree[find(u)] = circ[u] = circ[v] = true;
        else {merge(u, v); add(u, v);}   
    }
    for (int i = 1; i <= n; ++i) s[find(i)].pb(i);
    for (int i = 1; i <= n; ++i) 
        if (f[i] == i) {
            if (not_tree[i]) topo(i);
            else for (auto u : s[i]) if (deg[u] == 1) ans.pb(mp(u, e[hd[u]].to));
        }
    sort(all(ans));
    printf("%d\n", (int)ans.size());
    for (auto [u, v] : ans) printf("%d %d\n", u, v);
    return 0;
}

G - First of Her Name

一棵树，每个点上有一个字符，定义一个节点的串就是从他到根路径上的字符依次接起来。

每次询问一个串 \(s\) ，问有多少个节点的串以 \(s\) 为前缀。

把询问串翻转一下，节点的串顺序也改为从根到它的路径，相当于询问有多少个串以 \(s\) 为后缀。广义 SAM。

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
#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=1000000,maxt=maxn<<1,maxi=26;

int n,Q,p[maxn+5],cnt[maxt+5];
int E,lnk[maxt+5],nxt[maxt+5],to[maxt+5];
int pl,ro,son[maxt+5][maxi],fai[maxt+5],MAX[maxt+5];
char s[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);
}
char getupr() {char ch=readc();while (!isupper(ch)) ch=readc();return ch;}
int reads(char *s){
	int len=0;char ch=getupr();
	while (isupper(ch)) s[++len]=ch,ch=readc();
	return len;
}
struct fastO{
	int si;char buf[1<<16];
	void putc(char ch){
		if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0;
		buf[si++]=ch;
	}
	~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
	static int len=0,buf[100];
	if (x<0) fo.putc('-'),x=-x;
	do buf[len++]=x%10,x/=10; while (x);
	while (len) fo.putc(buf[--len]+48);
	if (ch) fo.putc(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
inline int newnode() {pl++;return pl;}
int Extend(int p,int c){
	if (son[p][c]){
		int q=son[p][c];if (MAX[p]+1==MAX[q]) return q;
		int nq=newnode();MAX[nq]=MAX[p]+1;
		for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
		fai[nq]=fai[q];fai[q]=nq;
		while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
		return nq;
	} else {
		int np=newnode();MAX[np]=MAX[p]+1;
		while (p && !son[p][c]) son[p][c]=np,p=fai[p];
		if (!p) {fai[np]=ro;return np;}
		int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
		int nq=newnode();MAX[nq]=MAX[p]+1;
		for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
		fai[nq]=fai[q];fai[q]=fai[np]=nq;
		while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
		return np;
	}
}
void DFS(int x) {for (int j=lnk[x];j;j=nxt[j]) DFS(to[j]),cnt[x]+=cnt[to[j]];}
int main(){
	readi(n);readi(Q);
	ro=newnode();p[0]=ro;
	for (int i=1,w,x;i<=n;i++){
		w=getupr()-'A';readi(x);
		p[i]=Extend(p[x],w);cnt[p[i]]++;
	}
	for (int i=2;i<=pl;i++) Add(fai[i],i);
	DFS(ro);
	for (int t=1;t<=Q;t++){
		int len=reads(s),p=ro;
		for (int i=len;i;i--) p=son[p][s[i]-'A'];
		writei(cnt[p]);
	}
	return 0;
}

*H - Hobsons' trains

给一个内向基环树森林，对于每个点，问有多少个点沿着出边走 \(k\) 步之内可以到达他。

如果是树，就可以树上差分，对每个点 \(+1\) ，再对其 \(k\) 级祖先 \(-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<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 rep(i, x, y) for (int (i) = (x); (i) <= (y); ++(i))
#define per(i, x, y) for (int (i) = (x); (i) >= (y); --(i))

#define N 500007

int n, m, k, tot, d[N], f[N], hd[N];

struct edge{int to, nxt;} e[N << 1];

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

int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}

int vis[N], circ[N], pref[N], ans[N], stk[N], top;

void dfs(int u, int id) {
    stk[++top] = u; ++ans[u];
    if (top - k > 1) --ans[stk[top - k - 1]]; 
    else {
        --ans[stk[1]];
        int len = k - top + 2;
        if (len >= m) ++pref[1];
        else {
            int l = id, r = id + len - 1;
            ++pref[l];
            if (r > m) {r -= m; ++pref[1];}
            if (r < m) --pref[r + 1];
        }

    }
    for (int i = hd[u], v; i; i = e[i].nxt) 
        if (vis[v = e[i].to] != 2) {dfs(v, id); ans[u] += ans[v];}
    --top;
}

inline void work(int u) {
    m = 0;
    int t = u;
    for (; !vis[t]; t = d[t]) vis[t] = 1;
    for (; vis[t] != 2; t = d[t]) {vis[t] = 2; circ[++m] = t;}
    rep(i, 1, m) dfs(circ[i], i);
    rep(i, 1, m) {pref[i] += pref[i - 1]; ans[circ[i]] += pref[i];}
    rep(i, 1, m) pref[i] = 0;
}

int main() {
    n = rd(); k = rd();
    rep(i, 1, n) f[i] = i;
    rep(i, 1, n) {d[i] = rd(); add(d[i], i); f[i] = find(d[i]);}
    rep(i, 1, n) if (f[i] == i) work(i);
    rep(i, 1, n) printf("%d\n", ans[i]);
    return 0;
}