Chip Game
博弈
从左下到右上的总步数为s=(n-1+m-1)步,只能走奇数步,Burenka移动后步数和是奇数,Tony移动后步数和是偶数
所以只用看s%2的奇偶性即可
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
//typedef long long LL;
#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;
//typedef pair<int,int>PII;
//#define x first
//#define y second
void solve()
{
int n,m;cin >> n >> m;
if((n + m) & 1)cout << "Burenka" << endl;
else cout << "Tonya" << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
一道构造题,我们可以想到从1~n中进行配对使得能被4整除,不管k是奇还是偶,我们选择两个偶数一定是比奇数
更容易满足条件,所以我们要均匀分配,给每个偶数分配一个奇数
考虑临近的即可,只是看对奇偶性的影响,数值无所谓
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
//typedef long long LL;
#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;
typedef pair<int,int>PII;
//#define x first
//#define y second
void solve()
{
int n,k;cin >> n >> k;
vector<PII>res;
bool flag = true;
for(int i = 1; i <= n; i += 2)
{
if((i + k) * (i + 1) % 4 == 0)
res.push_back({i,i + 1});
else if((i + k + 1) * i % 4 == 0)
res.push_back({i + 1,i});
else flag = false;
}
if(flag)
{
cout << "YES" << endl;
for(auto x : res)cout << x.first << " " << x.second << endl;
}
else cout << "NO" << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
关键点:只要力量最大的位于第一位时,以后所有的比赛只能是他赢,这也就约束了我们的比赛胜点是有规律的
具体做法见代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
//typedef long long LL;
//#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;
typedef pair<int,int>PII;
vector<int>pos[N];
int a[N];
void solve()
{
memset(pos,0,sizeof pos);
int n,m;cin >> n >> m;
int t;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
if(a[i] == n)t = i;
pos[i].clear();//清空
}
deque<int>q;
for(int i = 1;i <= n; i ++)q.push_back(i);
for(int i = 1; i <= n; i ++)//力量最大的人一定能走到开头位置
{
int t1 = q.front();q.pop_front();
int t2 = q.front();q.pop_front();
if(a[t1] < a[t2])swap(t1,t2);
q.push_front(t1);
q.push_back(t2);
pos[t1].push_back(i);//将获胜的位置放进去
}
while(m --)
{
int p,k;cin >> p >> k;
//下标是从0开始的,所以要找后一个位置
int res = lower_bound(pos[p].begin(),pos[p].end(),k) - pos[p].begin();
if(p == t && k > n)res += k - n;
cout << res << endl;
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
例如操作序列是x y z,在保证能将前面的数变成0的情况下,我们看是否能带上z
对于前两个数我们可以有:(0,y,z),(0,y^x,z),继续向后操作可能得到
(0,0,z^y),(0,0,z^y^x),(0,0,z),因此我们发现只用维护一个后缀异或和即可
并且我们发现我们的操作就两个:
1、将某个数异或上x
2、将某两个数异或上x
其余的情况都是由他们拼凑出来的,于是我们可以根据自己的需要将某一段后缀异或和堆叠起来即可
我们带上后就不能再用这个后缀异或和了,应请零重做,相当于被0隔断了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
//typedef long long LL;
//#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;
typedef pair<int,int>PII;
int a[N];
void solve()
{
int n;cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i];
a[0] = 0;
set<int>s;//存储当前可以使用的后缀和
s.insert(0);
int res = 0,suf = 0;//连续的后缀异或和
//核心:用一段后缀来顶替一次操作
for(int i = 1; i <= n; i ++)
{
if(s.count(a[i] ^ suf) || a[i] == 0)s.clear(),suf = 0;
else res ++,s.insert(suf),suf ^= a[i];
}
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}