526互联

CSP 2023 S2 游记

发布时间 2023-10-21 23:59:57作者: LittleDrinks

比赛实况

11:49，等地铁，先回家吃饭，等下去大同

13:11，出发，乘车去大同，刚睡了一觉，感觉挺好，头不疼了
还有手表没找到，希望电脑上的时间是准

大概早到了一个小时，还走错门了来着，和同学在考场门口进行一些抽象行为，包括但不限于放加油视频、讨论 WHK、模仿学校里老师说话、膜拜进省队大佬（已 AFO）的照片、敲电子木鱼求 rp……

14:25，监考读考场守则，看了下，电脑时间还算准，晚了一分钟，一进去就没网，没法配置 vsc。

14:28，发文件。

14:33，开题。

14:44，读完一遍题，开始写第二题 \(O(n^2\times n)\) 的暴力，先枚举再用栈检验方案数。

14:54，暴力写完，第一和第二个样例都对了，但第二个样例大概跑了 3 秒多，TLE。

大同的电脑是 win7，不知道为什么感觉跑起来有点卡。还有拿记事本看样例文件竟然不会显示换行，吓我一跳，赶紧换手写板。

15:08，打算开始写 T4 的特殊性质 A，每次贪心选择耗时最大的那一个点。

15:27，特殊性质打爆了，寄。

15:34，T1 猜了个结论，当 \(n=1\) 的时候答案必然为 81。

15:43，才想到，这么小的数据范围，估计枚举就是正解。

16:00，上完厕所，离比赛结束还有 2 个半小时，刚刚 A 题枚举写炸了，现在理下思路重新写。

16:29，T1 写完，用 set 写的，手动取交集，写完手都在抖，没有大一点的样例也不知道对不对。

16:35，糊了一组特别弱的数据，再丢进 linux 里面，编译过了，再改了下文件输入就丢在一边了。

预计得分：100+25+0+0=125。

还剩 2 个小时，开大模拟。

17:30，心态大崩，不想写 T3 了，真的写到胸闷气短，太绝望了。写 T4 去。

17:45，T4，查出来了，特殊性质 A，把所有树长成的时间处理出来之后应该取最大值。写完发现答案大了 1，原来是第一天也能长，把 1 扣掉，拿下 25 分，T4 放掉。

18:20，T3 写崩溃了，放弃了，一分没拿。转头去看 T2，看出来了个 \(O(n^2)\) 的暴力。

18:23，写完，再拿 10 分。

18:25，不写了，万恶的 T3。
预计得分：100+35+0+25=160

18:26，最后再用 Linux 跑了一遍编译，检查了一下 freopen。

18:30，交代码。
出来看到大家都一脸死相，有人说 T4 有线段树的分，但他没拿到……都太强了呜呜呜呜……

20:14，SH 代码发出来了，效率啊。

23:47，洛谷和小图灵只有前两题的数据，100+50，云斗测下来 100+50+0+0，寄。

代码

A

100 分。

#include <bits/stdc++.h>

using namespace std;

const int MAXN=15, MAXI=5;
int n, ans, lck[MAXN], ten[MAXI+5];
set <int> tb[2];

int dis1(int a, int b)
{
	return abs(a-b);
}

int dis2(int a, int b)
{
	if (a > b) { swap(a,b); }
	return abs(10+a-b);
}

void init()
{
	ten[0] = 1;
	ten[1] = 10;
	ten[2] = 100;
	ten[3] = 1000;
	ten[4] = 10000;
	ten[5] = 100000;
}

int main()
{
	freopen("lock.in", "r", stdin);
	freopen("lock.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		lck[i] = 1;
		for (int j = 1; j <= MAXI; ++j) {
			int a;
			cin >> a;
			lck[i] = lck[i] * 10 + a;
		}
	}
	init();
	if (n == 1) {
		cout << 81 << endl; return 0;
	}
	for (int j = 1; j <= MAXI; ++j) {
		int a = lck[1]/ten[j-1]%10;
		for (int k = 1; k <= 9; ++k) {
			tb[1].emplace(lck[1]-a*ten[j-1]+(a+k)%10*ten[j-1]);
			if (j >= 2) {
				int b = lck[1]/ten[j-2]%10;
				tb[1].emplace(
					lck[1]
					- a*ten[j-1] + (a+k)%10*ten[j-1]
					- b*ten[j-2] + (b+k)%10*ten[j-2]
				);
			}
		}
	}
	int num;
	for (int i = 2; i <= n; ++i) {
		tb[i%2].clear();
		for (int j = 1; j <= MAXI; ++j) {
			int a = lck[i]/ten[j-1]%10;
			for (int k = 1; k <= 9; ++k) {
				num = lck[i]-a*ten[j-1]+(a+k)%10*ten[j-1];
				if (tb[(i-1)%2].count(num)) { tb[i%2].emplace(num); }
				if (j >= 2) {
					int b = lck[i]/ten[j-2]%10;
					num = (lck[i]
						- a*ten[j-1] + (a+k)%10*ten[j-1]
						- b*ten[j-2] + (b+k)%10*ten[j-2]
					);
					if (tb[(i-1)%2].count(num)) { tb[i%2].emplace(num); }
				}
			}
		}
	}
	cout << tb[n%2].size() << endl;
	return 0;
}

B

50 分的 \(O(n^2)\) 版本

#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e6+5;
int n;
long long ans;
string s;

int main()
{
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	cin >> n >> s;
	s = " " + s;
	vector <char> stk;
	for (int l = 1; l <= n; ++l) {
		stk.clear();
		stk.push_back(s[l]);
		for (int r = l + 1; r <= n; ++r) {
			stk.push_back(s[r]);
			while ( (stk.size() >= 2) && (stk[stk.size()-1]==stk[stk.size()-2]) ) {
				stk.pop_back();
				stk.pop_back();
			}
			ans += (stk.empty());
		}
	}
	cout << ans << endl;
	return 0;
}

C

心态大崩，不放了

D

只写了特殊性质 A，但貌似写挂了，寄。

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e5+5;
int n;
long long a[MAXN], b[MAXN], c[MAXN];
bool c_all_0=true;
vector <int> G[MAXN];

namespace case_A
{
	struct node {
		int id;
		long long tm;
		bool operator < (const node &x) const {
			return tm < x.tm;
		}
	};
	
	bool inq[MAXN];
	long long t[MAXN], st[MAXN], nt, ans;
	priority_queue <node> q;
	
	void solve()
	{
		for (int i = 1; i <= n; ++i) {
			t[i] = a[i] / b[i];
			t[i] += (b[i]*t[i] < a[i]);
		}
		q.push( {1, t[1]} );
		inq[1] = true;
		while (!q.empty()) {
			node c = q.top();
			st[c.id] = ++nt;
			for (int v: G[c.id]) {
				if (!inq[v]) {
					q.push( {v, t[v]} );
					inq[v] = true;
				}
			}
			q.pop();
		}
		ans = 0;
		for (int i = 1; i <= n; ++i) {
			ans = max(ans, st[i]-1+t[i]);
		}
		cout << ans << endl;
	}
}

int main()
{
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		c_all_0 &= (c[i]==0);
	}
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	if (c_all_0) {
		case_A::solve();
	} else {
		srand(time(nullptr));
		cout << rand() << endl;
	}
	return 0;
}