Dashboard - Educational Codeforces Round 157 (Rated for Div. 2) - Codeforces

C. Smilo and Monsters

题意

有n头怪物，每个怪物有各自的血量。每次操作可以

  1. 对一个怪物造成一点伤害，并令连击值x加一。

  2. 消耗所有的连击值x，选择一个生命值大于等于x的怪物，对他造成x点伤害，然后连击值降为0。

问最少多少操作能够杀死所有的怪物？

思路

方案一、模拟

由于我们连击值越高，效益越大。所以先对怪物的血量由低到高排序，然后在血量较低的怪物身上使用普攻，然后当连击值和当前血量最高的怪物相等时，使用绝招杀死怪物。因此我们需要用l，r两个变量来记录当前普攻杀到了哪个怪物，以及大招该杀哪个怪物。

需要特判的是：可能普攻杀死一个最小的怪物时，连击值已经超过了最大血量怪物需要的连击值。这时候需要回退一些普攻操作。例如当前连击值为4，然后用6次普攻杀死了一个血量为6的小怪，但是另一只大怪的血量只有6，我们应该对小怪只造成2点普攻伤害，然后直接杀死大怪。（反例为 4 6 6 6 6）

还有就是杀死所有的小怪后，连击值不足以杀死大怪，这时候我们应该对大怪进行一些普攻，等连击值和大怪剩余血量相等时，直接使用大招杀死。

方案二、二分答案

代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
void solve(){
	int n;
	cin>>n;
	vector<int > vec(n+5);//血量数组
	int sum = 0;
	for(int i = 1;i<=n;i++){
		scanf("%lld",&vec[i]);
		sum += vec[i];
	}
	sort(vec.begin()+1,vec.begin()+1+n);
	int x = 0;
	int ans = 0;
	for(int l = 1,r = n;l<=r;){//l，r双指针
		if(x + sum >= 2 * vec[r]){//如果杀死小怪能够获得足够的连击值
			while(x < vec[r]){//杀死小怪,直到够杀死大怪
				x += vec[l];
				ans += vec[l];
				sum -= vec[l];
				l++;
			}
			if(x != vec[r]) {//如果普攻砍多了
				l--;
				vec[l] = x - vec[r];
				ans -= vec[l];
				sum += vec[l];
			}
			x = 0;
			ans++;
			sum -= vec[r];
			r--;
		}
		else {
			while(l<r){//不够的话，先普攻杀死其他所有的小怪
				x += vec[l];
				ans += vec[l];
				l ++;
			}
			int t = (vec[r] + x) / 2;//找到斩杀线
			ans += vec[r] - t;
			if(t != 0) ans++; 
			break;
		}
	}
	cout<<ans<<endl;
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

D. XOR Construction

给出n-1个数 $a1,a_2,…,a{n-1}$ ，你需要构造出一个排列b。使得$b1 \oplus b_2 = a_1 , b_2 \oplus b_3 = a_2,…,b{n-1} \oplus bn = a{n-1}$ 。

可以发现，只要我们知道了b1，就可以递推出$b_2,b_3,…,b_n$:

$b_2 = b_1 \oplus a_1\ b_3= b_2 \oplus a_2 = b_1 \oplus a_1 \oplus a_2 \…$

我们设$F(x)$ 代表a的前x项的异或和。 那么$b_i =b_1 \oplus F(i-1)$。

我们最终以此方法构造的b数组可能会不映射到0~n-1上，但一定可以保证b中的每个数都不同。因此我们需要判断是否存在$b_i\ge n$ ，如果存在，那么这个b数组就不成立。
如果我们遍历$b_1$为0~n-1， 对于每个$b_1$ 产生的b数组进行判断，那么时间复杂度就会变为$O(n * n)$ ，导致超时。

我们可以考虑使用字典树存储a的各个前缀和，然后通过遍历字典树来在$log2n$的复杂度下找到最大的$b_i$ ,并进行合理性判断。这样我们的时间复杂度就降到了$O(nlog2n)$

代码

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
#include<bits/stdc++.h>
using namespace std;
int nex[400005][2];//注意如果只开2e5+5的数组容量,会产生段错误
int cnt = 0;
int n;
void ins(int x){//向字典树中插入一个数
	int p = 0;
	for(int i = 20;i>=0;i--){
		int t = (x >> i) & 1;
		if(!nex[p][t]){
			nex[p][t] = ++cnt;
		}
		p = nex[p][t];
	}
	return ;
}
bool func(int x){//查找最大的b元素，并判断是否小于等于n-1
	int ans = 0;
	int p = 0;
	for(int i = 20;i>=0;i--){
		int t = (x >> i) & 1;
		if(nex[p][t ^ 1]){
			ans += (1 << i);
			p = nex[p][t ^ 1];
		}else p = nex[p][t];
	}
	return ans < n;
}
int main(){
	cin>>n;
	vector<int> vec(n+5);
	for(int i =1;i<n;i++){//求前缀异或，以及插入进字典树中
		cin>>vec[i];
		vec[i] ^= vec[i-1];
		ins(vec[i]);
	}
	for(int i = 0;i<n;i++){//遍历b1
		if(func(i)) {//如果成立
			for(int j = 0;j<n;j++){//输出b数组
				cout<<(vec[j] ^ i)<<" ";
			}
			break;
		}
	}

	return 0;
}