noone___'s blog
0%

10901202-AGC024

发表于 更新于 分类于
AGC024

D

给定一颗点数为 $N$ 的无根树，对于点 $u,v$ 若以 $u$为根的树与以 $v$ 为根的树同构，则 $uv$ 染上同一种颜色 ，可以给这个树加若干点，求加完点后树最少有多少颜色，以及此时最少有多少叶子节点

考虑当深度相同时树同构，那么最终树比绑定时某个点或边为根，深度相同的所有点的子树同构，颜色数为深度

那么枚举每个点为根，找最小深度即可

对于最小叶节点树，深度相同的所有点子树同构相当于深度相同的点度数相同，对每一层连向下一层数取最大值相乘即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int N=2e5+100;
int n;
vector<int> G[N];
int deg[N],mxdeg[N],dep[N];
queue<int> q;
PIL res;

inline void add(int f,int t){ G[f].push_back(t),G[t].push_back(f),++deg[f],++deg[t];}
inline void chmax(int &x,int y){ x<y ? x=y : x;}

int bfs(int u,int v){
    int rt=0;
    for(rei i=1;i<=n;++i) dep[i]=0;
    q.push(u),dep[u]=1;
    if(v) q.push(v),dep[v]=1;
    while(q.size()){
        rei u=q.front(); q.pop();
        chmax(mxdeg[dep[u]],deg[u]),chmax(rt,dep[u]);
        for(rei i=0,v;i<G[u].size();++i) if (!dep[ v=G[u][i] ]) dep[v]=dep[u]+1,q.push(v);
    }
    return rt;
}

PIL work(int u,int v){
    PIL rt;
    for(rei i=1;i<=n;++i) mxdeg[i]=0;
    rt=(PIL){ bfs(u,v),mxdeg[1]-(v!=0)};
    for(rei i=2;i<=n;++i){
        if (mxdeg[i]==1) break;
        rt.second*=(mxdeg[i]-1);
    }
    if(v) rt.second*=2;
    return rt;
}

int main(){
    scanf("%d",&n);
    if(n==2) return puts("1 2"),0;
    for(rei i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),add(u,v);
    res.first=200000;
    for(rei i=1;i<=n;++i){
        res=min(res,work(i,0));
        for(rei j=0;j<G[i].size();++j) res=min(res,work(i,G[i][j]));
    }
    printf("%d %d\n",res.first,res.second);
    getchar(),getchar();
    return 0;
}

E

给定 $n,m,k$ ，求满足条件的 $(n+1)$ 元序列组 $A_0,A_1,…A_n)$ 的数量，其中满足： $\forall i$ , $A_i$ 由 $1\sim k$ 组成且长度为 $i$ ； $\forall i,i>1$ ，序列 $A_{i-1}$ 是 $A_i$ 的子序列 ； $\forall i,i>1$ ，序列 $A_{i-1}$ 在字典序意义下严格小于 $A_i$

在 $aaab$ 中插入 $a$ 形成 $aaaab$ 时，字典序变小

那么每次将 $a$ 放在 $A_i$ 最后则不会算重

那么在 $A_i\rightarrow A_{i+1}$ 的过程中，满足加入的 $a$ 大于其后面的数（包括在末尾的情况）

设 $dp_{i,j,k}$ 表示第 $i$ 个操作，放到了数字 $j$ ，前面有 $k+1$ 个位置可以放

有转移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N=310;
int n,m,mod,dp[N][N][N];

int main(){
    scanf("%d%d%d",&n,&m,&mod);
    dp[0][1][0]=1;
    for(rei i=0;i<=n;++i){
        for(rei j=1;j<=m;++j){
            for(rei k=i;k>=0;--k){
                if(!dp[i][j][k]) continue;
                if(!k) dp[i][j+1][i]=(dp[i][j+1][i]+dp[i][j][k])%mod;
                else dp[i][j][k-1]=(dp[i][j][k-1]+dp[i][j][k])%mod;
                if(i<=n-1) dp[i+1][j][k]=(dp[i+1][j][k]+(ll) (k+1)*dp[i][j][k]%mod)%mod;
            }
        }
    }
    printf("%d\n",dp[n][m][0]);
    getchar(),getchar();
    return 0;
}

F

一个 $0/1$ 串集合 $S$ ，其中每个串的长度不超过 $N$ ，求出 $S$ 中至少是 $K$ 个串的子序列的最长串，输出字典序最小的解。由于 $S$ 很大，这样描述 $S$ ：给出 $N+1$ 个 $01$ 串，第 $i$ 个长度为 $2^{i-1}$ ；第 $i$ 个字符串的第 $j$ 个字符代表数字为 $j-1$，长度为 $i-1$ 的二进制表示是否出现在 $S$ 中

这个才应该是子序列自动机的模板题吧qwq

直接考虑所有 $2^{n+1}-1$ 个长度 $0\sim n$ 的 $01$ 串，计算其中有多少是 $S$ 子串的子序列

考虑如何判断串 $A=\{0101110\}$ 是串 $B={1010111001}$ 的子序列：

用 $A$ 的第一位 $0$ 去匹配 $B$ 中的第一个 $0$ ，转化为 $A=\{101110\},b=\{10111001\}$

对于 $01$ 串 $x\in S$ ,希望 $x$ 的所有子序列 $y$ 的 $val$ 值加 $1$ ，即，用 $dp$ 维护路径数

对于匹配的两个字符串 $A,B 有 |A|+|B|\leq n=20$ 只记录 $A+B$ ，长度，分界点，状压出路径即可

对于每次转移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const int N=1<<22;
const int INF=0x3f3f3f3f;
int Data[N][21],n,k,mem[N<<1];
char s[N];
int mx=INF,mxl=0;

inline void update(int sta,int nums,int len){
    mem[ sta|(1<<len) ]+=nums;
    if(mem[ sta|(1<<len) ]>=k)
        if(mxl<len) mxl=len,mx=sta;
        else if(mxl==len) mx=min(mx,sta);
}

int main(){
    scanf("%d%d",&n,&k);
    for(rei i=0;i<=n;++i){
        scanf("%s",s);
        for(rei j=0;j<(1<<i);++j){
            rei tmp=j; tmp|=1<<i;
            Data[tmp][0]+=(s[j]=='1');
        }
    }
    for(rei i=0;i<=n;++i){//拿了i个
        for(rei j=0;j<(1<<(n+1));++j){//一共有n+1位
            if(!Data[j][i]) continue;//t-s
            ull s=j&((1<<i)-1),t=j>>i;
            rei l=(32-__builtin_clz(t))-1;//有t多少位
            if(i) update(s,Data[j][i],i);
            if(!l) continue;
            t^=(1<<l);
            rei first1=(32-(t?__builtin_clz(t):32));//第一个1的位置
            ull num=t<<(32-l);
            rei first0=l ? (l-((~num) ? __builtin_clz(~num) : l)) : 0,newt,news;
            if(first1>0){//删去1
                newt=t&((1<<first1)-1);
                newt|=(1<<first1-1);
                news=(s<<1)|1;
                Data[ (newt<<(i+1))|news ][i+1]+=Data[j][i];
            }
            if(first0>0){//删去0
                newt=t&((1<<first0)-1);
                newt|=(1<<first0-1);
                news=(s<<1);
                Data[ (newt<<(i+1))|news ][i+1]+=Data[j][i];
            }
        }
    }
    if(mx==INF) return puts(""),0;
    for(rei i=mxl;i;--i) printf("%d",(mx&(1<<i-1)) ? 1 : 0); puts("");
    getchar(),getchar();
    return 0;
}