20231019 B 组模拟赛 题解
前言
暂时先写 T4（因为是推式子题），其它的等有时间了再补。
T1
这道题做法贼多，我这里说一下我的 $O(n\log n)$ exKMP 做法，应该是带 $\log$ 的做法中跑的最快的。
约定：字符串下标从 $0$ 开始。
先求出 exKMP 的 $nxt$ 数组，容易发现每个点的决策只有两种，分别是加上一个字符和复制一遍后删掉若干个字符，且在 $i$ 处至少要删掉 $i-nxt_i$ 个（不然就和 $S$ 不匹配了）。
那么容易想到 DP，设 $dp_{i}$ 表示匹配完 $[0,i)$ 的最小代价，根据刚才的结论，转移有两种：
$$ dp_i\gets dp_{i-1}+t_{s_{i-1}}\\ dp_i\gets \min_{j<i}^{j+nxt_j\ge i}\begin{Bmatrix}dp_j+t_1+t_2\times (2j-i)\end{Bmatrix} $$
然后第二个转移可以用优先队列维护，就做完了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e6+5,inf=1e18;
i64 n,a[N],cs[26],t1,t2;
char str[N];
i64 nxt[N],dp[N],ff[N];
void exKMP(){
nxt[0]=0;
i64 j=1,p=0;
while(str[p]==str[p+1]) ++p;
nxt[1]=p;
forup(i,2,n-1){
if(i>=j+p){
p=0;
while(str[p]==str[p+i]) ++p;
nxt[i]=p;j=i;
continue;
}
if(nxt[i-j]<j+p-i){
nxt[i]=nxt[i-j];
}else{
p=j+p-i;
while(str[p]==str[i+p]) ++p;
nxt[i]=p;j=i;
}
}
}
struct cmp{
bool operator ()(pii a,pii b){
return a.fi+a.se*t2>b.fi+b.se*t2;
}
};
priority_queue<pii,vector<pii>,cmp> q;
i64 gval(pii nw,i64 i){
return nw.fi+(nw.se-i)*t2;
}
signed main(){
scanf(" %s",str);
n=strlen(str);
forup(i,0,25) cs[i]=read();
forup(i,0,n-1) a[i]=cs[str[i]-'a'];
forup(i,0,n) dp[i]=inf;
t1=read();t2=read();
exKMP();
dp[0]=0;
forup(i,0,n-1){
while(q.size()&&q.top().se<i) q.pop();
if(q.size()){
pii nw=q.top();
dp[i]=min(dp[i],gval(nw,i));
}
dp[i+1]=min(dp[i+1],dp[i]+a[i]);
i64 pn=min(nxt[i],i);
if(pn!=0){
q.push(mkp(dp[i]+t1+t2*(i-pn),i+pn));
}
}
while(q.size()&&q.top().se<n) q.pop();
if(q.size()){
pii nw=q.top();
dp[n]=min(dp[n],gval(nw,n));
}
printf("%lld\n",dp[n]);
}
T2
很奇妙的一道题，我赛时臆想了一个做法，就是离散化后跑 DDP，但是没想出怎么维护区间操作就跳过这道题了。希望有有缘人可以尝试一下。
我赛后写的官方题解的做法。
首先容易发现每个连通的整块只有两种涂色方法，且两种涂法黑白两色的差值是一样的。那么我们可以考虑只维护差值 $diff$，然后黑白的答案就分别是 $\frac{sum \pm diff}{2}$。
那么我们就要维护两个东西，分别是连通块和区间内黑白色差值，其中连通块可以用 ODT 维护，这个很简单就不具体讲了。我们现在重点讲第二个。
首先，由于两种情况差值相同，我们不妨给每一个点钦定一个颜色（黑白交替），其中奇数列奇数行为白色，偶数行为黑色，偶数列反之，那么我们要维护区间深度加 $d$，考虑区间加 $d$ 会对差值 黑色 $-$ 白色 产生什么影响。
首先，若 $d$ 是偶数，那么相当于在下面加偶数行块，容易发现这一块的差为 $0$，而上面原有的不会变。故若 $d$ 为偶数可以直接不操作。
若 $d$ 为奇数，那么相当于区间内原有块黑白色交换，然后再加偶数行完整，再加一行。其中偶数行差为 $0$，不会产生影响，只考虑加的这一行和反转原来的颜色。
对于反转颜色，如果某一列深度为偶数，那么这一列不会产生额外影响。反之，如果是第奇数列，那么黑色 $+1$，白色 $-1$，差值 $+2$，若为偶数列则白色 $+1$ 黑色 $-1$，差值 $-2$。
然后考虑加的这一行，贡献显然是 偶数列数量 $-$ 奇数列数量。
那么我们可以维护区间内 深度为奇数的偶数列 $o_0$，深度为奇数的奇数列 $o_1$，区间内奇数列的数量 $c$ 来得出差值的变化。
那么设区间长度为 $l$，差值就是：
$$2o_1-2o_0+(l-2c)$$
而容易发现 $o_1-c$ 就是深度为偶数的奇数列的数量，那么我们可以改为维护 深度与下标奇偶性不同的列数 $o=(o_1-c)-o_0$，那么差值就是 $2o-l$，且修改后，$o$ 变为 $l-o$。
那么这个显然可以动态开点线段树维护，注意数组不要开小了，以及维护连通块的边界问题。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5;
i64 n,m,sum,diff;
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,ls[id]
#define rson mid+1,r,rs[id]
private:
i64 ls[N*80],rs[N*80],queryodd[N*80],querydif[N*80],mark[N*80],cntn=0;
i64 New(i64 l,i64 r){
i64 id=++cntn;
if(l%2==1){
queryodd[id]=(r-l+2)/2;
}else{
queryodd[id]=(r-l+1)/2;
}
return id;
}
void Modify(i64 id,i64 len){
i64 s=queryodd[id];
queryodd[id]=len-s;
querydif[id]+=s*2-len;
mark[id]^=1;
}
void PushUp(i64 id){
queryodd[id]=queryodd[ls[id]]+queryodd[rs[id]];
querydif[id]=querydif[ls[id]]+querydif[rs[id]];
}
void PushDown(i64 id,i64 l,i64 r){
Modify(ls[id],mid-l+1);
Modify(rs[id],r-mid);
mark[id]=0;
}
public:
void init(){
New(1,n);
}
void Update(i64 L,i64 R,i64 l=1,i64 r=n,i64 id=1){
if(L<=l&&r<=R){
Modify(id,r-l+1);
return;
}
if(!ls[id]) ls[id]=New(l,mid);
if(!rs[id]) rs[id]=New(mid+1,r);
if(mark[id]) PushDown(id,l,r);
if(L<=mid) Update(L,R,lson);
if(mid< R) Update(L,R,rson);
PushUp(id);
}
i64 Query(i64 L,i64 R,i64 l=1,i64 r=n,i64 id=1){
if(L<=l&&r<=R){
return querydif[id];
}
if(!ls[id]) ls[id]=New(l,mid);
if(!rs[id]) rs[id]=New(mid+1,r);
if(mark[id]) PushDown(id,l,r);
i64 res=0;
if(L<=mid) res+=Query(L,R,lson);
if(mid< R) res+=Query(L,R,rson);
return res;
}
}mt;
set<pii> odt;
signed main(){
n=read();m=read();
mt.init();
forup(Case,1,m){
i64 l=read(),r=read(),d=read();
++l;
sum+=(r-l+1)*d;
set<pii>::iterator st=odt.lower_bound(mkp(l-1,-1)),ed=odt.lower_bound(mkp(r,-1));
i64 ll=l,rr=r;
if(st!=odt.end()) ll=min(ll,st->se);
if(ed!=odt.end()&&ed->se<=r+1){
rr=max(rr,ed->fi);
++ed;
}
for(set<pii>::iterator it=st;it!=ed;odt.erase(prev(++it))){
i64 rs=abs(mt.Query(it->se,it->fi));
diff-=rs;
}
if(d%2==1) mt.Update(l,r);
odt.insert(mkp(rr,ll));
i64 rs=abs(mt.Query(ll,rr));
diff+=rs;
printf("%lld %lld\n",(sum-diff)/2,(sum+diff)/2);
}
}
T3
我认为是全场最简单题。
首先一眼看到如果是树会很好做，那么考虑变成树。
容易发现边双有很好的性质，你发现边双内任意两点之间必定存在一条路径可以经过某·指定边，因为任意两点之间都有至少两条路径，然后随意构造一下大概就行了。
那么缩点之后直接跑换根 DP 就行了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5;
int n,m,ans[N];
struct edge{
int u,v,p;
};
vector<edge> se;
vector<int> e[N],pt[N];
vector<pii> e1[N];
int csc,Tm,dfn[N],low[N],blg[N],ist[N],sf[N],sz[N];
stack<int> stk;
void Tarjan(int x,int fa){
low[x]=dfn[x]=++Tm;
ist[x]=1;stk.push(x);
for(auto i:e[x]){
if(i==fa) continue;
if(!dfn[i]){
Tarjan(i,x);
low[x]=min(low[x],low[i]);
}else if(ist[i]){
low[x]=min(low[x],low[i]);
}
}
if(dfn[x]==low[x]){
++csc;
while(stk.top()!=x){
blg[stk.top()]=csc;
ist[stk.top()]=0;
pt[csc].push_back(stk.top());sz[csc]++;
stk.pop();
}
blg[x]=csc;
ist[x]=0;
pt[csc].push_back(x);sz[csc]++;
stk.pop();
}
}
int dp[N],pd[N],siz[N];
void dfs1(int x,int fa){
siz[x]=sz[x];
for(auto i:e1[x]){
int v=i.fi;
if(v==fa) continue;
dfs1(v,x);
siz[x]+=siz[v];
if(sf[x]||sf[v]||i.se){
dp[x]+=siz[v];
}else{
dp[x]+=dp[v];
}
}
}
void dfs2(int x,int fa){
for(auto i:e1[x]){
int v=i.fi;
if(v==fa) continue;
if(sf[v]){
pd[v]=n-sz[v];
}else if(sf[x]||i.se){
pd[v]=n-siz[v]+dp[v];
}else{
pd[v]=pd[x];
}
dfs2(v,x);
}
}
signed main(){
n=read();m=read();
forup(i,1,m){
int u=read(),v=read(),p=read();
se.push_back(edge{u,v,p});
e[u].push_back(v);
e[v].push_back(u);
}
Tarjan(1,0);
for(auto i:se){
int u=i.u,v=i.v,p=i.p;
if(blg[u]==blg[v]){
if(p) sf[blg[u]]=1;
continue;
}
u=blg[u],v=blg[v];
e1[u].push_back(mkp(v,p));
e1[v].push_back(mkp(u,p));
}
dfs1(1,0);
pd[1]=dp[1];
dfs2(1,0);
forup(i,1,csc){
for(auto j:pt[i]){
if(sf[i]){
ans[j]=pd[i]+sz[i]-1;
}else{
ans[j]=pd[i];
}
}
}
forup(i,1,n){
printf("%d ",ans[i]);
}
}
T4
首先把排列拆成环（$i\to p_i$，比如排列 $3,5,4,1,2,6$ 就可以拆成三个环 $(3,4,1)(5,2)(6)$），为保证交换次数最小，只能再每个环内部交换，那么容易构造出每次用环上最小值当跳板和其他值交换，而这样显然是代价最小的，是最小值乘以其它值的和。那么整个排列的代价就是所有环的代价之和。
那么考虑枚举 $i$ 在所有情况下能作为环内最小值产生贡献的代价之和，易得以下式子：
$$\sum_{i=1}^{n-1}i\sum_{S\subseteq[i+1,n]}\left(\sum_{x\in S}x\right)|S|!(n-|S|-1)!$$
式子很好理解，前半部分枚举内容很显然，其中 $S$ 是去掉 $i$ 后环上点的集合。最后的 $(n-|S|-1)!$ 是环外的排列。$|S|!$ 比较复杂，考虑 $i\to p_i$ 的环上的顺序，我们钦定一个点断开后其余点排列方案数就是 $|S|!$，然后每个环都能唯一对应 $i\to p_i$ 的映射集合（显然是双射吧），故环内的方案数为 $|S|!$。
然后容易发现如果要枚举集合 $S$ 显然不可做，考虑枚举集合大小 $j=|S|$，然后每个 $x\in[i+1,n]$ 都能在 $\binom{n-i-1}{j-1}$ 个不同的 $S$ 中产生贡献，故上式可化为这样：
$$\sum_{i-1}^{n-1}\sum_{j=1}^{n-i}i\dfrac{(n+i+1)(n-i)}{2}\dbinom{n-i-1}{j-1}j!(n-j-1)!$$
不会连等差数列求和公式都看不懂吧？
容易看到中间有个组合数，旁边还有一堆阶乘，考虑把组合数拆成阶乘再化简：
$$\sum_{i-1}^{n-1}\sum_{j=1}^{n-i}i\dfrac{(n+i+1)(n-i)}{2}\times\dfrac{(n-i-1)!}{(j-1)!(n-i-j)!}j!(n-j-1)!$$
稍微约分一下：
$$\frac{1}{2}\sum_{i-1}^{n-1}i(n+i+1)(n-i)!\sum_{j=1}^{n-i}\dfrac{j(n-j-1)!}{(n-j-i)!}$$
这个式子虽然变好看了，但仍然需要 $O(n^2)$ 才能做，考虑拆掉后面的 $\sum$，但是为了消掉它，我们有一个套路，需要把它拆成难看的组合数。
$$ \begin{aligned} &\sum_{j=1}^{n-i}\dfrac{j(n-j-1)!}{(n-j-i)!}\\ =&(i-1)!\sum_{j=1}^{n-i}\dfrac{j(n-j-1)!}{(n-j-i)!(i-1)!}\\ =&(i-1)!\sum_{j=1}^{n-i}\dbinom{n-j-1}{i-1}\dbinom{j}{1} \end{aligned} $$
这里有一个套路，我们把它放到一个更一般的情况：
$$\sum_{x=d-c}^{a-b}\dbinom{a-x}{b}\dbinom{c+x}{d}=\dbinom{a+c+1}{b+d+1}$$
证明：
考虑组合意义，即在两段长度分别为 $a-x,c+x$ 的序列上分别找 $b,d$ 个点的方案数。
那么容易发现两段序列长度的和是固定的 $a+c$，我们再在中间塞一个分界点，且钦定它被选，左边恰好有 $b$ 个被选，右边有 $d$ 个（其实就是在选出来的所有 $b+d+1$ 个点中第 $b+1$ 个），那么一共就要选 $b+d+1$ 个，总方案数就是 $\binom{a+c+1}{b+d+1}$。
为什么这样就是对的呢？考虑分界点的移动，容易发现它最左为 $b+1$，最右为 $a+b-d$，恰好分别是 $a-x,c+x$ 的下界。换句话说，这样选恰好在 $\sum$ 约束的范围内算到了所有 $x$ 取值的方案数总和。
那么把这个情况放回式子中，若 $a=n-1,b=i-1,c=0,d=1$，那么 $x$ 的范围为 $[1,n-i]$，这不巧了吗，恰好是 $j$ 的范围。那么我们刚刚的式子恰好完美满足优化条件，可以化成这样：
$$(i-1)!\dbinom{n}{i+1}$$
再塞回原来的式子：
$$ \begin{aligned} &\frac{1}{2}\sum_{i-1}^{n-1}i(n+i+1)(n-i)!(i-1)!\dbinom{n}{i+1}\\ =&\frac{1}{2}\sum_{i-1}^{n-1}i!(n+i+1)(n-i)!\dfrac{n!}{(i+1)!(n-i-1)!}\\ =&\frac{1}{2}\sum_{i-1}^{n-1}\dfrac{(n+i+1)(n-i)n!}{i+1} \end{aligned} $$
那么我们就能得到一个又好算又好看的式子了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int mod=1e9+7;
int n,ans,fn;
int inv[10000007];
signed main(){
n=read();fn=1;
forup(i,1,n){
fn=1ll*fn*i%mod;
}
inv[1]=1;
forup(i,2,n) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
forup(i,1,n-1){
(ans+=1ll*(n+i+1)*(n-i)%mod*fn%mod*inv[i+1]%mod)%=mod;
}
ans=1ll*inv[2]*ans%mod;
printf("%d\n",ans);
}