noone___'s blog
0%

21801202-AGC009

发表于 更新于 分类于
AGC009

D

给定一棵树 $T$ ，递归定义一棵树是否为 $k$ -可点分的：$1$ : 包含一个顶点的树是 $0$ -可点分，$2$ :若存在顶点 $v\in T$ ，满足将 $v$ 删去后所有子树均为 $k$ -可点分的，则 $T$ 为 $(k+1)$ -可点分，求最小的 $k$ 使 $T$ 是 $k$ -可点分的

设每个点在点分治树种深度 $k_i$ ，对于任意两个深度相同的点路径上深度最大的点一定大于 $k_i$

由此得到性质：

  • 对于点 $u$ ，如果在其两个不同子树种同时存在 $k$ ，且到 $u$ 的路径上没有超过 $k$ 的点，则其标号一定大于 $k$
  • 如果某个子树种存在一个值 $k$ 且从它到 $x$ 的路径上都没有超过 $k$ 的点，则 $x$ 标号不能为 $k$
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
const int N=1e5+100;
int n,u,v,ans;
vector<int> a[N];
int bit[N],f[N];

void dfs(int x,int fa){
    rei l=0,Size=a[x].size();
    for(rei i=0;i<Size;++i){
        rei u=a[x][i]; if(u==fa) continue;
        dfs(u,x);
        l|=(bit[x] & bit[u]);
        bit[x]|=bit[u];
    }
    if(!bit[x]) bit[x]=1;
    else{
        while((1<<f[x])<l || (1<<f[x])&bit[x]) ++f[x];
        bit[x]=(bit[x]/(1<<f[x]) * (1<<f[x])) | (1<<f[x]);
    }
    ans=max(ans,f[x]);
}

int main(){
    scanf("%d",&n);
    for(rei i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),a[u].push_back(v),a[v].push_back(u);
    dfs(1,0);
    printf("%d",ans);
    getchar(),getchar();
    return 0;
}

E

有 $n$ 个 $0$ 和 $m$ 个 $1$ ，给定 $K\geq 2$ 且 $n+m\equiv \pmod {K+1}$ ，不断选取 $K$ 个数并替换为他们的平均数，求最终得到的数有多少可能的取值

考虑建出严格 $k$ 叉树，所有 $0$ 的深度为 $a_1,a_2,…,a_N$ ，所有 $1$ 的深度为 $b_0,b_1,…,b_m$ ,则最终所得到的数就等于 $B=\sum_{i=1}^m k^{-b_i}$

设 $A=\sum_{i=1}^n k^{-a_i}$ ，即，将 $0,1$ 翻过来，有 $A+B=1$

将 $B$ 以 $k$ 进制呈现，进位过程中，$\sum$ 数码 $\mod {k-1}$ 的值是不变量，一个必要条件就是 $\sum数码 \equiv \pmod {k-1}$ ，且有 $\sum 数码 \leq m$

则问题转化为求多少个数对 $(A,B)$ 满足 $A+B=1$ ，且 $S_k(A)\equiv N\pmod {k-1} 或 S_k(B)\equiv m\pmod{k-1}或S_k(B)\leq m$ ，其中 $S_k(x)$ 表示 $x$ 在 $k$ 进制下数码和

显然 $S_k(A)\equiv N\pmod {k-1}\Leftrightarrow S_k(B)\equiv m\pmod{k-1}$ ，保证其一即可

由于 $A+B=1$ ，可得 $S_k(A)+S_k(B)=(i-1)\times (k-1)+k=i\times (k-1)+1$ ，即， $S_k(B)\leq m \Leftrightarrow S_k(A)\geq i\times (k-1)+1-m$

至此，所有条件仅与 $S_k(A)$ 有关

做一个简单的数位 $\text{dp}$ ，加前缀和转移即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N=2010;
const int mod=1e9+7;
int A,B,k,f[N<<1][N],g[N<<1][N];
ll ans;

inline int &reduce(int &x){ return x+=x>>31&mod;}
inline int &add(int &x,const int y){ return x+=y-mod,x+=x>>31&mod;}

int main(){
    scanf("%d%d%d",&A,&B,&k);
    if(A>B) A^=B,B^=A,A^=B;
    rei limit=(A+B-1)/--k;
    **f=1;
    for(rei i=1;i<=limit;++i){
        for(rei j=0;j<=A;++j) add(g[i][j+1]=g[i][j],add(f[i][j]=f[i-1][j],g[i-1][j]));
        for(rei j=A;j>=k;--j) reduce(g[i][j]-=g[i][j-k]);
        for(rei l=max(A%k,i*k-B+1),r=i*k-l+1; l<=A && r>=0 ;l+=k,r-=k) ans+=g[i][l];
    }
    printf("%d\n",ans%mod);
    getchar(),getchar();
    return 0;
}