「Summary」CSP2020总结

前言

这是我第一次参加比较大型的比赛，也是我自认为打得最糟糕的一场比赛了，或许是前期模拟赛几起又几落，导致对自己实力概况不太熟悉，一参考心态就紧张的缘故，打pj时智商完全不在线上。
还是应该静下来好好总结一下吧。

PJ

情况

关于pj，我T1看错题，T2没想出来（直到看完，LYR提醒我才想起一个叫桶排的东西），然后没了信心做T3，T4，从考试开始一直慌到结束。分数难以接受，整个人郁闷到了极点。
考完之后反省，发现还是基础掌握薄弱，学了一些较为高级的算法后，把最根本的东西忘了，有一些知识点囫囵吞枣略过了。在考试的临场发挥上出了大问题，拿到题后整个人就麻了，心态没有调整好，没有提前做题的预判。

Solution

T1

题目看错了，以为必须2的幂连加。这本来就是一个简单的二进制拆分。

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int d[50] = {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824};

int n;
vector<int> ans;

int main() {
	scanf ("%d", &n);
	if (n % 2 == 1) {
		printf ("-1\n");
		return 0;
	}
	int tmp = n;
	for (int i = 30; i >= 1; i--) {
		if (tmp >= d[i]) {
			tmp -= d[i];
			ans.push_back(d[i]);
		}
		if (tmp == 0) break;
	}
	for (int i = 0; i < ans.size(); i++) {
		printf ("%d ", ans[i]);
	}
	return 0;
}

T2

考场上没看出来，忽略了分数的范围，搞忘了桶排。
扫一遍，来一个，桶排加一个，在从600往回找即可。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 5;
const int MAXM = 605;

int len, w, a, t[MAXM];

int main() {
	scanf ("%d %d", &len, &w);
	for (int i = 1; i <= len; i++) {
		scanf ("%d", &a);
		t[a] ++;
		int p = max(1, (i * w / 100));
		int sum = 0, last = 0;
		for (int i = 600; i >= 0; i--) {
			sum += t[i];
			last = i;
			if (sum >= p) {
				break;
			}
		}
		printf ("%d ", last);
	}
	return 0;
} 

T3

正在调。

T4

自认为此题比T3简单。
开始想成了spfa，打完发现死循环了，才知道这个图有环，于是又加了几个参数进去跑，还是不行。之后想出了正解，结果初始化值初始化了n*m内的dp（为了避免用memset），然而调了很久一直不对，耗得时间只剩40min还有两道题，被迫写了个暴力。
考完突然想起DP初始化要初始全局，因为当第一层有可能被第0层更新（其实特判一下也行。
思路比较好想。用dp[i][j][0]表示从上往下走到[i,j]的最大值，dp[i][j][1]表示从下往上走到[i,j]的最大值。从左至右的最大值在这两种状态中也可以更新。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 1e3 + 5;

int n, m;
int a[MAXN][MAXN];
LL dp[MAXN][MAXN][5];

int main() {
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf ("%d", &a[i][j]);
		}
	}
	memset(dp, 0xcf, sizeof(dp));
	dp[1][0][0] = 0;
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++)
			dp[i][j][0] = max(dp[i - 1][j][0] + a[i][j], max(dp[i][j - 1][1] + a[i][j], dp[i][j - 1][0] + a[i][j]));
		for (int i = n; i >= 1; i--) 
			dp[i][j][1] = max(dp[i + 1][j][1] + a[i][j], max(dp[i][j - 1][0] + a[i][j], dp[i][j - 1][1] + a[i][j]));
	}
	printf ("%lld\n", dp[n][m][0]);
	return 0;
}

TG

情况

稍微比PJ好了吧。。。
汲取了PJ崩溃的经验，提前浏览了四道题目并且看好了相关限制（但是最后一题还是忘了拼盘），T2太过于自信，结果用了map直接被卡。

T1，T3，T4

都没打出来。
T1还在调，T3没思路，T4拼盘20pts。

T2

思路很简单，用一个$all$或上所有的$a[i]$,然后依次标记每一个$p$即可。
注意$k<=64$，这种情况下加一个特判就够了。

#include <cstdio>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#define LL unsigned long long
using namespace std;
const int MAXN = 1e6 + 5;
const int MAXK = 1e8 + 5;

LL n, m, c, k, tot, all;
bool vis[MAXK];

int main() {
	scanf ("%llu %llu %llu %llu", &n, &m, &c, &k);
	for (int i = 1; i <= n; i++) {
		LL x;
		scanf ("%llu", &x);
		all |= x;
	}
	for (int i = 1; i <= m; i++) {
		LL q, p;
		scanf ("%llu %llu", &p, &q);
		if (!((1ull<<p) & all)) {
			if (vis[p] == 0) {
				vis[p] = 1;
				tot++;
			}
		} 
	}
	if (k - tot == 64 ) {
		if (n == 0) {
			printf ("18446744073709551616\n");
		} else {
			printf ("%llu\n", (1ull<<63) - n + (1ull<<63));
		}
	} else {
		printf ("%llu\n", (1ull<<(k - tot)) - n);
	}
	return 0;
}

总结

pj打得很是郁闷，但这次打击也给我提示了很多：不能好高骛远，最重要的应该是理解每个基础算法的思想，踏实做好接下来的每一题。
还是回到起跑线吧。