2021 CCPC Guilin 解题报告

Posted on In ,

比赛链接

A - A Hero Named Magnus

显然答案为 \(2x-1\).

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		long long x;
		cin >> x;
		cout << 2 * x - 1 << '\n';
	}
	return 0;
}

B - A Plus B Problem

两个加数的变换位数是显然的. 接下来考虑和的变换位数.

对于每一位, 定义 \(C_i\) 为是否有来自低位的进位, 则 \(S_i=(A_i+B_i+C_i)\bmod 10\).

要考虑和数的变换位数, 将作了改动的第 \(c\) 列单独处理, 这个只要知道 \(C_c\) 即可判断.

对于不在 \(c\) 列的列, \(S_i\) 变换等价于 \(C_i\) 发生变换. 于是只要维护 \(C_i\) 的总数即可在 \(O(1)\) 时间内得到 \(S_i(i\ne c)\) 变换位数. 具体地, 是 \(|\Delta\text{总进位数}| - [C_c \text{ 变化}]\).

那么怎么维护 \(C_i\) 的总数呢? 学过数逻计组的话可能会知道, 一个位置有 \(C_i\) 等价于存在 \(j\ge i\) 满足 \(x\in \lbrace i+1, i+2, \cdots, j-1\rbrace\) 都是 \(A_x+B_x= 9\) 且 \(A_j+B_j\ge 10\). (这里认为下标大的是低位).

于是可以用 set 维护所有 \(A_i+B_i\ge 10\) 的位置作为"发射源", 然后用树状数组维护 \(A_i+B_i=9\) 的位置的前缀和, 每次二分得到发射源向左可以到达最远的 \(A_i+B_i=9\) 段的边界, 于是可以借此维护. 总复杂度 \(O((n+q)\log ^2 n)\).

其实直接用 set 维护所有 \(A_i+B_i\ne 9\) 的位置, 容易做到 \(O((n+q)\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
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
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
constexpr int MAXN = 1e6 + 5;
int n, q, a[MAXN], b[MAXN], x[MAXN], ccnt;
set<int> pos;

namespace BIT {
	int t[MAXN], s[MAXN];
	int lowbit(int x) {return x & -x;}
	void init() {
		for (int i = 1; i <= n; i++) {
			s[i] = s[i-1] + x[i];
			t[i] = s[i] - s[i - lowbit(i)];
		}
	}
	void add(int x, int v) {
		for (int i = x; i <= n; i += lowbit(i))
			t[i] += v;
	}
	int sum(int x) {
		int ret = 0;
		for (int i = x; i; i -= lowbit(i))
			ret += t[i];
		return ret;
	}
	int sum(int x, int y) {
		return sum(y) - sum(x-1);
	}
}

int mdy(int c, int v) {
	auto it = pos.lower_bound(c+1);
	if (it == pos.end())
		return n + 2;
	int pw = *it;
	int l = 1, r = pw - 1, ret = pw;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (BIT::sum(m, pw-1) == pw-1-m+1) {
			r = m - 1;
			ret = m;
		} else {
			l = m + 1;
		}
	}
	ccnt += (pw - 1 - ret + 1 + (ret != 1)) * v;
	return ret;
}

void cancel(int c, int v) {
	if (v == 9) {
		BIT::add(c, -1);
	} else if (v >= 10) {
		mdy(c-1, -1);
		pos.erase(pos.find(c));
	}
}

void enable(int c, int v) {
	if (v == 9) {
		BIT::add(c, 1);
	} else if (v >= 10) {
		pos.insert(c);
		mdy(c-1, 1);
	}
}

void work() {
	int r, c, d;
	cin >> r >> c >> d;
	int lccnt = ccnt;
	int ori_c = (c >= mdy(c, -1) - 1);
	int ori = a[c] + b[c];
	cancel(c, ori);
	if (r == 1)
		a[c] = d;
	else 
		b[c] = d;
	int nwv = a[c] + b[c];
	enable(c, nwv);
	int nwv_c = (c >= mdy(c, 1) - 1);
	int ans = abs(ccnt - lccnt) - (ori_c != nwv_c) + ((ori + ori_c) % 10 != (nwv + nwv_c) % 10);
	cout << (nwv + nwv_c) % 10 << ' ' << ans+ (nwv != ori) << '\n';
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		char ch;
		cin >> ch;
		a[i] = ch - '0';
	}
	for (int i = 1; i <= n; i++) {
		char ch;
		cin >> ch;
		b[i] = ch - '0';
	}
	for (int i = 1; i <= n; i++) {
		int s = a[i] + b[i];
		if (s == 9)
			x[i] = 1;
		else if (s >= 10) {
			pos.insert(i);
		}
	}
	BIT::init();
	for(auto c : pos)
		mdy(c-1, 1);
	while(q--)
		work();
	return 0;
}

