CSP-S2023 题解

发表于 分类于 阅读次数： Waline：
签到+原+大模拟+典=？

CSP-S2023 游记

密码锁(lock)

\(10^5\) 枚举所有可能答案，然后判断。

代码

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

int n;
int a[13][7], b[7];

bool check(int i) {
	int cnt = 0;
	for(int j = 1; j <= 5; j++) cnt += (a[i][j] != b[j]);
	if(cnt == 1) return true;
	else if(cnt != 2) return false;
	for(int j = 1; j < 5; j++)
		if(a[i][j] != b[j] && a[i][j + 1] != b[j + 1] && (b[j] - a[i][j] + 10) % 10 == (b[j + 1] - a[i][j + 1] + 10) % 10) return true;
	return false;
}
bool check() {
	for(int i = 1; i <= n; i++) if(!check(i)) return false;
	return true;
}

int main() {
	freopen("lock.in", "r", stdin);
	freopen("lock.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) for(int j = 1; j <= 5; j++) scanf("%d", &a[i][j]);
	int ans = 0;
	for(b[1] = 0; b[1] <= 9; b[1]++)
		for(b[2] = 0; b[2] <= 9; b[2]++)
			for(b[3] = 0; b[3] <= 9; b[3]++)
				for(b[4] = 0; b[4] <= 9; b[4]++)
					for(b[5] = 0; b[5] <= 9; b[5]++)
						ans += check();
	printf("%d\n", ans);
	return 0;
}

消消乐(game)

首先发现对于同一个局面会有多个方案，比如 abbaabba 可以是 abbAAbba 也可以是 abbaAbbA （两个 a 匹配，两个 A 匹配）。那么我们钦定只考虑 abbaAbbA。怎么保证这一点呢？我们令 \(r(i)\) 等于最小的 \(j\) 满足 \([i, j]\) 这一段是可以被消除的。那么对于 abbaabba 来说，\(r(1)=4,r(5)=8\)。我们把 \([i, r(i)]\) 叫做 一段。

然后我们令 \(cnt(i)\) 表示从 \(i\) 开始最多往后走多少个段能走到 \(n\)，也就是 \(cnt(i)=cnt(r(i)+1)+1\) 且 \(cnt(n+1)=0\)，那么答案就是所有位置的 \(cnt\) 加起来。

然后考虑怎么算 \(r\)。容易发现 \(r(i)\) 其实等于最小的 \(j\) 使得 \([i+1, j-1]\) 能被消除且 \(s_i=s_j\)，也就是从 \(i+1\) 开始往后一段一段跳，直到某一段结尾的后一个字符等于 \(s_i\)。那么我们对于每个 \(i\) 记 \(nxt(i,c)\) 表示从 \(i\) 开始往后一段一段跳，第一次跳到 \(c\) 时的下标，然后就可以计算 \(r\) 了。有了 \(r\)，\(nxt\) 也是好转移的。

代码

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

typedef long long LL;

const int N = 2e6 + 5;

int n;
char s[N];

int cnt[N], nxt[N][26];

int main() {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	scanf("%d%s", &n, s + 1);
	for(int i = 1; i <= n; i++) s[i] -= 'a';
	for(int i = n - 1; i >= 1; i--) {
		if(s[i + 1] == s[i]) {
			for(int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 2][j];
			if(i + 2 <= n) nxt[i][s[i + 2]] = i + 2;
			cnt[i] = cnt[i + 2] + 1;
//			printf("%d -> %d\n", i, i + 2);
		} else if(nxt[i + 1][s[i]]) {
			int i_ = nxt[i + 1][s[i]];
			for(int j = 0; j < 26; j++) nxt[i][j] = nxt[i_ + 1][j];
			if(i_ + 1 <= n) nxt[i][s[i_ + 1]] = i_ + 1;
			cnt[i] = cnt[i_ + 1] + 1;
//			printf("%d -> %d\n", i, i_ + 1);
		}
	}
	LL ans = 0;
	for(int i = 1; i <= n; i++) ans += cnt[i];
	printf("%lld\n", ans);
	return 0;
}

结构体(struct)

直接模拟即可。

代码

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
#include <bits/stdc++.h>
using std::string;
using std::cin;
using std::cout;

typedef long long LL;

const int N = 100 + 5;

int Q;

struct Type {
	std::vector<std::pair<string, Type *>> m;
	LL size;
	int align;
} buffer[N], *Byte, *Short, *Int, *Long;
int ctype;
Type *nw_type() { ctype++; return &buffer[ctype]; }

std::map<string, Type *> type;
std::vector<std::pair<string, Type *>> vars;

char tmp[21];

inline LL align_to(LL x, int y) { return x % y ? x - x % y + y : x; }

int main() {
	freopen("struct.in", "r", stdin);
	freopen("struct.out", "w", stdout);
	Byte = nw_type(), Short = nw_type(), Int = nw_type(), Long = nw_type();
	Byte->size = Byte->align = 1, Short->size = Short->align = 2, Int->size = Int->align = 4, Long->size = Long->align = 8;
	type["byte"] = Byte, type["short"] = Short, type["int"] = Int, type["long"] = Long;
	cin >> Q;
	while(Q--) {
		int t;
		cin >> t;
		if(t == 1) {
			string name;
			int cnt;
			cin >> name >> cnt;
			Type *now = nw_type();
			type[name] = now;
			while(cnt--) {
				string typname, varname;
				cin >> typname >> varname;
				Type *typ = type[typname];
				now->m.push_back({varname, typ});
				now->size = align_to(now->size, typ->align) + typ->size;
				now->align = std::max(now->align, typ->align);
			}
			now->size = align_to(now->size, now->align);
			std::cout << now->size << ' ' << now->align << '\n';
		} else if(t == 2) {
			string typname, varname;
			cin >> typname >> varname;
			LL addr = 0;
			for(int i = 0; i < (int)vars.size(); i++) addr = align_to(addr, vars[i].second->align), addr += vars[i].second->size;
			addr = align_to(addr, type[typname]->align);
			std::cout << addr << '\n';
			vars.push_back({varname, type[typname]});
		} else if(t == 3) {
			LL addr = 0;
			int now = 0, nxtnow = 0;
			string buf;
			cin >> buf;
			sscanf(buf.c_str() + now, "%[a-z]%n", tmp, &nxtnow), now += nxtnow;
			string varname = tmp;
			Type *tp;
			for(int i = 0; i < (int)vars.size(); i++) {
				addr = align_to(addr, vars[i].second->align);
				if(vars[i].first != varname) addr += vars[i].second->size;
				else { tp = vars[i].second; break; }
			}
			while(sscanf(buf.c_str() + now, ".%[a-z]%n", tmp, &nxtnow) == 1) {
				now += nxtnow;
				addr = align_to(addr, tp->align);
				string name = tmp;
				for(int i = 0; i < (int)tp->m.size(); i++) {
					addr = align_to(addr, tp->m[i].second->align);
					if(tp->m[i].first != name) addr += tp->m[i].second->size;
					else { tp = tp->m[i].second; break; }
				}
			}
			std::cout << addr << '\n';
		} else {
			LL addr, now_addr = 0;
			bool flag = true;
			string ans;
			cin >> addr;
			Type *now = 0;
			for(int i = 0; i < (int)vars.size(); i++) {
				now_addr = align_to(now_addr, vars[i].second->align);
				if(addr < now_addr) { flag = false; break; }
				if(addr >= now_addr + vars[i].second->size) now_addr += vars[i].second->size;
				else { ans += vars[i].first; now = vars[i].second; break; }
			}
			if(!now) flag = false;
			while(flag && !now->m.empty()) {
				now_addr = align_to(now_addr, now->align);
				if(addr < now_addr) { flag = false; break; }
				bool fl = false;
				for(int i = 0; i < (int)now->m.size(); i++) {
					now_addr = align_to(now_addr, now->m[i].second->align);
					if(addr < now_addr) { flag = false; break; }
					if(addr >= now_addr + now->m[i].second->size) now_addr += now->m[i].second->size;
					else { ans += "." + now->m[i].first; now = now->m[i].second; fl = true; break; }
				}
				if(!fl) { flag = false; break; }
			}
			if(flag) cout << ans << '\n';
			else cout << "ERR" << '\n';
		}
	}
	return 0;
}

种树(tree)

首先二分答案，那么我们要判断答案是否大于等于 \(m\)。首先对于每个点，我们可以计算出它最晚被种下去的时间 \(r_i\)，这个可以二分（用 \(O(1)\) 似乎会被卡精度？）

先考虑没有“必须先种父亲再种儿子”的限制。我们令 \(s_i\) 表示有多少个 \(r_j\) 小于等于 \(i\)，那么我们只需要判断 \(s_i\le i\)。正确性显然。（其实这个也可以贪心做，本质上是一样的）

现在考虑有这个限制怎么做。一个显然的事情是 \(r_u<r_v\)（\(v\) 是 \(u\) 的儿子），所以我们用这个限制来更新 \(r\)。然后就不需要考虑这个限制，直接按照上面的做法去做就好了。

为什么呢？令 \(t_i\) 表示一个合法方案中 \(i\) 实际上是第几天被种下去的，那么显然 \(t\) 互不相同且 \(t_i\le r_i\)。接下来我们只需要证明能找到一个 \(t'_i\) 满足“先种父亲再种儿子”的限制就行了。考虑调整法，如果对于一对拥有祖先关系的 \(u,v\)，\(t_u>t_v\)，那么我们有 \(t_v<t_u\le r_u<r_v\)，那么我们可以将 \(t_u,t_v\) 交换，这样也是合法的。所以这个结论是对的。

代码

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>

typedef long long LL;

const int N = 1e5 + 5;

int n;
LL a[N], qk[N], qb[N];
struct Edge { int to, nxt; } edge[N << 1];
int head[N];
void add_edge(int u, int v) { static int k = 1; edge[k] = (Edge){v, head[u]}, head[u] = k++; }

int bd[N], cnt[N];
void dfs(int u, int fa) {
	for(int i = head[u]; i; i = edge[i].nxt) if(edge[i].to != fa) {
		int v = edge[i].to;
		dfs(v, u);
		bd[u] = std::min(bd[u], bd[v] - 1);
	}
}
inline LL div_ceil(LL x, LL y) { if(y < 0) x = -x, y = -y; return x < 0 ? x / y : (x + y - 1) / y; }
inline LL div_floor(LL x, LL y) { if(y < 0) x = -x, y = -y; return x < 0 ? (x - y + 1) / y : x / y; }
inline bool calc(LL k, LL b, LL x, LL m, LL target) {
	if(k == 0) return (m - x + 1) * b < target;
	else if(k > 0) {
		LL y = div_ceil(1 - b, k); __int128_t ret = 0;
		if(m >= y) ret += (m - std::max(x, y) + 1) * b + (__int128_t)(m + std::max(x, y)) * (m - std::max(x, y) + 1) / 2 * k;
		if(x < y) ret += std::min(m + 1, y) - x;
		return ret < target;
	} else {
		LL y = div_floor(1 - b, k); __int128_t ret = 0;
		if(x <= y) ret += (std::min(m, y) - x + 1) * b + (__int128_t)(std::min(m, y) + x) * (std::min(m, y) - x + 1) / 2 * k;
		if(m > y) ret += m - std::max(x - 1, y);
		return ret < target;
	}
}
bool check(int m) {
//	printf("check %d\n", m);
	for(int i = 1; i <= n; i++) {
		int l = 1, r = n + 1;
		while(l < r) {
			int mid = (l + r) >> 1;
			if(calc(qk[i], qb[i], mid, m, a[i])) r = mid;
			else l = mid + 1;
		}
		bd[i] = l - 1;
//		printf("bd[%d] = %d\n", i, bd[i]);
	}
	dfs(1, 0);
	for(int i = 1; i <= n; i++) if(bd[i] < 1) return false;
//	for(int i = 1; i <= n; i++) printf("bd[%d] = %d\n", i, bd[i]);
	for(int i = 1; i <= n; i++) cnt[i] = 0;
	for(int i = 1; i <= n; i++) cnt[bd[i]]++;
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		sum += cnt[i];
		if(sum > i) return false;
	}
	return true;
}

int main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lld%lld%lld", &a[i], &qb[i], &qk[i]);
	for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v), add_edge(v, u); }
//	for(int i = 1; i <= n; i++) if(calc(qk[i], qb[i], 1, 1000000000, a[i])) { printf("%lld %lld\n", qk[i], qb[i]); return 0; }
	int l = n, r = 1e9;
	while(l < r) {
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
	return 0;
}