[2020洛谷5月月赛Div1]中子衰变

本文主要是介绍[2020洛谷5月月赛Div1]中子衰变，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

中子衰变

题解

~~好水的题呀！~~

首先对于1到4是很容易手玩出来的~~，笔者懒得手玩5-8。~~

之后对于n为偶数的情况，我们发现我们后手构造一个对称的序列的话，是一定可以赢的，对方不可能比我方晚不能放，如果对方可以放，我方也一定可以放。

于是，我们尝试着把这个结论推广到n为奇数的情况上。可我们很快就发现，n为奇数，我们必定是先手，而这样的话，就可能构造出一个全为1或-1的序列，这样对方就赢了。不过我们发现，如果将中间为构造成-1的话，就可以过特殊策略的点了。

我们需要考虑一下如何处理中间位的情况，处理两边的序列对称的情况。

于是，我们就得到了一种新方法。我们在两边构造时，就构造一个相反的对称序列，而在中间，构造一个有一端为空，其它全为相同数字的奇序列。

如果放在两边相反序列不挨着中间段的位置的话，就可以直接在对称位置放一个相反数，容易证明这种情况是一定满足的。
而对于放在挨着空的一端的位置，如果它与中间序列相同的元素一样的话，就不能在对面构造相同元素，我们就只能将这个空填上，将中间序列的长度扩大。否则一定可以构造出一个相反的对称序列。
如果他将这个空填上的话，容易发现，中间序列的两侧一定是空的，由于是相反的序列，就一定有至少一个位置可以用于扩大中间序列，我们找到一个填上就行了。

于是乎，我们就成功的找到这道题的必胜策略，再把~~可恶的~~交互题打一遍就可以了。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<bitset>
#include<set>
using namespace std;
#define MAXN 1500
typedef long long LL;
typedef pair<int,int> pii;
#define gc() getchar()
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
int n,take_id,m;
bool a[MAXN][2],f[MAXN];
void fill(int place,int type){a[place][type]=a[place][type^1]=1;a[place-1][type^1]=a[place+1][type^1]=1;
}
bool check(){for(int i=1;i<=n;i++)if(!a[i][0]||!a[i][1])return 1;return 0;
}
signed main(){read(n);read(take_id);if(n==1){fflush(stdout);cout<<"1"<<endl;int place,type;read(place);read(type);return 0;}if(n&1){fflush(stdout);cout<<"1"<<endl;int place,type;int m=n/2,l=m+1,r=l,cc;while(check()){read(place);read(type);fill(place,type>0?1:0);if(!check())break;if(l==r&&place==l)cc=type;if(place==l||place==r){if(l>0&&!a[l-1][type]){fill(l-1,type>0?1:0);fflush(stdout);cout<<l-1<<" "<<type<<endl;}else if(r<=n&&!a[r+1][type]){fill(r+1,type>0?1:0);fflush(stdout);cout<<r+1<<" "<<type<<endl;}m--;l--;r++;}else if((place==l-1||place==r+1)&&type==cc){int p=(!a[l][cc])?l:r;fill(p,cc>0?1:0);fflush(stdout);cout<<p<<" "<<cc<<endl;m--;l--;r++;}else{fill(n-place+1,type>0?0:1);fflush(stdout);cout<<n-place+1<<" "<<-type<<endl;}}}else{fflush(stdout);cout<<"1"<<endl;int place,type;while(check()){read(place);read(type);fill(place,type>0?1:0);fflush(stdout);cout<<n-place+1<<" "<<type<<endl;fill(n-place+1,type>0?1:0);}}return 0;
}