Codeforces Round 545 (Div. 2)

Diposting di | Edited on

传送门

A - Sushi for Two(签到)

题意

在一个 01 序列中找出长为偶数的连续的一段使得它前一半和后一半内部分别相同，而前一半和后一半不同。

思路

纸上模拟了一下然后预处理 赛后发现太麻烦了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const int inf=1e9;
typedef unsigned long long ull;
int a[maxn];
int one[maxn];
int zero[maxn];
int num[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1)one[i]++;
        else zero[i]++;
    }
    for(int i=1;i<=n;i++){
        if(one[i])one[i]=one[i-1]+1;
        if(zero[i])zero[i]=zero[i-1]+1;
     //   cout<<one[i]<<" "<<zero[i]<<endl;
    }
    for(int i=n;i>=1;i--){
        if(one[i])one[i]=max(one[i],one[i+1]);
        if(zero[i])zero[i]=max(zero[i],zero[i+1]);
    }
  //  cout<<endl;
    int ans=0;
    for(int i=1;i<=n;i++){
     //   cout<<one[i]<<" "<<zero[i]<<endl;
        ans=max(ans,min(one[i-1],zero[i]));
        ans=max(ans,min(zero[i-1],one[i]));
    }
    cout<<ans*2<<endl;

    return 0;
}

B - Circus (数学，推公式)

题意

有 n个人，需要把它们分成两组，每组恰好 2/n 个人。每个人可能会技能 11或技能 2，一个人可能会其中一种、两种都会或什么都不会。

要求第一组中会技能 1的人数恰好等于第二组中会技能 2 的人数，输出方案

2<=n<=5000

思路

比赛在纸上写了两张纸都没写出来的题

参考https://www.cnblogs.com/wjyyy/p/cf1138.html 

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;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
vector<int>v[5];
char s[maxn],t[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s%s",s+1,t+1);
    for(int i=1;i<=n;i++){
        v[s[i]-'0'+(t[i]-'0')*2].push_back(i);
    }
    int a=v[0].size(),b=v[1].size(),c=v[2].size(),d=v[3].size(),h=n/2;
    for(int i=0;i<=d;i++){
        if(d-i+c>h||i+b>h)continue;
        if(i<d-i){
            if(b<d-2*i)continue;
            for(int j=0;j<i;j++)
                printf("%d ",v[3][j]);
            h-=i;
            for(int j=0;j<d-2*i;j++)
                printf("%d ",v[1][j]);
            h-=d-2*i;
            for(int j=0;j<c;j++)
                printf("%d ",v[2][j]);
            h-=c;
            for(int j=0;j<h;j++)
                printf("%d ",v[0][j]);
            return 0;
        }
        else{
            if(c<2*i-d)continue;
            c-=2*i-d;
            for(int j=0;j<i;++j)
                printf("%d ",v[3][j]);
            h-=i;
            for(int j=0;j<c;++j)
                printf("%d ",v[2][j]);
            h-=c;
            for(int j=0;j<h;++j)
                printf("%d ",v[0][j]);
            return 0;
        }
    }
    printf("-1");
    return 0;
}

C - Skyscrapers (离散化+贪心)

题意

有一个 n×m的矩阵 aijaij。

对于每个 (i,j)1≤i≤n1≤i≤n），你把第 i行和第 j 列单独抽出，这样就有 n+m−1 个数被你抽出。

你可以对这些数重新标号为正整数，但是要满足第 i行所有数的大小关系不变，第 j列所有数的大小关系不变（两个限制相互独立）。

满足这个限制下，你希望最大的标号尽量小，对每个 (i,j) 求出这个最小的最大标号。

思路

因为行大小关系不变，列大小关系不变，我们考虑分别离散化每行每列，并统计每个数在行内和列内的排名。

然后贪心取个最大的

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const int inf=1e9;
typedef unsigned long long ull;
vector<int>ve;
int a[1500][1500];
vector<int>h[1500];
vector<int>l[1500];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            h[i].push_back(a[i][j]);
            l[j].push_back(a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        sort(h[i].begin(),h[i].end());
        h[i].erase(unique(h[i].begin(),h[i].end()),h[i].end());
    }

    for(int i=1;i<=m;i++){
        sort(l[i].begin(),l[i].end());
        l[i].erase(unique(l[i].begin(),l[i].end()),l[i].end());
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int A=h[i].size(),aa=lower_bound(h[i].begin(),h[i].end(),a[i][j])-h[i].begin()+1;
            int B=l[j].size(),b=lower_bound(l[j].begin(),l[j].end(),a[i][j])-l[j].begin()+1;
            cout<<(aa<b?max(B,b+A-aa):max(A,aa+B-b))<<" ";
        }
        cout<<endl;
    }
    return 0;
}

