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。