[VP记录]AGC001

[AGC001A] BBQ Easy

普及题。排序后把奇数位置上的加上就好了。

int n,a[100010],ans;
int main(){
    scanf("%d",&n);n<<=1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i+=2)ans+=a[i];
    printf("%d\n",ans);
}

[AGC001B] Mysterious Light

不是很普及的找规律题。

发现轨迹是若干个等边三角形，所以考虑把它们拼成一个大的等边三角形然后找边长。每次反射相当于把边长变成 \(\gcd(n-x,x)\) ，然后根据这个 \(\gcd\) 手模几组数据打个表可以发现边长是 \(n-\gcd(n,x)\)。

long long n,x;
long long gcd(long long a,long long b){
    return b?gcd(b,a%b):a;
}
int main(){
    scanf("%lld%lld",&n,&x);
    printf("%lld\n",3*(n-gcd(n,x)));
    return 0;
}

[AGC001C] Shorten Diameter

一看这个 \(2000\) 的数据范围就可以枚举每个点跑 dfs。

奇偶讨论一下 \(k\)，如果是奇数那么就枚举中间的一条边，两边往下 dfs \(\dfrac k2\) 的深度。如果是偶数那么就枚举中间的一个点，然后搜 \(\dfrac k2\) 的深度。搜到的点数就是能保留的点数，取个最大值减一下就行了。

struct node{
    int v,next;
}edge[4010];
int n,k,t,ans,cnt,head[2010],fa[2010];
bool v[2010][2010];
void add(int u,int v){
    edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
void dfs1(int x,int f){
    fa[x]=f;
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=f)dfs1(edge[i].v,x);
    }
}
void dfs(int x,int f,int dep){
    if(!(~dep))return;
    cnt++;
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=f)dfs(edge[i].v,x,dep-1);
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs1(1,0);
    if(k&1){
        for(int i=2;i<=n;i++){
            cnt=0;
            dfs(fa[i],i,k>>1);
            dfs(i,fa[i],k>>1);
            ans=max(ans,cnt);
        }
    }
    else{
        for(int i=1;i<=n;i++){
            cnt=0;
            dfs(i,0,k>>1);
            ans=max(ans,cnt);
        }
    }
    printf("%d\n",n-ans);
    return 0;
}

[AGC001D] Arrays and Palindrome

模拟赛题。赛时由于并没有捉摸透题面的语文含义输出了个 \(-1\)。洛谷的翻译就好很多。

抽象成图论模型就是在 \(n\) 个点之间回文的对应位置连边，最后使得整张图连通。

首先特判无解，是 \(A\) 中奇数大于等于三个的情况。由于每个奇数会使得中间一个点少连一条边，度数少 \(1\)，而整张图的度数最少是 \(2n-2\)（一棵树）。然后把两个奇数一个开头一个结尾就是 \(a\) 数组，开头减一结尾加一，去掉前导 \(0\)就是 \(b\) 数组。

int n,m,a[100010];
int main(){
    scanf("%d%d",&n,&m);
    int cnt=0;
    for(int i=1;i<=m;i++)scanf("%d",&a[i]),cnt+=(a[i]&1);
    if(cnt>2){
        puts("Impossible");return 0;
    }
    for(int i=m;i>=1;i--)if(a[i]&1){
        swap(a[i],a[m]);break;
    }
    for(int i=1;i<=m;i++)if(a[i]&1){
        swap(a[i],a[1]);break;
    }
    for(int i=1;i<=m;i++)printf("%d ",a[i]);printf("\n");
    if(m==1&&a[1]!=1)m++;
    a[1]--;a[m]++;
    cnt=1;
    for(int i=1;i<=m;i++)if(!a[i])m--,cnt++;
    printf("%d\n",m);
    for(int i=cnt;i<=m+cnt-1;i++)printf("%d ",a[i]);
    return 0;
}

[AGC001E] BBQ Hard

套路题。但是忘了套路。看到题解第一眼发现我是sb那没事了。

忘了这个套路的可以看学长馈赠 1 的 T3。

实际上这个组合数可以长得像格路计数一样，一个点的坐标就是 \((a_i,b_i)\)。然后就可以 \(dp\) 。 \(dp_{i,j}\) 为到 \((i,j)\) 的方案数，转移 \(dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}\)。

然后看到值域很小，考虑在值域上下点功夫。又看到这个两个点坐标相加的形式，容易想到把一个点的坐标变成 \((-a_i,-b_i)\)，然后每个点对应坐标的 \(dp\) 值 \(+1\)，然后跑一遍就可以得到答案。记得去掉自己对自己的贡献然后除以 \(2\) 。

const int mod=1000000007;
int n,ans,dp[5010][5010],a[200010],b[200010],jc[10010],inv[10010];
const int mx=2005;
int C(int n,int m){
    return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
int main(){
    scanf("%d",&n);jc[0]=inv[0]=1;
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),dp[-a[i]+mx][-b[i]+mx]++;
    for(int i=1;i<=4*mx;i++)jc[i]=1ll*jc[i-1]*i%mod;
    inv[mx<<2]=qpow(jc[mx<<2],mod-2);
    for(int i=(mx<<2)-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(int i=1;i<=2*mx;i++){
        for(int j=1;j<=2*mx;j++){
            (dp[i][j]+=dp[i-1][j]+dp[i][j-1])%=mod;
        }
    }
    for(int i=1;i<=n;i++){
        ans=(1ll*ans+dp[a[i]+mx][b[i]+mx]-C(2*a[i]+2*b[i],2*a[i])+mod)%mod;
    }
    ans=1ll*ans*((mod+1)>>1)%mod;
    printf("%d\n",ans);
    return 0;
}

[AGC001F] Wide Swap

很玄妙的题。第一步把我卡住了。

考虑怎么把这个变换整成看着舒服点的形式。可以把 \(P\) 的下标和值调换得到排列 \(Q\)，然后变换就变成了对于 \(|Q_i-Q_{i+1}|\ge k\) 可以调换。长的就很像冒泡排序。

然后实际上你把冒泡换成归并就可以过了。归并的时候记录前面 \([l,mid]\) 的后缀最小值 \(minn\)，如果对右面的 \(j\) 有 \(minn_i-Q_j\ge k\) 就可以把右边归并上去。

int n,k,a[500010],b[500010],minn[500010];
void merge(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    merge(l,mid);merge(mid+1,r);
    minn[mid]=a[mid];
    for(int i=mid-1;i>=l;i--)minn[i]=min(minn[i+1],a[i]);
    int i=l,j=mid+1,pos=l;
    while(i<=mid&&j<=r){
        if(minn[i]-a[j]>=k)b[pos]=a[j],j++;
        else b[pos]=a[i],i++;
        pos++;
    }
    while(i<=mid)b[pos]=a[i++],pos++;
    while(j<=r)b[pos]=a[j++],pos++;
    for(int i=l;i<=r;i++)a[i]=b[i];
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);a[x]=i;
    }
    merge(1,n);
    for(int i=1;i<=n;i++)b[a[i]]=i;
    for(int i=1;i<=n;i++)printf("%d\n",b[i]);
    return 0;
}

完。