补题计划-CF DIV2.ABC题-2

CF Div2.

写了四个的 Div2 了，知道自己差不多在哪了，继续开始突破，看看一周能不能再突破一百。

现在大约在 \(1200\) 左右。

Codeforces Round 980 (Div. 2)

B 题

本来想的是排序之后一个一个判断是否能不能超过 \(k\)，如果不能则需要比这个多一次才能跳到下一个数组上，没想到连样例都没过。

后来看了看样例解释就懂了，同样是排序，变成递增的，然后一个一个判断能不能这个数后面的每个都去和他一样的话，总和能不能超过所需要的饮料，能的话就需要多一次去判断是否是空的了。

如果不能，那这个不行，就只能用完这个了。

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
#include<bits/stdc++.h>

using namespace std;
const long long maxn = 200010;
long long T;
long long a[maxn];

int main()
{
	cin>>T;
	while(T--){
		long long n,k;cin>>n>>k;
		for(long long i=1;i<=n;i++)	scanf("%d",&a[i]);
		
		sort(a+1,a+n+1);
		
		long long ans = 0;		
		for(long long i=1;i<=n;i++){
			long long len = (n - i + 1);
			// cout<<i<<" "<<a[i]<<" "<<len<<endl;
			if(a[i] * len >= k){
				ans += k;
				break;
			}
			else{
				ans += (a[i] + 1);
				k -= a[i];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

C 题

这道题题目根本没有什么提醒让我从哪里想，题解就感觉很空穴来风，样例解释也没有什么可以往这上面靠的。

题解思路就是用这两个小数组的总和作为值从小到大排序，最后排序的结果就是答案。题解证明：注意，如果在最终的顺序中有两个相邻的数组，左边数组的元素之和大于右边数组的元素之和，那么我们可以交换它们，并且逆序对的数量不会增加。因此，我们可以通过交换相邻的数组，使得每次逆序对的数量不增加，从而将任何最优解转化为我们的解。

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
#include<bits/stdc++.h>

using namespace std;

const int maxn = 100010;
struct nums{
	int a1,a2;
	int sum;
} a[maxn];

bool cmp(nums x,nums y){
	return x.sum < y.sum;
}

int main()
{
	int T;
	cin>>T;
	while(T--){
		int n;cin>>n;
		for(int i=1;i<=n;i++){
			scanf("%d %d",&a[i].a1,&a[i].a2);
			a[i].sum = a[i].a1 + a[i].a2;
		}
		
		sort(a+1,a+n+1,cmp);
		
		for(int i=1;i<=n;i++){
			printf("%d %d ",a[i].a1,a[i].a2);
		}
		cout<<endl;
	}
	return 0;
}

Codeforces Round 979 (Div. 2)

C 题

这个比赛前2题没什么难度，都是 \(800\) 分左右，有点简单了，C 题很显然是构造题，想了想，能想到有第一个或最后一个是 \(1\) 的肯定能赢，但是后面怎么处理，根本想不到。还是只能看题解了。

如果中间的有两个 true 那么一定可以赢，我们可以让 Alice 最后去管理两个 true。首先第一个放在 or 之前。如果 Bob 没有将他的运算符放在两个 true 之间，那么 Alice 将在下一步中将 or 放在两个 true 之间并获胜。

如果没有连续的 true，每当 Alice 将 true 或相邻位置放置时，Bob 都会通过在 true 之后放置 and 来响应，这将使此子句无效为 false。

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
#include<bits/stdc++.h>

using namespace std;

bool x[200010];

int main()
{
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		string s;
		cin>>s;
		memset(x,0,sizeof(x));
		for(int i=0;i<s.length();i++)
			if(s[i] == '1')
				x[i] = 1;
		
		bool win = false;
		if(x[0] || x[n-1]){cout<<"YES"<<endl;continue;}
		for(int i=1;i<n;i++){
			if(x[i] && x[i-1])
				win = true;
		}
		
		if(win) cout << "YES" << endl;
        else cout << "NO" << endl;
	}
	return 0;
}

Codeforces Round 979 (Div. 2)

B 题

这道题挺有意思，我发现最优的方案一定是先选出 \(k\) 个最大的，然后每个减去这 \(k\) 个中最小的一个数。最后将大于 \(0\) 的数再存进去。重复这几个操作。这期间可以用堆来存储数字，这样每次读取只需要 \(O(\log n)\) 读取每个数。这种贪心不太对，在评论区也有许多人用了这种方式，但是都无一例外的 Wa 了。

直到一位老哥的解释让我恍然大悟。他说可以看看这个样例。 

1
2
3
1 
3 2
4 4 3

的确，答案确实和我们想的不太一样。其实最优方案是，每次将最大 \(k\) 个元素取出，减去 \(1\) 后再放回，但是数字要大于 \(10^9\)，很显然 TLE 了。

有个更简单的方法。我们最大限度的让每个客人随机去选汽车。这样最后选不够 \(x\) 辆汽车之后，就会有两种情况；

  1. 所有型号都将具有相同数量的剩余汽车，很显然，这种答案就是 \(\lceil \dfrac{a_1+a_2+\dotsb + a_n}{x} \rceil\)。
  2. 如果还有型号不为 \(0\) 但是个数小于等于 \(x\)，那么答案为 \(\max(a_1+a_2+\dotsb +a_n)\)。

这两种结合一下就行了。

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
#include<bits/stdc++.h>

using namespace std;

int T;

int main()
{
	int T;
	cin>>T;
	while(T--){
		int n,r;
		cin>>n>>r;
		int cnt1 = 0,ans = 0;
		for(int i=1;i<=n;i++){
			int x;cin>>x;
			cnt1 += (x % 2);
			ans += (x/2)*2; 
			r -= (x/2);
		}
		
		if(r >= cnt1)	ans += cnt1;
		else{
			int t = cnt1 - r;
			ans += (cnt1 - t*2);
		}
		
		cout<<ans<<endl;
	}
	return 0;
}