[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;
}