FJ 省集补题笔记

我有认真在写哦 ♪

$\rm Difficulty$ 的意思：Easy（我会做）；Medium（不会做，但看了题解感觉不太难）；Hard（只能膜拜）。

Day 1

T1 树 (tree)

有一棵 $n$ 个点的树，初始占领了两个节点 $a$, $b$。每一秒，一个被占领的节点可以选择一个相邻的未被占领的节点占领之。求占领整棵树至少需要多少秒。

$n \leq 5\times 10^5$。

查看提示

$\rm Tag$：DP，二分
$\rm Difficulty$：Easy

查看题解

如果只有一个关键点，那么显然可以设 $dp_i$ 表示初始 $i$ 被染色，染完 $i$ 的子树的最小时间，$O(n\log n)$ 求出答案。也就是如果我们知道哪些点是 $a$ 染的，哪些是 $b$ 染的，求答案就简单了。

容易发现，只有 $a\sim b$ 这个链上悬挂的一堆子树不知道是谁染的。观察到 $a$ 与 $b$ 染的越接近越优，则可以在链上二分找出最近的，复杂度 $O(n \log^2 n)$。

瓶颈就在于排序了，而显然每次二分时只有 $a\sim b$ 这个链上的 DP 值会改变，所以我们只需要最开始排序一次即可，复杂度优化至 $O(n \log n)$。

查看代码

#include<bits/stdc++.h>
#define pbk emplace_back
#define FOR(i,a,b) for(int i=a,i##ED=b;i<=i##ED;++i)
using namespace std;
typedef vector<int> vi;
const int N=5e5+7;
int n,A,B,u,v,da[N],db[N],p[N],C,fl,ans=N;
vi a[N],sa[N],sb[N];
void dfs(int x,int f){
	p[++C]=x,fl|=x==B;
	for(int to:a[x])if(to!=f&&!fl)dfs(to,x);
	if(!fl)--C;
}
int calc(vi s){
	int S=s.size(),rs=0;
	if(!S)return 0;
	for(int t:s)rs=max(rs,t+S--);
	return rs;
}
int Dfs(int x,int f,int*dp,vi* st){
	for(int to:a[x])if(to!=f)st[x].pbk(Dfs(to,x,dp,st));
	sort(st[x].begin(),st[x].end());
	return dp[x]=calc(st[x]);
}
#define ins(x) s.insert(lower_bound(s.begin(),s.end(),x),x)
#define del(x) s.erase(lower_bound(s.begin(),s.end(),x))
signed main(){
	scanf("%d%d%d",&n,&A,&B);
	FOR(i,2,n)scanf("%d%d",&u,&v),a[u].pbk(v),a[v].pbk(u);
	dfs(A,0),Dfs(A,0,da,sa),Dfs(B,0,db,sb);
	for(int l=2,r=C;l<=r;){
		int md=(l+r)/2,ra=-1,rb=-1;
		for(int *t=p+md-1;t!=p;--t){
			vi s=sa[*t];
			del(da[*(t+1)]),ins(ra),ra=calc(s);
		}
		for(int *t=p+md;t!=p+C+1;++t){
			vi s=sb[*t];
			del(db[*(t-1)]),ins(rb),rb=calc(s);
		}
		if(ra>rb)ans=min(ans,ra),r=md-1;
		else ans=min(ans,rb),l=md+1;
	}
	printf("%d",ans);
	return 0;
}

T2 最小生成树 (mst)

给定一张 $n$ 个点 $m$ 条边的简单无向连通图，保证图的前 $n-1$ 条边是图的一棵生成树。

你需要为每条边分配一个 $1\sim m$ 的权值且每种权值只能用一次，求在所有前 $n-1$ 条边是图的最小生成树的方案中，前 $n-1$ 条边的权值和之和，对 $10^9+7$ 取模。

$n \leq 20$, $m \leq \dfrac{n(n-1)}2$。

查看提示

$\rm Tag$：组合数学，状压 DP
$\rm Difficulty$：Medium

假设我们已经知道了前 $n-1$ 条边的大小关系，那么非 MST 边带来的限制是什么？方案又如何求？

查看题解

假设我们已经用 $O(n!)$ 的时间枚举了前 $n-1$ 条边的大小关系，考虑答案如何求：这些边要作为 MST，那么一条其他的边 $e$ 不能环切之，也就是 $e$ 权值必须大于 MST 对应路径上边权的最大值。加上前 $n-1$ 条边的大小限制，这 $m$ 条边的限制就形如一条 $n-1$ 的链上挂着一些儿子，最终拓扑序就是合法方案。

