首页 > 其他分享 >AGC016

AGC016

时间:2023-06-23 15:12:16浏览次数:37  
标签:AGC016 val int 100010 include dp mod

sta 老师的曲绘风格确实很科幻。艺术番茄。

上边挂着个数分学习笔记确实很怪。赶紧把这一章完结了。

我之前写的题解没了,还得重写一遍。

[AGC016A] Shrinking

你说的好像挺对的。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <iostream>
using namespace std;
int n;
char s[110];
bitset<26>b[110],tmp;
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++)b[i][s[i]-'a']=1;
    for(int k=0;;k++){
        tmp.set();
        for(int i=1;i<=n-k;i++)tmp&=b[i];
        if(tmp.any()){
            printf("%d\n",k);return 0;
        }
        for(int i=1;i<n-k;i++)b[i]|=b[i+1];
    }
    return 0;
}

[AGC016B] Colorful Hats

???

首先 \(a_i\) 极差不超过 \(1\)。然后考虑两种情况:全相等和不全相等。

全相等的情况:这个数量要么 \(n-1\),要么每种都不为 \(1\) 次,即乘 \(2\) 不超过 \(n\)。

不全相等的情况,设较小值为 \(a\),个数为 \(cnt\),那么它们是只出现一次的。于是 \(cnt<a+1\),因为不能超过不止一种颜色的看到的颜色。然后剩下的 \(n-cnt\) 个出现不止一次,于是 \(2(n-cnt)\le n\)。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <iostream>
using namespace std;
int n,a[100010];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    if(a[1]==a[n]){
        if(a[1]==n-1||2*a[1]<=n)puts("Yes");
        else puts("No");
    }
    else if(a[1]+1==a[n]){
        int cnt=0;
        for(int i=1;i<=n;i++)if(a[i]==a[1])cnt++;
        if(cnt<a[n]&&2*(a[n]-cnt)<=n-cnt)puts("Yes");
        else puts("No");
    }
    else puts("No");
    return 0;
}

[AGC016C] +/- Rectangle

首先观察样例得到一个显然构造:每个 \(h\times w\) 的矩阵尽量往右下放一个 \(-h\times w\),其他放 \(1\)。很遗憾它是错的,交上去会挂两个点。

但是大体思路是没问题的,我们只要把这个数稍微开大点,开成 \(-h\times w\) 的 \(k\) 倍再减个 \(1\),别的地方全放 \(k\) 就行了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <iostream>
using namespace std;
int n,m,h,w,a[510][510];
int main(){
    scanf("%d%d%d%d",&n,&m,&h,&w);
    if(n%h==0&&m%w==0){
        puts("No");return 0;
    }
    puts("Yes");
    int k=1145;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i%h==0&&j%w==0)a[i][j]=-(h*w-1)*k-1;
            else a[i][j]=k;
            printf("%d ",a[i][j]);
        }
        puts("");
    }
    return 0;
}

[AGC016D] XOR Replace

观察性质发现相当于加一个 \(n+1\) 位置为全局异或和,每次是一个位置和 \(n+1\) 位置交换。那么无解很好判。

容易发现不同位置形成置换环,那么每个置换环需要先和 \(n+1\) 换一步联通再花费环长代价换好。最后根据 \(n+1\) 位置是否在别的置换环里有 \(1\) 的贡献。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <iostream>
using namespace std;
int n,a[100010],b[100010],fa[100010],tmp1[100010],tmp2[100010],sz[100010],s[100010];
int find(int x){
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    x=find(x);y=find(y);
    if(x==y)sz[x]++;
    else fa[y]=x,sz[x]+=sz[y]+1,s[x]+=s[y];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[n+1]^=a[i];
    for(int i=1;i<=n;i++)scanf("%d",&b[i]),b[n+1]^=b[i];
    for(int i=1;i<=n+1;i++)tmp1[i]=a[i],tmp2[i]=b[i];
    sort(tmp1+1,tmp1+n+2);sort(tmp2+1,tmp2+n+2);
    for(int i=1;i<=n+1;i++){
        if(tmp1[i]!=tmp2[i]){
            puts("-1");return 0;
        }
    }
    int cnt=unique(tmp1+1,tmp1+n+2)-tmp1-1;
    for(int i=1;i<=cnt;i++)fa[i]=i,s[i]=1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(tmp1+1,tmp1+cnt+1,a[i])-tmp1;
        b[i]=lower_bound(tmp1+1,tmp1+cnt+1,b[i])-tmp1;
        if(a[i]!=b[i])merge(a[i],b[i]);
    }
    a[n+1]=lower_bound(tmp1+1,tmp1+cnt+1,a[n+1])-tmp1;
    int ans=-(s[find(a[n+1])]!=1);
    for(int i=1;i<=cnt;i++)if(find(i)==i&&s[i]!=1)ans+=sz[i]+1;
    printf("%d\n",ans);
    return 0;
}

