难题选讲

难题

数学

Cirno的完美算数教室

baka数：只含有2和9两种数字
问一个区间中有多少个数能被baka数整除

容斥乱搞

treecut

给定一棵n个节点的树，从1到n标号。选择k个点，你需要选择一些边使得这k个点通过选择的边联通，目标是使得选择的边数最少。
现需要计算对于所有选择k个点的情况最小选择边数的总和为多少。

如果判断是否需要砍掉一条边，只需要判断是否有点在两部分，如果有那么这条边必须被选择。
判断这条边下面包含的子树个数是否是0或者k。
共有$C_n^k$种情况，算出都不在，两种情况，一种是k个点都在这条边的下方$s_1$个点之中，一个是都在$n-s_1$个点之中，也就是$C_{s_1}^k+C_{n-s_1}^k$
枚举每一条边，可以求得结果。

求和

给出一个N($1≤N≤10^6$)，使用一些2的若干次幂的数相加来求之．问有多少种方法
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

2n情况和2n+1一样，求2n即可
$s[i]=\sum s[k]+s[i-k]$是错误的。
在拼8的时候相当于4的方案+7的方案，这是因为除以2以后因数缩小一半但是并没有什么卵用，方案数不变。
因此s[i]=s[i-1](i为奇数)，s[i]=s[i-1]+s[i>>1](i为偶数)

字符串

相似子串

两个字符串相似定义为：
1.两个字符串长度相等
2.两个字符串对应位置上有且仅有至多一个位置所对应的字符不相同
给定一个字符串，每次询问两个子串在给定的规则下是否相似。给定的规则指每次给出一些等价关系，如’a'=’b'，‘b'=’c'等，注意这里的等价关系具有传递性，即若‘a'=’b'，‘b'=’c'，则‘a'=’c'。
1<=|s|,询问次数<=300000

两个串只有一位不同，则hash差为$w*base^i$
预先存出这些数字，可以判断是否在允许范围内
不保险可以多取几个质数
如果没有只有一个不同的限制条件，
我们知道如果标记一下两个串中某一对相等关系的位置
首先考虑某一个字母，该字母标记为1，否则为0.
这样求得的两个串的hash完全相同的话，这两个串中a的位置是完全相同的。
同样对b求hash，如果两串hash总和相同，那么就符合这一组等价关系。
依次搞即可

队列变换

求与一个字符串所有循环同构的字符串中，字典序最小的字符串
a.size()<=100000

循环同构：每次将第一个放到最后一个
如果字符串长度<=2000，那么暴力的枚举一次即可。$O(n^2)$
仍然暴力的枚举，二分+hash找到最大LCP，比较大小，O(nlogn)

矩阵模板

给定一个M行N列的01矩阵，以及Q个A行B列的01矩阵，你需要求出这Q个矩阵哪些在原矩阵中出现过。所谓01矩阵，就是矩阵中所有元素不是0就是1。
n,m<=1000, a,b<=100

如果是一维的，求一下hash然后判断一下即可。
对于二维，我们不妨求出以(0,0)为左上角、(a,b)为右下角的子矩阵的hash。这样对于一个子矩阵的hash可以类似前缀和的做法求出。
而二维hash，假定base=31，

然后以算出来的结果竖着做hash，可以表示每一个矩阵的hash
知道(0,0,a,b)，要求(c,d,a,b)
先减去$(0,0,a,b)*31^{(b-d)*n}$，同理减去两块，就可以求出。

DP

逆序对数列

对于一个数列{ai}，如果有iaj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？

f[i][j]表示1~i中有多少排列方式使得逆序对数为j
i+1加入后，如果这个数放在末尾逆序对数不变，放在最前面逆序对个数变成j+i，同理可以插入到某个位置。
所以f[i][j]可以向f[i+1][j]到f[i+1][j+i]转移
那么反过来，$f[i][j]=\sum_{k=0}^{i-1}f[i-1][j-k]$
对f[i-1]这一维维护一个前缀和，就可以快速的转移。

玩具取名

Description
某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的
Input
第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行，每行两个字母,表示W可以用这两个字母替代。接下来I行，每行两个字母,表示I可以用这两个字母替代。接下来N行，每行两个字母,表示N可以用这两个字母替代。接下来G行，每行两个字母,表示G可以用这两个字母替代。最后一行一个长度不超过Len的字符串。表示这个玩具的名字。
a[i]=a[i-1]+s[i]