为方便叙述，转化成如下问题：有一个空队列，你会依次收到 $w_1$ 个白球、一个黑球、$w_2$ 个白球、一个黑球，依此类推。黑球只能插入至队首，白球可以插入至任意位置，最后黑球的位置之和即为答案。

假设我们 DFS 时记录了四元组状态 $(n,b,c,s)$ 表示此时有 $n$ 个球，其中有 $b$ 个黑球，方案有 $c$ 种，所有方案黑球位置之和为 $s$，那么：

• 添加一个白球，对于每种方案而言，都能衍生 $n+1$ 种方案。考虑这些方案的黑球位置之和，第一部分是原先的 $s(n+1)$，第二部分是此白球贡献的 $s$。故四元组转化为 $(n+1,b,c(n+1),s(n+2))$。
• 添加一个黑球，则对于每种方案只能衍生出一种方案，并且 $s$ 增加 $b+1$。故四元组转化为 $(n+1,b+1,c,s+c(b+1))$。

而 DFS 时如何求出 $w$，我们按权值从大到小 DFS 选择该权值对应的边，加入这条边时所求即为：跨过这条边，但不跨过任一条已经选过的边的对应路径数。这个可以容斥后 $O\left(\dfrac {m2^n}\omega\right)$ bitset 预处理、$O(1)$ 求出。

将这个 DFS 改为状压 DP 即可，即记录 $c_S,s_S$ 表示已经从小到大选了 $S$ 内的边时的 $c$ 与 $s$，不用记录 $n$ 和 $b$ 是因为知道了 $S$ 之后二者很好求出。时间复杂度 $O\left(\dfrac{m2^n}{\omega}+n2^n\right)$。

查看代码

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a,ED=b;i<=ED;++i)
using namespace std;
const int N=22,M=191,S=(1<<(N-2))+5,mod=1e9+7;
int n,m,sz,u[M],v[M],w[M],st[N],C,cv[S];
long long c[S],f[S],ml[M][M];
vector<int>a[N];
bitset<M>p[S];
void dfs(int x,int t,int f=0){
	if(x==v[t])FOR(i,1,C)p[1<<st[i]][t-n]=1;
	for(int k:a[x]){int to=x^w[k];if(to!=f)st[++C]=k-1,dfs(to,t,x),--C;}
}
signed main(){
	scanf("%d%d",&n,&m),sz=(1<<(n-1))-1,*c=ml[1][0]=1;
	FOR(i,1,m){
		scanf("%d%d",u+i,v+i),ml[i][i]=i,ml[i+1][i]=1;
		FOR(j,i+1,m)ml[i][j]=ml[i][j-1]*j%mod;
		if(i<n)a[u[i]].push_back(i),a[v[i]].push_back(i),w[i]=u[i]^v[i];
		else dfs(u[i],i),C=0;
	}
	FOR(i,1,sz){int b=i&-i;if(b!=i)p[i]=p[i^b]|p[b];cv[i]=p[i].count();}
	FOR(s,0,sz)FOR(i,0,n-2){
		int B=1<<i,b=__builtin_popcount(s)+1,tn=cv[s]+b,tw=cv[s|B]+b-1;
		if(!(s&B)){
			long long Dc=ml[tn][tw]*c[s];
			(c[s|B]+=Dc)%=mod,(f[s|B]+=ml[tn+1][tw+1]*f[s]+Dc%mod*b)%=mod;
		}
	}
	printf("%lld",f[sz]);
	return 0;
}

T3 矩阵 (matrix)

出题人是有多大毛病才能出出来这种题。

Day 2

我草，三个串，谔谔了。

T1 子序列 (subseq)

给定一个长度为 $n$ 的只包含小写字母的字符串 $s$，$q$ 个询问 $l$, $r$，询问 $s[l, r]$ 中有多少本质不同的子序列。

答案对 $10^9 + 7$ 取模，$n, q \leq 10^6$。

查看提示

$\rm Tag$：字符串，矩阵优化 DP
$\rm Difficulty$：Medium

我觉得这题挺难的，但场上真的好多人过呀！

查看题解

先思考一次全体询问怎么做。

