B. GameGame 解析(思維、博弈)
2024-10-09 17:13:39
Codeforce 1383 B. GameGame 解析(思維、博弈)
今天我們來看看CF1383B
題目連結
題目
兩個人在玩遊戲,有一個長度為\(n\)的數列\(a\),每次每個人選一個數字和目前自己的分數XOR(初始為0分),最後拿到最多分數的人贏,求誰會贏?
前言
博弈的題目一直不是很會做,這次這題有個我平時可能不會想到的新想法:可以嘗試讓其中一個玩家跟隨另一個玩家做動作,如果被跟隨的那個玩家最後會輸,那麼跟隨的那個玩家就會贏。這是因為我們給出了一個明確的移動方法。
想法
首先要知道一件事:如果一個玩家能夠使得分數有最高位的bit,並且另外一個人沒有,那麼就贏了。這是因為在右邊的bit不管有多少,都比不上最左邊的bit(正式來說:\(2^n>\sum\limits_{i=0}^{n-1}2^i\ \forall n\in\mathbb{N}_{\ge1}\))。
那麼我們可以先統計對於bit有幾個元素有這個bit,接著我們從最左邊的bit開始「考慮」:
分為兩種情況:
這個bit有偶數個,那麼由於兩個玩家只有2種拿的方法
- 偶偶
- 奇奇
不管玩家怎麼拿,這個bit最後的狀態都是一樣的,所以我們可以完全不用考慮這個bit。
這個bit有奇數個,也就是玩家要去搶這個bit: 首先另\(x=\)有這個bit的元素的數量,\(y=n-x\)也就是剩下的數字的數量(這個bit是\(0\))。由於玩家們拿了\(4\)個\(1\)等同於沒有改變狀態,因此有以下的分類:
- \(x\mod 4=1\) and \(y\mod 2=0\): 先手先拿一個\(1\),接著完全照搬後手的行動。如此易發現先手會贏。
- \(x\mod 4=1\) and \(y\mod 2=1\): 先手先拿一個\(1\),接著完全照搬後手的行動,直到後手拿走了最後一個\(0\),那麼接著就剩下要拿偶數個\(1\),並且是先手先拿。由於是\(x\mod 4=1\),所以最後是先手贏。
- \(x\mod 4=3\) and \(y\mod 2=0\): 後手完全照搬先手的行動,最後先手一定會拿到偶數個\(1\),所以後手贏。
- \(x\mod 4=3\) and \(y\mod 2=1\): 先手先拿一個\(0\),那麼就是3.的情況了,先手贏。
程式碼:
const int _n=1e5+10;
int t,n,a[_n],cnt[32];
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);
cin>>t;while(t--){
cin>>n;rep(i,0,n)cin>>a[i]; memset(cnt,0,sizeof cnt);
rep(j,0,30)rep(i,0,n)cnt[j]+=((a[i]&(1<<j))?1:0);
per(i,0,30){
if(cnt[i]%2==0)continue;
int x=cnt[i],y=n-x;
if(x%4==3 and y%2==0){cout<<"LOSE\n";goto A;}
else {cout<<"WIN\n";goto A;}
}cout<<"DRAW\n";
A:;
}
return 0;
}
標頭、模板請點Submission看
Submission
最新文章
- 9.Struts2在Action中获取request-session-application对象
- 给td添加滚动条
- percona 5.6升级到5.7相关error及解决方法
- JQuery源码解析(九)
- Android 设置界面的圆角选项
- SQL Server 错误检测与修复
- 学习日记之模板方法模式和 Effective C++
- css设置黑体宋体等(转)
- ASP.NET如何通过后台数据库提供的链接播放视频(不使用外置插件)
- 接口测试执行工具Postman:模拟请求、用例执行、断言、批量运行用例、简单持续集成
- Testlink1.9.17使用方法(第六章 测试计划制定)
- [转载]理解 Git 分支管理最佳实践
- 基于Spring Security和 JWT的权限系统设计
- Prometheus MySQL_exporter
- .NET Core开发日志——结构化日志
- 实力封装:Unity打包AssetBundle(四)
- [翻译]Restful Web服务模型
- Make a Crystal UVA - 11014 (容斥定理)
- sql:PostgreSQL
- java 继承 String类
热门文章
- ElasticSearch 简单的crud查询
- PageRank算法(网页排名)
- 079 01 Android 零基础入门 02 Java面向对象 01 Java面向对象基础 01 初识面向对象 04 实例化对象
- Java知识系统回顾整理01基础03变量03字面值
- 1个LED灯闪烁的Arduino控制
- 【题解】CF1375D Replace by MEX
- 【题解】[USACO12MAR]Cows in a Skyscraper G
- 达梦产品技术支持-DM8-数据库安装
- Git操作常用的命令都在这里了。
- (转载)跟Classic ARM 处理器说拜拜——Atmel SAMA5D3 Xplained开发板评测