Codeforces Round 592 (Div 2)（A - G）

Codeforces Round 592 (Div. 2)（A - G）

Dashboard - Codeforces Round 592 (Div. 2) - Codeforces

A. Pens and Pencils(思维)

思路：比较完成 绘画课 和 讲座 所需的 最小笔数 和 k 的关系即可。

$$时间复杂度O(1)$$

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int a , b , c , d , k , t;

signed main(){

	cin >> t;
	while(t --){
		cin >> a >> b >> c >> d >> k;
		int cnt1 = (a - 1) / c + 1;
		int cnt2 = (b - 1) / d + 1;
		if(cnt1 + cnt2 <= k){
			cout << cnt1 << " " << k - cnt1 << "\n";
		} else {
			cout << "-1\n";
		}
	}
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
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

B. Rooms and Staircases(思维)

思路：对于每一个纵向的梯子 ， 如果走过梯子后不改变方向 ， 那么是否经过梯子不影响结果 ， 所以经过梯子后一定要改变方向 ， 贡献就是梯子位置离出发点的二倍 ， 枚举梯子位置计算最大贡献即可。

$$时间复杂度O(n)$$

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , n;
string s;

signed main(){

	IOS
	cin >> t ;
	
	while(t --){
		cin >> n >> s;
		int maxx = n;
		for(int i = 0 ; i < n ; i ++){
			if(s[i] == '1') maxx = max(maxx , (i + 1) * 2);
		}
		for(int i = n - 1 ; i >= 0 ; i --){
			if(s[i] == '1') maxx = max(maxx , (n - i) * 2);
		}
		cout << maxx << "\n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
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

C. The Football Season（扩展欧几里得算法)

大意：给出两个式子

$$x\ast w+y\ast d=p(1)$$

$$x+y+z=n(2)$$

现给出 n , p , w , d , 求是否存在一组 (x , y , z) 满足上式且都为非负数。

思路：看到 (1) 式 不难想到扩欧去解 x , y 的通解 ， 观察 (2) 式 ， 可以发现我们要在满足条件的情况下使 (x + y) 尽可能小 ， 这样 z 才能最大可能的有解 。

已知了 x ， y 的通解 ， 如何在满足条件(即 x , y 非负)的情况下使得 (x + y) 最小呢？

观察我们求出的通解：

$$x=x_0\ast \frac{p}{gcd(w,d)}+\frac{k\ast d}{gcd(w,d)}$$

$$y=y_0\ast \frac{p}{gcd(w,d)}-\frac{k\ast w}{gcd(w,d)}$$

题目中有一个极其重要的条件 ， 即：d < w , 即在 k 不断增大的时候 ， (x + y) 的和是不断在变小的 ， 我们可以根据 (y ≥ 0) 的条件算出满足条件的最大的 k ， 即算出了 (x + y) 的最小值 ， 判断是否有满足条件的 z 即可。

$$时间复杂度O(logn)$$

易错点：

1. 会爆 long long ， 用 __int128

2. 算出 k 带入通解求出 x 之后需要判断 x 是否合法。

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int __int128
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

inline void read(int &n){
	int x = 0 , f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ 48); ch=getchar();}
    n = x * f;
}
inline void write(int n){
    if(n < 0){ putchar('-'); n *= -1; }
    if(n > 9) write(n / 10);
    putchar(n % 10 + '0');
}

int exgcd(int a , int b , int &x , int &y){
	
	if(b == 0){ x = 1; y = 0; return a;}
	int g = exgcd(b , a % b , y , x);
	y -= a / b * x;
	return g;
}

int n , p , w , d , g , x , y;

