首页 > 其他分享 >博弈论练习7 栗酱的异或和(取石子问题)

博弈论练习7 栗酱的异或和(取石子问题)

时间:2022-11-17 21:56:12浏览次数:53  
标签:std 石子 int scanf 博弈论 异或 栗酱

题目链接在这里:

我们首先想到经典的取石子问题,考虑的是所有石子堆异或起来是不是0,如果为0就说明先手必败。这里面的逻辑和上一篇总结的博弈论基本规律是一样的,因为异或是相同为0,不同为1,因此如果异或和为0的话说明每一位上的1如果有人选了,那另一方一定能选一个对称的1。而本题中限制了先手必须选择哪个堆,我们就把其他的堆先异或和了,然后看当前堆能否转化为这个异或和,由结论,如果当前堆的个数大于异或和,那么一定能转化为异或和。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=1e5+5;
 4 int t,n,k,a[MAX];
 5 int main(){
 6     int i,j,zt;
 7     scanf("%d",&t);
 8     while (t--){
 9         scanf("%d%d",&n,&k);
10         for (i=1;i<=n;i++) scanf("%d",&a[i]);
11         zt=0;
12         for (i=1;i<=n;i++){
13             if (i==k) continue;
14             zt^=a[i];
15         }
16         if (zt>=a[k]) cout<<"No"<<endl;
17         else cout<<"Yes"<<endl;
18     }
19     return 0;
20 }

 

标签:std,石子,int,scanf,博弈论,异或,栗酱
From: https://www.cnblogs.com/keximeiruguo/p/16901110.html

相关文章

  • 博弈论练习5 小牛再战(取石子问题)
    题目链接在这里:F-小牛再战_牛客竞赛博弈专题班组合游戏基本概念、对抗搜索、Bash游戏、Nim游戏习题(nowcoder.com)这是比较经典的巴什博奕问题,在博弈论中想到的第一个操......
  • 博弈论练习4 Calendar Game(SG函数)
    题目链接在这里:D-CalendarGame_牛客竞赛博弈专题班组合游戏基本概念、对抗搜索、Bash游戏、Nim游戏习题(nowcoder.com)这题网上有关于奇偶性来找规律的做法,有点人类智慧......
  • 博弈论练习3 Palindrome Game (hard version) (人类智慧题)
    题目链接在这里:C-PalindromeGame(hardversion)_牛客竞赛博弈专题班组合游戏基本概念、对抗搜索、Bash游戏、Nim游戏习题(nowcoder.com)这题挺人类智慧的,但是也有博弈......
  • 博弈论之SG函数与SG定理
    SG定理&SG函数概念:必胜点N:在此位必胜必败点P:在此位必输更严谨的定义为:无法移动的状态(即terminal-position)为P可以移动到P的局面为N所有移动都会进入N的局面......
  • Java的位运算符详解实例——与(&)、非(~)、或(|)、异或(^)
    转自csdn==https://blog.csdn.net/is_zhoufeng/article/details/8112199位运算符主要针对二进制,它包括了:“与”、“非”、“或”、“异或”。从表面上看似乎有点像逻辑运......
  • 461. 汉明距离 ------ 位运算,二进制,异或求不同、内置函数、Brian Kernighan 算法
    两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给你两个整数x和y,计算并返回它们之间的汉明距离。 示例1:输入:x=1,y=4输出:2解释:1......
  • 异或操作的加密,解密,原理。
    异或加密异或加密是一种很简单的加密算法。原理:根据异或的运算规则,在二进制中,相同为0,不同为1。且:某个数与0异或等于这个数的本身,与1异或等于这个数的相反。特性:异或运算......
  • LG5283 [十二省联考 2019] 异或粽子 题解
    口胡一个异或经典问题LG5283[十二省联考2019]异或粽子给定一个长为\(n\)的序列,序列一段子区间\([l,r]\)的值为\([l,r]\)范围内所有数异或起来的值。现在求出前......
  • 博弈论初探
    博弈论基础概念先手:当前局面轮到谁操作,谁就是当前局面的先手。P点:当前先手必败点。N点:当前先手必胜点。公平组合游戏(ICG)的性质没有出边(无法操作)的点是P点(公理......
  • java逻辑运算中异或^
    本文主要阐明逻辑运算符^(异或)的作用a^b,相异为真,相同为假。注意,异或运算,还能交换两个变量。inta=1;intb=2;System.out.println("a="+a+",b="+b);a......