AGC009 做题记录¶

A¶

发现 \(A_N\) 只能被最后一个操作影响，倒着贪心，每次取最小操作次数即可。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n;
ll a[100005],b[100005],ans,num;
int main(){
    n=read();
    rep(i,1,n)a[i]=read(),b[i]=read();
    per(i,n,1){
        a[i]+=num;
        if(a[i]%b[i]){
            ll tmp=b[i]-(a[i]%b[i]);
            num+=tmp,ans+=tmp;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

树形dp。首先将所有点的父节点设为 \(a_i\) ，设 \(f_u\) 为节点 \(u\) 的子树中比赛的最小深度。设 \(v_1,v_2,\dots,v_k\) 为 \(u\) 的子节点，那么不难发现一个贪心思路：把 \(f_v\) 按深度排序，然后深度更深的这一轮就尽量轮空，深度第二的少轮空一轮，以此类推。这样 \(f_u=\max\{f_{v_i}+i\}\) ，\(f_{v_i}\) 是所有子树中第 \(i\) 大的答案。

时间复杂度：\(O(N\log N)\)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+5;
int n,f[N],tmp[N];
vector<int>G[N];
void dfs(int u){
    int tot=0;
    for(int v:G[u])dfs(v);
    for(int v:G[u])tmp[++tot]=f[v];
    sort(tmp+1,tmp+tot+1);
    rep(i,1,tot)f[u]=max(f[u],tmp[i]+tot-i+1);
}
int main(){
    n=read();
    rep(i,2,n){
        int u=read();G[u].push_back(i);
    }
    dfs(1);
    printf("%d\n",f[1]);
    return 0;
}

C¶

首先不妨设 \(A>B\) ，设 \(f_n\) 为第 \(n\) 个元素放进 \(X\) 集合中的方案数，可以通过加一个元素 \(S_{N+1}=\infty\) ，最后输出 \(f_{N+1}\) 即可。那么我们知道 \(f_i\) 可以从 \(f_j\) 转移，当且仅当 \([j+1,i-1]\) 中的所有数都可以放入 \(Y\) 。维护这些 \(f_j\) 的和，同时维护当前 \(j\) 的位置即可。

时间复杂度：\(O(N)\)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+5,P=1e9+7;
const ll inf=2e18+5;
ll n,A,B,s[N],j;
ll f[N],sum;
int main(){
    n=read(),A=read(),B=read();
    if(A<B)swap(A,B);
    rep(i,1,n)s[i]=read();
    s[0]=-inf,s[++n]=inf;
    f[0]=1;
    rep(i,1,n-2){
        if(s[i+2]-s[i]<B)return puts("0"),0;
    }
    rep(i,1,n){
        while(s[i]-s[j]>=A)sum=(sum+f[j++])%P;
        f[i]=sum;
        if(s[i]-s[i-1]<B)sum=0,j=i-1;
    }
    printf("%lld\n",f[n]);
    return 0;
}

D¶

理解为一个树最少的分治层数，上界显然是 \(O(\log N)\) 的。考虑一个关键性质：如果两点 \(u,v\) 的分治深度相同，那么 \(u,v\) 的树上路径上必然包含一个深度更小的。我们可以贪心，把每个点从深到浅编号，那么树上路径上则会有一个更大的编号，我们要最小化最大的编号。

这可以贪心，我们记录 \(u\) 的子树中是否有编号为 \(i\) 的节点 \(v\) ，且其到 \(u\) 的路径中不含 \(>i\) 编号的点，只有这样时我们才不能令 \(u\) 的编号为 \(i\) 。取符合条件最小的编号即可。

时间复杂度：\(O(N\log N)\) 或 \(O(N)\) （若使用位运算函数）

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+5;
int n,ans,f[N],c[21];
vector <int> G[N];
void dfs(int u,int fa){
    for(int v:G[u])if(v!=fa)dfs(v,u);
    rep(i,0,20)c[i]=0;
    for(int v:G[u]){
        rep(i,0,20){
            if((f[v]>>i)&1)++c[i];
        }
    }
    int k=0;
    per(i,20,0){
        if(c[i]>=2)break;
        if(!c[i])k=i;
    }
    ans=max(ans,k);
    f[u]|=(1<<k);
    rep(i,k+1,20){
        if(c[i])f[u]|=(1<<i);
    }
}
int main(){
    n=read();
    rep(i,1,n-1){
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}

E¶

好数位dp。

对这些操作建 \(K\) 叉树，父节点的权值为子节点的权值取平均数，即权值和除以 \(K\) ，根节点的权值则是剩下的数。如果我们设 \(M\) 个 \(1\) 的深度分别为 \(x_1,x_2,\dots,x_M\) ，不难得出结果为 \(\sum K^{-x_i}\) 。同时注意到如果叶子节点全部为 \(1\) ，那么根节点也为 \(1\) 。在这里我们把 \(N\) 个 \(0\) 改为了 \(1\) ，若它们的深度为 \(y_1,y_2,\dots,y_N\) ，则有 \(\sum K^{-x_i}=1-\sum K^{-y_i}\) 。

将等式两边用 \(K\) 进制小数表示为 \(z=0.c_1c_2c_3\dots\)，那么我们有：

\(0<c_1<K\) ，对于 \(i>1\) ，\(0\le c_i < K\)
考虑转换后的进位， \(\sum c_i\equiv N\pmod{K-1}\)
假设为 \(L\) 位小数，考虑 \(1-z\) ，有 \(L(K-1)-\sum c_i +1\equiv M \pmod{K-1}\)

利用这些条件，设 \(f_{i,j,0/1}\) 为 \(i\) 位小数，数位和为 \(j\) ，首位是否为 \(0\) 的答案，简单转移即可。

时间复杂度：\(O((N+M)^2)\)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2005,P=1e9+7;
int n,m,K,ans,f[N<<1][N][2],sum[N];
inline int qm(int x){return x>=P?x-P:x;}
int main(){
    n=read(),m=read(),K=read();
    f[0][0][0]=1;
    rep(i,1,2*max(n,m)){
        sum[0]=qm(f[i-1][0][0]+f[i-1][0][1]);
        rep(j,1,n){
            sum[j]=qm(sum[j-1]+qm(f[i-1][j][0]+f[i-1][j][1]));
        }
        rep(j,0,n){
            f[i][j][0]=qm(f[i-1][j][0]+f[i-1][j][1]);
            if(j){
                f[i][j][1]=qm(sum[j-1]);
                if(j-K>=0)f[i][j][1]=qm(f[i][j][1]-sum[j-K]+P);
            }
        }
        rep(j,0,n){
            if(j%(K-1)==n%(K-1)&&(i*(K-1)-j+1)%(K-1)==m%(K-1)&&i*(K-1)-j+1<=m){
                ans=qm(ans+f[i][j][1]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

AGC009 做题记录¶

A¶

B¶

C¶

D¶

E¶

Comments