做了10天。。除了final的1100pts都刷完了。。有一个题看了题解才明白trick，还有两个题是看了别人代码或是x大爷提醒的。。。。总之大部分是自己做的。。

可是打srm还是会爆负怎么办呀。。

省选课件：http://pan.baidu.com/s/1c0IrfJ6

1A:

250 写了DP。好像直接贪也是对的。

500 按字典序贪，检查时也是用贪。

1000 dp套dp 。。写的好麻烦。。。题解上的好像挺简洁

1B：

200 考你会不会编程

600 暴力枚举一维，剩下一维dp

900 我的dp状态是f[u][0]=u和u父亲都没填的概率，f[u][1]=u没填u父亲填了的概率

1C：

250 考你会不会编程

450 小学水平的容斥

950 直接裸三维状态的dp是O(n^3)就能过。用期望线性性可O(n^2)。O(n)不知道 没想过。

2A:

250 转化为最大化相邻格子高度差的绝对值的总和。贪心策略大概是高矮交错放。严格证明不大会

500 枚举中间次序不变的那一段，两边分别走到端点处再排好序走回来。但最后一个样例过不了，看题解发现漏了一种情况，可能有的狼从左端点一直跑到右端点的（题解里有张配图）。这时每只狼都至少到达过一个端点，中间一段狼到过两个端点，也是可以枚举的。

1000 难写。我是每次考虑能移到哪几个相邻位置结点再逐步扩展的。能移的条件大概有：子树有空位 或者 其他有两个子树分别有空位  或者 其他某一个子树里有两个分叉的空位。

2B:

350 按时间顺序贪。记录一下目前哪些点是两种状态都可能的。到不得不按的时候再按。

500 推理一下该满足的条件有哪些。。。然后可以nlogn筛

900 最后肯定得变为kW+1。。考虑一下怎么变过来的。。能推出一个形式，然后搜。  不知道复杂度，但跑的很快。

2C：

300 先考虑翻转的[l,r]满足s[l]!=s[r]的，这个显然可直接贪。然后s[l-1]==s[r+1]的话再一直往两边延伸

500 给每个团加个新点 都连向它。。。然后变成裸bfs   

900 先搞出每小段区间的最大值，然后判一下有没有包含同一个数的区间交集为空的情况。 然后变成个匹配一样的东西。。判有没有满流就行了。标解没有最大流，但应该差不多吧。

3A：

300 把下标按对k的余数分组。枚举总次数的奇偶性，然后每组里面贪。

500 最短路肯定是那两个联通块之间被加的新边 和 原各个联通块内的两点间最短路。状压当前已经连通的是哪些点 枚举新加哪条边。

1000 先搞出两两最短路。猜个结论：取到的硬币的顺序最多改变两次方向。。就是最多往右再往左然后一直往右。。总共就是三段，然后n^3的dp。不会证也不知道对不对。。反正能过

3B：

250 （k+1）进制。

500 等价的点组成的团先缩掉。发现剩下的每个连通分量都是链或圈，dp就好。想一想发现是能证的

1000 带边权的矩阵树定理。权为1就用字母x表示。然后行列式是一个多项式，代入几个数值然后插值搞出系数。

Celebrity:

250 小学奥数

450 若区间是[l,r]，推推式子发现l和r是能分离的。。枚举右端点就好

1000 先二分。然后构2sat。一开始想怎么构造4选1。。后来发现做不了。。然后X大爷提醒给4个小等腰三角形分别建一个点，然后对角线异或为1就好了

Semifinal1：

250 不能要的点全去掉后剩下好多段，显然每段要么全取要么全不取。段数只有n/2，暴力枚举取哪些。

450 只有能表示成若干个阶乘数的乘积的才可以。估计是构造姿势不对，点数超了。。最后压到了199

1000 就是一堆圆和矩形的交再求和。。考虑四分之一圆会方便些，然后就水掉了

Semifinal2：

300 W能切成若干个极小的段（不能再分的）。每段的结构肯定是两边共有h列是竖着贯通的，中间夹着h个横着，其余也都是竖着的。（如果高度等于h那么也可以全是竖着的。。）

500 弄出边双连通分量，每个分量显然能互通。然后暴力枚举看有没矛盾

850 弄出递推式写成生成函数，然后可以O(D)。

Wildcard:

275 搞出所有2的幂次在哪（只包含一个1的），特征是所在的行刚好有2^{n-1}个1。然后就全部出来了。

750 先考虑naive的dp，f[n][m]，总共有c^{nm}种，减掉其中不合法的话就需要枚举行有多少等价类列有多少等价类，大概就是乘上第二类斯特林数嘛，这样总共是n^4的。然后发现可以反演。。第二类反演过去就是第一类乘上-1的幂次。因为是二维的，得固定一维反演再反演另一维。这样就是n^2了。

1100 记到达每个点的剩余最大能量。。每个点拆成4个方向的点用来扩展，花样BFS可以搞到O(NM)。

Final：

350 考虑一下每一条边被走过的次数（有向的，正负抵消）。一个格子的转圈数就是它正上方的边的走过次数之和。。然后判每个点是否平衡。。然后再把各个连通块连起来

550 顺序肯定是加速度降序。。排好序的话答案是0.5\sum{x_i y_i}+\sum_{i<j}x_i y_j。一开始SB。。在最大割的路上愈走愈远。。。其实由于值域挺小，可以DP。按x/y（x>y)的升序加进去，那么始终是序列的中间一段，每次在左边或右边添加。状态是摆在分母的数字之和，记最大ans。

1100 好难啊。。。根本不会做。。题意大概是“一堆等长的区间。。。每个区间可以选中它的左端点或右端点   问排序后有多少种不同的ranking。。”然后就不知道怎么办了。。。。。。。弃疗大法好