D - Camp Schedule (KMP 贪心)

题意

有两个 01 串 s 和 t，要求重新排列 s 使得 t 在重新排列后的 s 中出现次数尽量多（位置相交的出现也算）。

思路

一眼KMP 求出T的next数组，然后贪心重叠匹配 关键是可以位置相交

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const int inf=1e9;
typedef unsigned long long ull;
char s[maxn];
char t[maxn];
void kmp_pre(char x[],int m,int next[]){
    int i,j;
    j=next[0]=-1;
    i=0;
    while(i<m){
        while(-1!=j&&x[i]!=x[j])j=next[j];
        next[++i]=++j;
    }
}
int mynext[maxn];
int kmp(char x[],int m,char y[],int n){
    int i,j;
    int ans=0;
    kmp_pre(x,m,mynext);
    i=j=0;
    while(i<n){
        while(-1!=j&&y[i]!=y[j])j=mynext[j];
        i++;j++;
        if(j>=m){
            ans++;
            j=mynext[j];
        }
    }
    return j;
}
string str;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>s;
    cin>>t;
    int lens=strlen(s);
    int a0=0,a1=0;
    for(int i=0;i<lens;i++)if(s[i]=='0')a0++;else a1++;
    int lent=strlen(t);
    kmp_pre(t,lent,mynext);
    int num=mynext[lent];
    //int num=kmp(t,lent,t,lent);
    string p="";
    int n1=0,n0=0;
    for(int i=num;i<lent;i++){
        p+=t[i];
        if(t[i]=='0')n0++;
        else n1++;
    }
    int b1=0,b0=0;
    for(int i=0;i<lent;i++){
        if(t[i]=='0')b0++;
        else b1++;
    }
    if(a0<b0||a1<b1){
        cout<<s<<endl;exit(0);
    }
    str+=t;
    a1-=b1;a0-=b0;
    while(a1>=n1&&a0>=n0){
        str+=p;
        a1-=n1,a0-=n0;
    }
    while(a1--){
        str+="1";
    }
    while(a0--){
        str+="0";
    }
    cout<<str<<endl;
    return 0;
}

F - Cooperative Game (Floyd判环，龟兔赛跑算法)

题意

一个条路 连着一个环，路和环的连接点定义为终点

十个人 每次可以移动一些人向前单项移动（参考链表）

交互题，每次选择一个人的编号让他想前移动

之后系统会告诉你现在哪些点有人，分别是谁

把所有人移动到终点就输出“done”结束

思路

裸的Floyd算法 过程完全一模一样

首先让两个人一个一次移动一步，一个一次移动两步。

然后两人会在一个点相遇。次数假设慢的人经过的距离为$s$ 那么快的人距离为$2s$

$s=m+i*l+k$ 1式

$2s=m+j*l+k$ 2式

两式相减

$s=(j-i)l$ 3式

带入1式

所以当一个点开始从m走到起点时，另一个点也走到了开始的地方

我的想法

1
2
3
假设出发起点到环起点的距离为m，已经确定有环，环的周长为n，（第一次）相遇点距离环的起点的距离是k。那么当两者相遇时，慢指针（t）移动的总距离i = m + a * n + k，快指针（h）的移动距离为2i，2i = m + b * n + k。其中，a和b分别为t和h在第一次相遇时转过的圈数。让两者相减（快减慢），那么有i = (b - a) * n。即i是圈长度的倍数。

将一个指针移到出发起点S，另一个指针仍呆在相遇节点M处两者同时移动，每次移动一步。当第一个指针前进了m，即到达环起点时，另一个指针距离链表起点为i + m。考虑到i为圈长度的倍数，可以理解为指针从链表起点出发，走到环起点，然后绕环转了几圈，所以第二个指针也必然在环的起点。即两者相遇点就是环的起点。
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
int t;
void get(){
    fflush(stdout);
    scanf("%d",&t);
    for(int i=1;i<=t;i++)scanf("%*s");
}
int main()
{
    do{
        puts("next 0 1"),get();
        puts("next 0"),get();
    }while(t==3);
    do{
        puts("next 0 1 2 3 4 5 6 7 8 9"),get();
    }while(t==2);
    puts("done");
    return 0;
}