Codeforces Round #717 (div.2) 游记

两个“人生第一次”——上蓝,变成 Acfboy\color{blue}\textsf{Acfboy} 了!以及第一次 FST\color{red}\textsf{FST} 了。

不过比赛状态真的是不好,第一题居然要交三次才过,第二题还 FST。但还是开心地庆祝上蓝!

A

英语不好有大问题, "two different elements" 指的是下标不同而不是那个数字不同,影响了一定的做题速度。

不过自己没有想清楚也是一个大的原因,没有考虑到根本不能减的情况。

开局不利,就比较慌。

B

nn 个数分成至少两段,使每一段异或和相同。

pretest 有点水啊。不过确实得怪自己没有考虑清楚。

思路是枚举第一段,然后后面验证能不能行。

验证时如果行的就直接断开就会遇到各种问题。一开始没有想到异或和本来就是 00 的问题,顺利 Wrong Answer on pretest 2。又没有注意到如果是 00 可以和前面并上,顺利 FST。 然后没注意到一段为 00 也可以和前面并上,又没有注意到如果前面只是一段就不能并过去,因为至少要两段。

最后居然交了 66 发才过!

把代码和提交记录放上来作 警示/纪念 吧。

#include <cstdio>
const int N = 2005;
int T, n, a[N];
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        int fi = 0, ne = 0;
        bool flag = 0;
        for(int i = 1; i < n; i++) {
            fi ^= a[i];
            ne = 0;
            bool twt = 0, did = 0;
            for(int j = i+1; j <= n; j++) {
                ne ^= a[j];
                if(ne == fi || ne == 0 && did) ne = 0, twt = 1, did = 1;
                else twt = 0;
                // printf("*%d %d\n", ne, twt);
            }
            if(twt) { flag = 1; /*printf("%d %d %d\n", i, fi, ne);*/ break;}
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

C

好题!

至少要删去几个数,使数组不能被分成和相等的两份。

至于判断一个数组,那么很好做到,直接背包一遍就可以了。

那么怎么去掉呢?显然若有奇数直接去掉好了,可是没有又怎么去掉?枚举每一个的话万一还需要去掉一个呢?

找一些数据玩一玩,发现最多去掉一个就可以了。证明使用第二类数学归纳法。

  1. 若存在 ai=20xa_i = 2^0x (xx 是奇数), 那么把它去掉肯定可以,所以若要去掉两个的,肯定不存在这样的 aia_i
  2. ai=2kxa_i = 2^kx (k<mk < m) 都不存在,那么去掉 ai=2mxa_i = 2^mx 的肯定可以,因为大家都是 2m2^m 的倍数,而去掉这个再除以二后就不能被 2m2^m 整除了,所以不能存在 ai=2mxa_i = 2^mx
  3. 所有的数都不能存在。

这样就证明了一堆数去掉一个肯定是可以的。

代码很好写,反而这题是我这场比赛最顺利的一道。

#include <cstdio>
#include <algorithm>
const int N = 105;
int n, a[N], f[200005], v;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), v += a[i];
    for(int i = 1; i <= n; i++)
        for(int j = v; j >= a[i]; j--)
            f[j] = std::max(f[j], f[j-a[i]] + a[i]);
    if(v % 2 == 1 || f[v/2] != v/2) {
        puts("0");
        return 0;
    }
    for(int i = 1; i <= n; i++) 
        if((v-a[i]) % 2 == 1 || f[(v-a[i])/2] != (v-a[i])/2) {
            printf("1\n%d", i);
            return 0;
        }
    return 0;
}

D

赛场上想着倍增但没想出个方案来,本来若积小一点就可以用线段树大力维护的,但这样的数据范围要么暴力出奇迹,高精去(用 Python 写线段树?),要么就另寻他法了。

结果题解真的是倍增。

先处理出每一个开始的断点是在哪儿,然后倍增跳过几段而不是跳过几个数字就好了。

感觉难点在于如何预处理那个第一个断点的问题。

可以先预处理存下每个数的质因数,然后从后往前每一个的质因子的下一个有的取个 min\min 就好了。

#include <cstdio>
#include <vector>
const int N = 100005;
int n, q, a[N], f[N][25], ans, l, r, next[N];
std::vector<int> p[N];
int main() {
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 2; i < N; i++) 
		if(p[i].empty()) {
			next[i] = n+1;
			for(int j = 1; i*j < N; j++)
				p[i*j].push_back(i);
		}
		
	f[n+1][0] = n+1;
	for(int i = n; i >= 1; i--) {
		f[i][0] = f[i+1][0];
		for(int j = 0; j < (signed)p[a[i]].size(); j++) {
			f[i][0] = std::min(f[i][0], next[p[a[i]][j]]);
			next[p[a[i]][j]] = i;
		}
	}
	for(int j = 1; j <= 20; j++)
		for(int i = 1; i <= n+1; i++)
			f[i][j] = f[f[i][j-1]][j-1];
	while(q--) {
		scanf("%d%d", &l, &r);
		ans = 0;
		for(int i = 19; i >= 0; i--)
			if(f[l][i] <= r) {
				ans += (1 << i);
				l = f[l][i];
			} 
		printf("%d\n", ans+1);
	}
	return 0;
}