织梦网站开发兼职,太原跨境电商,邮件订阅 wordpress,手机优化游戏性能的软件P4301 [CQOI2013] 新Nim游戏
题目#xff1a;
在传统的Nim游戏基础上加一步#xff0c;在第一个回合中#xff0c;第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿#xff0c;但不可以全部拿走。第二回合也一样#xff0c;第二个游戏者也有这样一次机会。从第…P4301 [CQOI2013] 新Nim游戏
题目
在传统的Nim游戏基础上加一步在第一个回合中第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿但不可以全部拿走。第二回合也一样第二个游戏者也有这样一次机会。从第三个回合又轮到第一个游戏者开始规则和 Nim 游戏一样。
题解
传统的Nim游戏策略非空石子数量xor和等于0则必败 A的目的是不论B怎么拿都无法剩下一个xor和等于0的子集。也就是A拿完后剩下一个线性基即可因为线性基是线性无关的肯定不为0题目又要求A拿走尽量少的石头先按照从大-小排序求最大的线性基
代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1030;
ll a[maxn];
int L60;
ll c[maxn];
bool insert(ll x){for(int jL;j0;--j){//从最高位开始看if((x(1llj))0) continue;if(a[j]){//若如主元j已经存在用a[j]消去x的第j位然后继续x ^ a[j];continue;} //让x当主元j需要先用第k(kj)个主元消去x的第k位for(int kj-1;k0;k--){if(x (1llk)) x ^ a[k];}//接着用x去消掉第k(kj)个主元的第j位for(int kL;kj;k--){if(a[k] (1llj)) a[k] ^ x;}a[j] x;return 1; }return 0;
}
int main()
{int n;cinn;for(int i1;in;i){cinc[i];}sort(c1,c1n,greaterint());ll ans0;for(int i1;in;i){bool winsert(c[i]);if(w0){ansc[i];}}if(ans0)cout-1endl;else coutans;
}
