ACM_JLINE.

CF 545 Div. 2

KMP 二分
字数统计: 1.3k阅读时长: 6 min
2019/03/12 Share

CF 545 Div. 2

原题链接：传送门

真香
又把这事给搁下了
打了场傍晚场的CF B题才过了五百来号人 太惨了啊。
打不动 打不动

A

题目大意：

在数组中 只包含 1 2， 找出最长连续的1 1 … 2 2 … 或者 2 2 … 1 1… ，要求 1 和 2 数量相等

题解：

0(n) 扫一遍就行, 签到

Code block

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;
const int MOD = 1e9+7;
const int Maxn = 200005;

int n, a[100005];

int main()
{
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	} 
	
	int x = 1, t = 0;
	int Max = 0;
	
	for(int i = 1; i < n; i++){
		if(a[i] == a[i-1]) {
			x++;
		}
		else{
			t = min(t, x);
			Max = max(t, Max);
			t = x;
			x = 1;
		}
	}
	
	t = min(t, x);
	Max = max(t, Max);
	printf("%d\n", Max * 2);
	
	return 0;
 }

B

题目大意：

有 n 个人， 每个人会表演小丑和杂技， 或者什么都不会， 或只会其一。
需要分成两组，每组 n / 2 个人，要求第一组中会小丑的人和第二组会杂技的人一样多！

题解：

解方程， 暴力枚举
疯狂判断

Code block

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 <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10005; 
int n;
char c[N], a[N];
vector <int> V[6]; 

int main(){
	scanf("%d", &n);
	scanf("%s", c + 1);
	scanf("%s", a + 1);
	
	for(int i = 1; i <= n; i++){
		if(c[i] == '0'){
			if(a[i] == '0') V[0].push_back(i);
			else V[1].push_back(i);
		}
		else{
			if(a[i] == '0') V[2].push_back(i);
			else V[3].push_back(i);
		}
	}
	
	int A = V[0].size(), B = V[1].size(), C = V[2].size(), D = V[3].size();
	
	for(int i = 0; i <= C; i++){
		for(int j = 0; j <= B; j++){
			if((j + D - i) % 2 == 0 && (j + D - i) / 2 >= 0 
                            && n / 2 - (B - j) - i - (j + D -i) / 2
			    >= 0 && n / 2 - j - (C - i)- (D- (j + D -i) / 2) >= 0 
                               && (j + D - i) / 2 <= D ){
				for(int k = 0; k < n / 2 - (B - j) - i - (j + D -i) / 2; k++)
                                  printf("%d ", V[0][k]);
				for(int k = 0; k < B - j; k++) 
                                    printf("%d ", V[1][k]);
				for(int k = 0; k < i; k++) printf("%d ", V[2][k]);
				for(int k = 0; k < (j + D - i) / 2; k++) 
                                    printf("%d ", V[3][k]);
				return 0;
			}
		}
	}
	
	printf("-1\n");
	return 0;
}

C

题目大意：

有 n * m 的一个矩阵，对于每一个点，需要对其一整行加上一整列近行从小到大编号
要求最大编号尽量小，可以出现1 1 2 2 2 3 这种编号方法，题目中有说明只要表明两两之间的相对关系大小即可。

题解：

对每一列每一行分别排序，然后对于其中的每一个点，只要二分查找齐对应的位置，注意行列影响。

Code block

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 <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

const int N = 1005;
int n, m;
int h[N][N];
vector <int> c[N], r[N];

int main(){
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%d", &h[i][j]);
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			r[i].push_back(h[i][j]); //行 
		}
		sort(r[i].begin(),r[i].end()); 
		r[i].erase(unique(r[i].begin(), r[i].end()), r[i].end());
    //unique()函数将重复的元素放到vector的尾部 
	//然后返回指向第一个重复元素的迭代器 再用erase函数擦除从这个元素到最后元素的所有的元素
	}
	
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			c[i].push_back(h[j][i]); //列 
		}
		sort(c[i].begin(), c[i].end());
		c[i].erase(unique(c[i].begin(), c[i].end()), c[i].end());
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			int x = lower_bound(r[i].begin(), r[i].end(), h[i][j]) - r[i].begin();
			int y = lower_bound(c[j].begin(), c[j].end(), h[i][j]) - c[j].begin();
			int a = r[i].end() - lower_bound(r[i].begin(), r[i].end(), h[i][j]);
			int b = c[j].end() - lower_bound(c[j].begin(), c[j].end(), h[i][j]);
			printf("%d ", max(x, y) + max(a, b)); 
		}
		printf("\n");
	}
		
	return 0;
}

D

题目大意：

有两个字符串 S，T，只包含 0 1 。现在需要把字符串 S 重新排序，使 S 中包含最多的 T，根据题目是可重复子串。

题解：

KMP 计算 next数组。
每当 T 构造完后，直接从它的相同前缀后一个开始构造。直到 0 1 有一个先用完。

Code block

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 500005;
char s[N], t[N], ans[N];
int nxt[N], cnt[N];

int main(){
	scanf("%s%s", s + 1, t + 1);
	int m = strlen(t + 1);
	int len = strlen(s + 1);
	
	for(int i = 1; i <= len; i++){
		cnt[s[i] - '0']++;
	}
	
	int p = 0; 
	for(int i = 2; i <= m; i++){
		while(p && t[p+1] != t[i]) p = nxt[p];
		if(t[p+1] == t[i]) p++;
		nxt[i] = p;
	}
	
	p = 1;
	for(int i = 1; i <= len; i++){
		if(cnt[t[p] - '0'] == 0){
			for(int j = i; j <= len; j++){
				ans[j] = ((t[p] - '0') ^ 1) + '0';
			}
			break;
		}
		cnt[t[p] - '0']--;
		ans[i] = t[p];
		p++;
		if(p > m) p = nxt[m] + 1;
	}
	
	for(int i = 1; i <= len; i++){
		printf("%c", ans[i]);
	}
	return 0;
}

原文作者：CHEN

原文链接：http://yourself.com/2019/03/12/Codeforces545/

发表日期：March 12th 2019, 7:17:11 pm

更新日期：March 12th 2019, 7:27:11 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. CF 545 Div. 2
    1. 1.1. 原题链接：传送门
    2. 1.2. A
      1. 1.2.1. 题目大意：
      2. 1.2.2. 题解：
      3. 1.2.3. Code block
    3. 1.3. B
      1. 1.3.1. 题目大意：
      2. 1.3.2. 题解：
      3. 1.3.3. Code block
    4. 1.4. C
      1. 1.4.1. 题目大意：
      2. 1.4.2. 题解：
      3. 1.4.3. Code block
    5. 1.5. D
      1. 1.5.1. 题目大意：
      2. 1.5.2. 题解：
      3. 1.5.3. Code block
Total : 28
2019
Invalid date
2019
Invalid date
Invalid date
2019
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
差分约束 KMP 二分 最短路 二分图 素数筛 LCA 树上差分 set维护 ICPC ccpc Hello CF 倍增 归并 随笔 贪心 map DP 树链剖分 树状数组 DFS CSP 贪心 并查集 dfs序 set 扫描线
ACM 最短路