首先模仿子序列自动机上路径计数，设计一个 DP：$f_{i,j}$ 表示考虑前 $i$ 个字符，以字符 $j$ 结尾的子序列数量。转移可以考虑由 $f_{i-1}$ 的所有状态加上一个空串添加一个字符 $s_i$ 而来，也就是 $f_{i,s_i} = 1+\sum f_{i-1}$，其他的继承 $f_{i-1}$。

那么区间询问自然是写成矩阵形式了，维护前缀矩阵之积与前缀逆矩阵之逆序乘积：

$\left(\begin{bmatrix}1&& &&\\&1& &&\\1&1&1&1&1\\&&&1&\\&&&&1\\\end{bmatrix}\right)^{-1}=\begin{bmatrix}1&& &&\\&1& &&\\-1&-1&1&-1&-1\\&&&1&\\&&&&1\\\end{bmatrix}$

现在我们已经得到一个 $O((n+q)|\Sigma|^3)$ 的做法，但矩阵乘法太慢了，这个矩阵的形式又非常简洁，有没有什么办法优化掉矩阵乘法？

• 右乘一个正矩阵，相当于将其某一行全部加到其它行上面去，对列维护一个整体加标记即可 $O(|\Sigma|)$ 计算。

• 左乘一个逆矩阵，相当于将将某一列减去其余所有列之和，维护每一列之和即可 $O(|\Sigma|)$ 计算。

这样就 $O((n+q)|\Sigma|)$ 解决问题了。

T2 所有子串 LCS (alcs)

给出字符串 $X, Y$，对于 $Y$ 的每个子串，求出其与 $X$ 的最长公共子序列。

为了加快输入输出，本题采用交互形式评测。$|X|,|Y|\leq 8192$。

查看提示

$\rm Tag$：字符串
$\rm Difficulty$：Hard

看了一下午还是没懂，自闭了。

T3 Pajel 游戏 (pajel)

Day 3

skipped.

Day 4

几题好像都是思路比较巧妙，但细节也多的题。

T1 路径求和 (sum)

弱智题。

T2 路径计数 (count)

$4$ 个点的无向环，求从 $1$ 出发到 $1$ 结束，且经过第 $i$ 条边 $v_i$ 次的路径数。

$v \leq 5\times 10^5$。

查看提示

$\rm Tag$：欧拉回路。
$\rm Difficulty$：Medium

对欧拉回路计数，联想到 BEST 定理，但如何应用在这题？

查看题解

一转无向图欧拉回路（两点间连 $v_i$ 条边），但无向图没法做。

我们直接对边定向，容易发现只需要钦定第一种边有多少正着的，有多少反着的，由于存在欧拉回路，其余的都容易递推出。然后直接套 BEST 定理完事。

T3 路径优化 (optimal)

$n$ 行 $m$ 列网格图，格点之间有无向带权边。给出一些格子为关键格，左上角必然是关键格，你需要求出包含所有关键格的环路的最短长度。

$n,m \leq 400$。

查看提示

$\rm Tag$：最短路，建模。
$\rm Difficulty$：Hard

最优环路一定包含着关键格间的一棵生成树，这棵生成树满足怎样的性质？

我们提出一棵生成树后，如何在最短路建模中刻画包含关系？

查看题解

考虑从格点 $(0,0)$ 出发，到任意一个关键格左上角的一条最短路径，它一定被包含在环路内。理由是，如果它露出了一部分在环路外，将环路扩展一定不劣。

那么关键格的任意一棵最短路径树一定要被包含在环路内。最短路径树显然是个连通块，那包含的限制就变成了环路不能穿过最短路径树，似乎好刻画了一些。

不难想到对偶图，但似乎直接对偶似乎不太好做。我们把一个格点拆成左上、右上、左下、右下四个，之间连 $0$ 的有向边；一个网格间的四个点，若相邻就连上对应边权。然后我们用这两个条件来刻画包含关键格：

• 删除 SPT 穿过的边；
• 删除关键格内的四个点。

$(0,0)$ 的右上-左下最短路就是答案了。

查看代码

