12.10模拟赛总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
第一次考试就爆炸...
---------------------------------------------------------------
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
评论 (0)
