AGC038

Ainu · 2020-09-21 19:05:33 · 个人记录

AGC038 A~F

A - 01 Matrix

actime: 2020/9/21 8:29

题意：

让你构造一个n\times m的01矩阵，使得每行每列01数量的较小值分别为a,b

题解：

把答案矩阵切成四个子矩形，其中左上角为a\times b，令左上角和右下角的矩形全1，另外两个全0即可

代码：

int n,m,a,b;

signed main(){
    read(n,m,a,b);
    for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++) write((i<=b&&j<=a)||(i>b&&j>a));
}

B - Sorting a Segment

actime: 2020/9/21 9:05

题意：

给出一个n的排列和系数k，可以将一段长度k部分从小到大排序得到n-k+1个新的排列，问新的排列有几个本质不同

题解：

发现相邻两个新排列相同的充要条件是重合部分的所有数\in(a_l,a_r)，于是可以用单调队列或ST表维护最大最小值解决

另外还有一种特殊情况，即排序的那一段本来就是有序的，这种情况需要特别记录，统一算成一种

代码：

const int N=2e5+5;
int n,k,e[N][30],f[N][30],a[N],cnt[N];

void init(){
    for(int i=1;i<=n;i++) e[i][0]=f[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++){
        e[i][j]=min(e[i][j-1],e[i+(1<<j-1)][j-1]);
        f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    }
}

int quee(int l,int r){
    int k=log2(r-l+1);
    return min(e[l][k],e[r-(1<<k)+1][k]);
}

int quef(int l,int r){
    int k=log2(r-l+1);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

signed main(){
    read(n,k);
    for(int i=1;i<=n;i++) a[i]=read(a[i])+1;
    init();
    for(int i=1;i<=n;i++) cnt[i]=cnt[i-1]+(a[i]>a[i-1]);
    int ans=n-k+1,exist=0;
    for(int i=k;i<=n;i++){
        if(cnt[i]-cnt[i-k+1]==k-1){
            exist=1;
            ans--;
            continue;
        }
        if(i>k&&a[i-k]<quee(i-k+1,i-1)&&quef(i-k+1,i-1)<a[i]) ans--;
    }
    write(ans+exist);
}

C - LCMs

actime: 2020/9/21 9:50

题意：

给出长度n的序列a，求\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\operatorname{lcm}(a_i,a_j)

题解：

首先转化式子\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\operatorname{lcm}(a_i,a_j)=\frac{\sum\limits_{i=1}^n\sum\limits_{j=1}^n\frac{a_i\times a_j}{\gcd(a_i,a_j)}-\sum a}{2}

于是可以枚举\gcd，记下每种数的出现次数cnt_i，容斥+递推出sum_i表示\gcd为i的数对的和，复杂度是调和级数值域的

代码：

const int M=1e6+5,mod=998244353;
int num[M],sum[M],n,inv[M],ma,ans;

signed main(){
    read(n);
    for(int i=1,x;i<=n;i++) ma=max(ma,read(x)),num[x]=(num[x]+x)%mod;
    inv[1]=1;for(int i=2;i<=ma;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; 
    for(int i=ma;i;i--){
        int cur=0;
        for(int j=i;j<=ma;j+=i) cur=(cur+num[j])%mod;
        sum[i]=1ll*cur*cur%mod;
        for(int j=i+i;j<=ma;j+=i) sum[i]=(sum[i]-sum[j]+mod)%mod;
        ans=((1ll*ans+1ll*sum[i]*inv[i]%mod-num[i]+mod)%mod);
    }
    write(1ll*ans*inv[2]%mod);
}

D - Unique Path

actime: 2020/9/21 11:08

题意：

给出Q条形如x,y之间是否有多条简单路径的限制

(只有一条为限制0，有多条为限制1）

问你能否构造出一张n点m边的无向图，满足所有性质

题解：

首先发现限制0具有传递性，即若ab,ac之间分别只有一条路径，那么ac之间也一定只有一条

于是就可以用并查集通过限制0搞出一个个0连通块，和一团没有0限制的点

考虑构造，最优的方案是把没限制的点作为根，0连通块作为叶子，连出一个菊花

根部分一定要是一个点双联通分量，叶子部分一定要是一棵树

由于根部分边数能变，叶子部分不能边

于是边数最少时，点双是一个环；边数最多时，点双是一个完全连通图

分别算出边数，若给出的m在这个范围内那就是合法的，否则不合法

注意m\le n-1要特判一棵树的情况

代码：

#define int long long

const int N=1e5+5;
int a[N],b[N],c[N],n,m,q,sz,f[N],c0;

void OK(){
    puts("Yes");
    exit(0);
}

void GG(){
    puts("No");
    exit(0);
}

int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}

bool merge(int x,int y){
    x=getf(x);y=getf(y);
    if(x==y) return 0;
    f[x]=y;sz--;
    return 1;
}

signed main(){
    read(n,m,q);sz=n;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=q;i++){
        read(a[i],b[i],c[i]);
        if(!c[i]) c0++,merge(a[i],b[i]);
    }
    if(m<=n-1){
        if(m<n-1) GG();
        if(q==c0) OK();
        GG();
    }
    int l=n,r=n-sz+sz*(sz-1)/2;
    for(int i=1;i<=q;i++) if(c[i]&&getf(a[i])==getf(b[i])) GG();
    if(m>=l&&m<=r) OK();
    else GG();
}

E - Gachapon

actime :2020/9/22 8:10

题意：

--by myh

题解：

Min-Max容斥：
\max(S)=\sum_{T\in S}(-1)^{|T|-1}\min(T)
在期望下依旧成立

--by myh

代码：

const int mod=998244353,N=405;
int n,fac[N],inv[N],pw[N][N],sa,sb,ans,a[N],b[N],f[N][N];

int fpow(int x,int y){
    int res=1;
    for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
    return res;
}

signed main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i],b[i]),sa+=a[i],sb+=b[i];
    fac[0]=1;for(int i=1;i<=sb;i++) fac[i]=1ll*fac[i-1]*i%mod;
    inv[sb]=fpow(fac[sb],mod-2);for(int i=sb-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(int i=1;i<=n;i++){
        pw[i][0]=1;
        for(int j=1;j<=b[i];j++) pw[i][j]=1ll*pw[i][j-1]*a[i]%mod;
    }
    f[0][0]=mod-1;
    for(int i=1;i<=n;i++)
        for(int j=sa;j>=a[i];j--) for(int k=sb;~k;k--)
            for(int l=0;l<=k&&l<b[i];l++)
                f[j][k]=(f[j][k]+1ll*(mod-f[j-a[i]][k-l])*pw[i][l]%mod*inv[l]%mod+mod)%mod;
    for(int i=1;i<=sa;i++) for(int j=0;j<=sb;j++) ans=(ans+1ll*f[i][j]*fac[j]%mod*fpow(i,1ll*(j+1)*(mod-2)%(mod-1))%mod)%mod;
    write(1ll*ans*sa%mod);
}

