AtCoder Grand Contest 008

100 阅读 0 评论 66 点赞

我是靠谱客的博主懵懂蜜蜂，这篇文章主要介绍AtCoder Grand Contest 008，现在分享给大家，希望可以做个参考。

AtCoder Grand Contest 008
题目链接： https://agc008.contest.atcoder.jp/
A.Simple Calculator（模拟）
B.Contiguous Repainting（贪心+枚举）
枚举一段k个相同颜色的位置用来中转，借由这k个位置，其他位置的数都可以选上，那么我们就把其他的数中的正数都选上。枚举所有这样的k个位置。取最优值
C.Tetromino Tiling（奇偶性）
O肯定能全取了，剩下的只有I、J、L三种有可能构成。任意两个同种的可以一起拿出来，或者三种一样一个可以一起拿出来。根据奇偶性，贪心地拿最多的。
D.K-th K （贪心+构造）
注意判断不合法的情况。
E.Next or Nextnext （组合数学+dp+图论+置换）
这题我哪会啊x

A

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int x,y,ans=0;
inline int abs(int x){return x<0?-x:x;}
int main(){
//  freopen("a.in","r",stdin);
    x=read();y=read();
    if(x==-y) ans=1;
    else if(abs(x)<abs(y)) ans=abs(y)-abs(x)+(x<0)+(y<0);
    else ans=abs(x)-abs(y)+(x>0)+(y>0);
    printf("%dn",ans);
    return 0;
}

B

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,k,a[N];
ll sum1[N],sum2[N],ans=0;//sum1[i],所有正数得前缀和 sum2[i],所有数得前缀和。
int main(){
//  freopen("a.in","r",stdin);
    n=read();k=read();
    for(int i=1;i<=n;++i){
        a[i]=read();sum2[i]=sum2[i-1]+a[i];sum1[i]=sum1[i-1]; 
        if(a[i]>0) sum1[i]+=a[i];
    }for(int i=1;i+k-1<=n;++i){//枚举一段长为k的区域来中转 
        ll res=sum1[n]-(sum1[i+k-1]-sum1[i-1]);
        if(sum2[i+k-1]-sum2[i-1]>0) res+=sum2[i+k-1]-sum2[i-1];
        ans=max(ans,res);
    }printf("%lldn",ans);
    return 0;
}

C

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
ll ans=0,a,b,c;
int main(){
//  freopen("a.in","r",stdin);
    a=read();ans=read();read();b=read();c=read();read();read();
    if(!a||!b||!c){printf("%lldn",ans+a/2*a+b/2*2+c/2*2);return 0;}
    if(a%2==b%2&&b%2==c%2){printf("%lldn",ans+a+b+c);return 0;}
    printf("%lldn",ans+a+b+c-1);
    return 0;
}

D

