Codeforces Round #700（div2 A~D2 ) 补题_b1. painting the array i

链接

https://codeforces.com/contest/1480

A. Yet Another String Game

（rating:800)
题意：
A，B两人轮流操作一个字符串（英文字母） ， 每次可以选择一个未操作过的字符 ， 将它变成任何字母 。 A希望把这个字符串的字典序尽可能变小 ， B希望尽可能变大 。 他们都按最优策略操作 ， 问最后字符串长什么样子 。

思路：
显然 ， 越靠前的字符对字典序大小的贡献越大 。 为了不给对手机会 ，两人必定是从头开始依次选取字符 。 再特判下边界（a和z）即可。

B. The Great Hero

（rating:900)
题意：
一个英雄要打怪兽 。
英雄和怪兽都有生命值和攻击力 。 每一次战斗都会根据对方的攻击力扣血 。 问英雄能否战胜所有怪兽 （最后一场英雄死了也算胜利） 。

思路：
因为最后一场英雄死了也算胜利 ，而且对于每一个怪兽 ， 英雄要杀死它所需的回合数是一定 ， 或者换句话说 ， 英雄杀死他所要付出的代价是一定的，不受战斗的先后影响 。 所以我们应该把攻击力高的英雄尽可能放在后面 ，然后按顺序模拟即可 。

C. Searching Local Minimum（交互+二分）

(rating:1700)

题意：
给定一个1 到 n 的重排 ，要求在100次询问之内得到一个极小值点。
（即 a[i]<a[i-1]&&a[i]<a[i+1]) ，每次询问得到当前询问的位置的值 ，第0项和第n+1项默认无穷大。
（ 其中n<=1*10⁵ 。 ）

思路：
二分 ， 每次询问取mid和mid+1的值 ， 来判断当前位置是递增还是递减 。 若a_mid > a_mid+1 , 则mid 后面必有极小值点 ； 反正，mid前面必有极小值点 。

代码：

    #include<bits/stdc++.h>
    using namespace std;
    int get(int x){
    	cout<<"? "<<x<<endl;
    	cout.flush();
    	int ans = 0;
    	cin>>ans;
    	return ans;
    }
    int main(){
    	int n;
    	cin>>n;
    	int left = 1,right = n;
    	while(left<right){
    		int mid = (left+right) / 2;
    		int nxt = get(mid) ; int to = get(mid+1);
    		if(nxt<to)
    		right = mid;
    		else
    		left = mid+1;
    	}
    	cout<<"! "<<right<<endl;
    	cout.flush();
    	
    	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

D1. Painting the Array I （贪心）

（rating：1900）

题意：
把一个序列a 拆分成 两个序列 a⁰ 和 a¹ ，然后把这两个序列的相邻相同元素合并 。
例如： a = [1,2,3,4,5,6] 可拆分成 a⁰ = [1 3 5 6] , a¹ = [2 4] 。
例如：a⁰ = [1,1,2,2,2,3,3,3,1] , 合并后为 a⁰ = [1,2,3,1] ,长度为4 ，记为seg(a⁰ )= 4; .
要求找到一种拆分方法 ， 使得 seg(a⁰) +seg(a¹) 最大 。

思路：
将a中元素依次放入a⁰ 或 a¹ 中 。 设当前a⁰ 的最后一个元素的值是x ， a¹ 的是y 。
那么要让seg和最大，我们就尽量让相邻相同的值错开 ：
如果a[i] = x , 那就把a[i]放到 y 中 。
如果a[i] = y,那就把a[i]放到x 中。
如果a[i] !=x && a[i]!=y , 那就判断a[i+1] , 如果a[i+1] = x , 那我们就把a[i]放进x ， 从而把 x 与 a[i+1]错开 。 a[i+1] = y同理 。 因为只有两个序列a⁰ 和 a¹ ， 在讨论最大值时观察到i+1 项即可 。

代码：

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    int a[maxn];
    int main(){
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    	}
    	int x = -1,y = -1;
    	int ans = 0;
    	for(int i=1;i<=n;i++){
    		if(a[i]!=x&&a[i]!=y){
    			if(a[i+1]==x)
    			x = a[i];
    			else if(a[i+1]==y)
    			y = a[i];
    			else
    			x = a[i];
    			ans++;
    		}
    		else if(a[i]==x&&a[i]==y){
    			x = a[i];
    		}
    		else if(a[i]==x&&a[i]!=y){
    			y = a[i];
    			ans++;
    		}
    		else if(a[i]!=x&&a[i]==y){
    			x = a[i];
    			ans++;
    		}
    	}
    	cout<<ans<<endl;
    } 
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

D2. Painting the Array I（贪心）

（rating :2100)
题意：
与D1完全相同 ， 但是将最大和 改为最小和 。
思路：
方向同样是贪心 。
1.如果当前元素等于某个队列的尾元素 ， 那就将它放进该队列 ，使之可以合并。
2.当1不满足时，如果当前元素的下一个元素等于某个队列的尾元素 ， 那就将当前元素放进另一个队列 ， 使得下一个元素加入该队列时可以合并 。
3.如果1，2都不满足呢 ， 那我们就暂时找不到可以合并的策略 ， 这个时候应该从长远考虑 ：
如果当前a⁰的队尾x距离下一个x 比较近 ， 那我们就将当前元素扔给a¹ ，反之同理 。
那么这样，我们就得预处理一个to[i]，来表示元素a[i]之后的与之最近且相等的值的位置 。

代码：
（这次补题时写得比较冗杂 ， 其实可以不分 x==y 与 x!=y 的情况的）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
vector<int> v[maxn];
int to[maxn];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		v[a[i]].push_back(i);
	}
	memset(to,1e9+7,sizeof(to));
	for(int i=1;i<=n;i++){
		for(int j=0;j<(int)v[i].size()-1;j++){
			to[v[i][j]] = v[i][j+1];
		}
	}
	int now = -1,next = -1;
	int x = -1,y = -1;
	int nex_x = 1e9+7,nex_y = 1e9+7;
	int ans = 0;
	for(int i=1;i<=n;i++){
		now = a[i];next = a[i+1];
		if(x==y){
			if(x==now){
				nex_x = to[i];
			} 
			else{
				if(x==next&&y!=next) y = now,nex_y = to[i] , ans++;
				else if(y==next&&x!=next) x = now,nex_x = to[i] , ans++;
				if(nex_x<nex_y)
				y = now,nex_y = to[i], ans++;
				else
				x = now,nex_x = to[i], ans++;
			}
		}
		else if(x!=y){
			if(x==now) {nex_x = to[i] ; continue;}
			else if(y==now) {nex_y = to[i] ; continue;}
			else if(x==next&&y!=next) y = now,nex_y = to[i] , ans++;
			else if(y==next&&x!=next) x = now,nex_x = to[i] , ans++;
			else{
				if(nex_x<nex_y)
				y = now,nex_y = to[i] , ans++;
				else
				x = now,nex_x = to[i] , ans++;
			}
		}
	}
	cout<<ans<<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