f[i][j]['w']表示第i个字符到第j个字符能否由字符w扩展出来
w->in，如果f[i][k]['i']，f[k+1][j]['n']，两个融合一下就是f[i][j]['w']
复杂度$O(n^3*50)$

硬币购物

一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
tot,si<=100000

如果没有限制d，那么预处理一个f[i]，表示所有情况。
那么对于不合法方案，第一枚硬币超过$d_i$枚，
减去f[s[i]-(d1+1)*c1]...这四种情况，然后其实这是个容斥。
手动容斥硬搞或者dfs的搞都可以。

//感谢cyxdalao的代码

送外卖

有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城市的直接通路的时间。
n<=15

dp[i][j]表示i号点的状态
例如，dp[4][13]表示在4这个点处，13=(1101)(2)，第二个点没走过，其它都走过。将dp预处理为INF，然后让dp[0][1]=0
如果存在一条i到k长度为z的边，那么就可以转移：$dp[k][j|(1<<k)]=dp[i][j]+z$表示包括进去k这个点。
用dp[0][1]扔到SPFA队列中不断更新其它信息，最后答案就是$dp[0][(1<<n)-1]$

混乱的奶牛

Farmer John的N(4 <= N <= 16)头奶牛中的每一头都有一个唯一的编号$S_i$(1 <= S_i <= 25,000).奶牛为她们的编号感到骄傲,所以每一头奶牛都把她的编号刻在一个金牌上, 并且把金牌挂在她们宽大的脖子上.奶牛们对在挤奶的时候被排成一支”混乱”的队伍非常反感.如果一个队伍里任意两头相邻的奶牛的编号相差超过K (1 <= K <= 3400), 它就被称为是混乱的. 比如说，当N = 6, K = 1时, 1, 3, 5, 2, 6, 4 就是一支”混乱”的队伍,但是1,3,6,5,2,不是(因为5和6只相差1).那么,有多少种能够使奶牛排成”混乱”的队伍的方案呢?

dp[i][j]表示最后一个数字是i，哪些数字被使用过压缩为j

for(int t=0;t<=n;++t){
    if(((j>>t)&1)==0)//第t维没有使用过
        if(fabs(t-j)>k)
           dp[t][j|(1<<t)]+=dp[i][j];
}
cout<<dp[i][(1<<k)-1];

牧场安排

Farmer John新买了一块长方形的牧场，这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12)，每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当的贫瘠，不能用来放牧。并且，奶牛们喜欢独占一块草地的感觉，于是FJ不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。当然，FJ还没有决定在哪些土地上种草。 作为一个好奇的农场主，FJ想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择。当然，把新的牧场荒废，不在任何土地上种草，也算一种方案。请你帮FJ算一下这个总方案数。

思考能否根据上一行信息确定下一行，例如1010->0101不能1000
判断一下能否转移即可，即dp[i][j]->dp[i+1][k]是否合法，$k\in[0,(1<<N)-1]$
比如说，$dp[1][3]$，k枚举0~15，符合条件就是可以转移的。
初始状态为$dp[0][0]=1$.

互不侵犯

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。n<=9

dp[i][j][t]表示前i行放入j个国王，第i行状态为t
枚举下一行状态即可。
结果就是dp[N][k]

集合选数

