蓝桥杯.异或数列(博弈，位运算)

Woodenman杜 2023-05-03 原文

Question:

Solve:

思路还是不太好想的，我尽量描述~

这道题最终的判断会归结于两个数 va 和 vb 比大小，所以可以借鉴两个数比较的过程来解这道题：

从最高位开始，依次比较二者的每一位的大小

对于这道题也是相同的思路

从最高位开始去判断最后的 va 和 vb 二进制的每一位，Alice和Bob谁会得到1，谁会得到0，还是都是0或者都是1打成平局，当然va和vb绝对不需要实际计算，用所有的 xi 推导出来结果就行

在使用上述思路之前，我们还需要讨论一个特殊情况：最终平局

因为题上说过所有的xi都会被使用

所以如果最后是平局（va == vb），所有的xi异或值必定为 0

va和vb都是一堆xi的异或值，又因为相同的两个数异或结果为0，所以所有的xi异或值为 0

解决了最后会得到平局的问题之后，就可以进入正题了：

因为要判断的是二人在某一二进制位会获得 0 还是 1，所以第一步肯定是先提取对应数据啦~

因此先将所有的xi的某一数位的 0 和 1 的个数计数为 cnt0，cnt1

接下来讨论cnt0和cnt1的数量对于结果的影响

1. 如果 cnt1 == 1，那么只有先手的人才有将当前位的 0 变为 1 的机会，所以先手必胜

2. 如果 cnt1 是一个偶数，那么在采取最优策略的时候（其实就是轮流异或 1 ），二人该数位的结果一定都是 1 ，无法决策出谁赢，所以需要判断下一位

3. 如果 cnt1 和 cnt0 都是奇数，那一定是后手赢，为什么呢？

模拟一次过程就明白了~

首先，Alice肯定会选择一个数位为 1 的数将自己的 0 变为 1

之后，二者都一直选 0直到 0 消耗完，因为现在是Alice占优势的，所以这个选择一定是成立的

到了现在，剩余了偶数个数的 1 ，而且又是Alice选择，一定就是Bob赢了

4. 如果 cnt1 和 cnt0 一奇一偶，那就会是先手赢

同样的上述模拟，留给读者了~

总结一下：

所有xi异或为 0，平局

cnt1 为偶数，当前位平局

cnt1 和 cnt0 都是奇数，后手赢

一奇一偶，先手赢

特别地，cnt1 == 1 ，先手赢

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, a[200010], sum;
int cnt1, cnt0;
//判断胜负函数
int judge(){
    //偶数个1，无法决定胜负
    if(cnt1 % 2 == 0) return 0;
    //只有1个1，先手必胜
    if(cnt1 == 1) return 1;
    //0和1的个数都为奇数，后手胜
    if(cnt1 % 2 != 0 && cnt0 % 2 != 0)
        return -1;
    //先手胜
    else
        return 1;
}
void solve()
{
    sum = 0;
    for(int i = 1; i <= n; i++){
        cin >>a[i];  sum ^= a[i];
    }
    //所有数异或值为0，平局
    if(sum == 0) { cout <<0 <<endl; return; }
    //从最高位开始枚举
    for(int i = 20; i >= 0; i--){
        cnt1 = cnt0 = 0;
        //计数
        for(int j = 1; j <= n; j++){
            if((a[j] >> i) & 1) cnt1++;
            else cnt0++;
        }
        //judge
        int res = judge();
        if(res == 0) continue;
        else{
            cout <<res <<endl;
            return;
        }
    }
}
int main(void)
{
    cin >>t;
    while(t--){
        cin >>n;
        solve();
    }
    return 0;
}

最后附上蓝桥杯汇总链接：蓝桥杯C/C++A组省赛历年真题题解

声明：图片均来源于蓝桥杯官网，以个人刷题整理为目的，如若侵权，请联系删除~

蓝桥异或 xff0c xff0 xff 蓝桥杯 c++c语言算法

有关蓝桥杯.异或数列(博弈，位运算)的更多相关文章

