Educational Codeforces Round 110 (Div. 2) 个人题解

Educational Codeforces Round 110 (Div. 2) 个人题解

C题过得确实有点惊险哈,快1:57才过,只剩三四分钟了……

A. Fair Playoff

题意

给a,b,c,d四个人的能力值,然后a,b较量,c,d较量,赢的人再进入决赛。问决赛的两人是不是能力值最大的,是就公平,不是就不公平
分析

嘛,怎么写都可以吧
给一份相对复杂的代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
 
signed main()
{
	IOS;
	int  t;
	cin >> t;
	while(t--)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int p[4] = {a, b, c, d};
		sort(p, p + 4, greater<int>());
		if(a < b) swap(a, b);
		if(c < d) swap(c, d);
		if(a < c) swap(a, c);
		if(a == p[0] && c == p[1]) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

B. Array Reodering

题意

给定一个数组,现在要你重排这个数组,使得有最多的数对,满足:
1 ≤ i < j ≤ n , g c d ( a i , 2 a j ) > 1 1≤i<j≤n, gcd(a_i,2a_j)>1 1≤i<j≤n,gcd(ai​,2aj​)>1
分析

贪心。由于数据只有2000,凹了一个 O ( n 2 ) O(n^2) O(n2)的贪心QWQ。先不看条件 1 ≤ i < j ≤ n 1≤i<j≤n 1≤i<j≤n,算出每个数和其他所有数最多形成的数对。然后,如果我们加上了条件 1 ≤ i < j ≤ n 1≤i<j≤n 1≤i<j≤n,那么每个数肯定会损失一些数对。贪心的构造是让整个数组损失的数对最小。那么可以猜想,结果是按每个数原本的数对个数降序排序。

粗略证明

(昨天随便想的,但感觉不太严格)

由于把“和其他所有数最多形成的数对”最大的数排在了第一个,故这个最大的数肯定不会有任何损失。进一步地思考,把形成数对大的尽量放前面,其后面的数就越多,前面的数就越少,其原本的数对满足 1 ≤ i < j ≤ n 1≤i<j≤n 1≤i<j≤n的机会就越多,所以损失的数对就会越少。因为形成数对大的数损失的机会是更大的,所以需要把它们放在前面,减少损失机会。

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2005;
int n;
struct node{
	int x, cnt;
	node(){
		x = cnt = 0;
	}
}a[maxn];
bool cmp(node x, node y){
	return x.cnt > y.cnt;
}
signed main()
{
	IOS;
	int  t;
	cin >> t;
	while(t--)
	{
		int ans = 0;
		cin >> n;
		fors(i, 1, n) cin >> a[i].x, a[i].cnt = 0;
		fors(i, 1, n){
			fors(j, 1, n){
				if(i == j) continue;
				if(__gcd(a[i].x, a[j].x * 2) > 1){
					a[i].cnt++;
				}
			}
		}
		sort(a + 1, a + 1 + n, cmp);
		fors(i, 1, n){
			a[i].cnt = 0;
		}
		fors(i, 1, n){
			fors(j, i + 1, n){
				if(__gcd(a[i].x, a[j].x * 2) > 1){
					ans++;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

C. Unstable String

题意

(题意稍微有点难理解)

给一个字符串,其含有’0’,‘1’,’?’. 其中,’?‘可以看成’1’,也可以看成’0’。如果一个字符串可以是0和1交替出现的,就称这个字符串是 b e a u t i f u l beautiful beautiful。问现在这个字符串有多少 b e a u t i f u l beautiful beautiful的子串?

例如,
字符串1,10是beautiful的;
字符串1???1也是beautiful的,因为通过问号可以转化为10101;
但字符串1???1不是beautiful的,因为通过问号不管怎么变,都不可能使得01交替出现。

分析

我的做法是双指针。(开局就想到了,但奈何我的讨论不细致,导致一个多小时以后才终于AC)

设两个指针 p 1 p1 p1, p 2 p2 p2,都从 0 0 0开始,然后 p 2 p2 p2前移,期间检查 p 1 p1 p1到 p 2 p2 p2是否可以组成一个 b e a u t i f u l beautiful beautiful的子串,如果可以就继续前移。

如何判断呢?我的做法是:

首先预处理,对每个连续的问号段,维护这整个问号段前面的那个数字。

为什么这样维护呢? 可以发现,当一个问号段长度是奇数时,如果其左右的数字都相同,那么一定可以把问号替换成数字,使得问号串加上两个数字仍然是 b e a u t i f u l beautiful beautiful的。例如,1???1可以替换成10101。反之,如果两端的数字不同,那么这个问号段就不可能保证加上两端的数字后还能 b e a u t i f u l beautiful beautiful。 对于问号段长度为偶数的情况则恰好相反。特别注意,如果问号段位于整个字符串的最左/最右端,那么它是肯定符合条件的

所以,判断问号后面的数字可不可以接,关键是看这个数字和问号段最前面的数字的关系,预处理出来即可。之后再讨论可否前移就比较清晰了。

例如,对于10011???,对于问号段"???",其 p r e [ i ] = 4 pre[i]=4 pre[i]=4,表示最前面的数字下标为4.


那如果通过判断,发现 p 2 p2 p2左移后不能保证 [ p 1 , p 2 ] [p1,p2] [p1,p2]仍然 b e a u t i f u l beautiful beautiful,该怎么办呢?

  1. 如果 p 2 p2 p2和 p 2 + 1 p2+1 p2+1都不是问号,说明这是两个相等的数字,无论如何它们都不能连在一起了,直接算出 p 1 p1 p1到 p 2 p2 p2的答案加到 a n s ans ans中。 p 1 p1 p1到 p 2 p2 p2的所有子串都是符合条件的,所以答案是 ∑ i = 1 p 2 − p 1 + 1 i \sum_{i=1}^{p2-p1+1}i ∑i=1p2−p1+1​i,一个等差数列和。最后把 p 2 p2 p2右移,然后令 p 1 = p 2 p1=p2 p1=p2(原来的区间已经统计完毕,可以彻底抛弃掉了)
  2. 如果 p 2 p2 p2是问号, p 2 + 1 p2+1 p2+1不是问号,说明 p 2 p2 p2所在的问号段的前面那些已经不可能再接上了。但是,从 p r e [ p 2 ] + 1 pre[p2]+1 pre[p2]+1到 p 2 p2 p2这个问号段不一定不再起作用,但可以肯定的是从 p 1 p1 p1到 p r e [ p 2 ] pre[p2] pre[p2]肯定不需要了,因此统计出 p 1 p1 p1到 p r e [ p 2 ] pre[p2] pre[p2]的等差和。 这个时候不要急着令 p 1 = p r e [ p 2 ] + 1 p1=pre[p2]+1 p1=pre[p2]+1,而要考虑,从 p 1 p1 p1到 p r e [ p 2 ] pre[p2] pre[p2],其和 p r e [ p 2 ] pre[p2] pre[p2]到 p 2 p2 p2仍然可以相连,组成 b e a u t i f u l beautiful beautiful串,记得把这些也统计进来。之后再令 p 1 = p r e [ p 2 + 1 ] p1=pre[p2+1] p1=pre[p2+1]。

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int n;
string s;
int cnt(int len)
{
	return (len + 1) * len / 2LL;
}
int cnt(int l, int r)
{
	return (r - l + 1) * (r - l + 2) / 2LL;
}
int pre[maxn];
signed main()
{
	IOS;
	// 前缀处理:对每个?,找其公共序列的最前面一个非问号
	int  t;
	cin >> t;
	
	while(t--)
	{
		// 0和1肯定不能连续. 对于?,按整个问号序列长度定
		// 双指针
		cin >> s;
		int p1 = 0, p2 = 0;
		for(int i = 0; i < s.size(); ++i){
			pre[i] = -1;
		}
		for(int i = 0; i < s.size(); ++i){
			if(i == 0 && s[i] == '?'){
				pre[i] = -1;
			}
			else if(i > 0 && s[i] == '?' && s[i - 1] == '?'){
				pre[i] = pre[i - 1];
			}
			else if(s[i] == '?'){
				pre[i] = i - 1;
			}
		}
		int ans = 0;
		for(;;){
			if(p2 + 1 >= s.size()){
				if(p2 == s.size() - 1){
					ans += cnt(p2 - p1 + 1);
				}
				break;
			}
			int flag = 1;
			if(s[p2] == '?' && s[p2 + 1] == '?');
			else if(s[p2] == '?' && pre[p2] == -1);
			else if(s[p2] == '?' && s[p2 + 1] != '?'){
				int len = p2 - pre[p2];
				if(len % 2 == 0 && s[p2 + 1] != s[pre[p2]]);
				else if(len % 2 != 0 && s[p2 + 1] == s[pre[p2]]);
				else flag = -1;
			}
			else if(s[p2] != '?' && s[p2] == s[p2 + 1]) flag = 0;
			if(flag == 1) p2++;
			else if(flag == 0){
				ans += cnt(p2 - p1 + 1);
				p2++;
				p1 = p2;
			}
			else{
				ans += cnt(pre[p2] - p1 + 1) + (pre[p2] - p1 + 1) * (p2 - pre[p2]);
				p1 = pre[p2] + 1;
				p2++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Love Sakurai Yamauchi forever!!!

上一篇:Codeforces 1264F - Beautiful Fibonacci Problem(猜结论+找性质)


下一篇:CodeForces300C Beautiful Numbers