2020.4.17 校内模拟赛游记

研究了 T2 一会儿居然写快速谭炜谭变换去了,结果后来发现这题……

以后得改变做题的模式了。

A

一只马,在 n×mn \times m 的棋盘中能跳到几个点。

对于大于 3×43 \times 4 的棋盘是都可以跳到的,因为在 上/下 和 右边 有 3×33 \times 3 的格子时就可以移动到右边的一个。

剩下的判掉就好了。

B

输入 nn 组数,每组 (li,di)(l_i, d_i), 每次两种操作:

  • 价值加 d1d_1, 去掉最左边的 l1l_1
  • 把最后一个换到开头,其它每个后移

求最大价值

想了一下模拟了几个数据没有什么思路,唯一发现的性质就是它换了个寂寞,反正相对位置永远不变的。

想不到什么思路人又比较浮躁,于是直接大力 exFTT(extand Fast Tanweitan Transform)\texttt{exFTT(extand Fast Tanweitan Transform)}, 就是从头开始随机每个选不选,一波计算后发现期望最多 2n2n 次就可以构成一次操作,而 nn5050 , 所以跑个几十万次没有问题。

然后……一下就被卡掉了。

因为从头开始选第一次选到后面的概率很小。于是就想着又随机每次从前还是从后开始,但是……对于分数来说还是没有任何用处,都是 2020, twt 直接无脑随机都有 3030

代码留作纪念吧,警示以后不要这么干了。

// Powered by exFTT(extand Fast Tanweitan Transform)
#include <cstdio>
#include <cstdlib>
#include <ctime> 
#include <algorithm>
int n, ans, D;
bool vis[55];
struct twt { int l, d; } a[55];
int inc(int &x) {
	x ++;
	if(x > n) x = 1;
}
bool check(int x) {
	for(int j = 1; j <= n; j++, D++) 
		if(!vis[j] && a[j].l <= x) return true;
	return false;
}
int main() {
	srand(time(0));
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].d);
	while(D < 50000000) {
		for(int j = 1; j <= n; j++) vis[j] = 0;
		int now = 1, j = 1, num = n, an = 0;
		while(check(num)) {
			for( ; vis[j] || a[j].l > num; inc(j), D++) ;
			if(rand()%2 == 0) { inc(j); continue; }
			an += a[j].d;
			int tmp = a[j].l;
			for(int cnt = 1; cnt <= tmp; inc(j)) cnt += !vis[j], vis[j] = 1, D++,  num--;
		}
		ans = std::max(ans, an);
	}
	printf("%d", ans);
	return 0;
}

然后是令人震惊的正解:直接 01 背包!

讲一下为什么:

  1. 若选出来的一堆的 ll 大于了 nn,那肯定没救了
  2. 若选出来的一堆 ll 不超过 nn, 那么肯定有一种方案可以选到这些所有,因为总有一个不会和其它接上。

所以这就是一个 01 背包了。

C

不会。

反思

感觉 B 题没做出来和我平时做了一会儿做不出就去看题解的做题习惯有很大的关系,失去了长时间思考的能力,就仿佛碎片化的阅读让人失去了读整本书的能力一样。

整天做些体力劳动远大于脑力劳动的练习是没有意义的,这样子追求所谓的过题量让算法竞赛本身的魅力丧失殆尽,此之谓失其本心。