day7 难题选讲

清北学堂--刷题班

2017.10.6-2017.10.7

10.6晚

Cirno的完美算数教室

容斥原理，大多数用不了几个

相似字串

定义：长度相等，对应位置有且仅有至多一个位置的字符不同。
给定等价关系，
具有传递性:'a'=='b','b'=='c',则'a'=='c'

判断是否相等

O(Len) 暴力判断
可以hash判断两个字串是否相等，O(1)

判断长度

strlen

判断相差一个

A = aca
B = aba
hash[A] - hash[B] = 31;
两个是否相似，即：两个串是否相差31的几次方，或者小于31（最后一位不同）

判断是否相似

对于两个串，只含abc
等价关系'a'=='b'，'c'
s1
s2
把'a','b'都标出来，看出现的位置是否相同，然后比较'c'的位置，判断是否相同

判断是否出现的位置是否相同

按照字母分类，
对于字母'a'，若果不是'a',为0，
如果hash值相同，则出现的位置一样
对26个字母都做一次，判断是否重合

等价关系：
对于'a'=='b'

s1: h1 = hash1[a]+hash1[b]，//a，b在s1出现的位置hash值
s2: h2 = hash2[a]+hash2[b]。//a，b在s2出现的位置hash值
判断: 若h1==h2 则相同，
比如：
s1 = aaba hash1[a] = 31^0+31^2+31^3 hash1[b] = 31^1
s2 = abaa hash2[a] = 31^0+31^1+31^3 hash2[b] = 31^2
所以，h1 = h2;

treecnt

n个点的树，选k个点，选最少的边，所有k个点情况

性质：一条树上的边如果删掉，则分成两部分。
所以：这样的边保留。
特殊点在两部分

考虑：每条边什么情况下被保留

总情况C(n,k)
算出不合法的情况,
分成两部分后，不合法的情况,就是都在一边，设一边为点数为s1,另一边则是n-s1
C(s1,k)+C(n-s1.k)

不合法情况：C(n,k)-C(s1,k)+C(n-s1.k)

求C（特别大），带取模。

C(n,k) = n!/(n-k)!k!
对(n-k)!k!求逆元

动规

逆序对数列

题目：求逆序对数为k的自然数数对有多少个。

状态:
f[i][j]表示1~i内的数字，有多少排列使得逆序对数为j。
转移:
当前状态1..i 逆序对为j。
对于i+1,放在开头就是i+k个逆序对。
那么，在中间的某个位置，加入数字i+1，也是可以算出。
f[i][j] -> f[i+1][j] ~ f[i+1][i+j]
n^3

优化

f[i][j] 由 f[i-1][j]~f[i-1][j-i+1] 推出
f[4][4] ~ f[4][8] = f[5][8]
前缀和优化（其他：四边形不等式优化，优先队列优化，数据结构优化）

玩具起名

题目:WING四个字母起名，每个字母可以变成两个字母（WING中的）
给定字符串，求初始的字母

区间动态规划

状态：
f[i][j][W/I/N/G] i...j字符串能都由W/I/N/G转移过来。 = true / false
转移
w -> in
f[i][j]['w'] = true;
f[i][k]['i'] & f[k+1][j]['n'] -> f[i][j]['w'];

状态：n^2*4
转移：n*4^2

硬币购物

题目：
四种硬币，面值c1,d2,c3,c4;
买东西tot次，每次带di枚ci硬币，买si的东西，每次由多少付款方法。
即：询问tot次，拼成si的方法。
tot，si <= 100,000;

容斥

首先，求出没有硬币限制的情况下，si的方案数，含有不合法的情况
求硬币超过di，拼成si的方案数，
如果超了di，先用了，然后
f[i]没有限制，拼成i的方案数，
f[si-(d1+1)*c1]用掉了d1+1枚c1。
2^4 枚举强制用超了的情况，减掉。
ans = f[si]-f[si-(d1+1)*c1]-f[si-(d2+1)*c2]...
+f[si-(d1+1)*c1-(d2+1)*c2]]...
-f[si-(d1+1)*c1-(d2+1)*c2-(d3+1)*c3]...
+f[si-(d1+1)*c1-(d2+1)*c2-(d3+1)*c3-(d4+1)*c4]

图论

欧拉图

欧拉回路： 回到原点，走完所有的边
判断：联通块，判段度数是否为偶数，只有两个点度数是奇数
欧拉路径： 把所有边走完
判断：只有两个点度数是奇数

输出欧拉路径：深度优先搜索。

10.7

舒适的路线

先排序，速度大的在前，先枚举
加边，并查集判断是否联通

星球大战

反着做
假设先摧毁，一个一个的加点

架设电话线

二分答案，

飞行路线

裂点，分成是否用k次机会
dis[][]

理想正方形

A*B的矩阵，找一个n*n的矩阵使得最大值-最小值最小

考虑对于上面的边和下面的边，预处理每个点作为右下的端点，向上n个长度的最大值与最小值，单调队列
以每个数作为右端点向左N个长度，最大值最小值
整体二分，二维线段树，
二维st表f[i][j][k] 以i,j为右下角，向上向左2^k长度，最大值最小值。
查询：由四个转移，左上左下右上右下的矩阵

上升序列

【bzoj1046】[HAOI2007]

　以每个数字作为端点，需要后面是否存在一个长度大于等于Li，的序列，
倒着做一个下降序列，就是以每个点向后最长的序列，遛遛遛！！！。
第一个数，取最小的即可，第二个数去最小的，扫一遍即可，扫n遍

优化

找所有合法的，且字典序小的。时间Ln
当前确定的数字是ai,后面的一定要大于ai，
先按字典序，（从小到大）排序，往后找，
可以找到第一个，
向后找第二个，找到的数一定，判断是否能作为第二个

a = 2143
b = 2211 //倒着做一个下降序列
Li = 2； //询问
排序：1234 //权值大小
1可以作为第一个b[1] = 2 >= Li;
判断2，2的坐标是1不行，3可以，4也可以