[cf545]A-D题解 - CheaSim Blog
发表更新cf9 分钟读完 (大约1325个字)0次访问

[cf545]A-D题解

Codeforces Round #545 (Div. 2)

ps 小生不才，比赛时只做出3道。后面补了一道。

Sushi for Two

题意

给定一个只含有1或者2的数组，让你找出一个子数组，子数组要求是$n个1 和 m个2$并要求$min(n,m)$最大。

题解

暴力模拟.

ac代码

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;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5+10;
int a[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    vector<int> ve;
    int n; scanf("%d",&n);
    int cnt1 = 0,cnt2 = 0;
    int ans = 0;
    rep(i,0,n) scanf("%d",a+i);
    int cnt = 0;
    while(cnt<n){
        cnt1= 0;
        cnt2 = 0;
        while(a[cnt] == 1){
            cnt++;
            cnt1++;
        }
        ve.push_back(cnt1);
        while(a[cnt] == 2){
            cnt++;
            cnt2++;
        }
        ve.push_back(cnt2);
    }
    int len = ve.size();
    rep(i,0,len-1){
        ans = max(ans,2*min(ve[i],ve[i+1]));
    }
    printf("%d\n",ans);
    return 0;
}

Circus

题意

给定$n$个人，其中每个人可能会表演小丑也可能会表演杂技演员。要求把$n$个人分成两堆。要求

  • 第一队只能表演小丑，第二队只能表演杂技演员
  • 第一队中小丑的个数和第二队中杂技演员的个数相等
  • 两队的人数相同。

题解

暴力枚举，因为人可以分为四类。所以我们可以枚举出其中两类的分配，之后通过条件舍掉一些答案，得到正确答案。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 1e3+10;
int idx[maxn][maxn];
int col_idx[maxn][maxn];
int mx[maxn][maxn];
int n,m;
int cnt_row[maxn];
int cnt_col[maxn];
int ans[maxn][maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n) rep(j,0,m){
        scanf("%d",mx[i] + j);
    }
    rep(i,0,n){
        vector<int> ve;
        rep(j,0,m) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        rep(j,0,m-1){
            if(ve[j] == ve[j+1]) cnt_row[i]++;
        }
    }
    rep(j,0,m){
        vector<int> ve;
        rep(i,0,n) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        rep(i,0,n-1){
            if(ve[i] == ve[i+1]) cnt_col[j]++;
        }
    }
    rep(i,0,n){
        vector<int> ve;
        rep(j,0,m) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        auto iter = unique(ve.begin(),ve.end());
        ve.erase(iter,ve.end());
        rep(j,0,m) idx[i][j] = lower_bound(ve.begin(),ve.end(),mx[i][j]) - ve.begin();
    }
    rep(j,0,m){
        vector<int> ve;
        rep(i,0,n) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        auto iter = unique(ve.begin(),ve.end());
        ve.erase(iter,ve.end());
        rep(i,0,n) col_idx[i][j] = lower_bound(ve.begin(),ve.end(),mx[i][j]) - ve.begin();
    }
    rep(i,0,n) rep(j,0,m){
        int x = idx[i][j];
        int y = col_idx[i][j];
        int temp = 0;
        if(x>y){
            temp = max(m - cnt_row[i], n + abs(x-y) - cnt_col[j]);
        }else{
            temp = max(n - cnt_col[j], m + abs(x-y) - cnt_row[i]);
        }
        ans[i][j] = temp;
    }
    rep(i,0,n) rep(j,0,m) {
        printf("%d%c",ans[i][j],j==m-1?'\n':' ');
    }

    return 0;
}

C. Skyscrapers

题意

较为简单，自己看吧。

题解

离散化+一些技巧。

因为横竖上最大值会因为中间而改变，所以答案是在

$$max(n-cnt[i],m+abs(x-y)-cnt[j])$$

中产生的。其中$cnt[i]$表示行的重复个数，$cnt[j]$表示列的重复个数。$x,y$表示在行和列中的排名。