ruby - 触发器 ruby 中 3 点范围运算符和 2 点范围运算符的区别 - 2
请帮助我理解范围运算符...和..之间的区别，作为Ruby中使用的“触发器”。这是PragmaticProgrammersguidetoRuby中的一个示例:a=(11..20).collect{|i|(i%4==0)..(i%3==0)?i:nil}返回:[nil,12,nil,nil,nil,16,17,18,nil,20]还有:a=(11..20).collect{|i|(i%4==0)...(i%3==0)?i:nil}返回:[nil,12,13,14,15,16,17,18,nil,20] 最佳答案触发器(又名f/f)是
ruby - 带括号和 splat 运算符的并行赋值 - 2
我明白了:x,(y,z)=1,*[2,3]x#=>1y#=>2z#=>nil我想知道为什么z的值为nil。最佳答案 x,(y,z)=1,*[2,3]右侧的splat*是内联扩展的，所以它等同于:x,(y,z)=1,2,3左边带括号的列表被视为嵌套赋值，所以它等价于:x=1y,z=23被丢弃，而z被分配给nil。关于ruby-带括号和splat运算符的并行赋值，我们在StackOverflow上找到一个类似的问题： https://stackoverflow
ruby - 定义自定义 Ruby 运算符 - 2
问题是:除了在“OperatorExpressions”？例如:1%!2 最佳答案是的，可以创建自定义运算符，但有一些注意事项。Ruby本身并不直接支持它，但是superatorsgem做了一个巧妙的把戏，将运算符链接在一起。这允许您创建自己的运算符，但有一些限制:$geminstallsuperators19然后:require'superators19'classArraysuperator"%~"do|operand|"#{self}percent-tilde#{operand}"endendputs[1]%~[2]#Out
ruby - Ruby 中 <=> 运算符的名称是什么？他们怎么调用它？ - 2
在Ruby中有运算符(operator)。在API中，他们没有命名它的名字，只是:Theclassmustdefinetheoperator...Comparableusestoimplementtheconventionalcomparison......theobjectsinthecollectionmustalsoimplementameaningfuloperator...它叫什么名字？最佳答案参见上面的@Tony。然而，它也被称为(俚语)“宇宙飞船运算符(operator)”。
ruby - 将运算符传递给函数？ - 2
也许这听起来很荒谬，但我想知道这对Ruby是否可行？基本上我有一个功能...defadda,bc=a+breturncend我希望能够将“+”或其他运算符(例如“-”)传递给函数，这样它就类似于...defsuma,b,operatorc=aoperatorbreturncend这可能吗？最佳答案两种可能性:以方法/算子名作为符号:defsuma,b,operatora.send(operator,b)endsum42,23,:+或者更通用的解决方案:采取一个block:defsuma,byielda,bendsum42,23,
ruby - OR 运算符和 Ruby where 子句 - 2
可能真的很简单，但我很难在网上找到关于这个的文档我在Ruby中有两个activerecord查询，我想通过OR运算符连接在一起@pro=Project.where(:manager_user_id=>current_user.id)@proa=Project.where(:account_manager=>current_user.id)我是ruby的新手，但我自己尝试使用||@pro=Project.where(:manager_user_id=>current_user.id||:account_manager=>current_user.id)这没有用，所以1.我想知道如何在
ruby - Ruby 中字符串运算符 + 和 << 的区别 - 2
我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc
ruby - 我可以在 Ruby 中动态调用数学运算符吗？ - 2
ruby中有这样的东西吗？send(+,1,2)我想让这段代码看起来不那么冗余ifop=="+"returnarg1+arg2elsifop=="-"returnarg1-arg2elsifop=="*"returnarg1*arg2elsifop=="/"returnarg1/arg2 最佳答案是的，只需像这样使用send(或者更好的是public_send):arg1.public_send(op,arg2)这是可行的，因为Ruby中的大多数运算符(包括+、-、*、/、andmore)只需调用方法。所以1+2与1.+(2)相同
蓝桥杯备赛（二） - 2
目录前言：一、ASC分析代码实现二、卡片分析代码实现三、直线分析代码实现四、货物摆放分析代码实现小结：前言：在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。一、ASC 已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy
ruby - 如何在不使用文本的情况下找到 Ruby 运算符的含义？ - 2
您如何找到有关代码中运算符用法的信息(最好是通过Google)？在这种情况下，我想找到这段代码在Ruby中的含义。x=[1,2,3]x.send:[]=,0,2x[0]+x.[](1)+x.send(:[],2)我要你教我如何钓鱼——不要告诉我运算符(operator)是做什么的。当我去Google并尝试搜索符号时，我得到的示例或教程没有涵盖特定的用法。https://stackoverflow.com/questions/1165786/how-to-search-for-punctuation-that-gets-ignored-by-google表示谷歌驳回了这种表示法；我寻找“

蓝桥杯.异或数列(博弈，位运算)

有关蓝桥杯.异或数列(博弈，位运算)的更多相关文章

随机推荐