复制代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 510
#define pa pair<int,int>
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,ans[N*N],id[N*N],cnt[N],num=0;
pa a[N];
int main(){
//  freopen("a.in","r",stdin);
    n=read();for(int i=1;i<=n;++i){
        int x=read();id[x]=i;a[i]=make_pair(x,i);
    }sort(a+1,a+n+1);
    for(int i=1;i<=n;++i){
        int x=a[i].second,pos=a[i].first;ans[pos]=x;cnt[x]=n-x;
        for(int owo=1;owo<x;++owo){
            while(ans[++num]&&num<=pos) continue;
            if(num>pos){puts("No");return 0;}
            ans[num]=x;
        }
    }queue<int>q;
    for(int i=1;i<=n*n;++i){
        if(id[i]&&cnt[id[i]]) q.push(id[i]);
        if(ans[i]) continue;
        if(q.empty()){puts("No");return 0;}int x=q.front();
        ans[i]=x;if(--cnt[x]==0) q.pop();
    }puts("Yes");
    for(int i=1;i<=n*n;++i) printf("%d ",ans[i]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 510
#define pa pair<int,int>
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,ans[N*N],id[N*N],cnt[N],num=0;
pa a[N];
int main(){
//  freopen("a.in","r",stdin);
    n=read();for(int i=1;i<=n;++i){
        int x=read();id[x]=i;a[i]=make_pair(x,i);
    }sort(a+1,a+n+1);
    for(int i=1;i<=n;++i){
        int x=a[i].second,pos=a[i].first;ans[pos]=x;cnt[x]=n-x;
        for(int owo=1;owo<x;++owo){
            while(ans[++num]&&num<=pos) continue;
            if(num>pos){puts("No");return 0;}
            ans[num]=x;
        }
    }queue<int>q;
    for(int i=1;i<=n*n;++i){
        if(id[i]&&cnt[id[i]]) q.push(id[i]);
        if(ans[i]) continue;
        if(q.empty()){puts("No");return 0;}int x=q.front();
        ans[i]=x;if(--cnt[x]==0) q.pop();
    }puts("Yes");
    for(int i=1;i<=n*n;++i) printf("%d ",ans[i]);
    return 0;
}

E

复制代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100020
#define mod 1000000007
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,a[N],du[N],col[N],len[N],cnt[N];
ll ans=1,dp[N];
bool cir[N];
inline int calc(int l1,int l2){
    return (l1<l2)+(l1<=l2);
}
int main(){
//    freopen("a.in","r",stdin);
    n=read();for(int i=1;i<=n;++i) a[i]=read(),du[a[i]]++;
    for(int i=1;i<=n;++i){
        if(col[i]) continue;int x=i;
        for(;!col[x];x=a[x]) col[x]=i;
        if(col[x]!=i) continue;//成环了，标记下环上的点
        for(;!cir[x];x=a[x]) cir[x]=1;
    }for(int i=1;i<=n;++i) if((!cir[i]&&du[i]>1)||(cir[i]&&du[i]>2)){puts("0");return 0;}
    for(int i=1;i<=n;++i){//计算foot的长度
        if(du[i]) continue;int x=i,res=0;
        while(!cir[x]) ++res,x=a[x];len[x]=res;
    }for(int i=1;i<=n;++i){//处理基环内向树
        if(!cir[i]) continue;int x=i,fir=0,firlen=0,k=0,last=0;
        while(cir[x]){
            ++k;cir[x]=0;
            if(len[x]){
                if(!fir){fir=last=k;firlen=len[x];x=a[x];continue;}
                ans=ans*calc(len[x],k-last)%mod;if(!ans){puts("0");return 0;}last=k;
            }x=a[x];
        }if(!fir) cnt[k]++;else ans=ans*calc(firlen,fir+k-last)%mod;
    }if(!ans){puts("0");return 0;}
    for(int i=1;i<=n;++i){//处理大小为i的所有环
        if(!cnt[i]) continue;dp[0]=1;int op=(i&1)+(i>1);//奇环且大于1有两种
        for(int j=1;j<=cnt[i];++j){
            dp[j]=dp[j-1]*op%mod;
            if(j>1) dp[j]=(dp[j]+(ll)(j-1)*i*dp[j-2]%mod)%mod;
        }ans=ans*dp[cnt[i]]%mod;
    }printf("%lldn",ans);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100020
#define mod 1000000007
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,a[N],du[N],col[N],len[N],cnt[N];
ll ans=1,dp[N];
bool cir[N];
inline int calc(int l1,int l2){
    return (l1<l2)+(l1<=l2);
}
int main(){
//    freopen("a.in","r",stdin);
    n=read();for(int i=1;i<=n;++i) a[i]=read(),du[a[i]]++;
    for(int i=1;i<=n;++i){
        if(col[i]) continue;int x=i;
        for(;!col[x];x=a[x]) col[x]=i;
        if(col[x]!=i) continue;//成环了，标记下环上的点
        for(;!cir[x];x=a[x]) cir[x]=1;
    }for(int i=1;i<=n;++i) if((!cir[i]&&du[i]>1)||(cir[i]&&du[i]>2)){puts("0");return 0;}
    for(int i=1;i<=n;++i){//计算foot的长度
        if(du[i]) continue;int x=i,res=0;
        while(!cir[x]) ++res,x=a[x];len[x]=res;
    }for(int i=1;i<=n;++i){//处理基环内向树
        if(!cir[i]) continue;int x=i,fir=0,firlen=0,k=0,last=0;
        while(cir[x]){
            ++k;cir[x]=0;
            if(len[x]){
                if(!fir){fir=last=k;firlen=len[x];x=a[x];continue;}
                ans=ans*calc(len[x],k-last)%mod;if(!ans){puts("0");return 0;}last=k;
            }x=a[x];
        }if(!fir) cnt[k]++;else ans=ans*calc(firlen,fir+k-last)%mod;
    }if(!ans){puts("0");return 0;}
    for(int i=1;i<=n;++i){//处理大小为i的所有环
        if(!cnt[i]) continue;dp[0]=1;int op=(i&1)+(i>1);//奇环且大于1有两种
        for(int j=1;j<=cnt[i];++j){
            dp[j]=dp[j-1]*op%mod;
            if(j>1) dp[j]=(dp[j]+(ll)(j-1)*i*dp[j-2]%mod)%mod;
        }ans=ans*dp[cnt[i]]%mod;
    }printf("%lldn",ans);
    return 0;
}