AGC009

吗了为什么我 T2 没开 long long。

吗了为什么我 T4 没想出来。

果然还是太菜。正在思考我现在在做什么，和意义在哪里。最近几天高强度 AGC 好像打的心态有点爆炸。明天如果不考试的话还有个洛谷月赛和 UER。而且现在看见右边一个黑色的难度标签就开始脑袋痛。

五题场，昨天和 artalter VP 了一下，切了前三题， T3 是 artalter 跟我说了一下大概的然后切的（然后不知道为什么她貌似只切了 T1 ）。大概平均水平。毕竟才刚刚进入 2017 年。

[AGC009A] Multiple Array

普及题。

#define int long long
int n,a[100010],b[100010];
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
    int cnt=0;
    for(int i=n;i>=1;i--){
        int ret=ceil(1.0*(a[i]+cnt)/b[i])*b[i]-(a[i]+cnt);
        cnt+=ret;
    }
    printf("%lld\n",cnt);
    return 0;
}

[AGC009B] Tournament

一开始将近 20 分钟胡了一个从 \(1\) 开始往下搜，每个点要连的都从大到小排一遍序往下扫的做法，交上去发现挂了一半。然后发现这样的话有两条链长度相同可能会挂，从下往上扫就没问题了。于是就写了个树形 dp。其实也不叫 dp。

int n,dp[100010];
struct node{
    int v,next;
}edge[100010];
int t,head[100010];
void add(int u,int v){
    edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
bool cmp(int a,int b){
    return a>b;
}
void dfs(int x){
    vector<int>v;
    int tmp=0;
    for(int i=head[x];i;i=edge[i].next){
        dfs(edge[i].v);
        v.push_back(dp[edge[i].v]);
    }
    sort(v.begin(),v.end(),cmp);
    for(int a:v)tmp++,dp[x]=max(dp[x],a+tmp);
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        int x;scanf("%d",&x);add(x,i);
    }
    dfs(1);
    printf("%d\n",dp[1]);
    return 0;
}

[AGC009C] Division into Two

一开始想了个 \(dp_{i,j,k}\) 为到第 \(i\) 个，\(X\) 集合上一个是 \(j\) ，\(Y\) 集合上一个是 \(K\) 的方案数，可以压掉一位，\(O(n^2)\) 还很难写。后来想了想可以只往一个集合里加数，然后还没细想 artalter 过来给我口胡了一个正解出来（

假设 \(A>B\)。设 \(dp_i\) 为 \(X\) 集合选 \(i\) 的方案数。转移枚举之前放了哪个数，要求这两个数之间两两的差都 \(\ge B\) 。然后发现转移显然是一段区间，前缀和随便搞搞就行了。还挺好写的。

#define int long long
const int mod=1000000007;
int n,ans,dp[100010],sum[100010];
long long a,b,s[100010];
signed main(){
    scanf("%lld%lld%lld",&n,&a,&b);
    for(int i=1;i<=n;i++)scanf("%lld",&s[i]);
    if(a<b)swap(a,b);
    for(int i=2;i<n;i++){
        if(s[i+1]-s[i-1]<b){
            puts("0");return 0;
        }
    }
    dp[0]=sum[0]=1;int l=0,r=0;
    for(int i=1;i<=n;i++){
        while(r<i&&s[i]-s[r+1]>=a)r++;
        if(l<=r)dp[i]=(sum[r]-(l?sum[l-1]:0)+mod)%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
        if(i&&s[i]-s[i-1]<b)l=i-1;
    }
    for(int i=n;i>=0;i--){
        ans=(ans+dp[i])%mod;
        if(i<n&&s[i+1]-s[i]<b)break;
    }
    printf("%lld\n",ans);
    return 0;
}

[AGC009D] Uninity

人话翻译一下题意是找一棵树深度最小的点分树。

两篇洛谷题解都有点语焉不详。不多评价。

设每个节点的编号为在最终答案的 Uninity k 的树中它的 \(k\) 是多少。那么显然有一个引理就是对于两个编号相等的点，它们的路径上必然有一个编号大于它们的点。

考虑从下到上贪心地选取。记录一个集合 \(s_x\) 表示 \(x\) 的子树内哪些数不能再被选了。由于 \(k\) 是 \(O(\log n)\) 的，可以压位。那么首先我们让 \(s_x\) 为所有儿子的 \(s\) 的或，那么能选取的点自然就是 \(s_x\) 中是 \(0\) 的位。然而还有一个问题，我们要保证子树中编号相等的点的路径上都有一个编号更大的点。这时我们取所有子树 \(s\) 的两两并集的交集，则 \(x\) 的编号必须比这个集合中最大的要大。然后就可以暴力扫一遍所有位确定 \(x\) 的编号。

确定了 \(x\) 的编号后还要决定 \(s_x\) 。首先 \(x\) 的编号已经被选了，那在保证有更大的之前就是不能选的。比编号大的显然不用动。比编号小的由于出现了比它们大的，所以就又都可以选了。

看不懂的看代码吧。

int n,ans,a[100010],dp[100010];
struct node{
    int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
    edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
void dfs(int x,int f){
    int s=0;
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=f){
            dfs(edge[i].v,x);
            s|=dp[x]&dp[edge[i].v];
            dp[x]|=dp[edge[i].v];
        }
    }
    for(int i=31;i>=0;i--){
        if((s>>i)&1)break;
        if(!((dp[x]>>i)&1))a[x]=i;
    }
    dp[x]=(dp[x]>>a[x]|1)<<a[x];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)ans=max(ans,a[i]);
    printf("%d\n",ans);
    return 0;
}

[AGC009E] Eternal Average

貌似某场 UR 也有这个套路。以后找个时间板刷 UR 去。

每次取平均数的过程可以看做一棵 \(k\) 叉树把 \(k\) 个儿子节点的平均数作为该节点的值。容易发现所有的数都可以表示为若干个 \(\dfrac 1{k^d}\) ，\(d\) 是深度。

如果枚举每层有多少 \(1\) 会算重。实际上既然我们只关心最后的值，不妨强制每层的 \(1\) 的数量不超过 \(k-1\) 。暴力背包即可。

const int mod=1000000007;
int n,m,K,ans,dp[4010][2010];
int main(){
    scanf("%d%d%d",&n,&m,&K);
    int cnt=(n+m-1)/(K-1);
    dp[0][0]=1;
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<K;j++){
            for(int k=j;k<=min(m,i*K);k++){
                dp[i][k]=(dp[i][k]+dp[i-1][k-j])%mod;
            }
        }
    }
    for(int i=m;i>=1;i-=K-1){
        ans=(ans+dp[cnt][i])%mod;
        cnt--;
    }
    printf("%d\n",ans);
    return 0;
}

完了。