12.10模拟赛总结

第一次考试就爆炸...
---------------------------------------------------------------
T1:
考试的时候想"啊,这不是做过的题吗,最后再写吧"
然后就没有时间写了...
考完之后发现大家都是先做T1的...
稳拿的题不做我在想什么啊..
最大流+离散化
---------------------------------------------------------------
T2:
考试的时候没什么想法,写了个暴搜
标算的话,是状压DP,从上到下一行一行的搞
每个格子有一个“属于几号连通块”的属性,这样搞一搞..
---------------------------------------------------------------
T3:
第一道写的题,一写写到11点..
刚开始开开心心码好了主席树,然后发现有区间修改
然后犹豫了很久(难数据结构恐惧症),还是写了个树状数组套线段树
然后发现树套树也不是很难写嘛~\(≧▽≦)/~
但还是调了很久以至于其他题都没时间写了
---------------------------------------------------------------
T4:
一看可以用加一大法,好开心~
然后把最简单的情况(2×2的)推了一下,发现好难啊
然后就放弃了
 
标算的话是这个样子的:
首先考虑加一
然后一个只有一个朝上的格子的状态只有一种转移,就是把它向左上翻
翻了之后又得到很多朝上的格子,递归的搞+记忆化即可
最后算出所有只有一个朝上的格子的情况,复杂度O(n^4)
然后,假设第i个任意取的格子如果为ai(0为不取,1为取)的话,且如果翻得SG值为bi
第i个一定要翻的状态SG为ci
发现最后状态的SG值就是sum(ai*bi) xor sum(ci),sum表示异或和
得到方程:sum(ai*bi) xor sum(ci) = 0
即:sum(ai*bi) = sun(ci),设sum(ci) = M
把bi按位拆开,设bi的第j位为bi,j , 把M也按位拆开,设M的第j位为Mj,得到方程组:
sum(ai*bi,j)=Mj
解这个异或方程组,得到任意一组解,即使原题的解
---------------------------------------------------------------
题号:SuperOj P1018~P1021