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，该怎么办呢？
- 如果 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+1i，一个等差数列和。最后把 p 2 p2 p2右移，然后令 p 1 = p 2 p1=p2 p1=p2（原来的区间已经统计完毕，可以彻底抛弃掉了）
- 如果 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!!!