前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >YbtOJ 604「强连通分量」字符变换

YbtOJ 604「强连通分量」字符变换

作者头像
yzxoi
发布2022-09-19 14:01:57
3850
发布2022-09-19 14:01:57
举报
文章被收录于专栏:OI

题目链接:YbtOJ #604

小 A 有一个长度为 n 字符串 s,满足 s 中只有 A,B,C,D 四种字符。

他还有 m 个二元组,第 i 个二元组可以用两个 等长 的字符串 (a_i,b_i) 表示。

小 A 可以进行两种操作:

  1. 任意交换字符串 s 中两个不同位置上的字符。
  2. 选择一个 i,截取 s 中一个与 a_i 相同的子串,将其替换为 b_i

小 A 想要知道从 任意 初始字符串 s 开始 连续 进行若干次变换,在这一过程中最多能得到多少种不同的字符串。

定义两个字符串不同,当且仅当它们存在至少一个位置上的字符不同。

1\leq n\leq 301\leq m\leq 1000

Solution

考虑到可以任意交换字符,我们直接用三元组 (x,y,z) 表示一种序列,序列中有 x 个 A,y 个 B,z 个 C,那么显然就有 (n-x-y-z) 个 D

那么,如果可以到达一种序列,能得到的字符串个数可以用可重排列数计算(即 \frac{n!}{x!\cdot y!\cdot z!\cdot (n-x-y-z)!})。

一种序列能通过变换方式 (a_i,b_i) 变成另一种序列,要满足四种字符的个数都大于等于 a_i 中这些字符的个数。

若序列 A 能变成序列 B,我们就连一条从 A 向 B 的有向边。按这种方式建图,就是要求出从一个点出发最多能到达多少种不同的点,因此 Tarjan 给强连通分量缩点后拓扑跑一下就可以了。

求可重排列数的时候由于无法直接求 n!,可以先把每个数质因数分解然后抵消掉再乘起来。

Code

代码语言:javascript
复制
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=35,M=1010;
int n,m,id[N][N][N],cnt,s[N],v[N],pri[N],tot,l[M][4],r[M][4],fir[N*N*N],nxt[N*N*N*M<<1],son[N*N*N*M<<1],ttot,dfn[N*N*N],low[N*N*N],col[N*N*N],stk[N*N*N],cc,top,deg[N*N*N],ccnt;
LL Ans,d[N*N*N],S[N*N*N],w[N*N*N];
I void Add(CI x,CI y){x^y&&(nxt[++ttot]=fir[x],fir[x]=ttot,son[ttot]=y,0);}
#define to son[i]
char sa[N],sb[N];
I void GP(){RI i,j;for(i=2;i<=n;i++) for(!v[i]&&(pri[++tot]=i),j=1;j<=tot&&i*pri[j]<=n;j++) if(v[i*pri[j]]=1,!(i%pri[j])) break ;}
I LL QP(LL a,LL b){LL X=1;W(b) b&1&&(X*=a),a*=a,b>>=1;return X;}
I void Mark(RI x,CI v){RI i;for(i=1;i<=tot;i++) W(!(x%pri[i])) s[pri[i]]+=v,x/=pri[i];}
I void Tarjan(CI x){
    RI i;for(dfn[x]=low[x]=++ccnt,stk[++top]=x,i=fir[x];i;i=nxt[i]) if(!dfn[to]) Tarjan(to),low[x]=min(low[x],low[to]);else if(!col[to]) low[x]=min(low[x],dfn[to]);
    if(dfn[x]==low[x]){col[x]=++cc,S[cc]+=w[x];W(stk[top]^x) col[stk[top]]=cc,S[cc]+=w[stk[top]],top--;top--;}
}
vector<int> G[N*N*N];
#define pb push_back
queue<int> q;
I void Topo(){
    RI i,u;for(i=1;i<=cc;i++) !deg[i]&&(q.push(i),d[i]=S[i]);W(!q.empty()){
        u=q.front(),q.pop();for(auto i:G[u]) d[i]=max(d[i],d[u]+S[i]),!--deg[i]&&(q.push(i),0);
    }return ;
}
int main(){
    freopen("character.in","r",stdin),freopen("character.out","w",stdout);
    RI i,i1,i2,i3,i4,j;LL t;for(read(n,m),GP(),i=1;i<=m;i++) for(scanf("%s%s",sa+1,sb+1),t=strlen(sa+1),j=1;j<=t;j++) l[i][sa[j]-'A']++,r[i][sa[j]-'A']--,r[i][sb[j]-'A']++;
    for(i1=0;i1<=n;i1++) for(i2=0;i1+i2<=n;i2++) for(i3=0;i1+i2+i3<=n;i3++){
        i4=n-i1-i2-i3,id[i1][i2][i3]=++cnt;for(j=1;j<=n;j++) Mark(j,1);
        for(j=1;j<=i1;j++) Mark(j,-1);for(j=1;j<=i2;j++) Mark(j,-1);for(j=1;j<=i3;j++) Mark(j,-1);for(j=1;j<=i4;j++) Mark(j,-1);
        for(t=1,j=1;j<=n;j++) t*=QP(j,s[j]),s[j]=0;w[cnt]=t;
    }for(i1=0;i1<=n;i1++) for(i2=0;i1+i2<=n;i2++) for(i3=0;i1+i2+i3<=n;i3++) for(i4=n-i1-i2-i3,j=1;j<=m;j++) i1>=l[j][0]&&i2>=l[j][1]&&i3>=l[j][2]&&i4>=l[j][3]&&(Add(id[i1][i2][i3],id[i1+r[j][0]][i2+r[j][1]][i3+r[j][2]]),0);
    for(i=1;i<=cnt;i++) !dfn[i]&&(Tarjan(i),0);for(i=1;i<=cnt;i++) for(j=fir[i];j;j=nxt[j]) if(col[i]^col[son[j]]) G[col[i]].push_back(col[son[j]]),deg[col[son[j]]]++;
    for(Topo(),i=1;i<=cc;i++) Ans=max(Ans,d[i]);return writeln(Ans),0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-02-11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Solution
  • Code
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档