Codeforces Round #685 (Div. 2)E2. Bitwise Queries (Hard Version)题解(数学竞赛/组合构造题)
2021/7/15 23:38:53
本文主要是介绍Codeforces Round #685 (Div. 2)E2. Bitwise Queries (Hard Version)题解(数学竞赛/组合构造题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:
https://codeforces.com/contest/1451/problem/E2
大意:这是一个人机交互题。一共有N个[0, N-1]的整数,其中N是2的幂次。允许每次人指定其中两个数字与AND、OR、XOR其中一种运算,查询其计算后得到的结果。最多查询N + 1次,复现出整个数组每个数字的值。
思路:
记我们的原始的数组为A数组。
定理一:
对于非负整数x与y,有:
x + y = (x xor y) + 2 * ( x and y)
证明:按照比特位,按位计算。
1 xor 1 + (1 and 1) * 2 = 2 = 1 + 1
1 xor 0 + (1 and 0) * 2 = 1 = 1 + 0
0 xor 0 + (0 and 0) * 2 = 0 = 0 + 0
按照二进制每一位加起来,可证。
定理二:
只需要N - 1次xor查询,即可得到任何两个数字的xor结果。
证明:
已知:A[1] xor A[1] = 0 (记为v1)
记录:
A[1] xor A[2] = v2;
A[1] xor A[3] = v3;
...;
A[1] xor A[n] = vn;
那么任意两个数字A[x] xor A[y] = A[x] xor (A[1] xor A[1]) xor A[y] = (A[x] xor A[1]) xor (A[y] xor A[1]) = vx xor vy。
那么我们可以设计方案如下:
首先先查询一遍v2, v3, ..., vn。
1、如果存在1<=i<=j<=n,vi = vj
那么vi xor A[1] = vj xor A[1]
有A[i] = A[j],通过A[i] And A[j] = A[i]算出A[i]
从而可以推出其他所有的数字了。
2、如果不存在vi = vj,那么因为N是2的幂次,v的取值一定在[0, n - 1]中中间都存在。
那么记下vx = n - 1,二进制下全为1
那么A[1]与A[x]一定每一位都不相同,A[1] and A[x] = 0。
那么只需要再任意指定一个其他的数字y,查询A[1] and A[y], A[x] and A[y]的值。
根据定理一,我们可以得到,
A[1] + A[x] = vx
A[x] + A[y] = (A[y] and A[x]) + (vx xor vy)
A[1] + A[y] = (A[y] and A[1]) + vy
解三元一次方程即可。得到其中任意一个值,推出其他所有数值就行了。
代码(cf服务器崩了,还未跑出结果,下面代码暂不支持直接复制粘贴保证通过):
#include "bits/stdc++.h" using namespace std; const int32_t maxN = (1 << 16) + 10; int32_t n; int32_t xorVal[maxN]; int32_t ans[maxN]; vector<int32_t> pos[maxN]; int32_t sendQuery(string s, int32_t i, int32_t j) { cout << s << " " << i << " " << j << endl; cout.flush(); int32_t ret; cin >> ret; if (ret == -1) { exit(0); }; return ret; } int main() { cin >> n; pos[0].push_back(1); for (int32_t i = 2; i <= n; i++) { int32_t ret = sendQuery("XOR", 1, i); xorVal[i] = ret; pos[ret].push_back(i); } int32_t a = 1, b, c; int32_t same = -1; for (int32_t i = 0; i < n; i++) { if (pos[i].size() > 1) { b = pos[i][0]; c = pos[i][1]; same = i; } } if (same == -1) { b = pos[n - 1][0]; if (b == n) { c = 2; } else { c = b + 1; } int32_t xab = xorVal[b]; int32_t xac = xorVal[c]; int32_t xbc = xorVal[b] ^ xorVal[c]; int32_t andac = sendQuery("AND", a, c); int32_t andbc = sendQuery("AND", b, c); int32_t ab = xab; int32_t ac = xac + 2 * andac; int32_t bc = xbc + 2 * andbc; ans[1] = (ab + ac - bc) / 2; } else { ans[b] = sendQuery("AND", b, c); ans[1] = xorVal[b] ^ ans[b]; } for (int i = 2; i <= n; i++) { ans[i] = ans[1] ^ xorVal[i]; } cout << "! "; for (int i = 1; i <= n; i++) { cout << ans[i] << " "; } cout << endl; cout.flush(); return 0; }
这篇关于Codeforces Round #685 (Div. 2)E2. Bitwise Queries (Hard Version)题解(数学竞赛/组合构造题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02在 Objective-C 中strong 和 retain有什么区别-icode9专业技术文章分享
- 2024-11-02NSString 中的 hasPrefix 有什么作用-icode9专业技术文章分享
- 2024-11-02在 C 和 Objective-C 中inline的用法是什么-icode9专业技术文章分享
- 2024-11-02文件掩码什么意思?-icode9专业技术文章分享
- 2024-11-02在 Git 提交之前运行 composer cs-fix 命令怎么实现-icode9专业技术文章分享
- 2024-11-02为 Composer 的 cs-fix 命令指定一个目录怎么实现-icode9专业技术文章分享
- 2024-11-02微信公众号开发中怎么获取用户的 unionid-icode9专业技术文章分享
- 2024-11-01lip-sync公司指南:一文读懂主要玩家和技术
- 2024-11-01Anthropic的新RAG方法——提升大型语言模型在特定领域的表现
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享