[日常训练]游戏题
ban
Description
n种英雄站成一列,要求每时每刻满足\(a_i\leq{a_{i+1}}\).
两人轮流操作,每次可以ban任意多人人.
问先手时候必胜.
HINT
\(n\leq10^5\).
Solution
这个条件有点麻烦...
然后把数列差分一下,\(d_i=a_i-a_{i-1}\),发现ban第i种英雄k个等价于\(d_i-k,d_{i+1}+k\),这就转化成了阶梯Nim了.
#define N 100005
int a[N],n,t,ans;
inline void Aireen(){
t=read();
while(t--){
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
ans=0;
for(int i=n;i>=1;i-=2)
ans^=(a[i]-a[i-1]);
ans?puts("HH"):puts("GG");
}
}
light
Description
给你一个\(n\times{n}\)的网格及每个网格中灯初始开关状态.
可以对格子\((x,y)\)进行操作:改变\((x,y)\)及其上下左右四个格子的开关状态.
求一种方案使得灯全关掉.
HINT
\(n^2\leq500\).
Solution
方法一
枚举第一行的操作状态,O(nm)判是否可行.
#define N 25
int a[N][N],b[N][N],n;
bool flag;
inline bool chk(){
for(int i=1;in){
if(chk()){
flag=true;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(b[i][j]) printf("%d %d\n",i,j);
puts("0 0");
}
return;
}
b[1][u]=0;dfs(u+1);
b[1][u]=1;dfs(u+1);
}
inline void Aireen(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&a[i][j]);
dfs(1);
}
方法二
将状态压成二进制判断.
#define N 25
int a[N],b[N],n;
bool flag;
inline bool chk(){
for(int i=1;i>1))&((1<>1))&((1<n){
b[1]=k;
if(chk()){
flag=true;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(b[i]&(1< 方法三
\(b_{i,j}\)表示\((i,j)\)的操作状态,则达成目标状态需要满足\(a_{i,j}\;xor\;b_{i,j}\;xor\;b_{i-1,j}\;xor\;b_{i+1,j}\;xor\;b_{i,j-1}\;xor\;b_{i,j+1}=0\).
解方程组即可.
#define N 25
#define M 505
int a[N][N],b[N][N],f[M][M],ans[M],n,cnt;
inline void gauss(int n){
for(int i=1;ippt
这道题真是$@#^#%...
两头往中间匹配:
尽量赢:小的尽量匹配比其小的,大的尽量匹配比其小的;不行的时候,用小的去换对方大的.
尽量输:小的尽量匹配比其大的,大的尽量匹配比其大的;不行的时候,用大的去换对方小的.
#define N 200005
int a[N],b[N],n,ans;
inline void Aireen(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
sort(a+1,a+1+n);sort(b+1,b+1+n);
for(int l=1,r=n,p=1,q=n;l<=r&&p<=q;){
while(a[l]>b[p]&&l<=r&&p<=q) ++l,++p,ans+=2;
while(a[r]>b[q]&&l<=r&&p<=q) --r,--q,ans+=2;
if(l>r||p>q) break;
ans+=(a[l]==b[q]);++l;--q;
}
printf("%d ",ans);
ans=0;
for(int l=1,r=n,p=1,q=n;l<=r&&p<=q;){
while(a[l]r||p>q) break;
ans+=2-(a[r]==b[p]);--r;++p;
}
printf("%d\n",ans);
}
2017-10-25 21:02:55