F - Two Permutations

actime: 2020/9/21 14:55

题意：

给定两个长度为 n 的排列 a_i,b_i，要求构造两个排列 p_i,q_i 满足 p_i=i/a_i 且 q_i=i/b_i，求最大的满足 p_i\neq q_i 的位置数量

题解：

首先考虑将问题转化为求最少的满足 p_i=q_i 的位置数量

现在对于 i 有若干种选择情况：

对于 i=a_i=b_i。必然有 1 的贡献

对于 i\neq a_i=b_i。则 p_i/q_i 都选 i 或者都选 a_i/b_i 会有 1 的贡献
对于 i=a_i\neq b_i。则 q_i 选 i 会有 1 的贡献
1. 对于 i=b_i\neq a_i。则 p_i 选 i 会有 1 的贡献
2. 对于 i\neq a_i\neq b_i。则 p_i/q_i 都选 i 会有 1 的贡献

容易发现这个模型可以最小割。具体来说，我们令 p_i 与 S 连边表示选择 i，否则表示选择 a_i， q_i 则相反。连边按照上述情况讨论即可

但是这样子复杂度并不优秀。我们考虑每个轮换必然选择相同，于是将每个轮换缩成一个点即可。这样子图就是一张二分图，且流量均为 1，可以分析出复杂度为 O(m\sqrt{n})

时间复杂度 O(n\sqrt{n})

代码：

const int N=2e5+5,M=5e6+5;
int en=1,h[N],n,a[N],b[N],id1[N],id2[N],cnt,cnt1,cnt2,d[N],cur[N];

struct edge{
    int n,v,w;
}e[M<<1];

void add(int x,int y,int z){
    e[++en]={h[x],y,z};
    h[x]=en;
}

void exadd(int x,int y,int f){
    add(x,y,f);
    add(y,x,0);
}

bool bfs(int s,int aim){
    memset(d,0,sizeof d);
    memcpy(cur,h,sizeof cur);
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(!d[y]&&e[i].w){
                d[y]=d[x]+1;
                if(y==aim) return 1;
                q.push(y);
            }
        }
    } 
    return 0;
}

int dfs(int x,int flow,int aim){
    if(x==aim) return flow;
    int rest=flow;
    for(int &i=cur[x];i&&rest;i=e[i].n){
        int y=e[i].v;
        if(d[y]==d[x]+1&&e[i].w){
            int tp=dfs(y,min(rest,e[i].w),aim);
            if(!tp) d[y]=0;
            rest-=tp;
            e[i].w-=tp;
            e[i^1].w+=tp;
        }
    }
    return flow-rest;
}

int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)) res+=dfs(s,INT_MAX,t);
    return res;
}

signed main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),a[i]++;
    for(int i=1;i<=n;i++) read(b[i]),b[i]++;
    for(int i=1;i<=n;i++) if(!id1[i]){
        cnt1++;
        int x=i;
        do{
            id1[x]=cnt1;
            x=a[x];
        }while(x!=i);
    }
    for(int i=1;i<=n;i++) if(!id2[i]){
        cnt2++;
        int x=i;
        do{
            id2[x]=cnt2;
            x=b[x];
        }while(x!=i);
    }
    for(int i=1;i<=n;i++){
        int x=id1[i],y=id2[i];
        if(a[i]!=i&&b[i]!=i){
            exadd(x,cnt1+y,1);
            if(a[i]==b[i]) exadd(cnt1+y,x,1);
        }
        else if(a[i]!=i) exadd(x,cnt1+cnt2+1,1);
        else if(b[i]!=i) exadd(0,cnt1+y,1);
        else cnt++;
    }
    write(n-cnt-dinic(0,cnt1+cnt2+1));
}