C - AC Automaton(UNDONE)

D - Assumption is All You Need

做法1

一个结论: 从值为 \(n\) 的元素到从值为 \(1\) 的元素, 一个一个按照以下的规律挪动:

假设挪动的元素 \(v\) 要从原位置 \(x\) 挪到目标位置 \(y\).

  1. 若 \(x>y\), 那么无解;
  2. 若 \(x\le y\), 那么从 \([x+1, y]\) 区间中找到小于 \(v\) 的元素中最大的一个 \(v'\), 然后把 \(v\) 和 \(v'\) 交换, 直到 \(x=y\).

单次上述过程可以用一个单调栈 \(O(n)\) 完成, 总时间复杂度 \(O(n^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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using pr = pair<int, int>;
constexpr int MAXN = 2100;

int n, a[MAXN], b[MAXN], p[MAXN], fp[MAXN];
int stk[MAXN], _stk;
vector<pr> ans;

bool work(int v) {
	int x = p[v], y = fp[v];
	if (x > y)
		return 0;
	stk[_stk = 1] = x;
	for (int i = x+1; i <= y; i++) 
		if (a[i] < v) {
			while (_stk > 0 && a[i] > a[stk[_stk]])
				--_stk;
			stk[++_stk] = i;
		}
	for (int i = 2; i <= _stk; i++) {
		ans.push_back(pr(stk[i-1], stk[i]));
		swap(p[a[stk[i-1]]], p[a[stk[i]]]);
		swap(a[stk[i-1]], a[stk[i]]);
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			p[a[i]] = i;
		}
		for (int i = 1; i <= n; i++) {
			cin >> b[i];
			fp[b[i]] = i;
		}
		ans.clear();
		for (int i = n; i >= 1; i--)
			if (!work(i)) {
				cout << -1 << '\n';
				goto END;
			}
		cout << ans.size() << '\n';
		for (auto i : ans) {
			cout << i.first << ' ' << i.second << '\n';
		}
END:
		;
	}
	
	return 0;
}

做法2

题解的做法: 找到最小的使得 \(A_p\ne B_p\) 的位置 \(p\), \(q\) 为最小的满足 \(q>p\) 且 \(A_p> A_q\ge B_p\) 的位置 \(q\), 交换 \(A_p\) 和 \(A_q\), 重复操作直到不可以操作为止. 有解当且仅当这种方法是可行解.

这个证明感觉不是很显然...之后再想.

E - Buy and Delete

容易发现答案不超过 \(2\) (比如, 一次删去 \(u<v\) 的边, 一次删除 \(u>v\) 的边).

  1. 如果任意一条边的权值比钱数 \(c\) 大, 那么答案为 \(0\).
  2. 否则, 答案为 \(1\) 或 \(2\). 设图中最小环的权值是 \(k\), 如果 \(c\ge k\) 即可以买下一个有向环, 那么答案为 \(2\); 否则答案为 \(1\).

故只需要求解图的最小环, 可以使用 \(n\) 次 Dijkstra 算法得到任意两点间的距离 \(dist(u, v)\), 那么最小环的权值为 \[ \sum_{(u, v, w)\in E}(w+dist(v, u)). \] 时间复杂度 \(O(n(n+m)\log 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
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
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;
using pr = pair<ll, int>;
constexpr int MAXN = 2005;
constexpr int MAXM = 5005;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 1e18;
int n, m;
ll c;
struct Edge {
	int v, nxt, w;
}e[MAXM];
int cnt, head[MAXN];

void addedge(int u, int v, int w) {
	e[++cnt] = {v, head[u], w};
	head[u] = cnt;
}

ll dist[MAXN][MAXN];
int vis[MAXN];

void SSSP(int s) {
	priority_queue<pr, vector<pr>, greater<pr> > pq;
	for (int i = 1; i <= n; i++) {
		dist[s][i] = LINF;
		vis[i] = 0;
	}
	dist[s][s] = 0;
	pq.push(pr(0, s));
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v, w = e[i].w;
			if (dist[s][v] > dist[s][u] + w) {
				dist[s][v] = dist[s][u] + w;
				pq.push(pr(dist[s][v], v));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> c;
	int mnw = INF;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		addedge(u, v, w);
		mnw = min(mnw, w);
	}
	if (mnw > c) {
		cout << 0 << '\n';
		return 0;
	}
	for (int i = 1; i <= n; i++)
		SSSP(i);
	ll ret = LINF;
	for (int u = 1; u <= n; u++)
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v, w = e[i].w;
			ret = min(ret, w + dist[v][u]);
		}
	if (ret > c)
		cout << 1 << '\n';
	else
		cout << 2 << '\n';
	return 0;
}

F - Illuminations II

求解在外部多边形上任意一个点上可以看到内部多边形的长度的期望. 容易发现对于内部的每条边, 要么完全看不到, 要么完全看不到. 于是利用期望的可加性, 而每条边上的贡献是它的长度乘以它延长线所截的右边外多边形长度所占周长的比例. 所以只要对内部每条边求解它延长线所截的右边外多边形的长度, 这可以用双指针完成. 时间复杂度 \(O(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
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
134
135
136
137
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <vector>
#define int long long
inline int getint(){
	int ssum=0,ff=1;char ch;
	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
	if(ch=='-') ff=-1,ch=getchar();
	for(;isdigit(ch);ch=getchar()) ssum=ssum*10+ch-'0';
	return ssum*ff;
}
using db = long double;
using namespace std;
constexpr int MAXN = 2e5 + 5;
constexpr db eps = 1e-10, inf = 1e10;
int dcmp(db x) {return x < -eps ? -1 : (x > eps ? 1 : 0);}
db Abs(db x) {return x * dcmp(x);}
struct Pnt {
	db x, y;
	Pnt(db x = 0, db y = 0) : x(x), y(y) {}
};
using Vec = Pnt;
db Dot(const Vec &a, const Vec &b) {return a.x * b.x + a.y * b.y;}
db Cro(const Vec &a, const Vec &b) {return a.x * b.y - a.y * b.x;}
db Len(const Vec &a) {return sqrt(Dot(a, a));}
Vec operator + (const Vec &a, const Vec &b) {return Vec(a.x + b.x, a.y + b.y);}
Vec operator - (const Vec &a, const Vec &b) {return Vec(a.x - b.x, a.y - b.y);}
Vec operator * (const Vec &a, const db &b) {return Vec(a.x * b, a.y * b);}
bool operator == (const Vec &a, const Vec &b) {return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);}

Pnt CrossPoint(const Pnt &a, const Pnt &b, const Pnt &c, const Pnt &d) {
	Vec ab = b-a, cd = d-c, ca = a-c;
	return a + ab * (Cro(cd, ca) / Cro(ab, cd));
}

int righthand(const Pnt &a, const Pnt &b, const Pnt &p)
{
	return dcmp(Cro(p-a, b-a));
}

using Poly = vector<Pnt>;

int _out, _in, s, t;
Poly out, in;
vector<db> dis;
db nowans, circ, ans;


void calc(int p) {
	int q = p + 1;
	if (q == _in) q = 0;
	db ret = nowans;
	int sn = s + 1;
	if (sn == _out) sn = 0;
	int tp = t - 1;
	if (tp < 0) tp = _out - 1;
	Pnt a = CrossPoint(in[p], in[q], out[s], out[sn]);
	ret += Len(out[sn]-a);
	Pnt b = CrossPoint(in[p], in[q], out[tp], out[t]);
	ret += Len(b-out[tp]);
	ans += Len(in[q] - in[p]) * (ret / circ);
}

void adjust(int p) {
	int q = p + 1;
	if (q == _in) q = 0;
	int sn = s + 1;
	if (sn == _out) sn = 0;
	while (righthand(in[p], in[q], out[sn]) < 0) {
		nowans -= dis[sn];
		s = sn;
		sn = s + 1;
		if (sn == _out) sn = 0;
	}
	while (righthand(in[p], in[q], out[t]) >= 0) {
		int tp = t - 1;
		if (tp < 0) tp = _out - 1;
		nowans += dis[tp];
		t++;
		if (t == _out) t = 0;
	}
}


signed main() 
{
	scanf("%lld%lld", &_out, &_in);
	out.resize(_out);
	in.resize(_in);
	dis.resize(_out);
	for (int i = 0; i < _out; i++) {
		int x, y;
		x=getint();y=getint();
		out[i].x = x; out[i].y = y;
	}
	for (int i = 0; i < _in; i++) {
		int x, y;
		x=getint();y=getint();
		in[i].x = x; in[i].y = y;
	}
	for (int i = 0; i < _out; i++) {
		int j = i+1;
		if (j == _out) j = 0;
		dis[i] = Len(out[j] - out[i]);
		circ += dis[i];
	}
	for(int i = 0; i < _out; i++) {
		int j = i + 1;
		if (j == _out) j = 0;
		if (righthand(in[0], in[1], out[i]) < 0 && righthand(in[0], in[1], out[j]) >= 0) {
			s = i;
			t = j;
			break;
		}
	}
	int flag = 0;
	while (!flag) {
		int nxt = t + 1;
		if (nxt == _out) nxt = 0;
		if (righthand(in[0], in[1], out[t]) >= 0 && righthand(in[0], in[1], out[nxt]) < 0) {
			flag = 1;
		} else {
			nowans += dis[t];
		}
		t = nxt;
	}
	calc(0);
	for (int i = 1; i < _in; i++) {
		adjust(i);
		calc(i);
	}
	printf("%.15lf\n", (double)ans);
	return 0;
}

G - Occupy the Cities

容易发现, 如果迭代 \(k\) 次, 那么原位置在 \(x\) 的一个 1 可以扩展到 \([x-k, x+k-1]\) 或 \([x-k+1, x+k]\). 所以可以 \(O(n)\) 判定: 贪心地从左到右"连接", 尽量选择后者. 于是可以在 \(O(n\log n)\) 的时间内二分+判定解决.

将上述算法稍加修改, 用动态规划算法即可在 \(O(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
#include <iostream>
#include <algorithm>
using namespace std;

constexpr int MAXN = 1e6 + 5;

int n;
char s[MAXN];

bool check(int k) 
{
	int lst = 0;
	for (int i = 1; i <= n; i++)
		if (s[i] == '1') {
			int le, ri;
			if (lst + 1 >= i - k + 1) {
				le = i - k + 1;
				ri = i + k;
			} else {
				le = i - k;
				ri = i + k - 1;
			}
			if (lst + 1 < le)
				return 0;
			lst = ri;
		}
	return lst >= n;
}

void work() 
{
	cin >> n;
	cin >> (s+1);
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		if (s[i] == '1')
			++cnt;
	if (cnt == n) {
		cout << 0 << '\n';
		return;
	}
	int L = 1, R = n, ans = -1;
	while (L <= R) {
		int M = (L + R) >> 1;
		if (check(M)) {
			ans = M;
			R = M - 1;
		} else {
			L = M + 1;
		}
	}
	cout << ans << '\n';
}
 
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--)
		work();
	return 0;
}

H - Popcount Words(UNDONE)

I - PTSD

一个简单的贪心.

代码 
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
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
constexpr int MAXN = 1e6 + 5;

int n, tot;
ll ans;
char s[MAXN];

void work() 
{
	cin >> n;
	cin >> (s + 1);
	ans = 0;
	tot = 0;
	for (int i = n; i >= 1; i--)
		if (s[i] == '1') {
			if (tot > 0) {
				ans += i;
				tot--;
			} else {
				tot++;
			}
		} else {
			tot++;
		}
	cout << ans << '\n';
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--)
		work();
	return 0;
}

J - Suffix Automaton(UNDONE)

K - Tax

容易发现, 在 Dijkstra 后形成一个分层 DAG (按照离起点 \(1\) 的最短距离分层,仅层间有边), 合法的路径必定是该分层 DAG 上的一条路径. 一个结论是: \(n\) 个点的这样的分层 DAG, 搜素所有路径的复杂度是 \(O(3^{n/3})\) 的.

一个简要的证明: 假设分为 \(k\) 层, 每层的节点数一次为 \(c_1, c_2, \cdots, c_k\), 那么搜素所有路径的时间是不超过 \[ \prod_{1\le i\le k}c_i, \text{when } \sum_{1\le i\le k} c_i=n \] 的. 那么也就最大化前者. 根据均值不等式, 当 \(c_1=c_2=\cdots =c_k=t\) 时, 前者最大, 所以得到前者不超过 \[ t^{k}=t^{n/t}, (t\in \mathbb N^+) \] 次, 即 \(e^{n\ln t/t}\). 而 \(\ln t/ t\) 在 \(t=3\) 时取得最大值, 故最大值为 \(3^{n/3}\).

代码 
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
#include <iostream>
#include <algorithm>
#include <queue>
using ll = long long;
using namespace std;

constexpr int MAXN = 55;
constexpr int MAXM = 2505;
constexpr ll lINF = 1e18;
int n, m;
int w[MAXM];
struct Edge {
	int v, nxt, c;
}e[MAXM];
int head[MAXN], cnt;
void addedge(int u, int v, int c) {
	e[++cnt] = {v, head[u], c}; 
	head[u] = cnt;
}

int dep[MAXN], vis[MAXN], num[MAXM];
ll dist[MAXN];

void bfs() {
	vis[1] = 1;
	queue<int> que;
	que.push(1);
	while (!que.empty()) {
		int u = que.front();
		que.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (vis[v])
				continue;
			dep[v] = dep[u] + 1;
			vis[v] = 1;
			que.push(v);
		}
	}
}

void dfs(int u, ll nowans) {
	dist[u] = min(dist[u], nowans);
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v, c = e[i].c;
		if (dep[v] != dep[u] + 1)
			continue;
		num[c]++;
		dfs(v, nowans + num[c] * w[c]);
		num[c]--;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> w[i];
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		addedge(u, v, c);
		addedge(v, u, c);
	}
	bfs();
	for (int i = 2; i <= n; i++)
		dist[i] = lINF;
	dfs(1, 0);
	for (int i = 2; i <= n; i++)
		cout << dist[i] << '\n';
	return 0;
}

L - Wiring Engineering(UNDONE)