我做的有一点烦

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 1e3+10;
int idx[maxn][maxn];
int col_idx[maxn][maxn];
int mx[maxn][maxn];
int n,m;
int cnt_row[maxn];
int cnt_col[maxn];
int ans[maxn][maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n) rep(j,0,m){
        scanf("%d",mx[i] + j);
    }
    rep(i,0,n){
        vector<int> ve;
        rep(j,0,m) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        rep(j,0,m-1){
            if(ve[j] == ve[j+1]) cnt_row[i]++;
        }
    }
    rep(j,0,m){
        vector<int> ve;
        rep(i,0,n) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        rep(i,0,n-1){
            if(ve[i] == ve[i+1]) cnt_col[j]++;
        }
    }
    rep(i,0,n){
        vector<int> ve;
        rep(j,0,m) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        auto iter = unique(ve.begin(),ve.end());
        ve.erase(iter,ve.end());
        rep(j,0,m) idx[i][j] = lower_bound(ve.begin(),ve.end(),mx[i][j]) - ve.begin();
    }
    rep(j,0,m){
        vector<int> ve;
        rep(i,0,n) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        auto iter = unique(ve.begin(),ve.end());
        ve.erase(iter,ve.end());
        rep(i,0,n) col_idx[i][j] = lower_bound(ve.begin(),ve.end(),mx[i][j]) - ve.begin();
    }
    rep(i,0,n) rep(j,0,m){
        int x = idx[i][j];
        int y = col_idx[i][j];
        int temp = 0;
        if(x>y){
            temp = max(m - cnt_row[i], n + abs(x-y) - cnt_col[j]);
        }else{
            temp = max(n - cnt_col[j], m + abs(x-y) - cnt_row[i]);
        }
        ans[i][j] = temp;
    }
    rep(i,0,n) rep(j,0,m) {
        printf("%d%c",ans[i][j],j==m-1?'\n':' ');
    }

    return 0;
}

D. Camp Schedule

题意

给定两串字符串$s,t$。要求把$s$重新排列使得$s$中的子串里，$t$出现的次数尽可能多。

题解

kmp

我们可以想象一下，如果要$s$中要有尽量多的$t$，那么首先我们在$s$的最前面是一个$t$。之后我们需要加入后续的数字，使得尽可能多的像$t$。这和kmp的思想是很相似的。就是我们在最后一个字母失配之后，我们应该跳转到的那个字母开始，继续匹配就可以匹配成一个字符串了。

举个栗子吧。

111000

101

这个例子中，我们先在$s$的前面放一个$101$。

之后我们需要配一个字母，使得尽量减少失配的字符串的长度，所以我们加入$len[next]$，也就是$0$。之后我们加入$1$形成了$10101$这样就产生了两个$t$。之后我们模拟这样子的行为就可以了。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e5+10;
char s[maxn],t[maxn];
int nxt[maxn];
void getnxt(char *str){
    int len = strlen(str);
    int i = 0, j = -1;
    nxt[0] = -1;
    while(i<len){
        if(j==-1 || str[i] == str[j]){
            i++,j++;
            nxt[i] = j;
        }else{
            j = nxt[j];
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%s",s); scanf("%s",t);
    getnxt(t);
    int len = strlen(t);
    int sz = 0;
    int cnt0 = 0,cnt1 = 0;
    int len1 = strlen(s);
    rep(i,0,len1){
        if(s[i] == '1') cnt1++;
        else cnt0++;
    }
    int i = 0;
    bool flag = true;
    while(flag && cnt0 > 0 && cnt1 > 0){
        for(i;i<len;i++){
            if(t[i] == '1' && cnt1-- > 0) printf("1");
            else if(t[i] == '0' && cnt0-- > 0) printf("0");
            else {
                flag = false;break;
            }
        }
        i = nxt[len];
    }
    while(cnt0-->0) printf("0");
    while(cnt1-->0) printf("1");
    return 0;
}

[cf545]A-D题解

https://www.cheasim.com/cf/2019/03/09/cf545-A-D%E9%A2%98%E8%A7%A3.html

作者

CheaSim

发布于

2019-03-09

更新于

2019-03-09

许可协议

#

喜欢这篇文章？打赏一下作者吧

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

评论

关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×