8.10 CSP 模拟 17
Bohemian Rhapsody - Queen
Is this the real life? Is this just fantasy?
Caught in a landslide, no escape from reality
Open your eyes, look up to the skies and see
I'm just a poor boy, I need no sympathy
Because I'm easy come, easy go, little high, little low
Any way the wind blows doesn't really matter to me, to me
Mama, just killed a man
Put a gun against his head, pulled my trigger, now he's dead
Mama, life had just begun
But now I've gone and thrown it all away
Mama, ooh, didn't mean to make you cry
If I'm not back again this time tomorrow
Carry on, carry on as if nothing really matters
Too late, my time has come
Sends shivers down my spine, body's aching all the time
Goodbye, everybody, I've got to go
Gotta leave you all behind and face the truth
Mama, ooh (Any way the wind blows)
I don't wanna die
I sometimes wish I'd never been born at all
I see a little silhouetto of a man
Scaramouche, Scaramouche, will you do the Fandango?
Thunderbolt and lightning, very, very frightening me
(Galileo) Galileo, (Galileo) Galileo, Galileo Figaro magnifico
But I'm just a poor boy, nobody loves me
He's just a poor boy from a poor family
Spare him his life from this monstrosity
Easy come, easy go, will you let me go?
Bismillah! No, we will not let you go
(Let him go) Bismillah! We will not let you go
(Let him go) Bismillah! We will not let you go
(Let me go) Will not let you go
(Let me go) Will not let you go
(Never, never, never, never let me go) Ah
No, no, no, no, no, no, no
(Oh, mamma mia, mamma mia) Mamma mia, let me go
Beelzebub has a devil put aside for me, for me, for me!
So you think you can stone me and spit in my eye?
So you think you can love me and leave me to die?
Oh, baby, can't do this to me, baby!
Just gotta get out, just gotta get right outta here
(Ooh)
(Ooh, yeah, ooh, yeah)
Nothing really matters, anyone can see
Nothing really matters
Nothing really matters to me
Any way the wind blows
之前考过所以直接打摆！
T1 弹珠游戏
从小到大枚举弹珠。
注意到在最优策略下，任意时刻拥有弹珠种类不同的人只有四种，例如此时 \(\texttt{R}\) 数量最多，\(\texttt{G}\) 次之，那么一定只有 \(\texttt{RGB},\texttt{RG},\texttt{G}\) 和为空的情况。证明考虑如果同时拥有 \(\texttt{R}\) 和 \(\texttt{G}\)，那么改为 \(\texttt{RG}\) 和空可以使得后者的最小编号更大。
这样每次优先补全一个状态，如果无法补全就新建，维护当前每个状态的个数，乘起来即可，答案还要带上 \(n!\)。
点击查看代码
int n;
char s[maxn];
map<string,int> mp;
int ans;
int main(){
n=read();
scanf("%s",s+1);
ans=1;
for(int i=1;i<=3*n;++i){
if(s[i]=='R'){
if(mp["GB"]){
ans=1ll*ans*mp["GB"]%mod;
--mp["GB"],++mp["RGB"];
}
else if(mp["G"]){
ans=1ll*ans*mp["G"]%mod;
--mp["G"],++mp["RG"];
}
else if(mp["B"]){
ans=1ll*ans*mp["B"]%mod;
--mp["B"],++mp["RB"];
}
else ++mp["R"];
}
else if(s[i]=='G'){
if(mp["RB"]){
ans=1ll*ans*mp["RB"]%mod;
--mp["RB"],++mp["RGB"];
}
else if(mp["R"]){
ans=1ll*ans*mp["R"]%mod;
--mp["R"],++mp["RG"];
}
else if(mp["B"]){
ans=1ll*ans*mp["B"]%mod;
--mp["B"],++mp["GB"];
}
else ++mp["G"];
}
else{
if(mp["RG"]){
ans=1ll*ans*mp["RG"]%mod;
--mp["RG"],++mp["RGB"];
}
else if(mp["R"]){
ans=1ll*ans*mp["R"]%mod;
--mp["R"],++mp["RB"];
}
else if(mp["G"]){
ans=1ll*ans*mp["G"]%mod;
--mp["G"],++mp["GB"];
}
else ++mp["B"];
}
}
for(int i=1;i<=n;++i) ans=1ll*ans*i%mod;
printf("%d\n",ans);
return 0;
}
T2 晚会
最终形成的图要求任意三个节点两两边权 \((a,b,c)\) 满足 \(a=b\le c\)。
两个连通块之间的边定为 \(1\) 即可。
树上一定有合法解，产生限制的边一定较小，因此从大到小枚举边，设当前枚举到 \((u,v,w)\)，那么 \(u\) 连通块和 \(v\) 连通块的连边必须均为 \(w\)。证明考虑节点 \(x\) 此时和 \(u\) 有连边，那么 \((u,v,x)\) 中 \((u,x)\) 的边权不小于 \(w\)，则新建的 \((v,x)\) 边权必须为 \(w\)，类似归纳即可证明，对答案贡献 \(w\times siz_u\times siz_v\)。
之后图上判断不合法方法已经明了了：合并两个连通块时，两个连通块之间全部连边应该相等。这等价于按照上面流程跑最大生成树后，两点树上路径最小值等于两点边权。
点击查看代码
int n,m;
ll ans;
struct edge{
int u,v,w;
edge()=default;
edge(int u_,int v_,int w_):u(u_),v(v_),w(w_){}
bool operator<(const edge&rhs)const{
return w>rhs.w;
}
}e[maxn];
int bel1[maxn],siz1[maxn],cntb;
bool mark[maxn];
int find1(int x){
if(bel1[x]==x) return x;
return bel1[x]=find1(bel1[x]);
}
int bel2[maxn],siz2[maxn];
int find2(int x){
if(bel2[x]==x) return x;
return bel2[x]=find2(bel2[x]);
}
struct Edge{
int v,w;
Edge()=default;
Edge(int v_,int w_):v(v_),w(w_){}
};
vector<Edge> E[maxn];
inline void Kruskal(){
for(int i=1;i<=n;++i) bel2[i]=i,siz2[i]=1;
sort(e+1,e+m+1);
int cnt=0;
for(int i=1;i<=m;++i){
int u=e[i].u,v=e[i].v,w=e[i].w;
int fu=find2(u),fv=find2(v);
if(fu==fv) continue;
E[u].push_back(Edge(v,w));
E[v].push_back(Edge(u,w));
ans+=1ll*w*siz2[fu]*siz2[fv];
bel2[fv]=fu,siz2[fu]+=siz2[fv];
++cnt;
if(cnt==n-cntb) break;
}
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn],dis[maxn];
int top[maxn],dfn[maxn],dfncnt;
int st[maxn][20];
void dfs1(int u,int f,int d){
fa[u]=f,dep[u]=d,siz[u]=1;
int maxson=-1;
for(Edge it:E[u]){
int v=it.v,w=it.w;
if(v==f) continue;
dis[v]=w;
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(siz[v]>maxson) maxson=siz[v],son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t,dfn[u]=++dfncnt;
if(dis[u]) st[dfn[u]][0]=dis[u];
else st[dfn[u]][0]=0x3f3f3f3f;
if(!son[u]) return;
dfs2(son[u],t);
for(Edge it:E[u]){
int v=it.v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline void build(){
for(int k=1;k<=19;++k){
for(int i=1;i+(1<<k)-1<=n;++i){
st[i][k]=min(st[i][k-1],st[i+(1<<k-1)][k-1]);
}
}
}
inline int query(int l,int r){
int k=log2(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
inline int query_min(int u,int v){
int res=0x3f3f3f3f;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
res=min(res,query(dfn[top[v]],dfn[v]));
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
if(u!=v) res=min(res,query(dfn[u]+1,dfn[v]));
return res;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) bel1[i]=i,siz1[i]=1;
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
e[i]=edge(u,v,w);
int fu=find1(u),fv=find1(v);
if(fu!=fv) bel1[fv]=fu,siz1[fu]+=siz1[fv];
}
ans=1ll*n*(n-1)/2;
for(int i=1;i<=n;++i){
if(find1(i)==i){
ans-=1ll*siz1[i]*(siz1[i]-1)/2;
++cntb;
}
}
Kruskal();
for(int i=1;i<=n;++i){
if(!dfn[i]){
dfs1(i,0,0);
dfs2(i,i);
}
}
build();
for(int i=1;i<=m;++i){
int u=e[i].u,v=e[i].v,w=e[i].w;
if(query_min(u,v)!=w) return printf("-1\n"),0;
}
printf("%lld\n",ans);
return 0;
}
T3 优美的字符串
考虑如何判断一个已知串是否合法，设 \(f_{i,0/1,0/1}\) 表示考虑 \(i\) 位置为 \(0\) 或 \(1\) 时，把前缀 \(i\) 处理成只剩一个字符能否是 \(0\) 或 \(1\)。
设第二维是 \(a\)，第三维是 \(b\)。转移自然是 \(f_{i-2}\) 到 \(f_i\)，考虑如果 \(i-2\) 只剩一个字符 \(c\)，那么直接判断 \(F(c,s_{i-1},s_i)\) 是否为 \(b\) 即可转移；否则 \(i-2\) 还剩若干字符，且 \(i-2\) 位置上仍为 \(s_{i-2}\)，那么第一次操作就是 \(F(s_{i-2},s_{i-1},s_i)\) 作为 \(i-2\) 位置新的字符，之后变成子问题 \(f_{i-2,F(s_{i-2},s_{i-1},s_i),b}\)。
发现在已知 \(s_{i-1},s_i\)（这部分是在外层 DP 可以枚举的）以及 \(f_{i-2},s_{i-2}\)（这部分需要考虑）时可以推出 \(f_i\)，那么把 \(f_{i-2},s_{i-2}\) 压成 \(2^5\) 的状态，可以预处理出转移指针 \(trans(S,a,b)\) 表示 \(S\) 状态且 \(s_{i-1}=a,s_i=b\) 时转移到的状态。这样 DP 计数即可。
注意最后算答案时要考虑 \(n\) 位置是 \(0\) 或 \(1\) 并判断对应 \(f_{n,0,1}\) 或 \(f_{n,1,1}\) 的值。
点击查看代码
int t;
int n;
char mp[8];
int F(int a,int b,int c){
return mp[a+b*2+c*4]-'0';
}
char s[maxn];
int last[2][2],now[2][2];
int trans[32][2][2];
int f[maxn][32],ans;
int main(){
t=read();
while(t--){
scanf("%s",mp);
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;++i){
for(int j=0;j<32;++j){
f[i][j]=0;
}
}
for(int j=0;j<32;++j){
last[0][0]=j>>4&1,last[0][1]=j>>3&1,last[1][0]=j>>2&1,last[1][1]=j>>1&1;
int s2=j&1;
for(int s1=0;s1<=1;++s1){
for(int s0=0;s0<=1;++s0){
for(int a=0;a<=1;++a){
for(int b=0;b<=1;++b){
now[a][b]=0;
now[a][b]|=last[F(s2,s1,a)][b];
for(int c=0;c<=1;++c) now[a][b]|=(last[s2][c]&&(F(c,s1,a)==b));
}
}
trans[j][s1][s0]=(now[0][0]<<4)|(now[0][1]<<3)|(now[1][0]<<2)|(now[1][1]<<1)|s0;
}
}
}
if(s[1]!='1') f[1][(1<<4)]=1;
if(s[1]!='0') f[1][(1<<1)+1]=1;
for(int i=3;i<=n;i+=2){
for(int j=0;j<32;++j){
if(!f[i-2][j]) continue;
for(int s1=0;s1<=1;++s1){
for(int s0=0;s0<=1;++s0){
if(s1+'0'!=s[i-1]&&s[i-1]!='?') continue;
if(s0+'0'!=s[i]&&s[i]!='?') continue;
f[i][trans[j][s1][s0]]=(f[i][trans[j][s1][s0]]+f[i-2][j])%mod;
}
}
}
}
ans=0;
for(int j=0;j<32;++j){
if(j&1){
// 1 -> 11
if(j>>1&1) ans=(ans+f[n][j])%mod;
}
else{
// 0 -> 01
if(j>>3&1) ans=(ans+f[n][j])%mod;
}
}
printf("%d\n",ans);
}
return 0;
}
T4 选举
有一个朴素的 \(O(n\sqrt{n}\log n)\) 的莫队+线段树做法。
意识到 \(O(n\sqrt{n})\) 次修改，\(O(n)\) 次查询，可以使用 \(O(1)\) 修改，\(O(\sqrt{n})\) 查询的分块。
区间最大值不支持撤销，改成回滚莫队。复杂度 \(O(n\sqrt{n})\)。
点击查看代码
int n,m,q;
int sizB=317;
int a[maxn],b[maxn];
struct Block{
int cntB;
ll tot[maxn],mxB[maxB];
int bel[maxn],lpos[maxB],rpos[maxB];
inline void build(){
cntB=(m-1)/sizB+1;
for(int i=1;i<=m;++i) bel[i]=(i-1)/sizB+1;
for(int i=1;i<=cntB;++i) lpos[i]=(i-1)*sizB+1,rpos[i]=min(i*sizB,m);
}
inline void update1(int x,int k){
tot[x]+=k,mxB[bel[x]]=max(mxB[bel[x]],tot[x]);
}
inline void update2(int x,pll k){
tot[x]=k.fir,mxB[bel[x]]=k.sec;
}
inline void clear(int x){
tot[x]=0,mxB[bel[x]]=0;
}
inline ll query1(int l,int r){
ll res=0;
if(bel[l]==bel[r]){
for(int i=l;i<=r;++i) res=max(res,tot[i]);
}
else{
for(int i=l;i<=rpos[bel[l]];++i) res=max(res,tot[i]);
for(int i=bel[l]+1;i<bel[r];++i) res=max(res,mxB[i]);
for(int i=lpos[bel[r]];i<=r;++i) res=max(res,tot[i]);
}
return res;
}
inline pll query2(int x){
return make_pair(tot[x],mxB[bel[x]]);
}
}B;
struct Query{
int l,r,vl,vr,id;
Query()=default;
Query(int l_,int r_,int vl_,int vr_,int id_):l(l_),r(r_),vl(vl_),vr(vr_),id(id_){}
bool operator<(const Query &rhs)const{
if((l-1)/sizB==(rhs.l-1)/sizB) return r<rhs.r;
else return (l-1)/sizB<(rhs.l-1)/sizB;
}
}Q[maxn];
pll tmp[maxn];
ll ans[maxn];
int main(){
n=read(),m=read(),q=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) b[i]=read();
B.build();
for(int i=1;i<=q;++i){
int l=read(),r=read(),vl=read(),vr=read();
Q[i]=Query(l,r,vl,vr,i);
}
sort(Q+1,Q+q+1);
int nowB=-1,R;
for(int i=1;i<=q;++i){
if(i==1||(Q[i].l-1)/sizB!=(Q[i-1].l-1)/sizB){
for(int j=1;j<=n;++j) B.clear(a[j]);
}
if((Q[i].l-1)/sizB==(Q[i].r-1)/sizB){
for(int j=Q[i].l;j<=Q[i].r;++j) B.update1(a[j],b[j]);
ans[Q[i].id]=B.query1(Q[i].vl,Q[i].vr);
for(int j=Q[i].l;j<=Q[i].r;++j) B.clear(a[j]);
}
else{
if(nowB!=(Q[i].l-1)/sizB+1){
nowB=(Q[i].l-1)/sizB+1;
R=nowB*sizB;
}
for(int j=R+1;j<=Q[i].r;++j) B.update1(a[j],b[j]);
R=Q[i].r;
for(int j=nowB*sizB;j>=(nowB-1)*sizB+1;--j) tmp[j]=B.query2(a[j]);
for(int j=nowB*sizB;j>=Q[i].l;--j) B.update1(a[j],b[j]);
ans[Q[i].id]=B.query1(Q[i].vl,Q[i].vr);
for(int j=nowB*sizB;j>=(nowB-1)*sizB+1;--j) B.update2(a[j],tmp[j]);
}
}
for(int i=1;i<=q;++i) printf("%lld\n",ans[i]);
return 0;
}