Codeforces Round #717 (div.2) 游记
两个“人生第一次”——上蓝,变成 了!以及第一次 了。
不过比赛状态真的是不好,第一题居然要交三次才过,第二题还 FST。但还是开心地庆祝上蓝!
A
英语不好有大问题, "two different elements" 指的是下标不同而不是那个数字不同,影响了一定的做题速度。
不过自己没有想清楚也是一个大的原因,没有考虑到根本不能减的情况。
开局不利,就比较慌。
B
把 个数分成至少两段,使每一段异或和相同。
pretest 有点水啊。不过确实得怪自己没有考虑清楚。
思路是枚举第一段,然后后面验证能不能行。
验证时如果行的就直接断开就会遇到各种问题。一开始没有想到异或和本来就是 的问题,顺利 Wrong Answer on pretest 2。又没有注意到如果是 可以和前面并上,顺利 FST。 然后没注意到一段为 也可以和前面并上,又没有注意到如果前面只是一段就不能并过去,因为至少要两段。
最后居然交了 发才过!
把代码和提交记录放上来作 警示/纪念 吧。
#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
好题!
至少要删去几个数,使数组不能被分成和相等的两份。
至于判断一个数组,那么很好做到,直接背包一遍就可以了。
那么怎么去掉呢?显然若有奇数直接去掉好了,可是没有又怎么去掉?枚举每一个的话万一还需要去掉一个呢?
找一些数据玩一玩,发现最多去掉一个就可以了。证明使用第二类数学归纳法。
- 若存在 ( 是奇数), 那么把它去掉肯定可以,所以若要去掉两个的,肯定不存在这样的 。
- 若 () 都不存在,那么去掉 的肯定可以,因为大家都是 的倍数,而去掉这个再除以二后就不能被 整除了,所以不能存在
- 所有的数都不能存在。
这样就证明了一堆数去掉一个肯定是可以的。
代码很好写,反而这题是我这场比赛最顺利的一道。
#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
写线段树?),要么就另寻他法了。
结果题解真的是倍增。
先处理出每一个开始的断点是在哪儿,然后倍增跳过几段而不是跳过几个数字就好了。
感觉难点在于如何预处理那个第一个断点的问题。
可以先预处理存下每个数的质因数,然后从后往前每一个的质因子的下一个有的取个 就好了。
#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;
}