[AGC016E] Poor Turkeys

这题想到倒推好像不难。

首先感性上就是枚举 \(i,j\) 统计。设个 \(dp_{i,j}\) 为要 \(i\) 活着 \(j\) 是否必须死,初始 \(dp_{i,i}=1\)。

那么转移倒着推回来,考虑每个关系,对于这个关系 \((x,y)\) 考虑所有 \(i\),如果 \(i\) 活着时 \(x,y\) 都必须死,那么 \(x,y\) 至少在这里死一个,也就是 \(i\) 一定保不住。反之,如果一个必须死那么另一个必须在这里死掉。

统计答案的时候枚举 \(i,j\) 看必须死的集合是否相交就好了。

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <bitset>
using namespace std;
int n,m,x[100010],y[100010];
bitset<410>v[410],ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=n;i++)v[i][i]=ans[i]=1;
    for(int i=m;i>=1;i--){
        for(int j=1;j<=n;j++){
            if(v[j][x[i]]&&v[j][y[i]])ans[j]=0;
            else v[j][x[i]]=v[j][y[i]]=v[j][x[i]]|v[j][y[i]];
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!ans[i])continue;
        for(int j=i+1;j<=n;j++){
            if(!ans[j])continue;
            if(!(v[i]&v[j]).count())cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

[AGC016F] Games on DAG

十分神秘的题。

\(1,2\) 是独立的,于是相当于两个有向图游戏的和,即 \(\text{SG}(1)\oplus\text{SG}(2)\)。于是只要两个的 \(\text{SG}\) 值不等就先手必胜。

考虑计数 \(\text{SG}\) 相等的情况。设一个 \(dp_S\) 为考虑了 \(S\) 内的方案,且 \(1,2\) 一定都在 \(S\) 内。转移考虑枚举子集 \(T\),使 \(S\) 内边连到 \(T\)。

那么考虑选边:假设我们已经确定了 \(\text{SG}\) 的序列 \(x\),那么设 \(x_i=k\),选边方案必须满足:

  1. 对于 \(v<k\),至少连一个。
  2. 对于 \(v=k\),不能连。
  3. 对于 \(v>k\),随意。

于是每次转移考虑枚举 \(S\) 中 \(\text{SG}\) 值不为 \(0\) 的子集 \(T\),那么 \(T\) 之间不能互相连边,\(S/T\) 中的点至少向 \(T\) 中的一个点连边。关于 \(S/T\) 中的点,如果没有 \(1,2\) 那么就可以随意互相连了,否则不能连。

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <bitset>
using namespace std;
const int mod=1000000007;
int n,m,dp[1<<15],g[20],pw[410];
int main(){
    scanf("%d%d",&n,&m);pw[0]=1;
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d%d",&u,&v);
        u--,v--;g[u]|=1<<v;
    }
    for(int i=1;i<=m;i++)pw[i]=(pw[i-1]<<1)%mod;
    for(int s=0;s<(1<<n);s++){
        if((s&3)!=3)continue;
        dp[s]=1;
        for(int t=s&(s-1);t;t=s&(t-1)){
            int val=1;
            if((t&3)==3){
                for(int i=0;i<n;i++){
                    if(s>>i&1){
                        if(t>>i&1)val=1ll*val*(pw[__builtin_popcount(g[i]&(s^t))]-1)%mod;
                        else val=1ll*val*pw[__builtin_popcount(g[i]&t)]%mod;
                    }
                }
                dp[s]=(dp[s]+1ll*val*dp[t])%mod;
            }
            else if((t&3)==0){
                for(int i=0;i<n;i++){
                    if(s>>i&1){
                        if(t>>i&1)val=1ll*val*(pw[__builtin_popcount(g[i]&(s^t))]-1)%mod*pw[__builtin_popcount(g[i]&t)]%mod;
                        else val=1ll*val*pw[__builtin_popcount(g[i]&t)]%mod;
                    }
                }
                dp[s]=(dp[s]+val)%mod;
            }
        }
    }
    int ans=(pw[m]-dp[(1<<n)-1]+mod)%mod;
    printf("%d\n",ans);
    return 0;
}

标签:AGC016,val,int,100010,include,dp,mod
From: https://www.cnblogs.com/gtm1514/p/17499170.html

相关文章

  • [dp 记录]agc016F Game on DAG
    博弈论好题,做完感觉加深了对SG函数的理解!题意:给定一张DAG,问该DAG的\(2^m\)张导出子图中有多少张满足\(SG[1]=SG[2]\)注:此为转换后题意\(n\leq15\)考虑推......
  • AGC016D XOR Replace(并查集)
    AGC016DXORReplace一个序列,一次操作可以将某个位置变成整个序列的异或和。问最少几步到达目标序列。\(n\le100000\)。CODE令最后一个数是初始异或和然后每次操作就......