#include<bits/stdc++.h>
#define pbk emplace_back
#define cl(c,x) memset(c,x,sizeof c)
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
#define p(x,y) (x)*(m+1)+(y)
#define P(x,y) (x)*(2*m+3)+(y)
using namespace std;
typedef long long ll;
const int N=407,S=N*N*4;
int n,m,wl[N][N],wc[N][N],key[N][N],vis[S],fa[S];
struct edge{int to,w;edge(int u,int c){to=u,w=c;}};
ll d[S];
vector<edge>a[S];
struct node{int id;ll dis;bool operator<(node x)const{return dis>x.dis;}};
void dij(int s){
	priority_queue<node>q;
	cl(vis,0),cl(d,63);
	for(q.push({s,d[s]=0});!q.empty();){
		int x=q.top().id;q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(auto k:a[x]){
			int to=k.to,w=k.w;
			if(d[to]>d[x]+w)q.push({to,d[to]=d[fa[to]=x]+w});
		}
	}
}
int al[N*2][N*2],ac[N*2][N*2],ok[S];
void link(int u,int v,int w){if(!ok[u]&&!ok[v])a[u].pbk(v,w),a[v].pbk(u,w);}
signed main(){
	scanf("%d%d",&n,&m);
	FOR(i,0,n-1)FOR(j,0,m-1)scanf("%d",key[i]+j);
	FOR(i,1,n)FOR(j,0,m)scanf("%d",wl[i]+j),link(p(i-1,j),p(i,j),wl[i][j]);
	FOR(i,0,n)FOR(j,1,m)scanf("%d",wc[i]+j),link(p(i,j-1),p(i,j),wc[i][j]);
	dij(0),cl(vis,0),*vis=*ok=1;
	FOR(i,0,n-1)FOR(j,0,m-1)if(key[i][j]){
		int X[]={2*i+2,2*i+1},Y[]={2*j+2,2*j+1};
		FOR(a,0,1)FOR(b,0,1)ok[P(X[a],Y[b])]=1;
		for(int x=p(i,j);!vis[x];x=fa[x])vis[x]=1;
	}
	FOR(i,1,n)FOR(j,0,m){
		int u=p(i-1,j),v=p(i,j),w=wl[i][j],I=2*i,J=2*j+1;
		al[I][J-1]=al[I][J]=w;
		if(vis[u]&&vis[v]&&(d[u]+w==d[v]||d[v]+w==d[u]))ac[I-1][J]=ac[I][J]=-1;
	}
	FOR(i,0,n)FOR(j,1,m){
		int u=p(i,j-1),v=p(i,j),w=wc[i][j],I=2*i+1,J=2*j;
		ac[I-1][J]=ac[I][J]=w;
		if(vis[u]&&vis[v]&&(d[u]+w==d[v]||d[v]+w==d[u]))al[I][J-1]=al[I][J]=-1;
	}
	FOR(i,0,n)FOR(j,0,m)a[p(i,j)].clear();
	FOR(i,1,n*2+1)FOR(j,0,m*2+1)if(~al[i][j])link(P(i-1,j),P(i,j),al[i][j]);
	FOR(i,0,n*2+1)FOR(j,1,m*2+1)if(~ac[i][j])link(P(i,j-1),P(i,j),ac[i][j]);
	dij(1),printf("%lld",d[P(1,0)]);
	return 0;
}

Day 5

这场好简单阿，T1 提答题就跳过了。

T2 搭积木 (block)

给定 $n$ 块积木，第 $i$ 块宽度为 $1$，高度为 $h_i$。

将这些积木以任意顺序排列，形成一个容器：若第 $i$ 个位置高度为 $h_i$，它左 / 右边最高的位置的高度是 $l$ / $r$（若不存在则为 $0$），那么 $i$ 处能装的水量是 $\max(\min(l,r)-h,0)$。

问在所有可能的排列方案中，所有能装入的水量分别是多少。$n \leq 2000$, $h \leq 50$。

查看提示

$\rm Tag$：背包
$\rm Difficulty$：Easy

考虑总体积减去积木本身的体积。总体积呈什么形态？

查看题解

显然最大值没卵用，将其作为中心，分成左右两个互不相干的部分。

如果画个图容易发现，从中心往左右会形成单调非严格递减的图形，这启示我们用总体积减去积木本身的体积。我们将左右归并排序放到一起，最大值就成为了最左边，右边的贡献是单调栈。

接下来就是，去掉最大值后，$n-1$ 个物品按体积从大到小排序，每个物品可以放若干个，但前 $i$ 个物品的总数不能超过 $i$。bitset 优化背包可以解决，时间复杂度 $O\left(\dfrac{n^2h^2}{\omega}\right)$。

T3 背包 (pack)

有 $n$ 个物品，每个物品有类型 $a_i$ 和权值 $c_i$。类型共有 $m$ 种，对于每个类型 $i$，你想选 $x\in [l_i,r_i]$ 个物品装入你的背包。

