AtCoder Grand Contest 037

发表于 更新于 分类于

比赛链接： https://atcoder.jp/contests/agc037/tasks 。

A - Dividing a String

注意到最优解一定长度为$1$或$2$，所以直接$\rm dp$就行了。

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
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
char s[maxn];
int f[maxn][3];
 
int main() {
    scanf("%s",s+1);int n=strlen(s+1);
    for(int i=1;i<=n;i++) {
        if(s[i]==s[i-1]) f[i][1]=f[i-1][2]+1;
        else f[i][1]=f[i-1][1]+1;
        if(i>=2) {
            f[i][2]=f[i-2][1]+1;
            if(s[i]!=s[i-2]||s[i-1]!=s[i-3]) f[i][2]=max(f[i][2],f[i-2][2]+1);
        }
    }write(max(f[n][1],f[n][2]));
    return 0;
}

B - RGB Balls

可以把题意转化为这样：把这个数列顺序扫一遍，然后把当前这个球分配给任意一个没有这个颜色的人，最小化每个人拿到第一个球和拿到最后一个球的时间差。

也就是要最小化每个时刻拿到一个或两个球的人数之和。

那么每次一定是如果能凑满一个人就凑满，否则优先给已经有一个球的人。

那么记录一下每个状态当前有多少人，方案数直接乘一下就好了。

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
50
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;
 
int n,c[8];
char s[maxn];
 
int main() {
    read(n);scanf("%s",s+1);
    for(int i=1;i<=n*3;i++) s[i]=s[i]=='R'?0:(s[i]=='G'?1:2);
    int ans=1;c[0]=n;
    for(int i=1;i<=n*3;i++) {
        int t;
        if(c[t=7-(1<<s[i])]) {ans=1ll*ans*c[t]%mod,c[t]--;continue;}t=0;
        for(int x=0;x<3;x++)
            if(x!=s[i]&&c[1<<x]) {t=1;ans=1ll*ans*c[1<<x]%mod;c[1<<x]--,c[(1<<x)|(1<<s[i])]++;break;}
        if(!t) ans=1ll*ans*c[0]%mod,c[0]--,c[1<<s[i]]++;
    }
    write(ans);
    return 0;
}

C - Numbers on a Circle

考虑倒着操作，每个操作改为$b-=a+c$，那么我们需要把$b$数组变成$a$。

如果我们当前能操作$x$，那么一定满足$b_x\geqslant b_{x+1}+b_{x-1}$，也就是说如果我们不操作$x$那么一定不能操作$x+1,x-1$，所以这个操作如果不进行那么他永远都不会改变。

所以可以得到一个暴力，每次找到一个可以操作的做一次。

考虑如何优化，拿一个堆存下当前$b_x>a_x$的集合，每次取出$b_x$最大的那个，如果不能操作显然无解，否则就尽量操作到恰好大于等于$a_x$。

这相当于是一个辗转相除的过程，设值域为$v$，那么复杂度就是$O(n\log n\log v)$。

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
50
51
52
#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int a[maxn],b[maxn],n,ans;
priority_queue<pii > q;
 
signed main() {
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
    for(int i=1;i<=n;i++) if(b[i]>a[i]) q.push(mp(b[i],i));
    while(!q.empty()) {
        int x=q.top().sc;q.pop();
        int p=b[(x-1)?x-1:n]+b[x%n+1],t=0;
        ans+=(t=(b[x]-a[x])/p),b[x]-=t*p;
        if(!t) return puts("-1"),0;
        if(b[x]>a[x]) q.push(mp(b[x],x));
    }write(ans);
    return 0;
}

D - Sorting a Grid

考虑对最后的矩阵每一行染色，共$n$种颜色，那么我们只需要保证在第三次操作之前把颜色弄对就行了。

进一步来说，只需要在第二次操作之前使得每一列的颜色构成一个排列即可。

那么只需考虑第一次操作怎么做，我们先确定最左边的一列，容易发现剩下的构成了一个子问题。

考虑二分图，左边为$n$行，右边为$n$种颜色，若第$i$行存在第$j$种颜色就连边，注意到对于每一个行的子集，假设大小为$x$，那么这些行必然包括大于等于$x$中颜色，那么根据$\rm hall$定理可知这个二分图存在完美匹配。

如果用$\rm dinic$实现二分图匹配复杂度为$O(n^3\sqrt n)$。

