CSP2019总结

Posted on | In

一个初二OIer的总结~

CSP-J

T1 数字游戏

这道题是真的水题，要不是今年PJ难度降低了不少，不然觉得连做PJD1T1的难度都没有。。。

相信不用怎么讲的了，因为CCF保证输入文件没有任何多余行末空格或多余文件末换行，不用考虑奇怪的情况，比如假设CCF不保证，那么下面的代码就很容易被Hack：

1
2
3
4
5
6
7
8
9
10
#include <cstdio>

signed main(signed argc, char **argv) {
	char ch;
	int tot = 0;
	while (~(ch = std::getchar())) {
		tot += ch - '0';
	}
	return 0;
}

T2 公交换乘

实话说我对这道题究竟该怎么实现纠结了很久……本来想皮一下用std::set的，但是最后还是用了队列实现。。

不知道考场怎么想的，为了遍历队列，我手写了一个长达41行的队列……应该是过了吧

T3 纪念品

成功爆炸……

大致思路是分段乱搞……如果t==1，那当然直接输出m啦，然后其他的点乱打，成功只拿到了t==1的点。

考场上本来应该能想到背包的……

T4 加工零件

考试的时候当然想到了从1开始求最短路的方法，但是苦于不知道怎么处理奇偶的情况，然后在lg上40分……

个人觉得奇偶还挺好想的？

CSP-S

D1T1 格雷码

祖宗我总算见到你了！！！

显然我没有开unsigned long long，但是就算开了unsigned long long也不能保证万无一失，比如这是我考场的代码，就算long long全部改成unsigned long long也无济于事：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void code(const int &n, const long long &m) {
	if (n == 1) {
		std::putchar(m + '0');
		return;
	}
	
	if (m < (1ll << (n - 1))) {
		std::putchar('0');
		code(n - 1, m);
	}
	else {
		std::putchar('1');
		code(n - 1, (1ll << n) - 1ll - m);
	}
	return;
}

为什么呢？因为1ull << 64会爆unsigned long long。

D1T2 括号树

直接打链的情况，调了会之后在lg上75分。

对于每个结点，一路往上走，直到到根结点，然后记得维护前缀和，然后对于i和i的一个祖宗j，如果S[i] > S[j]，那么直接不合法，跳出。否则如果S[i] == S[j]，++ans[i]。

D1T3 树上的数

样例都没过，还想拿分？

在lg上成功爆0，大致讲讲思路吧

时间复杂度$O(n!)$，对于$1\sim n$的每个排列（使用<algorithm>里的std::next_permutation），都计算一遍当前字典序，然后看看最小的是什么。

D2T1 Emiya家今天的饭

直接爆搜。lg上能跑32分，大概拿满爆搜分了吧……

按照烹饪方法枚举。

考场上居然忘记剪枝了，表示崩溃……

D2T2 划分

真的不知道怎么打了。。。随便想了一种解法，看似没有问题，过了样例，然而只拿了8分的高分……

D2T3 树的重心

连暴力都木有，直接一个std::freopen和std::fclose结束了程序。。。

估分

CSP-J 250~290

CSP-S 160~190