《集合论与图论》这门课程有一道作业题，要求同学们求出{1,2,3,4,5}的所有满足以下条件的子集：若x在该子集中，则2x和3x不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数n≤100000，如何求出{1, 2,…, n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就交给你了。

a影响的数字是$2^j$与$3^k$
例如，1 2 3 4 5 6 7 8 9 10
分为两类：1 2 3 4 6 8 9、5 10、7
将这三类拼接起来，然后乘法原理
对于每一类：
..
4 ..
2 6 ..
1 3 9 ..
设计这样的形式。横着差3倍，竖着差2倍如果两个数不相邻，一定是合法的方案。
由于$log 100000$与$log_3 100000$都比较小，就相当于在一个矩阵中选不相邻的数的计数。也就是普通的状压dp。

windy数

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

每100w个预处理一次，打个表，可以在规定时间算出来。
正解：
区间减满足，相当于只求上限，即1~B-1~A
统计长度8位的合法情况
dp[i][j]第i位数字上一位数字为j，合法情况有多少。
例如，对1536，我们考虑的就是1000~1536多少合法
第一位不考虑，第二位为3、4打头的，然后统计152、151、150打头的...这样的方案数。这样可以考虑所有情况。
前三位的在之前的dp中已经求了一次，直接加上即可。

图论

欧拉图

能一笔画的图。
对于一个连通图判断每一点度数是不是偶数，如果只有两个或0个是奇数就是欧拉图。如果是两个奇数那么就是起点和终点。
DFS输出欧拉回路：向其它层搜索，如果一个点的所有边都被访问过那么就输出这个点，然后回溯。

舒适的路线

Z小镇附近共有N$(1<N≤500)$个景点（编号为1,2,3,…,N），这些景点被M$（0<M≤5000）$条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

固定路线最大值，然后加边，判断是否联通用并查集维护。

星球大战

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

要求的是一棵树的摧毁，很难搞，可以倒着来，也就是一棵树的重建。
并查集维护即可。

飞行路线

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？
2<=n<=10000,1<=m<=50000,0<=k<=10.

k=1时，在跑SPFA时，要松弛dist[i][1]，那么可以转换到dist[i][0]与dist[i][1]表示这一段不使用或使用免费机会。而对dist[i][0]，只能转移到dist[j][1]。
推广时，可以用第二维维护还剩下几次免费机会。
这种思路叫做裂点。

架设电话线

Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。
FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。
第i对电话线杆的两个端点分别为$A_i$、$B_i$，它们间的距离为$L_i$ (1 <=$L_i$<= 1,000,000)。数据中保证每对{$A_i$，$B_i$}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。
经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过K对，那么FJ的总支出为0。
请你计算一下，FJ最少需要在电话线上花多少钱。

考虑裂点的做法。如果使用免费机会就不计入max，否则求一次最大值，与上一道题类似。但是这样会T。
如果二分答案t，使得大于t的免费，小于t的收费，也就是判断一条路径边权>=t的数量<=k。对大于t的新建1，否则新建0，然后跑一次最短路，也就是至少要经过几条边权>t的边。

墨墨的等式

墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
N≤12,0≤ai≤5*10^5,1≤BMin≤BMax≤10^12

满足区间减性质，只考虑上限。
跑SPFA，dist[0]设为0，其余设为无穷。那么转移$u->(u+a_i)\%a_n$，如果$u+a_i>a_n$费用是1否则是0.
这是因为将所有数字按取模$a_n$分类，$k_{min}a_n+t$存在正整数解，那么$k_{min}a_n+t+a_n*m$是合法的。而寻找每一类最小的$k_{min}$，就是最短路可以求出的东西。也就相当于类与类之间求最短路。

其它

理想的正方形

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

确定上边和下边的位置后该正方形是确定的。
预处理每个端点向上和向右最大的值，也就是单调队列。
求出以每一个点为右端点，然后两次求单调队列。
（没听懂

也可以二维st表。
f[i][j][k]表示以[i][j]为右端点，向上、向左$2^k$个长度的矩阵最小值。
普通的倍增转移即可。查询时可以将一块转化为4块，这样也是O(1)的。

上升序列

对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ax2 < … < axm)。那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。任务给出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.

如果k时符合条件的点，那么就是判断是否存在Li的序列。
可以预处理时逆着求LIS，然后得到每个顶点的最长上升序列值。
判断一下即可，然后取比较小的，就得到了第一个数。
对第二个数，找一个> Li-1且在上一个数的后面的大于ai数，扫一遍。
$O(nL_i)$，会T。

所有数字按字典序排序，然后找第一个，从这个位置开始找第二个。
然后检验合法性，这样可以贪心的往下找。
例如，1 2 3 4预处理结果为2 2 1 1，排序后结果为1 2 3 4
如果长度为2，那么1的结果是2是符合条件的，然后去扫，2不符合，3符合，3就一定是所求。

后记

于是八天就这么结束了。
感谢各位的支持，以及感谢hzk大佬，没有您的话我真的坚持不到现在。
作为一名蒟蒻，许多东西没有学过，许多东西不会写。想要做这个笔记，初衷其实只是为了强制自己不要溜神，尽力听懂，及时提问。虽然最后还是有很多没有搞明白的东西，orzzz。
出于这样一种自私的目的，这种蒟蒻笔记的价值并不算大。如果能在各位神犇复习的时候提供一点点微漠的帮助，就是在下的荣幸。
如果有什么错误或者想要补充的东西的话请尽管联系在下。在下会怀揣着犬马惧怖之情听取您的意见的。在下的qq：1614868321
最后祝愿各位NOIP能考出好成绩。
（在下的blog：blog.csdn.com/lirewriter 相当辣鸡的博客，请无视就好）