测试106 T1 20pts

T1:

背景:简单模板题
原因:1、细节打错
     2、无法对拍
方法:
1、输出过程量,替代对拍。
2、打时、检查时,想运行方式。

T2:

分为两部分,a-b和最后跳的一下a。称为X,Y.

X贪心大到小排序。

枚举Y,n^2 check

优化check过程:若Y在X后,直接后缀最大值,向前扫序列统计。

考虑Y在X前。视为X中摘出一个作为最后一跃 信仰之跃     。

考虑L减去i的贡献,加上i的a的贡献。lowerbound找到起跳点,称为p。

则1~i-1必须合法,i~p视为贡献向左平移一位。平移后加下一位减i。

定义W数组为Sum[i+1]-C[i];i~pW最小值ST表找到,减去i位贡献,看>0即可。

(为什么随机化这么多A的啊,正解很无奈)

T3:

对于达到全零状态:

a[i][j]=0,1的位置可以限制 当前点覆盖次数奇偶。

实际上是I行J列同时选或不选或只其一。

考场缺乏进一步思考,在dfs时想这个,以为是类似2-sat但是复杂度假了。

转化思路:不再dfs搜索方案。行列划分到相同或对立集合。转化为dfs染色判定。

即可知能否达到全零。

进一步是思考先后手。

一个盲点:并非一个联通块,而是若干个。

讨论两对立集合sz奇偶,划分为同奇11,同偶00,相异10。

讨论即可。

更巧妙的是sg函数。先后手转化思想。

sg(11)=1,sg(00)=0,sg(01)=2;

异或和为0,B$哥赢。否则小wMz赢。

实际含义:(01)个数偶数后手平衡状态,先手奇数选择状态。(00)无用。(11)先胜后败。

      只有(11)偶数,(01)偶数时先手败。

      sg(01)=2,不同于(00),(11),是因为这是两个域,作用不同。

题解:sg(00)=0.sg(11)走一步到偶数块,sg(0)=0,则sg(11)=1;

sg(01)可奇偶,到0/1,所以为2。

 

上一篇:如何开发自己的股票软件106


下一篇:模拟106 题解