昨晚 CF D
2026-09-27 09:38:08
发布于：广东
27阅读
0回复
0点赞
还能这种人类智慧的/xk
这么小，感觉有说法。
枚举一下 16 以内 3 的倍数的二进制位：
0000
0011
0110
1001
1100
1111
会发现全都有偶数个 1，而且很完全（？。
显然奇数个 1 的不可能通过操作变为 3 的倍数。
然后我们猜测任意二进制位两个偶数个 1 的数异或后一定可以变成 3 的倍数。所以答案为二进制位数为 1 的 个数。
然后就做完了（笑）。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <int> a(n + 5);
int ans = 0;
for(int i = 1; i <= n; i++){
std::cin >> a[i];
ans += (__builtin_popcount(a[i]) % 2 == 0);
}
std::cout << ans << ' ';
while(m--){
int idx, val;
std::cin >> idx >> val;
ans -= (__builtin_popcount(a[idx]) % 2 == 0);
a[idx] = val;
ans += (__builtin_popcount(a[idx]) % 2 == 0);
std::cout << ans << ' ';
}
std::cout << '\n';
}
}
时间复杂度：。
全部评论 6
当一切归于寂静 cjdst 所处的机房也成为一片废墟，自烟尘中踉踉跄跄走出的是已经被前三题卡了 43min 同时身体各处都破败不堪的 cjdst，似乎是来自战场的嘲讽就连他原先的排名也在此刻直接倒塌
而作为他对手的 Div2 也开始了颇具嘲讽意味的「战斗复盘」
Div2：「不指定对象，连我自己都会被卷进去的无限制的「C 题」……」「但是…好像卡的程度不太一样呢」「看来是不是自己的题影响很大啊」「不过…结果好就行了吧」「即兴创作的远距离操作「m-k+1」」「好像完成的还不错？」「这还是我第一次出这种题呢」
「也就是说……」
「没错 是 Div2 赢了」
下一话 靠北1周前 来自 广东
0
有帮助，赞一个