DAY 1：
一上来就考试，考得很难，不记得多少名了。
T1
题意：
有 \(N\) 个节点，第 \(i\) 个节点上有 \(d[i]\) 个本质不同的孔，现在用 \(N-1\) 条边将 \(N\) 个节点连成一棵树（一个孔只能使用一次），定义两棵树相同当且仅当对于每一条边，它插入的两个孔在两棵树中相同。问可以连出多少不同的树，对 \(M\) 取模。
解题思路
考虑对于每一个非根节点，定义它连接父节点的孔为特殊孔。对于根节点，选取一个与儿子相连的孔为特殊孔。
红色为特殊孔
对于每一个特殊孔，它的选取是独立的，所以选取特殊孔的方案数是 \(\prod_{i=1}^{n} d[i]\)
考虑只要每一条边连接的两个孔相同，这条边就是唯一确定的。所以只需对于每一个节点算出它选父节点的孔的方案数，乘法原理求解即可。
先考虑孔可以重复的情况。令\(S=\sum_{i=1}^{N} d[i]\)在 \(Prufer\) 序列中，每一个节点有 \(S-N\) 种方案选取父节点（ \(N\) 个已选的特殊孔），则共有\(\left ( S-N \right ) ^{\left ( N-2 \right ) }\)种方案。但孔不能重复使用，所以对于第 \(i\) 个节点，方案数需减去前 \(i-1\) 个节点选过的父节点，即方案数为\((S-N-i+1)\),即选取父节点的方案数为\(\prod_{i=1}^{n}\left ( S-N-i+1 \right )\)
根据乘法原理，答案为\(\prod_{i=1}^{n} d[i] \times \prod_{i=1}^{n}\left ( S-N-i+1 \right )\%M\)
CODE:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,mod;//N，模数M
int sum=0;//S
int kv=1;//累乘计数器
int d[1000001];
signed main(){
cin>>n>>mod;
for(int i=1;i<=n;i++){
cin>>d[i];
sum+=d[i];
}
for(int i=1;i<=n;i++){
kv*=(d[i]%mod);
kv%=mod;
}
for(int i=1;i<=n-2;i++){
kv*=((sum-n-i+1)%mod);
kv%=mod;
}
cout<<kv;
return 0;
}
T2
题意：
给定一个正整数序列，将它划分成了最少个连续子段，使得每段的元素都严格递增。给定原序列中数字的值域，每个数字的出现次数和分出的子段数，求有多少种可能的原序列。
第一行两个整数N,K分别表示原序列值域与最少划分段数。
第二行N个整数，第i个整数 $a_{i} $ 表示原序列中i的出现次数。
解题思路
先设 $f\left ( k \right ) $ 为至少有k个，但不一定恰好有k个严格递增子段的方案数。
先不考虑空的集合不合法，将数随机填进这k割几何中，方案总数是\(\prod C_{a[i]}^{k}\)
再考虑减去重复的方案数,对于任意的一组i<j,f(j)的构造方案都有可能有j-i个空子段。
考虑插板法，令\(tot=\sum a[i]\)系数为\(C_{i-j}^{tot+i-j}\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int c[5001][5001];
int n,k;
int a[100];
int dp[5001];
int tot;
void pre(){
for(int i=0;i<=5000;i++){
c[i][i]=c[i][0]=1;
}
for(int i=1;i<=5000;i++){
for(int j=1;j<=5000;j++){
c[i][j]=c[i-1][j]%mod+c[i-1][j-1]%mod;
c[i][j]%=mod;
}
}
}
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
pre();
for(int i=1;i<=n;i++){
tot+=a[i];
}
for(int i=1;i<=k;i++){
dp[i]=1;
for(int j=1;j<=n;j++){
dp[i]=dp[i]%mod*c[i][a[j]]%mod;
dp[i]%=mod;
}
for(int j=1;j<i;j++){
dp[i]-=(dp[j]%mod*c[tot+i-j][i-j]%mod);
dp[i]+=mod;
dp[i]%=mod;
}
}
cout<<(dp[k]+mod)%mod;
return 0;
}
DAY 2：
今天金天讲数据结构，舒心结构几乎每道题都要用，听课是听懂了，代码很难写，自习的时候就感觉很烦。
DAY 3：
还是数据结构专题，记得最清楚的就是曼哈顿和切比雪夫距离的Trick：
T1 Ice-cream Tycoon
题意：
一个商店，有两种操作：
-
（1）ARRIVE n c表示进货n个，每个c元。
-
（2）BUY n t表示一个买货的人要买n个，一共拿了t元钱。如果现在店里的货的数量大于等于n且最便宜的n个的价格小于等于t则将最便宜的卖给他。否则不卖。
思路:
简单题，一个线段树，节点存储货物的数量和价格，每次计算价格的时候向上更新总数和价格，用一个标记记录这段区间有没有卖掉
T2 New Year Tree
题意：
给出一棵 \(n\) 个节点的树，根节点为 \(1\)。每个节点上有一种颜色 \(c_i\)
\(m\) 次操作。操作有两种：
- \(1 u c\)：将以 \(u\) 为根的子树上的所有节点的颜色改为 \(c\)。
- \(2 u\)：询问以 \(u\) 为根的子树上的所有节点的颜色数量。
思路：
把dfs序存在pos数组中，并把每个节点第一次遍历到的时间点和第二次遍历到的时间点存到in和out数组中，这样就成功地把一棵树转换为了线性结构。对一棵子树进行操作时，只需对这棵子树的根节点两次遍历到的时间戳中间的部分进行操作即可。考虑到60位正好小于Long Long范围，状态压缩放到线段树上,把它分解
T3 Ping-Pong
题意：
有一个区间的集合，初始为空。当 \(c<a<d\) 或 \(c<b<d\) ，且 \((a,b),(c,d)\) 都在集合中时，你可以从区间 \((a,b)\) 移动到 \((c,d)\)。你需要支持下面的操作：
-
\(1 x y\)，加入一个新区间 \((x,y)\)。保证加入的区间长度严格单调递增。
-
\(2 a b\)，询问是否能从第 \(a\) 个加入的区间移动到第 \(b\) 个。
操作数 \(1≤n≤10e5\)，保证其他任何数字都是整数且不超过 \(10^9\)。
解法：
首先考虑两种移动的情况：
-
1.两个区间相交但并不包含
-
2.一个大区间包含一个小区间
对于1情况，这两个区间是可以互相到达的，对于2情况，我们可以从小区间跳到大区间，而不能从大区间到小区间。
1询问不太好想，考虑建一棵线段树，在插入新的区间之前有若干合并过的区间，那么在线段树上找一个节点打上标记，考虑新加入的区间长度严格单调递增，所以必定不被另一个区间所包含。所有右端点在该区间左端点右方或者左端点在该区间右端点左方的区间都是应与该区间合并的。使用并查集，把合并了的旧区间标记删除（最多logn个），打上新区间的标记。
对于2询问，我们直接从包含这个区间的合并区间往上跳包含它的合并区间，看能否跳到包含目标区间的合并区间。
T4 Life as a monster
题意
在一个王国里，有N个人。第i个人住在一个点上（xi, yi）。你是一个怪物，需要绕过王国，抓住所有N个人。
你从某个点开始（u，v）。
在1秒内，你可以从点（u，v）移动到点（u'，v'），其中|u'-u|≤1，|v'-v|≤1。这意味着在1秒内你可以移动到8个相邻的点。你也可以停留在同一位置（这毫无意义）。
你的旅程将是这样的：
你从（u，v）开始
你走到(x1, y1)的第一个人面前，立即抓住他。
然后你需要回到你的家，并休息2秒。
然后你去找位于（x2，y2）的第二个人，立即抓住他。
然后你需要回到你的家，休息2秒。
这样重复下去，直到你抓到所有N个人。
你必须处理2种类型的Q查询：
0 - 第i个人移动到某个新点（xi', yi'）。
1 - 如果你从点（u，v）开始，完成旅程的最短时间是多少？
在这个问题中，你将得到整数BASE和多个查询。你将不得不设置初始值T=0。
0类型的查询意味着指定的人移动到点（（a1 * T + b1）%BASE，（a2 * T + b2）%BASE）。
对于类型1的查询，你需要输出捕获所有的人的旅程的最小时间，如果你将从坐标（（a1 * T + b1）%BASE，（a2 * T + b2）%BASE）开始。你应该用计算出的时间更新T的值。
在第一行输入中，有三个整数N、Q和BASE（0≤N、Q≤105，0≤BASE≤109。在接下来的N行中，有两个整数xi和yi（0≤xi, yi≤BASE）--人们的坐标。
在下面的Q行中，有以下类型的查询：
0 i a1 b1 a2 b2
1 a1 b1 a2 b2
其中i是人的索引（1≤i≤N），a1、b1、a2、b2是前面提到的值（0≤a1、b1、a2、b2≤109）。
解题思路
考虑抓每一个人都是独立的，只需要找到去每一个点的最短距离\(\times2\)(要回来)，再加上2N-2秒的休息就行了。
Part 1 如何使抓人移动次数最短
根据题意，每一次移动可使横纵坐标之差分别减去0或1，所以移动次数最短就是横纵坐标差的最大值。
如下图，假设怪物在(-1,-1),人在(3,2),那么横坐标差了4，纵坐标差3，最少移动次数为4。
Part 2 如何计算
看上去速度很快，实则1e10。
设怪物所在位置为(x1,y1)，要抓的人在(x2,y2)，移动次数为S，根据Part1有：
$ S=max\left ( |x1-x2|,|y1-y2| \right )\( \)=max\left ( x1-x2,x2-x1,y1-y2,y2-y1 \right ) $
其实就是切比雪夫距离，我们知道切比雪夫距离和曼哈顿距离是可以互化的。
对点(x,y),把它转化为点(x+y,x-y),此时怪物在(x1-y1,x1+y1),人在点(x2-y2,x2+y2)
此时计算曼哈顿距离为
$max\left ( x1+y1-x2-x2,x2+y2-x1-y1,x1-y1-x2+y2,x2-y2-x1+y1 \right ) $
化简一下：
$max\left ( 2x1-2x2,2y2-2y1,2y1-2y2,2x2-2x1 \right ) \(，是所求的两倍！！（返程不用\)\times2$了）
剩下的交给动态二维偏序
T5 Tourists
不会
T6 New Year and Conference
题目描述
充满快乐的，Hyunuk将要举办一个关于将来的一年有多伟大的大会！
大会有 \(n\) 个讲座。Hyunuk有两个可供选择的会场\(a\)和\(b\)。对于n个讲座中的每一个，演讲者选择了两个时间区间\([sa_{i},ea_{i}]\)（\(sa_{i} \leq ea_{i}\)）和\([sb_{i},eb_{i}]\)（\(sb_{i} \leq eb_{i}\)）。如果大会在a会场举办，那么讲座就会在\(sa_{i}\)到\(ea_{i}\)的时间举行；如果大会在b会场举行，那么该讲座就会在\(sb_{i}\)到\(eb_{i}\)的时间举行。Hyunuk只能选定两个会场中的一个，然后所有讲座都要在那个会场举行。
两个讲座被称为冲突，当且仅当它们共用了同一个时间点。正式地，我们称一个在区间\([x,y]\)中举办的讲座和一个在\([u,v]\)区间举办的讲座冲突，当且仅当\(\max(x,u) \leq \min(y,v)\)。
我们称一个听众可以参加所有讲座的一个子集\(s\)，当且仅当这个子集中任何一对讲座都不冲突。注意：是否能参加这个子集\(s\)的可能取决于Hyunuk选择的是\(a\)会场或是\(b\)会场来举办大会
对于一个子集\(s\)，若在一个会场，观众可以参加，而在另一个会场，观众却不可以参加，那么它被称为“会场敏感的”。
对于观众来说，是否存在一个会场敏感的子集\(s\)是一个重要的问题，因为观众无法确定讲座时间是否会冲突。Hyunuk会开心当且仅当不存在任意一个会场敏感的子集。请判断Hyunuk是否会开心
解法：
我们考虑给每一个讲座一个随机值\(v[i]\),两个讲座冲突就加入\(v[i]\times v[j]\)的贡献，最后比较一下两个会场的贡献大小就行了。使用扫描线，每一扫到讲座的开始就把\(v[i]\)加入当前的可贡献SUM，扫到结束就从SUM里删除；搜到一个讲座开始计算\(v[i]\times\)之前的SUM的贡献。
DAY 4：
进入了数论专题，这回是彻底反过来了，感觉题目很可做，可是上课很难听懂，朱富海教授讲高等数论。（其实也不是很高等，可是教授痴迷于证明）
DAY 5：
上午模拟测试，感觉还好，出现了哈希和并查集，记得这次T1挂掉了，排名好像还可以。下午还是讲数论，很多同学都改题去了。一开始的题单竟然是a+b problem。
T1 Strange Limit
题意：
给你两个数p，m，计算bn的极限，其中bn等于an对m的阶乘取模，而an = ppp...
解法：
欧拉定理直接递归求解就行了
T2 GCD Determinant
题意：
求一个gcd矩阵行列式的值
解法：
Smith在1875年首次证明了以下结果：
结论题
T4 矩阵游戏P1397
题意：
自己去看
解法：
首先这个东西其实就是求（A的m-1次方* B）的n-1次方* A的m-1次方
这个式子可以使用矩阵快速幂。对于同一行，构造：
【a 0】
【b 1】
对于同一列可以构造：
【c 0】
【d 1】
按矩阵快速幂搞就行了
T5 Remainders Game
题意：
给定n个数字，使得一个x使得x对这n个数取模的值固定，给定一个数k，问x除以k的余数是否恒定。
解法：
显然有一个结论就是对于满足对c1,c2....cn模数固定的x,x+gcd(c1,c2....,cn)肯定也满足条件，这告诉我们x对gcd(c1,c2,....,cn)取模为定值。所以显然当且仅当gcd(c1,c2,......cn)对k取模为0时，x对k取模为定值。
T6 Power Tower
没什么好说的，跟T1都是扩展欧拉定理板题
T8 Border
题意：
火星上的钞票面额有\(n\)种，第\(i\)种的价值是\(a_i\)。$Natasha $ 每个面额的钞票都有无数张。
火星人有\(k\)个手指，所以他们使用\(k\)进制。此外，火星人认为数字\(d\)（在\(k\)进制中）是神圣的。因此，如果凑出来的钱中在\(k\)进制中最后一位数字是\(d\)，火星人会很高兴。不幸的是，$Natasha $ 还不知道\(d\)是几。所以，他想知道他能凑出哪些数字。
解法：
首先显然选择的面额之和肯定是d=gcd(a1,a2....,an)的倍数设凑出的数字为c,设总和为dx,那么显然有dx与c modk同余。根据裴蜀定理，c为gcd(d,k)的倍数，有k/gcd(d,k)种c的值
Day 6:
讲图论，感觉老师讲得很好。就是感觉题目的思路很神奇，想不出来。
DAY 7：
又是一次模拟测，自己在考场上胡出来了整体二分，结果进度给卡掉了，白开心一场。
T1 避雷针 (lightning)
题意：
给定一个序列，对每个i询问使得任意非i的j满足h[j]<=h[i]+p-sqrt(abs(i-j))
解题思路：
好好的场切被ceil精度卡了。
思路是很简单的，考虑sqrt(x)的增长速度是由快变慢的，那么对于一个i，找出使得p最大的一个j。如果i增大，答案一定不在j左。考虑到这一点，整体二分即可。
T3 滑雪 (ski)
题意：
很难形容
解题思路：
因为“#”太难画了，所以用×代替，蓝色×为移动后产生的冰块，S为起点，T为终点
如果你颓多了，结论是显然的——ZYB。首先来证明上下和左右横跳一定最优。
显然一个点要不通过横跳到达相邻的点至少需要三步
而横跳只需要两步
自此，左右横跳更优证毕。我们易知返回同一个节点显然不优。那么只需要考虑每一个节点向上下左右四个相邻点的距离。分为两种情况，当前点是“.”和当前点是“#”。
- 1.当前点是"."
考虑去左边的相邻点(如果不是“#”)，其他方向是一样的，有两种情况
第一种显然只需要一次，向左连一条边权为1的边：
第二种则需要两次，向左连一条边权为2的边：
- 2.当前点是"#"
你们的代码一个比一个鬼畜——ZYB
显然我们现在只加了相邻点的边，那要没有一种可能连接不相邻的两个点呢？是有可能的,比如这一个：
#......#
考虑为什么会出现这种情况。本质的原因就是左右两个"#"，所以在遇到一个“#”后，如果上下左右相邻格为"."，从相邻两格的格子开始拓宽，向相邻格连一条边权为1的边。
下午讲完网络流，（代码还是不会写）就放假了。
DAY 8：
玩了一整天，晚自习都迟到了。
DAY 9：
杂题选讲，史无前例看出来几道题目，但最难忘的还是FSYo在课间打图寻。
DAY 10：
今天讲的杂题字符串偏多，但很多可以桶排，哈希，并查集草过去。比赛不记得怎么推迟了一天
T1 动物园
题意：
定义num[i]为一个序列前i位不重叠公共前后缀的个数，给定序列，对于每一个i求num[i]
解法：
先不考虑前后缀重不重叠的问题，那么当且仅当\(next[i]\)，\(next[next[i]]\)，\(next[next[next[i]]]......\)是这个前缀串i的公共前后缀。
如何去除有重叠的？
首先显然\(next[i] < i\)
也就是说，一旦有一个递归了\(n\)层的\(next\)，比原前缀\(i\)的长度的一半要小，那么这个\(next\)的递推出的答案\(ans\)就是\(i\)的\(num\)了
一个问题
假如我们拿到的串是1e6个'a'，那么上面那个算法就会被卡成\(O(n^2)\)
那么我们需要做一个优化，来解决这个问题，而解决问题的核心就是：减少重复递归
如同求next时一样的方法,我们将递归用的变量j的值不更新，这样，求完了i的答案以后，j的位置一定在$ i / 2$
的左边，也就是它已经满足要求了,再递归求解。
T2 字符串的匹配
题意：
定义 \({ai}, {bi}\) 相同，当且仅当它们离散化之后相同。
给定 \(a1, . . . an\) 以及 \(b1, . . . bm\)，找到所有位置 \(p\) 使得 \(ap...ap+m-1\) 和\({bi}\) 相同。\(m ≤ n ≤ 1e5\)。
解法：
我的做法，有些逆天。用一个桶排序。再套上一个哈希滑动窗口，每次检查直接乘上桶的权值即可。
T3 Sza-Template
题意：
\(Byteasar\) 想在墙上涂一段很长的字符, 他为了做这件事从字符的前面一
段中截取了一段作为模版。然后将模版重复喷涂到相应的位置后就得到
了他想要的字符序列。一个字符可以被喷涂很多次, 但是一个位置不能
喷涂不同的字符。做一个模版很费工夫, 所以他想要模版的长度尽量小,
求最小长度是多少。\(n ≤ 10e6\)。
解法：
真的我这个解法打出来就是误人子弟
T4 Country
题意：
有 \(n ≤ 26\) 个字符串变量，它们可以包含其他的字符串变量，也可以包
含小写字母（这些变量用大写字母表示）。
举个栗子：\(A=greatglorycorrect\)，\(B=xx\)，\(C=leadusgo\)，\(D=ABC\)，\(E=DDDDdjh\) ，\(F=EEEEEgoodbye\)
数据保证定义是无环的。
给定一个小写字母组成的模式串，求某一个变量所代表的字符串里这个
模式串出现了几次。模式串长度, 每条描述的长度 \(≤ 100\)
解法：
首先我们设dp[i][j] 表示当前处理到字符串i(还未与i匹配),上一次模板串匹配到j位时的匹配次数。我们就发现一件事，就是这个东西显然是可以记忆化的。我们用dfs(i,j)深搜当前的dp[i][j]（为了方便判断是否搜过先把dp数组设置成-1）。
首先我们遍历整个字符串i。对于所有大写字母，直接dfs到下一层就可以了。对于小写字母，我们直接做KMP板子就行了。
炸了的代码有大神看到请帮忙看看，十分感谢
#include<bits/stdc++.h>
using namespace std;
const int mod=10000;
int n;
int t;
char tt;
char tol[200];
string mean[30];
char c[30][100000];
int sz[200];
string comp;
int nxt[200];
int dp[30][100000];
//dp[i][j] 表示当前处理到字符串i(还未与i匹配),上一次模板串匹配到j位时的匹配次数。
int pos[30][100000];
//pos[i][j] 表示当前处理到字符串i(还未与i匹配),上一次模板串匹配到j位,匹配结束后模板串的位置。
void get_nxt(string s1){
int i=0,j=-1;
nxt[0]=-1;
while(i!=s1.size()){
if(s1[i]==s1[j] || j==-1){
i++;
j++;
nxt[i]=j;
}
else{
j=nxt[j];
}
}
for(int i=1;i<=30;i++){
for(int j=1;j<=100000;j++){
dp[i][j]=-1;
}
}
}
int dfs(int i,int j){
if(dp[i][j]!=-1) return dp[i][j];
dp[i][j]=0;
int x=j+1;
for(int k=1;k<=sz[i];k++){
if(c[i][k]>='A' && c[i][k]<='Z'){
int id=c[i][k]-'A'+1;
dp[i][j]+=dfs(id,x);
dp[i][j]%=mod;
x=pos[id][x]+1;
}
else{
int p=x;
while(p && comp[p]!=c[i][k]) p=nxt[p];
if(comp[p]==c[i][k]) p++;
x=p;
if(x==comp.size()){
dp[i][j]++;
dp[i][j]%=mod;
}
}
}
pos[i][j]=x;
return dp[i][j];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
cin>>tt;
t=tt-'A'+1;
for(int i=1;i<=n;i++){
cin>>mean[i];
sz[i]=mean[i].size()-2;
for(int j=1;j<mean[i].size();j++){
c[i][j]=mean[i][j+1];
}
}
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=sz[i];j++){
cout<<c[i][j];
}
cout<<endl;
}*/
cin>>comp;
get_nxt(comp);
dfs(t,0);
cout<<dp[t][0]<<endl;
return 0;
}
T9 Substrings in a String
题意：
单点修改，每次问一个串 \(Ti\) 在 \(S[l,r]\) 中的出现次数.
\(n, q\),\(∑|Ti| <=1e5\)
解法：
用bitset并就行了，我觉得关键点反而是bitset的操作。
count(): 返回 true 的数量。
size(): 返回 bitset 的大小。
test(pos): 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查。
any(): 若存在某一位是 true 则返回 true，否则返回 false。
none(): 若所有位都是 false 则返回 true，否则返回 false。
all():C++11，若所有位都是 true 则返回 true，否则返回 false。
set(): 将整个 bitset 设置成 true。
set(pos, val = true): 将某一位设置成 true/false。
reset(): 将整个 bitset 设置成 false。
reset(pos): 将某一位设置成 false。相当于 set(pos, false)。
flip(): 翻转每一位。（0\leftrightarrow1，相当于异或一个全是 1 的 bitset）
flip(pos): 翻转某一位。
to_string(): 返回转换成的字符串表达。
to_ulong(): 返回转换成的 unsigned long 表达（long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）。
to_ullong():C++11，返回转换成的 unsigned long long 表达。
DAY 11:
模拟考T1的DP神奇优化不难想，火灾的平行四边形优化还和一般的不一样。之后的讲课碰到过弱化版的。
挂惨了 \(100+1+3+0=104\)
\(rank=?\)
这里我要点名批评那位收代码的老师，她告诉我交\(ZIP\)没关系，hhx爷爷的ZIP是没问题，可能是我太弱了。
T1 珠宝 (jewel)
题意：
一个\(01\)背包，只不过个数\(n<=1e6\),询问的总花费\(k<=5e4\),每一件的花费\(c[i]<=300\),价值\(v[i]<=1e9\)
解法：
首先最朴素的\(01\)背包在此不再赘述，不会就别打OI，去采药。
普通的\(01\)背包是\(O(nk)\)的，显然过不了。但我们发现\(c[i]\)很小，这启示我们可以先根据\(c[i]\)分类。
考虑对于同一个花费的物品，如果要选肯定是先选择价值大的再选择价值小的，所以这个东西它是有单调性的。搞一个东西维护\(c[i]\)从大到小排序，再简单的一个分治就行（为什么现在很多大神喜欢用\(cdq\)命名分治？一下考场\(ZYB\)说\(cdq\),然后\(kcr\)说他也是，吓死我）。我考场忘记优先队列，就用的\(vector\)记录以后排序。为什么我能场切？看变量名有惊喜！
//kcrboshasta kcr薄纱std
//hhxqqq hhx强强强
//wqxjgman wqx金钩man
//ChiFanAKioi 字面意思
//zyb(wyb)_tql zyb(wyb)太强力
#include<bits/stdc++.h>
#define int long long
#define kcrboshastd 0
using namespace std;
struct stu{
int w;
int v;
}hhxqqq[1000001];//暴力的存储
int c,v;
char cb[40000],*cs=cb,*ct=cb;
int n,k;
int wqxjgman[305];//每一个数的出现次数
vector<int>wybtql[305];//sum
int dp[2][50001];
int g[2][50001];
int ChiFanAKioi[50001];//暴力dp
int now=1,pre=0;
void ans(int l,int r,int ql,int qr,vector<int>&wybtql,int &wqxjgman){
if(ql>qr || l>r) return;
int zyb_tjl=-1;
int mid=(ql+qr)/2;
int val=0;
for(int i=max(l,mid-wqxjgman);i<=r && i<mid;i++){
if(zyb_tjl==-1||g[0][i]+wybtql[mid-i-1]>val){
val=g[0][i]+wybtql[mid-i-1];
zyb_tjl=i;
}
}
g[1][mid]=val;
if(zyb_tjl==-1) zyb_tjl=l;
ans(l,zyb_tjl,ql,mid-1,wybtql,wqxjgman);
ans(zyb_tjl,r,mid+1,qr,wybtql,wqxjgman);
}
bool cmp(int xx,int yy){
return xx>yy;
}
signed main(){
//freopen("jewel.in","r",stdin);
//freopen("jewel.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>c>>v;
wybtql[c].push_back(v);
wqxjgman[c]++;
hhxqqq[i].w=c;
hhxqqq[i].v=v;
}
if(n<=10000 && k<=10000){
for(int i=1;i<=n;i++){
for(int j=k;j>=hhxqqq[i].w;j--){
ChiFanAKioi[j]=max(ChiFanAKioi[j],ChiFanAKioi[j-hhxqqq[i].w]+hhxqqq[i].v);
}
}
for(int i=1;i<=k;i++){
cout<<ChiFanAKioi[i]<<" ";
}
return 0;
}
for(int i=1;i<=300;i++){
if(wqxjgman[i]){
sort(wybtql[i].begin(),wybtql[i].end(),cmp);
for(int j=1;j<wqxjgman[i];j++) wybtql[i][j]+=wybtql[i][j-1];
for(int j=0;j<i;j++) {
int p=j,bk=0;
for(;p<=k;p+=i,bk++) g[0][bk]=dp[pre][p];
ans(0,bk-1,0,bk-1,wybtql[i],wqxjgman[i]);
for(p=j,bk=0;p<=k;p+=i,bk++) dp[now][p]=max(g[0][bk],g[1][bk]);
}
swap(now,pre);
}
}
for(int i=1;i<=k;i++) cout<<dp[pre][i]<<" ";
return kcrboshastd;
}
T3 迷宫 (trap)
调了我1.5h。
有四个结论：
1.一旦老鼠被困在某个叶节点(前提)，在老鼠不能动的时候把老鼠通到根节点的那一条路上的其他支路都封死，然后再把走廊擦干净，这是最佳决策。
证明：考虑如果在老鼠通往根节点的路径上进入了其他的支路，就算支路的大小为1也需要一次操作擦进去的边。如果支路的大小更大则需要更多的操作数，不如花一次操作把支路堵上
2.一旦老鼠进入一个子树内，他最终会被自己弄脏的走廊困在某个叶节点。
证明：首先老鼠肯定是走不出这个子树的。老鼠如果不待在叶子节点到跟的路径比待在叶子节点短，这样管理者的操作数就变少了，显然不优。
3.耗子决策只能是：向上主动走一些(或不走)，然后找棵子树一头钻进去，然后等待收编。
证明：首先老鼠进入钻进一棵子树就出不去了(脏了)，在钻进子树前向上走能增大步数。
4.f[i]为老鼠在进入i子树后，最后不得不回到i点消耗的最大步数。在老鼠向下走之后(前提)每次堵住通向f值最大的子树的边，一定最优。
证明 老鼠进入f值最大的子树和其他子树结果都是返回i节点，i节点的子树数量不会变，堵住支路的代价是一样的，当然先阻止老鼠进入步数大的。
#include<bits/stdc++.h>
using namespace std;
int n,t,m;
bool tag[1000001];
vector<int> v[1000001];
int f[1000001];//f[i]表示老鼠进入了节点i为根的子树，然后又把老鼠赶回节点i所需要的步数。
int sum[1000001];
int num[1000001];
int faa[1000001];
int get_f(int now,int fa){
faa[now]=fa;
int maxn=0,maxnf=0,nu=0;
int kk=v[fa].size();
//sm[now]=sm[fa]+max(0,kk-2);
kk=v[now].size();
if(kk==1 && fa!=0){
f[now]=0;
return 0;
}
for(int i=0;i<v[now].size();i++){
if(v[now][i]==fa) continue;
nu++;
int k=get_f(v[now][i],now);
if(k>maxn){
maxnf=maxn;
maxn=k;
}
else if(k>maxnf){
maxnf=k;
}
}
f[now]=nu+maxnf;
num[now]=nu;
return f[now];
}
bool check(int k){
int now=m;
int cnt=1;
while(now!=t){
int lp=0;
for(int i=0;i<v[now].size();i++){
if(tag[v[now][i]]) continue;
if(f[v[now][i]]+sum[now]>k){
if(!cnt) return false;
lp++;cnt--;
}
}
k-=lp;
if(k<0) return false;
now=faa[now];
cnt++;
}
return true;
}
int erfen(int l,int r){
if(l==r) return l;
if(l==r-1){
if(check(l)) return l;
else return r;
}
int mid=(l+r)/2;
if(check(mid)){
return erfen(l,mid);
}
else return erfen(mid+1,r);
}
int main(){
cin>>n>>t>>m;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
get_f(t,0);
for(int i=1;i<=n;i++){
sum[i]=sum[faa[i]]+num[i]-(i!=m);
}
for(int i=m;i;i=faa[i]) tag[i]=true;
/*
for(int i=1;i<=n;i++) cout<<f[i]<<" ";
cout<<endl;
for(int i=1;i<=n;i++) cout<<sum[i]<<" ";
cout<<endl;
*/
//for(int i=1;i<=n;i++) cout<<h[i]<<" ";
//cout<<endl;
cout<<erfen(0,2*n);
return 0;
}
T4 迷宫 (trap)
感恩ZYB爷爷
题意：
给定一张 n 个点 m 条边的图，q 次询问，每次询问删掉 [l_i,r_i]内的边，问这张图是否存在奇环。
解法：
这题更是逆天，写了1h,调了1.5h，写错n多
一部分的提交：
首先找奇环可以转化为判断二分图(二分图无奇环)。然后你发现直接在一个区间内操作十分的麻烦。
下图中绿色为剩余线段：
考虑将区间复制一份,这样剩余的线段就是两个l,r的中间部分
SOLVE 1
考虑当l一定时，当r的位置达到一个定值使得剩余线段是二分图，再往后肯定也是(中间部分越来越少了)，所以可以对每个i求出to[i]表示以i为l的最后一个满足剩下图不是二分图的r,显然可以整体二分。判断二分图可以用扩展域可撤销并查集。这种方法写了代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q;
int num=0;
int ld[400010],rd[400010];
int fa[400010];
int sz[400010];
int to[400010];
struct stu{
int pla1;
int pla2;
int time;
};
stack<stu> sta;
inline int cdq(int x){for(;x!=fa[x];x=fa[x]);return x;}
void segment_tree(int xx,int yy){
yy=cdq(yy);
if(xx==yy) return;
else{
if(sz[xx]>sz[yy]) swap(xx,yy);
sz[yy]=sz[xx]+sz[yy];
fa[xx]=yy;
sta.push({xx,yy,num});
}
}
bool check(int xx,int yy){
num++;
int fx=cdq(xx),fy=cdq(yy);
if(fx==fy) return true;
segment_tree(fx,yy+n);
segment_tree(fy,xx+n);
return false;
}
void treap(){
for(;sta.size() && sta.top().time==num;sta.pop()){
fa[sta.top().pla1]=sta.top().pla1;
sz[sta.top().pla2]-=sz[sta.top().pla1];
}
num--;
}
void Dirichlet(int l,int r,int L,int R){
if(l>r) return;
if(L>R) return;
if(L==R){
for(;l<=r;l++){
to[l]=L;
}
return;
}
int mid=(l+r)/2;
int i;
for(i=mid;i<=R;i++){
if(i==r+1) i=max(i,L);
if(check(ld[i],rd[i])) break;
}
to[mid]=i;
for(;i>=L && i>=mid;i--){
if(i==L-1) i=min(i,r);
treap();
}
Dirichlet(l,mid-1,L,to[mid]);
for(int i=mid;i<=r && i<=L-1;i++){
treap();
}
for(int i=max(r+1,L);i<=to[mid]-1;i++){
check(ld[i],rd[i]);
}
Dirichlet(mid+1,r,to[mid],R);
for(int i=max(L,r+1);i<=to[mid]-1;i++){
treap();
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
cin>>ld[i]>>rd[i];
ld[i+m]=ld[i];
rd[i+m]=rd[i];
}
for(int i=1;i<=2*n;i++){
fa[i]=i;
sz[i]=1;
}
ld[m*2+1]=rd[m*2+1]=1;
Dirichlet(1,m+1,1,2*m+1);
while(q--){
int ll,rr;
cin>>ll>>rr;
if(to[rr+1]<=m+ll-1){
cout<<"YES";//不是二分图，有奇环
}
else{
cout<<"NO";
}
cout<<endl;
}
return 0;
}
//考虑把边建两次，把问题转化成了两个l~r之间的段是否为二分图
//用扩展域可撤销并查集判断二分图
//记to[i]为以i边为左端点从左到右的最后一条加入后满足二分图的点
SOLVE 2(zyb神仙的TJ)
考虑二分做法最后提到的线段树分治，显然在化简完问题后这就是一个线段树分治形式，可以将询问视为时间轴，仿照其做。
但是有一个问题，边在时间轴上的区间不是连续的，我们可以隔一天加一次边将总区间数卡到 \(\frac{nq}{2}\)
个，这是不好的。
但是对于这类问题我们还有一个 LCT 做法，同二分思路一样的考虑预处理出 to，使用一个双指针，同时维护一个支持删边加边维护最小生成树的 LCT （其中边权为加入时间）就可以快速的预处理出来了。时间复杂度 \(O(n \log n + q)\)，更为优秀。
SOLVE 3( _ ChiFAN _ 神仙的TJ)
真的卡不动了，但是我感觉我的思路还是有一些价值的，就来写一篇题解吧。
考虑使用回滚莫队（不增）来维护，当区间删去一个点时相当于全局加入一条边，这个询问的本质是询问是否是二分图，所以考虑扩展值域并查集，这里使用路径压缩加按秩合并，记录下修改，在回滚时全部还原。
总复杂度是 \(O(n \sqrt n \alpha(n))\)目前还卡不过去。
蒟蒻wwh:理论上是能过去的
DAY 12：
继续讲杂题，LK的湖南口音听起来很亲切。
DAY 13：
又是测试。这场测试绝对臭名昭著。T1一个字符串输入的大模拟竟然输入里还有空格，最后一题的高斯消元优化主元没看懂。
DAY 14：
没想过DP也会有神奇的复杂度，扫描线配DP也是挺神奇的，DP难度真的很大，老师说他那个时候能做出来，可是他那时AK了NOI。
DAY 15：
老师讲课没控制好时间，后面有一节没讲完。还是觉得集训完了不把最后一次模拟测放上改题界面上不太合理。
标签：题意,int,集训,yy,一个,区间,游记,成都,节点 From： https://www.cnblogs.com/wangwenhan/p/17589757.html