AGC008 做题记录

A

可以通过分类讨论实现，也可以枚举翻转次数暴力解决，这里用了后者。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#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 S(int x,int y){
    if(x<=y)return y-x;
    else return x-y+2;
}
int main(){
    int x=read(),y=read();
    int ans=min(min(S(x,y),S(-x,y)+1),min(S(-x,-y)+2,S(x,-y)+1));
    printf("%d\n",ans);
    return 0;
}

B

熟知结论为任何存在连续 \(k\) 格颜色相同的方案都可以被构造，于是暴力枚举连续段+前缀和即可。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#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;
ll n,k,a[N],sum[N],sum2[N],ans;
int main(){
    n=read(),k=read();
    rep(i,1,n){
        a[i]=read();
        sum[i]=sum[i-1]+a[i];
        sum2[i]=sum2[i-1]+(a[i]>0)*a[i];
    }
    rep(i,k,n){
        ll tmp=sum[i]-sum[i-k];
        tmp=(tmp>0)*tmp+sum2[n]-sum2[i]+sum2[i-k];
        ans=max(ans,tmp);
    }
    printf("%lld\n",ans);
    return 0;
}

C

手玩几种不同的俄罗斯方块发现 \(T,S,Z\) 形方块多出的一格无法处理，所以不能放置。而 \(O\) 形可以自己贡献答案，其他方块可以和相同块两两组合贡献，也可以 \(I,J,L\) 各一块贡献，简单判断即可。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#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;
}
ll a[8],ans;
ll calc(ll a1,ll a4,ll a5){
    return a1+a4+a5-a1%2-a4%2-a5%2;
}
int main(){
    rep(i,1,7)a[i]=read();
    ans=calc(a[1],a[4],a[5]);
    if(a[1]&&a[4]&&a[5])ans=max(ans,calc(a[1]-1,a[4]-1,a[5]-1)+3);
    printf("%lld\n",ans+a[2]);
    return 0;
}

D

贪心构造。

首先想到 \(X_i\) 左边会有 \(i-1\) 个 \(i\) ，右边有 \(n-i\) 个 \(i\) ，只要能满足这样的限制就构造成功了。然后我们对 \(X_i\) 排序，越靠左的越需要用 \(i\) 填空，同理反着也这么做一遍。这样的贪心是最优的，因为若 \(X_j>X_i\) ，那么 \(X_i\) 前面的位置必须有 \(i-1\) 个被 \(i\) 占领才能给 \(j\) 填空。

#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 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=505;
struct node{int v,p;}x[505];
bool cmp(node a,node b){return a.p<b.p;}
int n,ans[N*N];
int main(){
    n=read();
    rep(i,1,n){
        int p=read();
        x[i]={i,p},ans[p]=i;
    }
    sort(x+1,x+n+1,cmp);
    int k=1;
    rep(i,1,n){
        rep(j,1,x[i].v-1){
            while(ans[k])++k;
            if(k>=x[i].p)return puts("No"),0;
            ans[k++]=x[i].v;
        }
    }
    k=n*n;
    per(i,n,1){
        rep(j,1,n-x[i].v){
            while(ans[k])--k;
            if(k<=x[i].p)return puts("No"),0;
            ans[k--]=x[i].v;
        }
    }
    puts("Yes");
    rep(i,1,n*n)printf("%d ",ans[i]);
    return 0;
}

E

置换会形成若干个有向环。观察这些环如何和 \(a\) 图建立联系：

• 情况1：\(p_i=a_i\)

会形成和 \(a\) 图完全一样的环。

• 情况2：\(p_{p_i}=a_i\) 且原环长为奇。

会形成和原来的环同构的一个环。

情况3：环长为偶。

会把原来的环分成两个大小相同的小环。

• 情况4：一部分 \(p_i=a_i\) ，一部分 \(p_{p_i}=a_i\) 。

会形成一个上面挂着几条链的环，即为一种特殊的基环树。

首先考虑 \(a\) 图中的所有环，两个大小一样的环可能在 \(p\) 图的同一个环中（即情况3）。如果有 \(n_k\) 个大小为 \(k\) 的环，不难发现它们带来的总方案数可以 \(O(n_k)\) 内用 \(dp\) 求解。值得注意的是在情况3中我们有 \(k\) 种合并两个环的方案。

下面考虑如何处理 \(a\) 图中特殊的基环树，我们需要把多出的链塞进这个环里。设 \(l_1\) 为当前链长，\(l_2\) 为当前链在环上的端点距离上一条链的端点的距离，经过一些简单构造，我们有：

• \(l_1<l_2\) 时有 \(2\) 种方案。
• \(l_1=l_2\) 时有 \(1\) 种方案。
• \(l_1>l_2\) 时无解。