signed main(){

	read(n);read(p);read(w);read(d);
	
	g = exgcd(w , d , x , y);
	
	if(p % g){
		write(-1);
	}else{
		w /= g;d /= g;p /= g;
		int k = floor(1.0L * (y * p) / (1.0L * w));
		int xx = x * p + k * d;
		int yy = y * p - k * w;
		if(xx + yy > n || xx < 0){
			write(-1);
		}else{
			write(xx);
			putchar(' ');
			write(yy);
			putchar(' ');
			write(n - (xx + yy));
		}
	}
	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
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

D. Paint the Tree(树链 ， 构造)

思路：不难发现 ， 要染色树必须是一条链 。 且确定一条链一侧的两个节点颜色后整条链的颜色就确定了 ， 总共 6 种染色方案 ， 依次遍历求最小值即可。

$$时间复杂度O(nlogn)$$

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
int val[N][4] , n , cnt , in[N] , lis[4];
vector<int>ve[N];
bool vis[N];
struct node{
	int x , ans;
}a[N];

bool bfs(){
	
	queue<int>q;
	
	for(int i = 1 ; i <= n ; i ++){
		if(in[i] == 1) {
			q.push(i);
			a[++cnt].x = i;
			vis[i] = 1;
			break;
		}
	}
	
	while(q.size()){
		int now = q.front();q.pop();
		for(auto k : ve[now]){
			if(vis[k]) continue;
			vis[k] = 1;
			q.push(k);
			a[++cnt].x = k;
		}
		if(q.size() > 1) return 0;
	}
	return 1;
}

signed main(){

	cin >> n;
	
	for(int i = 1 ; i <= 3 ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			cin >> val[j][i];
		}
	}
	
	for(int i = 1 ; i <= n - 1 ; i ++){
		int u , v;
		cin >> u >> v;
		in[u] += 1;
		in[v] += 1;
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	
	if(bfs()){
		int all = 6;
		for(int i = 0 ; i < 3 ; i ++) lis[i] = i + 1;
		int minn = 9e18;
		while(all --) {
			int now = 0;
			for(int i = 1 ; i <= n ; i ++){
				now += val[a[i].x][lis[i % 3]];
			}
			if(now < minn) {
				minn = now;
				for(int i = 1 ; i <= n ; i ++){
					a[i].ans = lis[i % 3];
				}
			}
			next_permutation(lis , lis + 3);
		}
		sort(a + 1 , a + 1 + n , [&](node x , node y){
				return x.x < y.x;
			}
		);
		cout << minn << "\n";
		for(int i = 1 ; i <= n ; i ++){
			cout << a[i].ans << " ";
		}
		cout << "\n";
	}else{
		cout << "-1\n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
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

E. Minimizing Difference(双指针 ， 贪心)

思路：不难发现 ， 想要让 (max(a) - min(a)) 减小 1 , 每次操作就要让所有的最小值增加 1 或者 让所有的最大值 减小 1. 所以考虑每次贪心的操作最大值和最小值中少的那个 ， 那么变化多少呢 ， 以最小值为例 ， 由于我们是以个数少为贪心的策略 ， 当最小值变化到次小值的时候显然个数会发生变化 ， 此时就要重新调整策略 ， 故每次调整的上界就是和相邻值的差值 ， 双指针维护即可。

$$时间复杂度O(n)$$

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int n , k;
int a[N];

signed main(){

	cin >> n >> k;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	sort(a + 1 , a + 1 + n);
	
	int l = 1 , r = n;
	int cntl = 1 , cntr = 1;
	int now = a[r] - a[l] , res = 0;
	
	while(l < r) {
		
		while(a[l] == a[l + 1]) l += 1 , cntl += 1;
		while(a[r] == a[r - 1]) r -= 1 , cntr += 1;
		
		if(cntl < cntr) {
			res = (a[l + 1] - a[l]) * cntl;
			if(k >= res) {
				k -= res;
				now -= (a[l + 1] - a[l]);
				l += 1;cntl += 1;
			} else {
				int cntk = k / cntl;
				now -= cntk;
				break;
			}
		} else {
			res = (a[r] - a[r - 1]) * cntr;
			if(k >= res) {
				k -= res;
				now -= (a[r] - a[r - 1]);
				r -= 1;cntr += 1;
			} else {
				int cntk = k / cntr;
				now -= cntk;
				break;
			}
		}
	} 

	cout << max(0ll , now) << "\n";

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
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

F. Chips(分类讨论 + 模拟)

思路 ： 手模一下发现可以分类讨论 ，我们把环拆成两种序列。

第一种序列是 相邻元素相同的序列 ， 例如 WWW , BBBBB

第二种序列是 两种元素交错出现的序列 ， 例如 ： WBWBWBW

每次操作 ， 第一种序列是不会改变的 ， 而第二种序列会被两侧的第一种序列不断同化 ， 每次操作第二种序列的长度减少 2

举例：假如环是 WWBWBWBWW ， 我们可以把环拆成 WWWW 和 BWBWB

第一次操作序列会变成 WWWBWBWWW

第二次操作序列会变成 WWWWBWWWW

第三次操作序列会变成 WWWWWWWWW

举例：假如环是 WWBWBWBB ， 我们可以把环拆成 WW ， BB 和 BWBW

第一次操作序列会变成 WWWBWBBB

第二次操作序列会变成 WWWWBBBB

如果 k 足够大 ， 第二种序列会被前后的第一种序列同化 ， 否则剩余的部分会根据 k 的奇偶性决定是否变化。

分三种情况讨论 ：

1. 环上全是第一种序列 ， 如何操作都不发生变化

2. 环上全是第二种序列 ，根据 k 的奇偶性发生变化。

3. 环中既有第一种序列也有第二种序列 ， 考虑断环为链 ， 取出环中所有的第二种序列 ， 根据 序列的长度 与 操作次数的关系 分类讨论即可。

$$时间复杂度O(nlogn)$$

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int n , m ;
string s;
int vis[N] , now[N];

int nex(int x) {
	return (x + 1) % n;
}
int pre(int x){
	return (x - 1 + n) % n;
}

signed main(){

	cin >> n >> m >> s;
	for(int i = 0 ; i < n ; i ++) {
		if(s[i] == s[nex(i)]) {
			if(s[i] == 'B') vis[i] = vis[nex(i)] = 1;
			else vis[i] = vis[nex(i)] = -1;
		}
	}
	
	int cnt = 0;
	
	for(int i = 0 ; i < n ; i ++) {
		if(vis[i]) cnt += 1;
	}
	
	if(cnt == n) {
		cout << s << "\n";
	} else if (cnt == 0) {
		if(m & 1) {
			for(int i = 0 ; i < n ; i ++) if(s[i] == 'B') s[i] = 'W'; else s[i] = 'B';
		}
		cout << s << "\n";
	} else {
		set<tuple<int , int , int>>info;
		for(int i = 0 ; i < 2 * n ; i ++) {
			if(i < n) now[i] = vis[i];
			else now[i] = vis[i - n];
//			cout << now[i] << " ";
		}
//		cout << "\n";
		int l = 0 , r = 2 * n - 1;
		while(!now[l]) l += 1;
		while(!now[r]) r -= 1;
//		cout << l << " " << r << '\n';
		bool tag = 0;
		int ans_l = 0 , ans_r = 0 , len = 0;
		for(int i = l ; i <= r ; i ++) {
			if(now[i]) {
				if(!tag) continue;
				ans_r = (i - 1) % n;
				info.insert({ans_l , ans_r , len});
				len = 0;tag = 0;
				continue;
			}
			if(!tag) {
				ans_l = i % n;
				tag = 1;
				len += 1;
			} else {
				len += 1;
			}
		}
		
//		for(int i = 0 ; i < n ; i ++) cout << vis[i] << " " ; cout << "\n";
		
		for(auto [l , r , len] : info) {
//			cout << l << " " << r << " " << len << "\n";
			int typel = vis[pre(l)];
			int typer = vis[nex(r)];
			if(m >= (len + 1) / 2) {
				for(int i = 1 , j = l , k = r; i <= (len + 1) / 2 ; i ++ , j = nex(j) , k = pre(k)) {
					vis[j] = typel;
					vis[k] = typer;
				}
			} else {
				int j = l , k = r;
				for(int i = 1 ; i <= m ; i ++ , j = nex(j) , k = pre(k)) {
					vis[j] = typel;
					vis[k] = typer;
				}
				if(m & 1) for(int i = j ; i != nex(k) ; i = nex(i)) if(s[i] == 'W') vis[i] = 1 ; else vis[i] = -1;
				else for(int i = j ; i != nex(k) ; i = nex(i)) if(s[i] == 'W') vis[i] = -1 ; else vis[i] = 1;
			}
		}
		for(int i = 0 ; i < n ; i ++ ){
			if(vis[i] == 1) cout << 'B';
			else if(vis[i] == -1) cout << 'W';
		}
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

/*
5 1
WBBWB
*/
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
103
104
105
106
107
108
109
110
111

G. Running in Pairs (贪心 + 构造)

思路：对于一个 n ， 我们不难发现其下界的 max 数组是

$$[n,n-1,...,2,1]$$

即

$$\frac{(n+1)\ast n}{2}$$

其上界的 max 数组是

$$[n,n,n-1,n-1,...,(n+1)/2]$$

即

$$(n/2)\ast (n+1+(n+1)/2)+(n+1)/2\ast (n\&1)$$

而且显然上下界之间的数字都是能构造出来的

以 n = 5 举例

上界：[5 , 5 , 4 , 4 , 3] 21

下界：[5 , 4 , 3 , 2 , 1] 15

这样给出一个 k 值 ， 我们对上下界区间 和 k 值进行分类讨论

1 : k 小于 下界 ： 无解

2 : k 大于上界 ： 取上界

3 : k 在上下界之间 ， 我们可以根据其与上下界之间的差值构造出 max 数组 ， 接下来的任务就是把 max 数组分成两个排列 。

如何把max数组分成两个排列呢 ， 这里我们要用到贪心的思想。

首先把 max 数组中重复出现的元素放到第二个数组中 ， 然后对于剩下的元素 ， 我们用排列中未出现的元素进行填充 ， 如何填充呢 ， 考虑贪心的从大往小填充 ， 因为 max 数组中大的也在前面 ， 填充完第一个数组填充第二个数组即可。

例：n = 5 k = 20

max 数组 ： [5 , 5 , 4 , 4 , 2]

分离：

数组 1 ： [5 , 0 , 4 , 0 , 2]

数组 2 ： [0 , 5 , 0 , 4 , 0]

填充：

数组 1 ： [5 , 3 , 4 , 1 , 2]

数组 2 ： [3 , 5 , 2 , 4 , 1]

这样贪心的填充是一定不会影响原来的 max 数组的值的。

$$时间复杂度O(n)$$

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int n , k;

int pre[N] , nex[N] , cnt[N] , ans[N];
bool vis[N];

signed main(){

	cin >> n >> k;
	
	int l = (n + 1) * n / 2;
	int r = (n / 2) * (n + 1 + (n + 1) / 2) + (n + 1) / 2 * (n & 1);

//	cout << l << " " << r << "\n";

	if(k < l) {
		cout << "-1\n";
	} else if(k > r) {
		cout << r << "\n";
		for(int i = 1 ; i <= n ; i ++) cout << i << " ";cout << "\n";
		for(int i = n ; i >= 1 ; i --) cout << i << " ";cout << "\n";
	} else {
		cout << k << "\n";
		for(int i = 1 ; i <= n ; i ++) pre[i] = (n - i + 1);
		for(int i = 1 , j = n ; i <= n ; i ++) {
			nex[i] = j;
			if(!(i & 1)) j -= 1;
		}
		int res = k - l;
		for(int i = 1 ; i <= n ; i ++) {
			int now = nex[i] - pre[i];
			if(now <= res) {
				res -= now;
				pre[i] += now;
			} else {
				pre[i] += res;
				break;
			}
		}
		for(int i = 1 ; i <= n ; i ++) {
			if(vis[pre[i]]) {
				ans[i] = pre[i];
				pre[i] = 0;
			} else {
				vis[pre[i]] = 1;
			}
		}
		for(int i = 1 , j = n ; i <= n ; i ++) {
			while(vis[j]) j -= 1;
			if(pre[i]) continue;
			vis[j] = 1;
			pre[i] = j;
		}
		for(int i = 1 ; i <= n ; i ++) vis[i] = 0;
		for(int i = 1 ; i <= n ; i ++) vis[ans[i]] = 1;
		for(int i = 1 , j = n ; i <= n ; i ++) {
			while(vis[j]) j -= 1;
			if(ans[i]) continue;
			vis[j] = 1;
			ans[i] = j;
		}
		for(int i = 1 ; i <= n ; i ++) cout << ans[i] << " ";cout << "\n";
		for(int i = 1 ; i <= n ; i ++) cout << pre[i] << " ";cout << "\n";
	}
	

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

/*
5 5 4 4 3
5 4 3 2 1
加不会溢出 ， 减会溢出
*/
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