虽然省选和我没有任何瓜葛，我依然抱着$NOIP$般的热情去对待，因为谁都不知道省选之后会发生什么。
当然，我也不知道。也不用去知道，只需要做好当下，每一步不会让未来的自己后悔就行了。
这次省选的目标是不要打暴力，这对于专攻数据结构的$NERLCI_$同学似乎太简单了，但对于肝了3个礼拜网络流的我来说仿佛登天，因为网络流的题目只有0分和满分。。
这次复习硬说的话从两个礼拜前就开始了。
$(19/03/22)$陈老师的练习1
虽说是NOIP模拟赛但是题目还是很良心的。。考场死磕最难的规律题结果后面两道USACO大水题没写。。
还是策略问题吧，省选倒是不存在这种事情，暴力就完事了。
$T1:$斐波拉契表示
题面：
每一个正整数都可以表示为若干个斐波那契数的和，一个整数可能存在多种不同的表示方法。
定义F(n) = n的最短表示中的数字个数，F(14) = 2，F(100) = 3（100 = 3 + 8 + 89），F(16) = 2（16 = 8 + 8 = 13 + 3）。
定义G(n) = F(1) + F(2) + F(3) + …… F(n)，G(6) = 1 + 1 + 1 + 2 + 1 + 2 = 8。给出若干个数字n，求对应的G(n)。
分析：
陈老师把它放在第一题搞的我以为找规律不是挺简单的吗，结果肝了我1个半小时。。
但这也说明自己找规律还是太弱了，没数学敏感性，但这也没办法。。
首先你可以把这个$F(n)$的表给打出来，由于n为斐波拉契数时函数值为1，于是看看每隔一个斐波拉契就按个回车，得到以下情况：
1
1
1 2
1 2 2
1 2 2 2 3
1 2 2 2 3 2 3 3
1 2 2 2 3 2 3 3 2 3 3 3 4
....
根据上表我们可以发现
第$i$行的长度为第$i-1,i-2$长度和，且长度满足斐波拉契数列。
设$A[i]$是第i行的序列，可以发现$A[N]=A[N-1]+{A[N-2]+1}$，其中${A[N]+1}$表示第n行每个元素都加1。
由2可知，每行的前缀均为上一行。
我们可以利用块的思想，按照斐波拉契数列长度来分块，并维护以下的信息：
q1[]-->块开始的斐波拉契编号。
q2[]-->块的长度
q3[]-->块的和
q4[]-->块的前缀和
对于每一个询问$N$，先确定他属于哪一个块(q1确定)，在通过递归求解，由于块个数不会超过100个，所以代码近乎常数。
定义状态为dfs(add,ans,x)，add作用待会提，ans是当前答案，x是还剩的元素个数。
通过枚举找比当前长度小的最长块，把当前块的和加上，长度减去块的长度，思路就这样。
但是由于规律2，我们发现每递归一层，序列就会集体+1（好比如我们递归的是A[N-1]，算A[N-2]的时候会增加）。于是我们搞一个add，随递归深度增加，于是算答案时候顺便加上块长*add即可。
怎么这么长啊。。
$T2:$ [USACO19JAN]奶牛诗人
题目描述：
Bessie认识N（1≤N≤5000）个单词，她想要将她们写进她的诗。Bessie已经计算了她认识的每个单词的长度，以音节为单位，并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。
Bessie的每首诗由M行组成（1≤M≤10^5），每一行必须由K（1≤K≤5000）个音节构成。此外，Bessie的诗必须遵循某个指定的押韵模式。
Bessie想要知道她可以写出多少首符合限制条件的不同的诗。
样例输入：
3 3 10
3 1
4 1
3 2
A
B
A
输出：
960
分析：
就是加法，乘法原理的运用，首先你要把样例搞懂，这题概念太多。
对于韵脚$A$，以1为单词，则有如下情况：
1 3 1
3 1 1
1 2 1
2 1 1
对于以2为单词也有4种，所以对于韵部1共8*8=64种方案填A。
对于以3为单词结尾的情况：
1 1 3
1 2 3
2 1 3
2 2 3
所以对于韵部2的方案有4*4=16种填A，对于韵脚A有64+16=80种。
对于韵脚$B$，以1，2为单词方案同上，共8+4=12种，共80*12=960种。
于是得到一般公式：
$$\prod _{i=1}^{cnt1} (\sum _{j=1}^{cnt2} f[j]^{s[i]} )$$
其中$cnt1$是韵脚数，$cnt2$是韵部数，$g[j]$是以第j个韵部为结尾的方案数，$s[i]$是第i韵脚的方案数。
对于$g[j]$，等价于选k个数使其和为m的方案数，是一个经典的背包模型。
可以通过$f[i-s[j]]$来转移。
然后就是套一下卡苏米的事情了。。
关键代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll find(ll p)
{
ll ans=0;
for (int i=1;i<=n;i++) if (g[i]) ans=(ans%mo+pow(g[i],p)%mo)%mo; return ans;
}
int main()
{
cin>>n>>m>>k; f[0]=1;
for (int i=1;i<=n;i++) cin>>s[i]>>c[i];
for (int j=0;j<=k;j++)
for (int i=1;i<=n;i++) f[j]+=f[j-s[i]];
for (int i=1;i<=n;i++) g[c[i]]+=f[k-s[i]];
//以上背包DP
char c;
for (int i=1;i<=m;i++) cin>>c,sum[c-'A'+1]++;
for (int i=1;i<=26;i++)
if (sum[i]) ans*=find(sum[i]);
cout<<ans<<endl;
return 0;
}
$(19/03/29)$陈老师的练习2
每周日其实是有专门的省选模拟赛的，，可惜蒟蒻是真的一题不懂，于是不如自己刷刷题。。
$T1:$货物运输
题目描述：
其中有$m$种物资的运输方案，每种运输方案形如$l_i,r_i$。表示存在一种货物从$l_i$运到$r_i$。
这里有$n$个城市，第$i$个城市与第$i+1$个城市相连，每条道路需要耗费1点时间。
由于高科技的存在，小Y想到了一种节省时间的好方案。在X号城市与Y号城市之间设立传送站，只要这么做，在X号城市走到Y号城市不需要耗费时间，同样的，从Y号城市走到X号城市也不需要耗费时间。
但是为了防止混乱，只能设立这么一条传送站。
现在这些运输方案同时进行，小Y想让最后到达目的地的运输方案时间最短。
分析：
由于端点的不确定性，很难去确定某个算法，我们不妨先固定一个端点在进行思考。
加入确定了左端点$L$，对于右端点的选取肯定是一个有极点的答案，于是直接三分我们可以二分答案啊！！
假设$now$为当前最长的路径，则任意路线都满足：
$$|x_i-s|+|y_i-t|<=now$$
其中$x_i,y_i$为路径端点，$s$为我们确定的左端点，那对于右端点的选取，我们带入绝对值后可得（设$x_i-s=k_i$）：
$$k_i+y_i-now<=t<=now+y_i-k_i$$
于是我们枚举所有路径并缩小t的范围，若最后不等式有解则成立。。
现在我们考虑两端点都不确定的情况，仍可二分答案！
假设$now$为当前最长的路径，则任意路线都满足：
$|x_i-s|+|y_i-t|<=now$
对于两个绝对值都把他拆开，得到一个四元方程：
$\left\{\begin{matrix}
x_i - s + y_i - t <= now
\ s - x_i + y_i - t <= now
\ x_i - s + t - y_i <= now
\ s - x_i + t - y_i <= now
\end{matrix}\right
$
$
\left\{\begin{matrix}
x_i + y_i - now <= s + t <= x_i +y_i + now
\ x_i - y_i - now <= s - t <= x_i - y_i + now
\end{matrix}\right
$
于是类似上面这样缩小范围即可，特判两式取等情况。
最后一礼拜
由于学的少的缘故，复习的知识也很少，并不确定能不能用上。。
主席树：
之前只做过板子，以为必须套在权值线段树上，现在想想只要是可以有时间轴表示，用前缀和套的都可以上主席树（核心还是维护每个节点的历史状态）。
比如这题，【USACO】逃跑的Barn：
就是问你子树里面深度在$[1,k]$范围内点的个数，如果没有子树的限制就可以上线段树，以深度为下标，通过一个 dfs 找到并顺手维护当前深度的点个数。
有了子树的话就可以用主席树维护，可以用前缀和的思想挖一个子树出来，若以dfs序为编号的话，那么以$x$为根的子树点的范围就是$[dfn_x,dfn_x+s_x-1]$。
但由于此题深度太大，故先离散化。。
可以把板子的思路记一下：
- 建一颗空树，根为$rt[0]$。
- 以dfs序（或其他顺序）遍历，每节点建一颗主席树，一开始左节点右节点接到上颗树上，然后从上向下建树（跑一链）并修改对应的左右节点
- 查询时确定前缀和的范围节点，用动态开点线段树搞就行了。。
高斯消元
又一个不会考的东西。。
三步走：找系数最大，暴力删点，倒序算答案。
判无解可看一行式子：
- 若所有系数（包括常数）为0是无限解。
- 若除系数所有系数为0就是无解。
网络流
这东西要么0分要么AC啊，，把之前的习题集锦看看。。
数论（exgcd,线性逆元,LUCAS,中国剩余定理）
$1.~ $卢卡斯本质就是进制的转换，若p为质数，则：
$$lucas(n,m)=lucas(n/pp,m/pp)*lucas(n\mod pp,m\mod pp)$$
$2.~ exgcd$本质就是利用求最大公约数的方式递归求不定方程解，有个公式推一下可得：
$$a=b; b=a-(x/y)*b$$
套就行了。
$3.~ 线性逆元$本质还是推式子，而且很好推：
$$inv[i]=(p-p/i*inv[p\mod i])\mod p$$
$4.~$中国剩余定理本质依然推式子：
对于每个式子构造一组解，则可以凑出
$$\sum _{i=1}^n a_i*M/p_i*inv[M/p_i]$$
其中$a_i$为系数，$p_i$为模数。
缩点割点
缩点本质还是递归找深度，如果一个点能跑到比父亲还早到的地方去，那肯定在一个环内。开栈弹出即可。
割点本质是一个点没有一个子代能跑到自己上面去，或者是根节点且有好du儿子。