由乘法原理，所有情况的方案数相乘即为答案。

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

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#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;
int Mod(int x){return x>=P?x-P:x;}
int n,a[N],deg[N],cir[N],vis[N],flen[N],cnt[N];
ll ans=1,dp[N];
int k(int l1,int l2){
    if(l1<l2)return 2;
    if(l1==l2)return 1;
    return 0;
}
void work(int x){
    int now=0,len=0,last=0,fir=0;
    while(cir[x]){
        ++now,cir[x]=0;
        if(flen[x]){
            if(!fir)fir=last=now,len=flen[x];
            else{
                ans=ans*k(flen[x],now-last)%P,last=now;
            }
        }
        x=a[x];
    }
    if(!fir)++cnt[now];
    else{
        ans=ans*k(len,now-last+fir)%P;
    }
}
int main(){
    n=read();
    rep(i,1,n)a[i]=read(),++deg[a[i]];
    rep(i,1,n){
        if(vis[i])continue;
        int x=i;
        while(!vis[x])vis[x]=i,x=a[x];
        if(vis[x]!=i)continue;//不在环上
        while(!cir[x])cir[x]=1,x=a[x];//标记环
    }
    rep(i,1,n){//特判无解
        if((cir[i]&&deg[i]>2)||(!cir[i]&&deg[i]>1))
            return puts("0"),0;
    }
    rep(i,1,n){
        if(deg[i])continue;
        int x=i,len=0;
        while(!cir[x])++len,x=a[x];
        flen[x]=len;//记录链长
    }
    rep(i,1,n)if(cir[i])work(i);//基环树
    rep(i,1,n){//环
        if(!cnt[i])continue;
        dp[0]=1;
        rep(j,1,cnt[i]){
            if(i>1&&(i&1))dp[j]=Mod(dp[j-1]*2);//奇环
            else dp[j]=dp[j-1];
            if(j>1)dp[j]=Mod(dp[j]+dp[j-2]*(j-1)%P*i%P);//合并两小环成大环
        }
        ans=ans*dp[cnt[i]]%P;
    }
    printf("%lld\n",ans);
    return 0;
}

F

神仙树形dp。

首先考虑如何转换题意方便我们计数，不妨先设所有点均为关键点。发现对于相同的染色方案，仅存在一个点 \(u\) 作为圆心时半径最小，记为 \(d\) 。我们设 \(f(u,d)\) 为距离 \(u\) 不超过 \(d\) 的点集，计数时只需要记 \(d\) 最小的情况，于是

• \(f(u,d)\) 不覆盖所有点。（最后加上整棵树被染色的情况即可）
• \(\forall (u,v)\in E,f(u,d)\neq f(v,d-1)\)

当 \(u\) 为根节点时，第一个条件即为 \(d<mx_u\) ，\(mx_u\) 为离 \(u\) 最远的点的深度。而因为 \(f(v,d-1)\) 能覆盖其子树内 \(f(u,d)\) 能覆盖的所有点，第二个条件等价于 \(f(v,d-1)\) 无法覆盖 \(u\) 其他子树上 \(f(u,d)\) 能覆盖到的节点，这提示了我们 \(d\) 的另一个上界 \(d-1\le mx2[u]\) ，即离 \(u\) 节点次长的距离。对于统计所有节点的答案，显然可以通过换根 \(dp\) 实现。

下面考虑不全是关键点的情况。若 \(u\) 不是关键点，\(v\) 为 \(u\) 子节点且 \(v\) 子树中有关键点，如果 \(f(u,d)\) 为某个关键点为圆心覆盖的集合，设 $$d_u=\min\{mx_v\}+1$$ 即所有 \(v\) 子树的深度加上 \((u,v)\) 边长。因为 \(d_u\) 需要覆盖某个 \(v\) 子树中关键点 \(w\) 能覆盖的所有点，不难发现 \(d_u\) 为半径最小值。通过类似的换根 \(dp\) 技巧去维护 \(mx,mx2,d\) ，把每个点为圆心的可能半径统计进答案即可。

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

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#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=2e5+5,inf=1e9;
int n,d[N],sz[N],mx[N],mx2[N];
char col[N];
ll ans;
vector <int> G[N];
//若v为u子节点且v子树中有关键点，d[u]为min(mx[v]+1)
//不难发现d[u]为半径最小值，因为d[u]需要覆盖至少一个v子树中关键点无法覆盖的点
void dfs1(int u,int fa){
    if(col[u]=='1')d[u]=0,sz[u]=1;
    else d[u]=inf;
    for(int v:G[u])if(v!=fa){
        dfs1(v,u);sz[u]+=sz[v];
        if(mx[v]+1>mx[u])mx2[u]=mx[u],mx[u]=mx[v]+1;//最长距离
        else if(mx[v]+1>mx2[u])mx2[u]=mx[v]+1;//次长距离
        if(sz[v])d[u]=min(d[u],mx[v]+1);
    }
}
void dfs2(int u,int fa){//换根dp
    int R=min(mx2[u]+1,mx[u]-1);//最大半径
    if(d[u]<=R)ans+=(ll)(R-d[u]+1);
    for(int v:G[u])if(v!=fa){
        int len;//v子树外的最长距离
        if(mx[u]==mx[v]+1){
            len=mx2[u]+1;
        }else len=mx[u]+1;
        if(len>mx[v])mx2[v]=mx[v],mx[v]=len;
        else if(len>mx2[v])mx2[v]=len;
        if(sz[1]>sz[v]&&d[v]>len)d[v]=len;
        dfs2(v,u);
    }
}
int main(){
    n=read();
    rep(i,1,n-1){
        int u=read(),v=read();
        G[u].push_back(v);G[v].push_back(u);
    }
    scanf("%s",col+1);
    dfs1(1,0);dfs2(1,0);
    printf("%lld\n",ans+1);
    return 0;
}