Codeforces Round #700 (Div. 2) (A ~ D2)_codeforces round 700 (div. 1)

A (贪心）

思路：
字符串的每一位将会从左到右依次被选择，否则，被跳过的字符将会被对手选择并向对手有利的方向修改。所以从左到右依次修改即可。

AC代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;

#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; 

//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);

int n, m, k;

int main()
{
	int T;
	cin >> T;
	while (T --)
	{
		string s;
		cin >> s;
		
		for (int i = 0; s[i]; i ++)
		{
			if (i & 1)
			{
				if (s[i] < 'z') s[i] = 'z';
				else s[i] = 'z' - 1;
			}
			else
			{
				if (s[i] > 'a') s[i] = 'a';
				else s[i] = 'b';
			}
		}
		
		cout << s << endl;
	}
	
	return 0;
}
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

---

B (枚举)

思路：
1：击杀所有怪物所需血量小于英雄血量时，直接输出 “YES”
2：否则，假如能成功，必定是与最后一个怪物同时死亡，所以只需枚举最后一个怪物并判断英雄是否在死亡之时将怪物击杀即可。

---

注意：由于范围都是1e9，最好全开 long long。

AC代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;

#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; 

//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);

int n, m, k;
LL a[N], b[N], c[N];

int main()
{	
	int T;
	cin >> T;
	while (T --)
	{
		LL A, B;
		cin >> A >> B >> n;
		for (int i = 1; i <= n; i ++)
			cin >> a[i];
		for (int i = 1; i <= n; i ++)
			cin >> b[i];
		for (int i = 1; i <= n; i ++)
		{
			c[i] = a[i] * ((b[i] + A - 1) / A);
			B -= c[i];
		}
		
		bool flag = true;
		if (B <= 0)
		{
			flag = false;
			for (int i = 1; i <= n; i ++)
			{
				B += c[i];
				
				if (B > 0)
				{
					LL kill = A * ((B + a[i] - 1) / a[i]);
					if (kill >= b[i])
					{
						flag = true;
						break;
					}
				}
				
				B -= c[i];
			}
		}
		
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}
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

---

C (二分）

思路：
首先判断 a[1] 和 a[n] 是不是局部最小值，假如是则输出。
否则：a[1] 到 a[2] 呈下降趋势，a[n] 到 a[n - 1] 呈下降趋势，则 2 ~ n-1中必定存在拐点，即局部最小值。

---

这时候发现一个性质:
当一个区间 [l, r]左右皆呈向中间下降的趋势的时候，区间一定存在局部最小值。

---

不难想到在该区间中（不包含端点）任取一点 pos，该点要么是局部最小值，否则它一定存在一个相邻点比它小，假设 a[pos - 1] < a[pos]，那么 [l, pos] 便可作为一个新的区间，便可缩小区间范围，至于这个 pos 怎么取很明显可以二分。

---

注意特判 n = 1 的情况

---

之前代码有点问题，把区间端点写错了，代码被新添的数据抬走了，现在代码改正了，可以AC了

AC代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;

#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; 

//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);

int n, m, k;
int a[N]; 

int query(int pos)
{
	cout << "? " << pos << endl;
	int x;
	cin >> x;
	fflush(stdout);
	return x;
}

void print(int pos)
{
	cout << "! " << pos << endl;
	fflush(stdout);
	exit(0);
}

int main()
{
	cin >> n;
	if (n == 1) print(1);
	
	a[1] = query(1);
	a[2] = query(2);
	a[n] = query(n);
	a[n - 1] = query(n - 1);
	
	bool flag = false;
	
	if (a[1] < a[2])
	{
		print(1);
	}
	
	if (a[n] < a[n - 1])
	{
		print(n);
	}
	
	int l = 1, r = n;
	while (l < r)
	{
		int mid = l + r >> 1;
		
		int left = query(mid - 1);
		int right = query(mid + 1);
		int now = query(mid);
		
		if (left > now && right > now) print(mid);
		
		else if (left < now) r = mid;
		else l = mid;
	}
	
	print(l);
	
	return 0;
}

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

---

D1 (贪心）

题意：
将序列从左到右依次加入到两个集合中的一个，使得最后的结果最小。

---

思路：
遍历序列，将数字依次存入队列，再未遇到相邻两数相同的情况下先按兵不动，依据此后情况再做操作有利无害。

---

当第一次出现相邻两数相同时，此时两集合为空。
此时 a[pos] == a[pos - 1] 并且 pos - 1 之前无相邻两数相同。
这时最优操作可为： 将 [1, pos - 1] 放入某一集合，将 pos 单独放入另一集合，即将 pos 与 pos - 1 分开放置，使得贡献为区间长度。如若不分开放置，则当前贡献减一，使得之后贡献最多加一，所以选择前者。

---

设当前两集合的末尾元素是 x。
当遍历到 a[i], 此时队列为空，但是 a[i] == x 时，只能将 a[i] 放入任意集合，贡献为0，末尾元素依然为 x。

---

当再次遇到相邻两数相同时，思考此时能进行的操作：
设此时队列对应的原区间为 [l, r] a[r] == a[r - 1]。

1. a[r] == x.
   1.假如队列中存在相邻两数都不等于 x， 设 a[pos] != x && a[pos + 1] != x 那么可以将 [l, pos] 放在某一集合(a[l] 一定不等于 x)，将[pos + 1, r - 2] 放置在某一集合，再将[r - 1, r]分开放置到两集合中,贡献为区间长度，集合末尾依然为 x。
   2.假若不存在相邻两数都不等于x，无论怎么放置，贡献最高都为区间长度减一，并且集合末尾依然为 x。
2. a[r] != x.
   此时将 [l, r - 1] 放置在某一集合，r 单独放置于某一集合即可，贡献为区间长度，集合末尾为 a[r]。

在第一种情况中，需要记录队列中是否存在相邻两数都不等于 x，为了方便，不妨设集合刚开始为空时末尾元素都为 0。

---

重复操作，直到遍历完序列为止，此时队列剩余的元素也能算进贡献。

想着挺麻烦，但是代码挺短的
AC代码如下:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;

#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; 

//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);

int n, m, k;
int a[N];

int q[N], hh = 0, tt = -1;

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
		scanf("%d", &a[i]);
		
	int b = 0, res = 0; //b为当前集合末尾元素
	bool add = true;
	for (int i = 1; i <= n; i ++)
	{
		if (hh > tt && a[i] == b) continue;
		
		q[++ tt] = a[i];
		
		if (hh < tt && q[tt] != b && q[tt - 1] != b) add = true;
		if (hh < tt && q[tt] == q[tt - 1])
		{
			res += tt - hh + add;
			b = q[tt];
			tt = -1;
			add = false;
		}
	}
	res += tt - hh + 1;
	
	cout << res << endl;
	
	return 0;
}
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

D2(贪心)

该题也是贪心，所需的一些证明方法与上题类似

---

思路:
从左到右遍历数组，当前无法合并时先按兵不动。
能合并的3种情况:

1. a[i] == q[tt]，此时直接将该元素与队尾元素合并为最优，该操作可使得队列出现相同元素时两元素不会相邻。
2. a[i] 等于某一集合末尾元素，此时最优操作为想办法将该元素与该集合末尾元素合并。
3. 队列中出现相同元素时，最优操作为将这两元素想办法合并。

---

该题的贪心证明，合并方法，以及合并后的状况就留给读者思考，这里不再过多叙述。

AC代码如下:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;

#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; 

//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);

int n, m, k;
int a[N], q[N], hh = 0, tt = -1;
bool st[N];

void clean()
{
	while (hh <= tt) st[q[tt --]] = false;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	
	int tail1 = 0, tail2 = 0;
	int res = 0;
	for (int i = 1; i <= n; i ++)
	{
		if ((a[i] == tail1 || a[i] == tail2))
		{
			if (hh > tt) continue;
			
			tail1 = (tail1 == a[i] ? a[i] : q[tt]);
			tail2 = (tail2 == a[i] ? a[i] : q[tt]);
			
			res += tt - hh + 1;
			
			clean();
			
			continue;
		}
		if (hh <= tt && q[tt] == a[i]) continue;
		
		if (st[a[i]])
		{
			tail1 = a[i], tail2 = q[tt];
			res += tt - hh + 1;
			clean();
		}
		else
		{
			q[++ tt] = a[i];
			st[a[i]] = true;
		}
	}
	res += tt - hh + 1;
	
	cout << res << endl;
	
	return 0;
}
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