Preface
关于军训……它死了
第一次感觉到疫情的好处，就是不知道训了一半给不给学分，要不要补训
一直打隔膜颓废也不是办法，因此来写写题（才不是因为路由器没到舍不得用流量更新永劫无间呢）
A. Chip Game
看到这种可以用SG函数的题目先暴力艹上一发，发现当且仅当\(n,m\)奇偶性相同时为Tonya，反之
后来一想证明也很eazy，因为总的移动格子数是\(n+m-2\)，每次的变化值都是奇数，因此等价于看\(n+m\)的奇偶性
#include<cstdio>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
//const int N=105;
//int SG[N][N]; bool vis[N];
int t,n,m;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
/*RI i,j,k; for (i=1;i<=20;++i) for (j=1;j<=20;++j)
{
memset(vis,0,sizeof(vis));
for (k=1;k<i;k+=2) vis[SG[i-k][j]]=1;
for (k=1;k<j;k+=2) vis[SG[i][j-k]]=1;
for (k=0;vis[k];++k); SG[i][j]=k;
}
for (i=1;i<=20;++i) for (j=1;j<=20;++j)
printf("%d %d: %d\n",i,j,SG[i][j]);*/
for (scanf("%d",&t);t;--t) scanf("%d%d",&n,&m),puts((n&1)==(m&1)?"Tonya":"Burenka");
return 0;
}
B. Mathematical Circus
首先把\(k\)对\(4\)取模，不难证明当\(k=0\)时是无解的
接下来考虑\(k=1/3\)的情况，容易发现只要分成一个奇数+一个偶数的情况即可
对于\(k=2\)的情况，我们每次考虑相邻的\(4\)个数\(\{4n+1,4n+2,4n+3,4n+4\}\)，显然可以划分成\((4n+1,4n+4),(4n+2,4n+3)\)的形式，对于可能剩下的两个数\(\{4n+1,4n+2\}\)也分成\((4n+2,4n+1)\)即可
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
int t,n,k;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&k); k%=4; if (!k) { puts("NO"); continue; }
if (puts("YES"),k==2)
{
for (i=1;i+3<=n;i+=4) printf("%d %d\n%d %d\n",i,i+3,i+1,i+2);
if (n%4==2) printf("%d %d\n",n,n-1);
} else
{
for (i=1;i<=n;i+=2) printf("%d %d\n",i,i+1);
}
}
return 0;
}
C. Fighting Tournament
不难发现一个关键性质，当最大的那个人来到最前面后其他人的胜利次数就不会发生变化了，这个人会一直赢下去
同时我们发现我们可以离线询问，这样就可以直接模拟比赛过程了，可以用deque，非常方便
#include<cstdio>
#include<algorithm>
#include<deque>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
struct ques
{
int id,p,t;
friend inline bool operator < (const ques& A,const ques& B)
{
return A.t<B.t;
}
}q[N]; int t,n,m,a[N],c[N],pos,num[N],ans[N]; deque <int> dq;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
scanf("%d",&a[i]),c[i]=0,dq.push_back(a[i]),num[a[i]]=i;
for (i=1;i<=m;++i) scanf("%d%d",&q[i].p,&q[i].t),q[i].id=i;
RI now=1; for (sort(q+1,q+m+1),i=1;;++i)
{
int x=dq.front(); dq.pop_front(); int y=dq.front(); dq.pop_front();
if (x<y) swap(x,y); ++c[num[x]]; dq.push_front(x); dq.push_back(y);
while (now<=m&&q[now].t==i) ans[q[now].id]=c[q[now].p],++now;
if (x==n) { pos=i; break; }
}
while (now<=m) ans[q[now].id]=c[q[now].p]+(q[now].p==num[n]?q[now].t-pos:0),++now;
for (i=1;i<=m;++i) printf("%d\n",ans[i]); dq.clear();
}
return 0;
}
D. Burenka and Traditions
这里不单独讲easy version了，直接讲正解
首先不难发现我们只需要考虑长度为\(1/2\)的操作即可，因为所有更大的区间操作都可以分解，并且这样更灵活
设\(pre_i=\bigoplus_\limits{1\le j\le i} a_j\)，我们考虑以下一种操作方式：对于所有的\([i,i+1](1\le i<n)\)进行操作，每次异或上\(pre_i\)
不难发现经过\(i\)次操作后，\(a_j=0,j\in [1,i]\and a_{i+1}=pre_{i+1}\)，最后我们对剩余的\(a_n\)单独处理即可
然后我们发现如果操作的过程中出现了某个\(pre_i=0\)，那么到这个位置时会出现无需操作而\(a_{i+1}\)已经等于\(0\)的情形，相当于减少了一次操作
显然要想让答案更小，就要使得这种情况次数更多
普遍地，若\(pre_j=pre_i(j<i)\)，那么\((j,i]\)必然可以节省一次操作，只需要把原来的正序操作在这个区间内逆序即可（建议手玩模拟一下）
一个naive的想法是记录\(f_i\)表示前\(i\)个数的最小操作次数，可以从所有\(pre_j=pre_i\)的位置转移过来
但是我们很容易发现最优的转移位置一定是最近的那个，因此直接用set维护所有的\(pre_j\)，如果找到相同的就清空即可
#include<cstdio>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
int t,n,x,pre,ans; set <int> s;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n); ans=pre=0; s.clear(); s.insert(0); for (RI i=1;i<=n;++i)
{
scanf("%d",&x); pre^=x; if (s.count(pre)) s.clear(); else ++ans; s.insert(pre);
}
printf("%d\n",ans);
}
return 0;
}