联合省选2022题解
Day1
T1 预处理器 preprocessor
link
题意
模拟 C++ 的 #define 的展开。具体细节参见题面。
数据范围：行数 \(n\le 100\)，每行长度 \(\le 100\)，答案的每行长度 \(len \le 1000\)。
solution
直接大力模拟即可通过官方数据，不过如果常数写的丑的话在 hack 数据上可能会 T。
暴力模拟的化复杂度是 \(O(n^3len)\) 的，不过常数很小。因为可能需要 \(O(n^2)\) 的复杂度来确定答案串的一位。
如果一直不能确定答案的一位，一定是存在下面这种情况
#define A B
#define B C
#define C D
.....
#define Z xxx
A
其中 A，B，C，...，Z 是一堆长度为 \(O(n)\) 的串。
字符串 A \(\to\) B 的变化需要 \(O(n)\) 的代价。所以我们把这一过程改为哈希值的变化，每次变化就是 \(O(1)\) 的了。
这样总复杂度是 \(O(n^2len)\)。
view code
#include
using namespace std;
inline int read(){
char ch=getchar();
int s=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();
}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
while(ch!='\n')ch=getchar();
return s*f;
}
inline bool check(char x){
if(x>='A'&&x<='Z')return 1;
if(x>='a'&&x<='z')return 1;
if(x>='0'&&x<='9')return 1;
if(x=='_')return 1;
return 0;
}
#define ll long long
const int mod1=998244353,mod2=1e9+7;
inline ll gethsh(const string&s){
int ret1=0,ret2=0;
for(char x:s){
ret1=(233ll*ret1+x)%mod1;
ret2=(233ll*ret2+x)%mod2;
}
return 1000000000ll*ret1+ret2;
}
const int N=1005;
unordered_map name;
unordered_map to;
unordered_map S[N];
unordered_map d;
unordered_map id;
unordered_map to1;
bool vis[N],previs[N][N];
inline string bfs(string x,ll hsh){
if(!id.count(hsh)||!d[hsh]||vis[id[hsh]])return x;
ll cur=hsh,nxt=to1[hsh];
while(id.count(nxt)){
if(vis[id[nxt]]||!d[nxt])
break;
vis[id[nxt]]=1;cur=nxt;nxt=to1[cur];
}
return to[cur];
}
inline string solve(string s,int dep){
string st=s;
memcpy(previs[dep],vis,101);
if(dep)s=bfs(s,gethsh(s));
int n=s.size(),l=0;
S[dep].clear();
s.push_back('\n');
string ret;
for(int i=0;i<=n;++i){
if(!check(s[i])){
if(l!=i){
string t;
for(int j=l;j T2 填树 tree
link
题意
给定一棵树，每个点的点权要么是 \(0\)，要么是 \([l_u,r_u]\) 之内的一个整数。现在已知树上所有点权非 \(0\) 的点构成一条路径，且非 \(0\) 权值的极差 \(\le k\)。
求满足条件的给每个点分配点权的方案数 \(\bmod 10^9+7\)，以及所有方案中的所有点的点权和 \(\bmod 10^9+7\)。
数据范围：\(n\le 200,1\le l_i\le r_i\le 10^9,1\le k\le 10^9\)。
solution
设值域为 \(V\)，先考虑一个 \(O(nV)\) 的暴力：枚举最大值 \(mx\)，求所有方案中以 \(mx\) 为最大值的方案数和所有方案中的点权和。
设 \(f_{u,0/1}\) 表示以 \(u\) 为端点，路径上是否有一个点的点权 \(=mx\) 的路径数量。\(g_{u,0/1}\) 表示 \(f_{u,0/1}\) 中所有路径的权值和。
初值设为 \(uf_{u,0/1},ug_{u,0/1}\)。
那么合并 \(u,v\) 时，对答案的贡献是
\[ans1\gets f_{u,x}\times f_{v,y}(x=1\lor y=1)\\ ans2\gets f_{u,x}\times g_{v,y}+g_{u,x}\times f_{v,y}(x=1\lor y=1) \]转移有：
\[f_{u,x|y}\gets uf_{u,x}\times f_{v,y}\\ g_{u,x|y}\gets uf_{u,x}\times g_{v,y}+ug_{u,x}\times f_{v,y} \]即把 \(v\) 为端点的所有路径接上一个 \(u\)。
容易发现，\(uf_{u,0/1}\) 是一个关于 \(mx\) 的分段一次函数：
- \(mx\in [0,l_u)\)
- \(mx\in [l_u,r_u]\)
- \(mx\in (r_u,l_u+k]\)
- \(mx\in (l_u+k,r_u+k]\)
- \(mx\in (r_u+k,+\infty)\)
先是 \(0\)，然后以斜率为 \(1\) 的速度增长，然后取得最大值（\(k\) 或 \(r_u-l_u+1\)），然后以斜率为 \(-1\) 的速度减小，然后变为 \(0\)。
同理，\(ug_{u,0/1}\) 也是一个关于 \(x\) 的分段函数，只不过是一个分段的二次函数。
这样 \(ans1\) 是一个关于 \(mx\) 的 \(n\) 次多项式，\(ans2\) 是一个关于 \(mx\) 的 \(n+1\) 次多项式。
把所有点的分段情况合并起来，就是分成 \(O(n)\) 段，每段是一个不超过 \(n+1\) 次的多项式。我们要求的是多项式的前缀和。一个 \(m\) 次多项式的前缀和是一个 \(m+1\) 次多项式。所以我们需要一个 \(n+2\) 次的多项式。求出 \(n+3\) 个点值然后拉格朗日插值即可。如果这一段值域里没有 \(n+3\) 个数就直接暴力。
复杂度 \(O(n^3)\)。
view code
#include
using namespace std;
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*f;
}
#define ll long long
const int mod=1e9+7,N=205;
inline int quick_pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ret=1ll*ret*a%mod;
return ret;
}
inline int Inv(int a){return quick_pow(a,mod-2);}
inline int add(int a,int b){return (a+b>=mod)?a+b-mod:a+b;}
inline int dec(int a,int b){return (a-b<0)?a-b+mod:a-b;}
inline void Add(int &a,int b){a+=(a+b>=mod)?b-mod:b;}
inline void Dec(int &a,int b){a-=(a-b<0)?b-mod:b;}
int fac[N];
namespace lagrange{
int x[N],y[N],tot;
inline void clear(){
tot=0;
}
inline void Set(int _x,int _y){
x[++tot]=_x;y[tot]=_y;
}
inline int calc(int k){
int ret=0,prod=1;
fac[0]=1;
for(int i=1;i<=tot;++i)prod=1ll*prod*dec(k,x[i])%mod,fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1;i<=tot;++i){
int fz=1ll*y[i]*prod%mod*Inv(dec(k,x[i]))%mod;
int fm=1ll*fac[i-1]*fac[tot-i]%mod;
if((tot-i)&1)fm=mod-fm;
ret=(ret+1ll*fz*Inv(fm))%mod;
}
return ret;
}
}
int f[N][2],g[N][2];
ll f1[2],g1[2];
int s[N<<1],n,K,l[N],r[N],lim;
vector e[N];
int buc[N*N],tot;
inline int S1(int x){return ((1ll*x*(x+1))>>1)%mod;}
inline int calc1(int l,int r){
return (l<=r)?r-l+1:0;
}
inline int calc2(int l,int r){
if(rmxr)break;
if(R-L+1<=n+3){
for(int i=L;i<=R;++i){
retf=retg=0;
dfs(1,0,i);
Add(F,retf);
Add(G,retg);
}
continue;
}
for(int i=L;i<=L+n+2;++i){
retf=retg=0;
dfs(1,0,i);
F1[i-L]=retf;
G1[i-L]=retg;
}
lagrange::clear();
for(int i=0;i<=n+2;++i){
if(i)Add(F1[i],F1[i-1]);
lagrange::Set(L+i,F1[i]);
}
Add(F,lagrange::calc(R));
lagrange::clear();
for(int i=0;i<=n+2;++i){
if(i)Add(G1[i],G1[i-1]);
lagrange::Set(L+i,G1[i]);
}
Add(G,lagrange::calc(R));
}
printf("%d\n%d\n",F,G);
return 0;
}
T3 学术社区 community
link
题意
有 \(n\) 个人，总共发出 \(m\) 条消息。每条消息是下面 \(3\) 种中的一种。
A：B 楼上，称为楼上型消息，\(A\) 为发送人A：B 楼下，称为楼下型消息，\(A\) 为发送人A： ...，称为学术消息，\(A\) 为发送人
价值的定义如下：
- 对于楼上型消息
A：B 楼上，如果它的下一条消息的发送人是B，那么有 \(1\) 的价值，否则没有价值。 - 对于楼下型消息
A：B 楼下，如果它的上一条消息的发送人是B，那么有 \(1\) 的价值，否则没有价值。 - 对于学术消息，没有价值。
构造一个使得价值最大的重排消息的方案。保证每个人都发出了至少 \(1\) 条学术消息。\(T\) 组数据。
数据范围：\(T\le 100,n\le m\le 77777,\sum m\le 2.5\times 10^5\)。
solution
先考虑特殊性质 \(C\) 的做法：
把每条限制拆点，对于楼上型消息 \(x\) A：B 楼上，\(x\) 的出点连向所有 \(B\) 的消息的入点 \(y\)，表示如果 \(x\) 在 \(y\) 前面就有 \(1\) 的价值。楼下型消息类似。这样变成了一个二分图匹配问题。现在边数是 \(O(m^2)\) 的，不过我们连的边只跟一条消息的发出人有关，加 \(2n\) 个虚点即可把边数优化到 \(O(m)\)。现在的图不是一个二分图，不过用与二分图最大匹配相同的复杂度分析方法可知，现在的跑 Dinic 二分图匹配的复杂度依然是 \(O(m\sqrt{m})\) 的。
不过这样构造出来的方案可能成环，比如 \(x\to y\to z\to x\)。
注意到这个环上有如下两个性质：
- 环上的所有消息要么都是楼上型消息，要么都是楼下型消息。
- 环上的所有消息不包含学术消息。
我们可以用学术消息来断环为链。
具体的，\(x\) 的发出人 \(A\) 有一条学术消息 \(x'\)。设此时 \(x'\) 的连边关系是 \(p\to x'\to q\)（显然此时 \(p\) 要么不存在，要么是楼上型消息，\(q\) 要么不存在，要么是楼下型消息）。
- 如果 \(x,y,z\) 均为楼上型消息，那么断环为链的方式是 \(p\to x\to y\to z\to x'\to q\)。
- 如果 \(x,y,z\) 均为楼下型消息，那么断环为链的方式是 \(p\to x'\to y\to z\to x\to q\)。
跑完 Dinic 之后找到一组匹配，把所有环断掉即可。复杂度瓶颈在 Dinic，为 \(O(m\sqrt{m})\)
现在没有了特殊性质 \(C\)，直接连边是不行的，因为A B 楼上 在 B A 楼下 前面的化，价值是 \(2\) 而不是 \(1\)，就得跑费用流了。容易发现直接把 A B 楼上 和 B A 楼下 匹配起来一定不会更劣。然后就又变成了上面一样的问题。
唯一的区别是这些被匹配的消息只有入点/出点了。
总复杂度 \(O(m\sqrt{m})\)。如果 Dinic 跑不动的化不妨尝试以下改变建边顺序，能从十几秒优化到 \(1\) 秒。
view code
#include
using namespace std;
namespace iobuff{
const int LEN=1000000;
char in[LEN+5],out[LEN+5];
char *pin=in,*pout=out,*ed=in,*eout=out+LEN;
inline char gc(void){
return pin==ed&&(ed=(pin=in)+fread(in,1,LEN,stdin),ed==in)?EOF:*pin++;
}
inline void pc(char c){
pout==eout&&(fwrite(out,1,LEN,stdout),pout=out);
(*pout++)=c;
}
inline void flush(){fwrite(out,1,pout-out,stdout),pout=out;}
template inline void read(T &x){
static int f;
static char c;
c=gc(),f=1,x=0;
while(c<'0'||c>'9') f=(c=='-'?-1:1),c=gc();
while(c>='0'&&c<='9') x=10*x+c-'0',c=gc();
x*=f;
}
inline void tostring(string&s){
s.clear();
char ch=gc();
for(int i=1;;++i,ch=gc()){
if(ch==' '||ch=='\n')break;
else s.push_back(ch);
}
}
template inline void putint(T x,char div='\n'){
static char s[20];
static int top;
top=0;
x<0?pc('-'),x=-x:0;
while(x) s[top++]=x%10,x/=10;
!top?pc('0'),0:0;
while(top--) pc(s[top]+'0');
pc(div);
}
}
using iobuff::putint;
using iobuff::read;
using iobuff::tostring;
using iobuff::pc;
using iobuff::flush;
namespace Flow{
const int N=3.2e5+5,M=1e6+5,inf=1e9;
struct Edge{
int fr,to,next,flow;
}e[M];
int head[N],ecnt=1,tot;
inline void adde(int u,int v,int flow){
e[++ecnt]=(Edge){u,v,head[u],flow};head[u]=ecnt;
e[++ecnt]=(Edge){v,u,head[v],0};head[v]=ecnt;
}
inline void init(){
memset(head+1,0,tot<<2);
ecnt=1;
tot=0;
}
int dep[N],cur[N],q[N];
inline bool bfs(int s,int t){
memset(dep+1,0x3f,tot<<2);
dep[s]=0;
int l=1,r=1;q[l]=s;
while(l<=r){
int u=q[l++];
cur[u]=head[u];
if(t==u)return 1;
for(int i=head[u],v;i;i=e[i].next){
if(e[i].flow&&dep[v=e[i].to]>dep[u]+1){
dep[q[++r]=v]=dep[u]+1;
}
}
}
return dep[t]>1];
int head[N],ecnt,cur[N];
inline void adde(int u,int v){
e[++ecnt]=(Edge){v,head[u]};head[u]=ecnt;
}
map mapp;
int fr[N],to[N],pre[N],nxt[N],n,m;
int ans;
map,int> mapp1;
int inde;
inline void init(){
memset(head+1,0,(2*n+2*m+2)<<2);
ecnt=0;
inde=0;mapp1.clear();
}
inline int gid(int u,int v){
if(mapp1.count(make_pair(u,v)))return mapp1[make_pair(u,v)];
else return mapp1[make_pair(u,v)]=++inde;
}
inline int gid1(int u,int v){
if(mapp1.count(make_pair(u,v)))return mapp1[make_pair(u,v)];
else return 0;
}
vector buc_down[N];
bool del[N],vis[N];
int deg[N],Nxt[N],ed[N],st[N],Pre[N];
inline void Add(int u,int v){
if(!v||!u)return;
Nxt[u]=v;
Pre[v]=u;
}
inline void Cut(int u,int v){
if(!v||!u)return;
Nxt[u]=Pre[v]=0;
}
void solve_notC(){
for(int i=1;i<=m;++i){
if(nxt[i]){
int t=gid1(to[i],fr[i]);
if(t&&buc_down[t].size()){
del[i]=1;
del[*buc_down[t].rbegin()]=1;
Nxt[i]=*buc_down[t].rbegin();++deg[*buc_down[t].rbegin()];
Add(i,Nxt[i]);
buc_down[t].pop_back();
ans+=2;
}
}
}
}
int dfs(int u){
if(u==2*n+2*m+2)return u;
for(int &i=cur[u];i;i=e[i].next){
int ret=0;
if(ret=dfs(e[i].to)){
i=e[i].next;
if(ret==2*n+2*m+2)return u;
else return ret;
}
}
return 0;
}
int stac[N],top,fat[N],sz[N],bc[N];
bool instac[N];
void dfs1(int u){
stac[++top]=u;
instac[u]=1;
vis[u]=1;
int v=Nxt[u];
if(vis[v]){
if(instac[v]){
if(pre[v]==fr[u]){
int p1=Nxt[v],p2=Nxt[ed[fr[v]]];
Cut(v,Nxt[v]);
Cut(ed[fr[v]],p2);
Add(ed[fr[v]],p1);
Add(v,p2);
}else{
int p2=Pre[ed[fr[v]]];
Cut(u,v);
Cut(p2,ed[fr[v]]);
Add(p2,v);
Add(u,ed[fr[v]]);
}
}
}else if(v){
dfs1(v);
}
instac[u]=0;--top;
}
int main(){
int T;read(T);
for(int o=1;o<=T;++o){
read(n);read(m);
mapp.clear();
Flow::init();
ans=0;
for(int i=1;i<=n;++i){
string name;
tostring(name);
mapp[name]=i;
}
init();
for(int i=1;i<=m;++i){
del[i]=0;deg[i]=0;vis[i]=0;Nxt[i]=0;Pre[i]=0;
buc_down[i].clear();
string name;
tostring(name);
fr[i]=mapp[name];
tostring(name);
if(mapp.count(name))to[i]=mapp[name];
else to[i]=0;
tostring(name);
pre[i]=nxt[i]=0;
if(to[i]&&name=="loushang"){
nxt[i]=to[i];
}else if(to[i]&&name=="louxia"){
pre[i]=to[i];
buc_down[gid(fr[i],to[i])].push_back(i);
}else to[i]=0,ed[fr[i]]=i;
++sz[fr[i]];bc[fr[i]]=i;
}
solve_notC();
int s=2*n+2*m+1,t=s+1;
Flow::tot=t;
for(int i=1;i<=m;++i){
if(!del[i]&&pre[i])
if(sz[pre[i]]>1)Flow::adde(2*m+pre[i],i+m,1);
else Flow::adde(bc[pre[i]],i+m,1);
else if(!del[i]&&nxt[i]){
if(sz[nxt[i]]>1)Flow::adde(i,2*m+nxt[i]+n,1);
else Flow::adde(i,m+bc[nxt[i]],1);
}
if(!del[i]||!pre[i]){
if(sz[fr[i]]>1)Flow::adde(2*m+fr[i]+n,i+m,1);
Flow::adde(i+m,t,1);
}
if(!del[i]||!nxt[i]){
Flow::adde(s,i,1);
if(sz[fr[i]]>1)Flow::adde(i,2*m+fr[i],1);
}
}
ans+=Flow::maxflow(s,t);
putint(ans);
for(int i=2;i<=Flow::ecnt;i+=2)
if(!Flow::e[i].flow)adde(Flow::e[i].fr,Flow::e[i].to);
for(int i=1;i<=t;++i)cur[i]=head[i];
for(int i=1;i<=m;++i){
int v=dfs(i);
if(v)
Nxt[i]=v-m,Add(i,Nxt[i]);
}
for(int i=1;i<=m;++i)
if(!vis[i])
dfs1(i);
for(int i=1;i<=m;++i)++deg[Nxt[i]];
for(int i=1;i<=m;++i){
if(!deg[i]){
int u=i;
for(;u;u=Nxt[u])
putint(u,' ');
}
}
pc('\n');
}
flush();
return 0;
}
Day 2
T1 卡牌 card
link
题意
有 \(n\) 个数，第 \(i\) 个数是 \(a_i\)。有 \(m\) 次询问，每次给出 \(c\) 个质数 \(s_i\)，求有多少种选数的方案使得这些数的积能被每个质数整除。答案 \(\bmod 998244353\)。
数据范围：\(n\le 10^6,m\le 1500,\sum c\le 18000,1\le a_i,s_i\le 2000\)。
solution
一种暴力做法是直接装压维护当前出现过的质数集合。注意到值域很小，\(\sqrt{2000}\approx 44.7\) 以内的质数只有 \(14\) 个，而第 \(14\) 个质数 \(43\times 47=2021>2000\)，我们暴力维护最小的 \(B=13\) 个质数的出现情况，剩下的大质数最多出现 \(1\) 个。把所有数按照大质数分类，每一类预处理 \(f_s\) 表示出现了 \(s\) 集合内的所有小质数的方案数。这样最终答案就是一个或卷积的形式。
但是这样复杂度还是很高，考虑优化。首先考虑 FWT，我们要算的东西应该是若干个 FWT 之后东西对位相乘，然后最后 IFWT 回去。IFWT 的复杂度是 \(O(m2^{B}B)\) 的，可以接受。
如果询问的质数中不包含 \(x\) 的大质数，那么 \(x\) 对答案的贡献是：卷上一个 \(f_0=1,f_x=2^{cnt}-1\)。其中 \(cnt\) 表示 \(n\) 个数中 \(x\) 的出现此次数。我们预处理出所有 \(x\) 的 \(f\) FWT 之后的积，当作询问的质数中不包含任意一个 \(x\) 的大质数。
如果询问的质数中包含 \(x\) 的大质数，那么 \(x\) 对它的大质数的答案的贡献是：卷上一个 \(g_0=1,g_x=2^{cnt}-1\)。同时，\(x\) 还对上面的答案有贡献，需要在原来的答案中把它的贡献除掉。我们预处理出每个大质数的 FWT 结果（即 \(FWT(\prod g)\)），同时预处理出所有 \(x\) 的 \(f\) FWT 之后的积，要在答案中把它除掉。
注意到要卷的东西都只有 \(2\) 项，可以 \(O(2^B)\) 求出 FWT 之后的结果，预处理复杂度 \(O(V2^B)\)，\(V\) 是值域。
询问的时候把询问的质数中不包含 \(x\) 的大质数的 \(x\) 的贡献全部算上（即全局积除掉询问中出现的大质数的贡献），然后再把大质数的贡献算尽来。复杂度 \(O(\sum c2^B)\)。
总复杂度 \(O(V2^B+\sum c2^B+m2^BB)\)。
view code
#include
using namespace std;
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*f;
}
const int N=2005,M=2e4+5,mod=998244353;
const int p1[]={2,3,5,7,11,13,17,19,23,29,31,37,41};
inline int add(int a,int b){return (a+b>=mod)?a+b-mod:a+b;}
inline int dec(int a,int b){return (a-b<0)?a-b+mod:a-b;}
inline void Add(int &a,int b){a+=(a+b>=mod)?b-mod:b;}
inline void Dec(int &a,int b){a-=(a-b<0)?b-mod:b;}
inline int quick_pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ret=1ll*ret*a%mod;
return ret;
}
inline int Inv(int a){return quick_pow(a,mod-2);}
int Pow[N*N],cnt[N],n,m,mx,a[N],s[M];
inline void FWT_or(int *f,int len,int x){
for(int mid=1,k=2;k<=len;mid<<=1,k<<=1)for(int i=0;i0?Add(f[i+j+mid],f[i+j]):Dec(f[i+j+mid],f[i+j]);
}
int prime[N],pcnt,F[N>>1][1<<14],prod[N>>1][1<<14],rk[N];
bool vis[N];
inline int gets(int x){
int ret=0;
for(int i=0;i<13;++i)
if(x%p1[i]==0)ret|=(1<mx)fff=0;
}
if(!fff){
puts("0");
continue;
}
sort(s+1,s+1+c);
c=unique(s+1,s+1+c)-s-1;
memcpy(F[0],prod[0],sizeof(F[0]));
for(int i=1;i<=c;++i){
if(s[i]<=41)continue;
int x=rk[s[i]];
for(int j=0;j<(1<<13);++j)
F[0][j]=1ll*F[0][j]*prod[x][j]%mod*F[x][j]%mod;
}
FWT_or(F[0],1<<13,-1);
int ans=0;
for(int i=0;i<(1<<13);++i)if((i&S)==S)Add(ans,F[0][i]);
printf("%d\n",ans);
}
return 0;
}
T2 序列变换 bracket
link
题意
给定一个长为 \(2n\) 的合法括号串，每个左括号有一个权值 \(val_i\)，你可以进行如下两种操作：
- 交换形如
p(A)(B)q的串中A和B之间的两个括号，变换为p(A()B)q（其中p,q为任意串，可以为空，但不一定分别为合法括号序列，A和B必须是合法非空括号序列，下同），它的代价为 \(x\) 乘(A)中第一个左括号的权值加上 \(y\) 乘(B)中第一个左括号的权值。 - 交换形如
pABq的串中的A和B，变换为pBAq，这个操作不需要代价。
其中 \(x,y\in\{0,1\}\)，权值会随着左括号的移动而移动。
你要求最终的括号串中不存在子串 )(，求最小代价。
数据范围：\(n\le 4\times 10^5,1\le val_i\le 10^7\)。
solution
观察这个变化究竟是在干什么。
我们把括号树建出来，称一个括号在第 \(i\) 层表示它的括号树上的深度为 \(i\)。那么我们的操作相当于是：
把第 \(i\) 层的所有括号拿出来，任选这一层的两对括号 \(A,B\)（因为操作 \(2\) 不花费代价），以 \(x\cdot val_A+y\cdot val_B\) 的代价将括号 \(B\) 扔到下一层去。重复此操作直到这一层只剩下 \(1\) 个括号，把这个括号留在这一层，开始做下一层。
更抽象一点，每一层有若干个数，每次要选择两个数 \(a_1,a_2\)，以 \(x\cdot a_1+y\cdot a_2\) 的代价将 \(a_2\) 扔到下一层去。每次选择一个数留在当前层，剩下的都必须要扔到下面一层去。
根据 \(x,y\) 的取值分类讨论，设当前层有 \(m\) 个数，最大值为 \(mx\)，最小值为 \(mn\),所有数的和是 \(sum\)：
- \(x=1,y=1\)
一共有 \(2(m-1)\) 个代价，每个数都至少对代价贡献了一次。
那么贪心的，从次小值开始，每次以 \(a_x+mn\) 的代价把 \(a_x\) 放到下一层，最后用 \(mx+mn\) 的代价把 \(mn\) 放到下一层，\(mx\) 留在当前层。总代价是 \(sum+(m-2)mn\)。
随便使用一个能支持删除最大值和取最小值的数据结构（比如 multiset） 维护即可。
- \(x=0,y=1\)
代价是被放到下一层的数的大小，用最大值把所有其他数都方下去即可。代价是 \(sum-mx\)。同样可以用 multiset/priority_queue 维护。
- \(x=1,y=0\)
显然我们希望用最小的代价把所有数都放下去，即用 \(mn\) 的代价把想要方下去的东西方下去。设不放下去的数是 \(c\)，再以 \(c\) 的代价把 \(mn\) 放下去即可。（在只剩 \(2\) 个串的时候直接把要放下去用另外一个数放下去即可）
除了最后一层剩下的括号不需要贡献代价之外，其他所有串都会在被留在当前层时贡献 \(1\) 的代价。所以贪心的，我们把最大值一直往下放，直到放到最后一层。
所以有贪心：如果当前的集合内有全局最大值 \(Mx\)，我们要确保 \(Mx\) 被放下去，同时我们要确保 \(mn\) 被放了下去（比如在出现了全局最大值的时候用全局次大值把 \(mn\) 放进去）。
不过现在有点问题：当前层只有 \(2\) 个括号，那么只能把 \(Mx\) 和 \(mn\) 中的一个放下去，而我们没办法贪心地选择应该把哪个放下去。
设初始时，每层的数的数量为： \(1,1,1,\cdots,1,2,1,1,\cdots 1,x\)（\(x>1\)）。
把最开始的一段全是 \(1\) 的先删掉，变成 \(2,1,1,\cdots 1,x\)。对于 \(x\) 之前的这一段前缀，每层在处理的时候都会是 \(2\) 个 \(\to 1\) 个，下一层又加一个进来。所以这一段前缀中，每层的数的数量都是 \(2\)。因为每层至少加进来一个数，所以每层的数量是先单调不降，后每次减 \(1\)。所以后面再出现 \(2\) 就是最后一步了，删掉一个就完了。
我们最终留下来的数一定是这些每层处理 \(2\) 个数的层的最大值/最小值，因为只有这两个值会影响答案。
分留下最大值/最小值讨论，然后做上面的每层都 \(\ge 3\) 个数的贪心。
multiset 维护，复杂度 \(O(n\log n)\)。
view code
#include
using namespace std;
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*f;
}
const int N=8e5+5;
#define ll long long
char s[N];
int R[N],L[N],stac[N],top,n,x,y,val[N],a[N],cntl[N],cntr[N],dep[N];
vector buc[N];
int mxdep;
ll sl[N];
void build(int l,int r,int depp){
cntl[l]=cntr[l]=1;
sl[l]=a[l];
++depp;
dep[l]=dep[r]=depp;
mxdep=max(mxdep,depp);
buc[depp].push_back(a[l]);
if(r<=l+1)return;
for(int i=l+1;i s;
if(cur>=0)s.insert(cur);
bool flag=0;
ll ans=0;
for(int i=d;i<=mxdep||s.size()>1;++i){
for(int x:buc[i])s.insert(x);
if(s.size()==2){
ans+=*s.begin();
break;
}
flag|=(*s.rbegin())==mx;
if(flag){
int mm=*prev(s.end());
s.erase(prev(s.end()));
ans+=1ll*(*s.begin())*(s.size()-1)+(*s.rbegin());
s.erase(prev(s.end()));
s.insert(mm);
}else{
ans+=1ll*(*s.begin())*(s.size()-2)+(*s.rbegin());
s.erase(prev(s.end()));
}
}
return ans;
}
int main(){
n=read();x=read();y=read();
if(x==0&&y==0){
puts("0");
return 0;
}
scanf("%s",s+1);
s[0]='(';s[n+n+1]=')';
for(int i=1;i<=n;++i)
val[i]=read();
int cnt=-1;
for(int i=0;i<=n+n+1;++i){
if(s[i]=='('){
stac[++top]=i;
++cnt;
a[i]=val[cnt];
}else{
R[stac[top]]=i;
L[i]=stac[top];
--top;
}
}
build(0,n+n+1,-1);
ll ans=0;
if(x==1&&y==1){
multiset s;
ll sum=0;
for(int i=1;i<=mxdep||s.size()>1;++i){
for(int x:buc[i])s.insert(x),sum+=x;
if(s.size()>1)ans+=sum+1ll*(*s.begin())*(s.size()-2);
sum-=*s.rbegin();
s.erase(prev(s.end()));
}
printf("%lld\n",ans);
}else if(y==1){
priority_queue q;
ll sum=0;
for(int i=1;i<=mxdep||q.size()>1;++i){
for(int x:buc[i])q.push(x),sum+=x;
if(q.size()>1)ans+=sum-q.top();
sum-=q.top();
q.pop();
}
printf("%lld\n",ans);
}else{
int pos1=1;
for(int i=1;i<=mxdep;++i){
if(buc[i].size()==1)pos1=i+1;
else break;
}
int pos2=0,mn=1e9,mx=0;
for(int i=pos1,cnt=0;!pos2;++i){
cnt+=buc[i].size();
if(cnt!=2)pos2=i;
else{--cnt;for(int x:buc[i])mn=min(x,mn),mx=max(x,mx);}
}
if(pos1==pos2)
ans=work(-1,pos2);
else{
ans=1e18;
{
ll sum=0;
multiset s;
for(int i=pos1;i s;
for(int i=pos1;i T3 最大权独立集问题
link
题意
给定一个二叉树，点有点权，删一条边的代价是两个端点的点权和，删完之后交换两个点的点权。你需要找到一个删边的顺序，要把所有边删完，最小化代价之和。
数据范围：\(n\le 5000,1\le d_i\le 10^9\)。
solution
显然考虑树形 DP，先考虑一个暴力的树形 DP，设 \(f_{u,x,y}\) 表示考虑以 \(u\) 为根，从子树内换进来的值是 \(d_y\)，从子树外换出去的值是 \(d_x\)，把子树内边都断完的最小代代价（算上把 \(d_x\) 换出去的代价）。状态数就已经是 \(O(n^3)\) 了，无法接受。
第三维是把状态数变高的罪魁祸首，我们考虑能不能用点别的替换掉它。\(f_{u,x,i}\) 表示考虑以 \(u\) 为根，从子树外换出去的值是 \(d_x\)，从子树外换进来的数还在字数内被换了 \(i\) 次，把子树内边都断完的最小代代价。如果我们知道是 \(y\) 被换进字数内，代价就是 \(d_y\times i+f_{u,x,i}\)。
状态数看起来还是 \(O(n^3)\) 的，不过对于 \(u\) 和 \(x\)，设 \(v\) 为 \(u\) 的两个儿子中是 \(x\) 的祖先的那一个，\(v'\) 为 \(u\) 非 \(v\) 的儿子，\(f_{u,x,i}\) 的所有 \(i\) 都 \(\le v'\) 子树的所有点中离 \(u\) 距离的最大值。根据树形背包的复杂度分析，现在的状态数也是 \(O(n^2)\) 的。
然后考虑转移：
先只考虑一个度数为 \(3\) 的点的转移（即这个点有左儿子，记为 \(ls\)；右儿子，记为 \(rs\)，父亲，记为 \(fa\)）。
- 断边顺序为 \(fa,ls,rs\)
此时换出去的值一定是自己，换进 \(rs\) 的值是 \(ls\) 换上来的值，\(fa\) 的值会进 \(ls\) 的子树，那么有
\[f_{u,u,i+1}\gets f_{ls,v_1,i}+f_{rs,v_2,j}+d_{v_1}(j+1)+d_u \]预处理 \(mn_j=\min_{v_2}\{f_{rs,v_2,j}\}\)。枚举 \(v_1\)，然后再枚举 \(j\)，求出 \(mn2=\min\{mn_j+d_{v_1}(j+1)\}\)，再枚举 \(i\)，转移到 \(f_{u,u,i}\gets mn2+f_{ls,v_1,i}+d_u\)。这样转移的复杂度和状态数是一样的。
- 断边顺序为 \(ls,fa,rs\)
此时换出去的值一定是 \(ls\) 换出来的值，换进 \(ls\) 的值是 \(u\) 的值，\(fa\) 的值会进 \(rs\) 的子树，那么有
\[f_{u,v_1,j+1}\gets f_{lc,v_1,i}+f_{rc,v_2,j}+d_u(i+1)+d_{v_1} \]同样可以优化到 \(O(n^2)\)。
- 断边顺序为 \(ls,rs,fa\)
此时换出去的值一定是 \(rs\) 换出来的值，换进 \(ls\) 的值是 \(u\) 的值，换进 \(rs\) 的值是 \(ls\) 换上来的值，同时换进来的值会留在 \(u\)，那么有
\[f_{u,v_2,0}\gets f_{lc,v_1,i}+f_{rc,v_2,j}+d_u(i+1)+d_{v_1}(j+1)+d_{v_2} \]同样可以优化到 \(O(n^2)\)。
-
\(3!\) 中的剩下三种把 \(ls\) 和 \(rs\) 交换再跑一遍即可。
-
对于当前点为根 (\(1\) 号点）的情况，枚举先删 \(ls\) 还是 \(rs\)，直接对答案做出贡献。
-
对于当前点没有 \(rs\) 的情况：
- 断边顺序为 \(fa,ls\)：\(f_{u,u,i+1}\gets f_{ls,v_1,i}+d_u\)
- 断边顺序为 \(ls,fa\)：\(f_{u,v1,0}\gets f_{lc,v_1,i}+d_u(i+1)+d_{v_1}\)
总复杂度 \(O(n^2)\)。
view code
#include
using namespace std;
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*f;
}
const int N=5005;
vector e[N],son[N];
#define ll long long
#define pb push_back
templateinline void Max(T&a,T b){if(ainline void Min(T&a,T b){if(a>b)a=b;}
struct Val{
ll *f;
int sz=0;
inline ll& operator[](int x){return f[x];}
inline void resize(int x){f=new ll[x];sz=x;memset(f,0x3f,x<<3);}
inline ll gmn(){
ll ret=1e18;for(int i=0;i 游记参见