我总觉得我写网络流的时候有buff。。。这代码我二十分钟不到敲完1a了

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e2+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int a[maxn][maxn],n,m,vis[maxn][maxn];
int head[maxn<<1],tot,dis[maxn<<1],s,t;
struct edge{int to,nxt,w;}e[100050];

void add(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}

void ins(int u,int v,int w=1) {add(u,v,w),add(v,u,0);}

int bfs() {
    memset(dis,-1,sizeof dis);
    queue<int > q;q.push(s),dis[s]=1;
    while(!q.empty()) {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nxt)
            if(e[i].w&&dis[e[i].to]==-1) {
                dis[e[i].to]=dis[x]+1;
                if(e[i].to==t) return 1;
                q.push(e[i].to);
            }
    }return 0;
}

int dfs(int x,int f) {
    if(x==t) return f;
    int used=0;
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].w&&dis[e[i].to]==dis[x]+e[i].w) {
            int d=dfs(e[i].to,min(f,e[i].w));
            e[i].w-=d,e[i^1].w+=d,f-=d,used+=d;
            if(!f) break;
        }
    if(!used) dis[x]=-1;
    return used;
}

int dinic() {
    int flow=0;
    while(bfs()) flow+=dfs(s,inf);
    return flow;
}

int main() {
    read(n),read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) read(a[i][j]);
    for(int j=1;j<=m;j++) {
        s=n*2+1,t=s+1,tot=1;memset(vis,0,sizeof vis);
        for(int i=1;i<=t;i++) head[i]=0;
        for(int i=1;i<=n;i++)
            for(int k=j;k<=m;k++) {
                int c=(a[i][k]-1)/m+1;
                if(!vis[i][c]) vis[i][c]=tot+1,ins(i,c+n);
            }
        for(int i=1;i<=n;i++) ins(s,i),ins(i+n,t);
        dinic();
        for(int i=1;i<=n;i++)
            for(int k=1;k<=n;k++)
                if(vis[i][k]&&!e[vis[i][k]].w) {
                    for(int x=j;x<=m;x++) if((a[i][x]-1)/m+1==k) {swap(a[i][j],a[i][x]);break;}
                    break;
                }
    }
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=m;j++) printf("%d ",a[i][j]);
    for(int i=1;i<=n;i++,puts("")) 
        for(int j=1;j<=m;j++) 
            for(int x=1;x<=n;x++) if((a[x][j]-1)/m+1==i) {printf("%d ",a[x][j]);break;}
    return 0;
}

E - Reversing and Concatenating

注意到如果最小的字母为$x$，显然我们想最大化串全为$x$的前缀的长度。

那么考虑把给出的串翻转之后接在后面，取出最长的连续一段的$x$，以这一段作为后缀得到第一次操作后的串。

那么接下来的每次操作我们可以把$x$的后缀的长度翻倍。

也就是说我们可以得到一个全为$x$的前缀长度为$mx\cdot 2^{k-1}$的串，其中$mx$为一开始最长连续一段$x$的长度。

那么如何最小化剩下的长度呢，其实只需要在一开始取最长一段$x$的时候长度相等的时候取倒序字典序最小的就行，因为这一段会在最后一次操作被弄成顺序。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,k;
char s[maxn];
vector<int > p;

int cmp(int a,int b) {
    for(;a&&b;a--,b--)
        if(s[a]>s[b]) return 0;
        else if(s[a]<s[b]) return 1;
    return 0;
}

int main() {
    read(n),read(k),scanf("%s",s+1);int t=1e9;
    for(int i=n+1;i<=2*n;i++) s[i]=s[2*n-i+1],t=min(t,(int)s[i]);
    int mx=0,r=0;
    for(int i=1;i<=(n<<1)+1;i++)
        if(s[i]!=t&&s[i-1]==t) {
            if(r>mx) mx=r,p.clear(),i>n?p.pb(i-1):void();
            else if(r==mx) i>n?p.pb(i-1):void();r=0;
        } else if(s[i]==t) r++;
    t=p[0];
    for(int i=1;i<p.size();i++) if(cmp(p[i],t)) t=p[i];k--;
    if(k>18) for(int i=1;i<=n;i++) putchar(s[t]);
    else {
        for(int i=1;i<=min(n,mx*(1<<k));i++) putchar(s[t]);
        for(int i=1;i<=max(0,n-mx*(1<<k));i++) putchar(s[t-mx+1-i]);
    }puts("");
    return 0;
}