[atAGC051C]Flipper

对于这一个平面用$a_{x,y}$来表示，即$(x,y)$为黑色则$a_{x,y}=1$，否则$a_{x,y}=0$，之后定义$a$能生成$b$当且仅当$a$能够通过若干次操作后得到$b$

令$p_{y}=\bigoplus_{x}a_{x,y}$、$q_{x,i}=\bigoplus_{y\equiv i(mod\ 3)}a_{x,i}$（其中$0\le i<3$），考虑两个序列能相互生成当且仅当$pa_{i}=pb_{i}$且$\forall x,(qa_{x,0}\oplus qb_{x,0})=...=(qa_{x,2}\oplus qb_{x,2})$，证明如下：

首先考虑一次操作$(x,y)$会带来的影响：对于$p_{i}$没有影响，对于$q_{i}$是将$q_{x}$和$q_{x+1}$所有位置异或1，那么所能产生的仅有原序列和异或1后的序列，即证明了后面条件的必要性

接下来证明对于两个满足上述条件的$a$和$b$，证明$a$能生成$b$（操作可逆，因此生成也具有可逆性）

找到$a_{x,y}=1$，满足$x\ge 2$且$y\ge 3$，若仍有多个取$x$最大的，若仍有多个取$y$最大的（若不存在则停止），之后执行$(x-2,y-1)$这个操作

对$a$和$b$都重复此过程，若最终得到的$a=b$，则根据操作可逆性，初始的$a$能生成$b$，因此以下来证明$a=b$，先将整个平面分为四个部分，分别证明相等：

1.$x\ge 2$且$y\ge 3$，此时$a_{x,y}=b_{x,y}=0$（否则还可以继续操作）

2.$x=1$且$y\ge 3$，此时$a_{x,y}=b_{x,y}=p_{y}$（两者$p_{y}$相同）

3.$x\ge 2$且$y\le 2$，此时$qa_{x,0}=qb_{x,0}=0$，因此$a_{x,1}=qa_{x,1}=qb_{x,1}=b_{x,1}$，同理$a_{x,2}=b_{x,2}$

4.$x=1$且$y\le 2$，根据3可以得到$a_{x,1}=b_{x,1}$，可推出$\bigoplus_{x>1}a_{x,1}=b_{x,1}$，又因为$pa_{1}=pb_{1}$，因此$a_{1,1}=b_{1,1}$，类似的$a_{1,2}=b_{1,2}$

由此，即证明了该结论，现在我们要找到满足此条件下最小的1个数最小的$a$

考虑先暴力$o(2^{\infty})$去枚举每一个$q_{x}$是否要全部异或1（即让$q$需要完全相等），接下来构造最少的$a$

首先，若$0\le i<3$满足$\bigoplus_{y\equiv i(mod\ 3)}p_{y}\ne\bigoplus_{x}q_{x,i}$，意味着产生了矛盾，无解

（其实这里产生这个条件的原因是每一次翻转了两列，因此翻转的列数必然是偶数列，但如果翻转奇数列会引发$p_{i}$变化，不存在合法的$a$，而证明就是对于给定已经合法的$a$和$b$去考虑，因此没有问题）

其次，考虑至少需要$\sum_{i=0}^{2}\max(\sum_{y\equiv i(mod\ 3)}p_{y},\sum_{x}q_{x,i})$个，接下来构造恰好达到下限的解：

对于$p_{y}=1$且$q_{x,i}=1$（其中$y\equiv i(mod\ 3)$），仅在$(x,y)$放置一个就可以满足两个，对于其他的在$(x,\infty)$或$(\infty,y)$放即达到了该下限，且由于异或相等，即必然剩余偶数个，最终$p_{\infty}$和$q_{\infty,0/1/2}$都为0

预处理初始前面以及后面的三个值，分别记作$(X,Y,Z)$和$(x,y,z)$，翻转即将$(x,y,z)$其中一个减1并将另外两个加1，之后满足$x\equiv X,y\equiv Y,z\equiv Z(mod\ 2)$且最小化$\max(x,X)+\max(y,Y)+\max(z,Z)$

贪心去操作$x-X$、$y-Y$和$z-Z$中最大的数（如果会使答案增加就不操作），最终若$x\not\equiv X(mod\ 2)$则再操作一次即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 map<int,int>p1,p2;

 4 map<int,int>::iterator it;

 5 int n,x,y,s,ans,a[3];

 6 int calc(){

 7     return max(a[0],0)+max(a[1],0)+max(a[2],0);

 8 }

 9 int main(){

10     scanf("%d",&n);

11     for(int i=1;i<=n;i++){

12         scanf("%d%d",&x,&y);

13         p1[x]^=(1<<(y%3));

14         p2[y]^=1;

15     }

16     for(it=p1.begin();it!=p1.end();it++){

17         x=(*it).second;

18         if ((x==1)||(x==6))a[0]++;

19         if ((x==2)||(x==5))a[1]++;

20         if ((x==4)||(x==3))a[2]++;

21     }

22     for(it=p2.begin();it!=p2.end();it++)

23         if ((*it).second){

24             ans++;

25             a[(*it).first%3]--;

26         }

27     s=calc();

28     while (1){

29         sort(a,a+3);

30         a[0]++,a[1]++,a[2]--;

31         if (calc()>=s){

32             a[0]--,a[1]--,a[2]++;

33             break;

34         }

35         s=calc();

36     }

37     if (a[0]&1){

38         sort(a,a+3);

39         a[0]++,a[1]++,a[2]--;

40     }

41     printf("%d",ans+calc());

42 }

巴特西

[atAGC051C]Flipper

最新文章

热门文章