F - XOR Game
题意
给定n,k ,k代表0的个数,现在有一个数x初始为0
接下来n个数,每一个数代表
这个数字的个数
每次操作可以选择a数组中的一个数字并且可以选择是否将这个x异或上这个数字,然后把这个数字从a数组中删除,Alice先手,Alice想让答案尽可能大,Bob想让答案尽可能小,问最后答案(用n位二进制数输出)
思路
手玩一下可以发现,假设此时某一位数字有个,当
>=3的时候,无论谁选择这个数,无论x是否异或上这个数字,对答案都没有任何影响,只有当
==2的时候,当其中一个人选择这个数字的时候,另一个人都可以选择对应的操作使得这一位上的答案最小/最大,当
==1的时候,ALICE和BOB肯定能选择选,ALICE一定会把x异或上这个数，BOB一定会把这个数直接删掉
于是就把==1的存下来,从大到小遍历,答案一定异或上奇数位的
（Alice优先操作）,然后把每次操作存下来
然后把0和所有>=3的部分也存下来,判断存下来的操作数是奇数还是偶数,是奇数的话,接下来Bob操作,Bob每一次操作Alice都能找到对应的操作使得这一位为1，是偶数的话Alice的每一次操作Bob都能找到对应的操作使这一位为0
代码
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
string s,pres;
vector<int>v;
void solve()
{
cin>>n>>m;
_rep(i,0,n-1)s+='0',pres+='0';
_rep(i,0,n-1)
{
int x;
cin>>x;
if(!x)continue;
if(x==1)v.pb(i);
else
{
if(x>2)m+=x-2;
pres[i]='1';
}
}
int res=0;
reverse(all(v));
_for(i,(int)v.size())
{
if(i%2==0)s[v[i]]='1';
m++;
}
if(m&1)
{
_rep(i,0,n-1)
if(s[i]=='0')s[i]=pres[i];
}
_pre(i,n-1,0)
cout<<s[i];
return ;
}
signed main()
{
IOS;
int T=1;
// cin>>T
while(T--)
solve();
return 0;
}L - Rubbish Sorting
思路
操作为1的时候,用一遍深搜把所有情况的编号用map存下来(注意不匹配被标记为‘*’),时间复杂度最多为比如
假设输入样例
3
1 aa 2
1 ab 1
2 ba输入1 aa 2
那么此时mp[aa]=2,mp[a]=2,mp[*]=2,mp[a*]=2,mp[*a]=2,mp[**]=2
假设在这之后输入1 ab 1
那么接下来mp[ab]=1,mp[a]=1(更新),mp[a*]=1(更新),mp[*b]=1,mp[**]=1(更新)
接下来询问,只需要深搜找到匹配字母数量最多的对应的map编号即可(不匹配被标记为‘*’)
假设输入 2 ba
此时mp[]找不到"ba",于是深搜一个不匹配mp[b*]和mp[*a],找到了并且输出这一轮的最小序号也就是mp[*a]=2,于是这一次询问终止,不需要在深搜两个不匹配的情况，此时输出序号2
代码
#include<bits/stdc++.h>
using namespace std;
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld%lld",&x,&y)
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pf(x) printf("%lld",x)
#define pii pair<int,int>
#define f first
#define s second
#define int long long
typedef unsigned long long ull;
//
//
const int N = 3e5+10;
const ull P = 13331;
unordered_map<ull,int> mp;
int m;
char ss[N];
void mpp(ull str,int n)
{
if(mp.count(str))
mp[str]=min(mp[str],n);
else mp[str]=n;
}
void dfs1(int u,ull now,int op)
{
ull z = now;
if(u==strlen(ss))
{
int n=5-strlen(ss);
while(n--) now=now*P+(ull)'*';
mpp(now,op);
return ;
}
dfs1(u+1,now*P+ss[u],op);
dfs1(u+1,now*P+'*',op);
}
int dfs2(int u,ull now,int j,int now1)
{
int res=0x3f3f3f3f;
if(u==strlen(ss))
{
int n=5-strlen(ss);
while(n--) now=now*P+(ull)'*';
if(mp.count(now)) return mp[now];
else return 0x3f3f3f3f;
}
if(now1<j){
res=min(res,dfs2(u+1,now*P+'*',j,now1+1));
}
res=min(res,dfs2(u+1,now*P+ss[u],j,now1));
return res;
}
void solve()
{
sf(m);
for(int i=1;i<=m;i++)
{
int op,x;
sf(op);
scanf("%s",ss);
if(op==1){
sf(x);
dfs1(0,0,x);
}
else
{
int len=strlen(ss);
for(int j=0;j<=len;j++)
{
int now=dfs2(0,0,j,0);
if(now!=0x3f3f3f3f)
{
pf(now);
puts("");
break;
}
}
}
}
}
signed main()
{
// IOS
int _=1;
while(_--)
solve();
return 0;
}
