2022-2023 ICPC Southern and Volga Russian Regional

比赛地址 ：Codeforces Contest 1765

待补：CGIJ

A - Access Levels

定义 \(S_i\) 为可以看第 \(i\) 个文档的人的集合，如果 \(S_i\subseteq S_j\) ，那么 \(i\) 和 \(j\) 可以放到一组。

最小链覆盖，转换成二分图匹配，然后按照链的顺序依次构造即可。注意需要去重（或 \(S\) 相同的定序）。

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
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=500;

int n,m,K,ID[maxn+5],val[maxn+5],ans[maxn+5][maxn+5];
char pic[maxn+5][maxn+5];
vector<int> e[maxn+5];
int ti,vis[maxn+5],who[maxn+5];

#define ID(x,y) (((x)<<1)-(y))
bool check(int i,int j){
	bool fl=true;
	for (int k=1;k<=n;k++) if (pic[k][i]!=pic[k][j]) {fl=false;break;}
	if (fl) return i<j;
	for (int k=1;k<=n;k++) if (pic[k][i]<pic[k][j]) return false;
	return true;
}
bool Find(int x){
	if (vis[x]==ti) return false;
	vis[x]=ti;
	for (auto y:e[x])
		if (!who[y] || Find(who[y]))
			{who[y]=x;return true;}
	return false;
}
void DFS(int i){
	ID[i]=ID[0];val[i]=++val[0];
	if (who[i]){
		for (int j=1;j<=n;j++)
			if (pic[j][i]>pic[j][who[i]])
				ans[j][ID[0]]=val[i];
		DFS(who[i]);
	} else {
		for (int j=1;j<=n;j++)
			if (pic[j][i]=='1')
				ans[j][ID[0]]=val[i];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%s",pic[i]+1);
	for (int i=1;i<=m;i++)
		for (int j=1;j<=m;j++)
			if (check(i,j)) e[j].push_back(i);
	K=m;
	for (int i=1;i<=m;i++) ti++,K-=Find(i);
	ti++;
	for (int i=1;i<=m;i++) vis[who[i]]=ti;
	printf("%d\n",K);
	for (int i=1;i<=n;i++) for (int j=1;j<=K;j++) ans[i][j]=1;
	for (int i=1;i<=m;i++)
		if (vis[i]<ti) ID[0]++,val[0]=1,DFS(i);
	for (int i=1;i<=m;i++) printf("%d",ID[i]),i<m?putchar(' '):puts("");
	for (int i=1;i<=m;i++) printf("%d",val[i]),i<m?putchar(' '):puts("");
	for (int i=1;i<=n;i++)
		for (int j=1;j<=K;j++)
			printf("%d",ans[i][j]),j<K?putchar(' '):puts("");
	return 0;
}

B - Broken Keyboard

签到。

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
#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 1007

char s[N];

inline void work() {
	int n = rd();
	scanf("%s", s + 1);
	for (int t = 1, i = 1; i <= n; ++t) {
		if (t & 1) ++i;
		else {
			if (s[i] != s[i + 1]) {puts("NO"); return;}
			i += 2;
		}
	}
	puts("YES");
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

*C - Card Guessing

D - Watch the Videos

有 \(n\) 个 \(a_i\) ，总价格是 \(\sum (a_i+1)\) ，将他们排序，如果相邻的两个 \(a_i+a_j\le m\) ，答案减少 \(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
#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 200007

int a[N];

inline void work() {
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) a[i] = rd();
	sort(a + 1, a + 1 + n);
	ll ans = 0;
	int l = 1, r = n;
	for (; l < r; ++l) {
		while (a[r] + a[l] > m && r > l) {ans += a[r] + 1; --r;}
		if (r > l) ans += a[r--];
		else break;
		ans += a[l] + 1;
		while (a[r] + a[l] > m && r > l) {ans += a[r] + 1; --r;}
		if (r > l) --ans;
		else {++l; break;}
	}
	if (l <= r) ans += a[l] + 1;
	printf("%lld\n", ans);
}

int main() {
	work();
	return 0;
}

E - Exchange

签到。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
using namespace std;

int te,A,B,C;

int main(){
	for (scanf("%d",&te);te;te--){
		scanf("%d%d%d",&A,&B,&C);
		if (B<=C) printf("%d\n",(A+B-1)/B);
		else puts("1");
	}
	return 0;
}

*F - Chemistry Lab

假设已经选好了方案，那么按照 \((x_i,c_i)\) 建立凸包，想要兑出最贵的百分比为 \(x\) 的药水，一定取在上凸壳上。

由于均匀分布进行随机，因此上凸壳和 \(x\) 轴夹住的区域面积再 \(\times k\) 就是答案，dp 上凸壳即可。

将点按照 \(x\) 从小到大排序，分段算贡献（梯形面积），注意第一次选取特殊，只有买的代价，没有收益。

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

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 5007

struct node {double x, w, c;} sol[N];

double f[N], ans;

int main() {
    int n = rd(), k = rd();
    for (int i = 1; i <= n; ++i) {sol[i].x = rd(); sol[i].w = rd(); sol[i].c = rd();}
    sort(sol + 1, sol + 1 + n, [&](const node &a, const node &b){return a.x < b.x;});
    for (int i = 1; i <= n; ++i) {
        f[i] = -sol[i].w; // the first one
        for (int j = 1; j < i; ++j) // the previous one is j
            f[i] = max(f[i], f[j] + (sol[i].c + sol[j].c) * (sol[i].x - sol[j].x) * k / 200.0 - sol[i].w);
        ans = max(ans, f[i]);
    }
    printf("%.15lf\n", ans);
    return 0;
}

*G - Guess the String

*H - Hospital Queue

将 \(n\) 个人排队，第 \(i\) 个人一定要站在前 \(p_i\) 个位置，还有若干限制形如 \(a_i\) 站在 \(b_i\) 之前。

现在对于每个人询问，如果只要求其他人位置合法，这个人能站到最靠前的位置是哪里。保证存在一个合法方案。

先考虑如何求出一个合法方案：用堆代替队列进行拓扑排序，\(p_i\) 小的优先。

但对于每个人求最优方案时，很难想办法确定 \(i\) 的优先级。因此考虑从后往前放。

建图 \(b_i\to a_i\) ，然后用堆代替队列进行拓扑排序，\(p_i\) 大的优先，从后往前放。

对于询问第 \(i\) 个人，考虑强制不让 \(i\) 进队，则某个位置别人都放不了的时候就必须放 \(i\) 了，复杂度 \(O(n^2\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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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 2007

int deg[N], Deg[N], p[N];

vector<int> e[N];

priority_queue<pii> q;

int main() {
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) p[i] = rd();
	for (int i = 1; i <= m; ++i) {
		int a = rd(), b = rd();
		++Deg[a]; e[b].push_back(a);
	}
	for (int i = 1; i <= n; ++i) {
		while (!q.empty()) q.pop();
		for (int j = 1; j <= n; ++j) {
			deg[j] = Deg[j]; 
			if (!deg[j] && j != i) q.push({p[j], j});
		}
		int res = n;
		while (!q.empty()) {
			int u = q.top().second; q.pop();
			if (p[u] < res) break;
			--res;
			for (auto v : e[u]) {
				--deg[v];
				if (!deg[v] && v != i) q.push({p[v], v});
			}
		}
		printf("%d ", res);
	}

	return 0;
}

*I - Infinite Chess

*J - Hero to Zero

K - Torus Path

手玩一下发现路径一定会漏掉一个副对角线上的格子，且可以做到只漏掉任意一个，答案就是全部的和减去副对角线最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200;

int n;LL ans;

int main(){
	scanf("%d",&n);
	int MIN=2e9;
	for (int i=1;i<=n;i++)
		for (int j=1,x;j<=n;j++){
			scanf("%d",&x);
			ans+=x;
			if (i+j==n+1) MIN=min(MIN,x);
		}
	printf("%lld\n",ans-MIN);
	return 0;
}

L - Project Manager

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

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 200007

inline int trans() {
	static char s[20];
	scanf("%s", s + 1);
	if (s[1] == 'M') return 0;
	if (s[1] == 'T' && s[2] == 'u') return 1;
	if (s[1] == 'W') return 2;
	if (s[1] == 'T' && s[2] == 'h') return 3;
	if (s[1] == 'F') return 4;
	return (s[2] == 'a' ? 5 : 6);
}

queue<int> holiday, order[N];

vector<int> workday[N];

set<int> s[7], add[7], del[7];

priority_queue<int, vector<int>, greater<int> > work[N];

vector<pii> addwork;

int ans[N];

int main() {
	int n = rd(), m = rd(), k = rd();
	for (int i = 1; i <= n; ++i) 
		for (int t = rd(); t; --t) workday[i].push_back(trans());
	for (int i = 1; i <= m; ++i) holiday.push(rd());
	for (int i = 1; i <= k; ++i) {
		for (int t = rd(); t; --t) order[i].push(rd());
		int u = order[i].front(); order[i].pop();
		work[u].push(i);
		for (auto d : workday[u]) s[d].insert(u);
	}
	for (int i = 0, cnt = 1, K = k; K; ++cnt, i = (i == 6 ? 0 : i + 1)) {
		if (!holiday.empty() && cnt == holiday.front()) {holiday.pop(); continue;}
		addwork.clear();
		for (int j = 0; j < 7; ++j) {add[j].clear(); del[j].clear();}
		for (auto x : s[i]) {
			int id = work[x].top(); work[x].pop();
			if (work[x].empty()) for (auto d : workday[x]) del[d].insert(x);
			if (order[id].empty()) {--K; ans[id] = cnt;}
			else {
				int nxt = order[id].front(); order[id].pop();
				addwork.push_back(make_pair(nxt, id));
				for (auto d : workday[nxt]) add[d].insert(nxt);
			}
		}
		for (int j = 0; j < 7; ++j) for (auto x : del[j]) s[j].erase(x);
		for (int j = 0; j < 7; ++j) for (auto x : add[j]) s[j].insert(x);
		for (auto [x, id] : addwork) work[x].push(id);
	}
	for (int i = 1; i <= k; ++i) printf("%d ", ans[i]);
	return 0;
}

M - Minimum LCM

给定 \(n\) ，找一对 \(a+b=n\) ，最小化 \(\text{lcm}(a, b)\)

猜测 \(a\) 是 \(b\) 的倍数时最优，所以检查 \(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
#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 1007

char s[N];

inline void work() {
	int n = rd();
	int ans = 1e9;
	int lim = sqrt(n);
	for (int i = 1; i <= lim; ++i) 
		if (n % i == 0) {
			if (n / i > 1) ans = min(ans, i * (n / i - 1));
			if (i > 1) ans = min(ans, (n / i) * (i - 1));
		}
	printf("%d %d\n", ans, n - ans);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

N - Number Reduction

一个很长的数 \(x\)（保证以非 \(0\) 开头），删掉恰好 \(k\ (k< \lfloor \log_{10} x\rfloor)\) 位，使得剩下的数值最小，且没有前导零。

如果没有 \(0\) 就是一个常考面试题，从前往后扫，遇到 \(x_i>x_{i+1}\) 即前面的数位比后面大，就把前面的删掉即可。

但是 \(0\) 的数位一定不能删吗？形如 \(x000y....\) 的数字，如果 \(x>y\) ，且 \(k\) 足够的时候，是应该把前缀 \(x000\) 删掉的。

所以每次当前位置非 \(0\) 且前一个位置是 \(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
#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 500007
#define pb push_back

char s[N];

deque<int> a;

inline void work() {
	a.clear();
	scanf("%s", s + 1); int n = strlen(s + 1);
	int k = rd();
	a.pb(s[1] - '0');
	for (int i = 2; i <= n; ++i) {
		int x = s[i] - '0';
		if (!k) {a.pb(x); continue;}
		if (x) {
			while (!a.empty() && k && a.back() > x) {a.pop_back(); --k;}
			if (!a.empty() && a.back() == 0 && k >= a.size() && x < a.front()) {k -= a.size(); a.clear();}
			a.push_back(x);
		} else {
			while (a.size() > 1 && k && a.back() > 0) {a.pop_back(); --k;}
			a.push_back(x);
		}
	}
	for (; k; --k) a.pop_back();
	for (auto x : a) printf("%d", x); puts("");
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}