求权值和最小的 $k$ 种选取物品的方案，输出其权值和。$n,m,k \leq 2\times 10^5$, $c \leq 10^9$。

查看提示

$\rm Tag$：。
$\rm Difficulty$：。

捏麻麻地，假了。

查看题解

删了。

Day 6

T1 消失的序列·改

有些排列是可以用一个栈进行排序的，排序方式如下：

• 另外准备一个栈和一个空的序列；
• 每一次操作可以把排列中的第一个数（如果排列不为空）压入栈中或把栈的栈顶元素（如果栈不为空）弹出并加入序列尾；
• 设排列长度为 $n$，则最后序列中的 $n$ 个元素应单调递增。

给一个长度为 $n$ 的排列 $A$，求有多少个长度为 $n$ 且字典序大于等于 $A$ 的排列 $p$ 满足 $p$ 可用栈排序。

对 $998244353$ 取模，$n \leq 10^6$。

查看提示

$\rm Tag$：组合计数
$\rm Difficulty$：Medium

排列能被栈排序的充要条件：不存在三个位置，离散化后依次是 $2$, $3$, $1$。

查看题解

提示中的结论，必要性显然。充分性：考虑你在排序的过程，肯定先找到还没排好序的最小的数，然后把这个数前面的所有数全部入栈，最后把这个数弹出。由于不存在上述三元组，而你弹出的数是当前最小的数，即这个数前面的数都大于它，那么它前面的数一定是单调递减的。换句话说，排序的过程中栈里的数单调，那就不存在取不到最小的数的情况，就一定可以排好序。

考虑怎么实现这个判断，我们可以顺序枚举中间的那个 $3$，同时维护一个 $vis_x$ 表示前面是否出现过 $x$ 这个数。枚举到 $i$ 时，如果 $vis$ 数组在 $p_i$ 左边存在依次为 $0$, $1$ 的数对，那就不合法了。

从左至右填充 $p$ 排列，填到 $i$ 位置时 $p_i$ 的限制就明晰了：取值范围是 $vis$ 数组第一个 $0$ 的连续段。那么不考虑字典序的限制，一个长度为 $n$ 的排列的填充对应着唯一一种值域上的分治过程，也就是分治树，这是任意的一棵二叉树。现在我们得到了强有力的结论：长度为 $n$ 的合法排列有 $C_n$ 种，其中 $C$ 是卡特兰数。

现在考虑进字典序的限制，暴力就是直接枚举 $A$ 与答案序列的最长公共前缀，再枚举下一位填的什么，这样值域就被分成了若干小段，可以快速计算。而观察可知，从前至后每确定答案序列一位，就将值域多分出一份：贡献形如 $\sum\limits_{i=0}^x C_i\cdot C_{a-i}$。而 $\sum\limits_{i=0}^a C_i\cdot C_{a-i}$ 是很好计算的，等于 $C_{a+1}$，所以当 $2x>a$ 时用整体减去 $x+1$ 枚举到 $a$ 的部分，复杂度就变成了 $O(n \log n)$。

查看代码

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;
const int N=1e6+7,mod=998244353;
ll qpow(ll a,int b=mod-2){
	ll R=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)R=R*a%mod;
	return R;
}
int n,x,v[N],l=1;
ll C[N],ans=1;
std::priority_queue<int,std::vector<int>,std::greater<int>>q;
int main(){
	scanf("%d",&n),*C=1,q.push(n+1);
	FOR(i,1,n+1)C[i]=C[i-1]*(4*i-2ll)%mod*qpow(i+1)%mod;
	ll nw=C[n];
	FOR(i,1,n){
		for(scanf("%d",&x);q.top()<l;q.pop());
		int r=q.top()-1;
		ll fc=nw*qpow(C[r-l+1])%mod,su=fc*C[r-l+1]%mod;
		if(r-x<x-l)FOR(i,x+1,r)(ans+=fc*C[i-l]%mod*C[r-i])%=mod;
		else{
			(ans+=su)%=mod;
			FOR(i,l,x)(ans-=fc*C[i-l]%mod*C[r-i])%=mod;
		}
		if(x<l||x>r){--ans;break;}
		nw=fc*C[x-l]%mod*C[r-x]%mod;
		for(v[x]=1,q.push(x);v[l]&&l<=n;++l);
	}
	printf("%lld",(ans+mod)%mod);
	return 0;
}

T2 异或矩阵

看了一早上还是没懂，自闭了。