当前位置：首页 > ds >正文

【数论】P10558 [ICPC 2024 Xi‘an I] XOR Game|普及+

ds 2025/9/1 12:43:05

本文涉及知识点

数论：质数、最大公约数、菲蜀定理

P10558 [ICPC 2024 Xi’an I] XOR Game

题目描述

Alice 和 Bob 正在进行一场游戏。

在他们面前有一个多重集 ${a_i\}$ ，其中包含非负整数，还有一个整数 $x$ 。在游戏开始前， $a$ 中的每个数字都是 $0$ 或 $2i(0≤i<k)2^i(0\le i<k)$ 。

这是一场回合制游戏，Alice 先开始。在一个人的回合中，他或她将从 $a$ 中选择一个整数。设这个数为 $p$ 。然后这个人可以选择是否执行 $x←x⊕px\gets x\oplus p$ ，接着从 $a$ 中移除 $p$ 。这里，操作 $⊕\oplus$ 表示按位异或。

Alice 想让 $x$ 尽可能大，而 Bob 想让 $x$ 尽可能小。

你是一个旁观者，想知道最终的 $x$ 值。然而， $a$ 的大小是一个巨大的数字。形式上，对于所有 $0≤i<k0\le i<k$ ，有 $b_i$ 个数在 $a$ 中的值为 $2^i$ ，并且有 $z$ 个数的值为 $0$ 。但你仍然想挑战这个不可能的问题。

如果 Alice 和 Bob 足够聪明，请输出最终的 $x$ 值。

输入格式

第一行包含两个整数 $k,z(1≤k≤105,0≤z≤109)k,z(1\le k\le10^5,0\le z\le 10^9)$ 。

下一行包含 $k$ 个整数，第 $i$ 个整数是 $bi−1(0≤bi−1≤109)b_{i-1}(0\le b_{i-1}\le10^9)$ 。

输出格式

以二进制格式输出答案。注意，即使这个数字有前导 $0$ ，你也应该从高位到低位输出恰好 $k$ 位。

输入输出样例 #1

输入 #1

1 0
3

输出 #1

输入输出样例 #2

输入 #2

2 0
2 1

输出 #2

输入输出样例 #3

输入 #3

2 0
2 2

输出 #3

说明/提示

（由 ChatGPT 4o 翻译）

数论

性质一：如果 $2^i不存在$ ，则此位一定是0。
性质二：如果 $2^i$ 只有一个，当前方必须选。
想让x最大：
如果x第i位位1，扔掉；否则异或。
想让x最小：
操作相反。
性质三：如果 $2^i$ 只有2个，则不能选。选了不利于于己方，对方马上选就是性质二。
性质四：如果 $2^i$ 数量>2，则选择无坏处。

实现

只有一个的数，x包括最大值（第0大)，不包括次大值，包括第2大，不包括第3大。
即包括 $第 i 大$ ，i是偶数;不包括i是奇数。
令 $\sum (其它数-2)+一个数的数量$ ，如果y是偶数，x不包括这些数；否则包括。
v1记录 $b [i] == 1$ 的所有下标,v2记录 $\ge 2$ 的下标。
v1 升序，ans[v1[i]] =1，i是偶数。
如果y是奇数，ans[v2[i]]=1。
注意：z不能忽略，可以改变当前行动放。
即 $y=∑(b)+zy=\sum(b)+z$

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5,T6,T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class Solution {
public:string  Ans(const vector<int>& bs, int z) {const int K = bs.size();vector<int> v1, v2;long long y = 0;for (int i = K - 1; i >= 0; i--) {if (1 == bs[i]) {v1.emplace_back(i);}else if (bs[i] > 1) {v2.emplace_back(i);}y += bs[i];}vector<int> ans(K);for (int i = 0; i < v1.size(); i += 2) {ans[v1[i]] = 1;}if ((y + z) & 1) {for (const auto& i : v2) {ans[i] = 1;}}string str;for (auto it = ans.rbegin(); it != ans.rend(); ++it) {str += ('0' + *it);}return str;}
};
int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;int n, z;cin >> n >> z;auto bs = Read<int>(n);
#ifdef _DEBUG	//printf("N=%d", N);//Out(not1, ",not1=");//Out(ope, ",ope=");//Out(str2, ",str2=");//Out(que, ",ope=");
#endif // DEBUG		auto res = Solution().Ans(bs,z);cout << res;	}

单元测试

vector<long long> a;TEST_METHOD(TestMethod11){auto res = Solution().Ans({ 3 },0);AssertEx("1", res.c_str());}TEST_METHOD(TestMethod12){auto res = Solution().Ans({ 2,1 },0);AssertEx("11", res.c_str());}TEST_METHOD(TestMethod13){auto res = Solution().Ans({ 2,2 },0);AssertEx("00", res.c_str());}TEST_METHOD(TestMethod14){auto res = Solution().Ans({ 2,1 }, 1);AssertEx("10", res.c_str());}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功