Dashboard - Codeforces Round 1073 (Div. 2) - Codeforces

A

模拟一下即可

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

int t, n;
typedef pair<int, int> PII;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> t;
	while (t--)
	{
		cin >> n;
		vector<PII> v(n);
		for (int i = 0; i < n; i++)
		{
			cin >> v[i].first;
			v[i].second = i % 2 == 0 ? 1 : 0;
		}
		sort(v.begin(), v.end());
		bool f = true;
		for (int i = 1; i < n; i++)
			if (v[i].second == v[i - 1].second)
			{
				f = false;
				break;
			}
		if (f)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	
	return 0;
}

B

如果 M = 0（也就是数组里没有 0）：无论怎么重排，任意非空前缀/后缀都不含 0，所以它们的 MEX 都是 0，必然会出现相等 ⇒ NO

如果 M = 1（有 0，但没有 1）：

  • 任意一段的 MEX 只可能是 0（没 0） 或 1（有 0）
  • 要让每个切分点前后 MEX 都不同，必须保证每个切分点两边不可能“同时有 0”
  • 这只有在 0 的出现次数恰好为 1 时成立（0 只在一边） ⇒ cnt0==1 YES，否则 NO

如果 M ≥ 2：一定能 YES

  • 构造：把所有 0 放到最前面，其余随便放后面
  • 设 c = cnt0
    • 当切分点 i < c：前缀只有 0（没有 1），所以 mex(prefix)=1；后缀含 0 且含所有 1..M-1，所以 mex(suffix)=M，不同
    • 当切分点 i ≥ c：后缀没有 0，所以 mex(suffix)=0；前缀至少有 0，因此 mex(prefix)≥1，不同
  • 所以对所有切分点都满足 ⇒ YES
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
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;

int n, t;

//int f(vector<int> v, int n)
//{
//	v.push_back(-1);
//	sort(v.begin(), v.end());
//	int i = 1;
//	while (i < n + 1 && v[i] - v[i - 1] <= 1)
//		i++;
//	return v[i - 1] + 1;
//}

int f(vector<int> a, int n) {
	sort(a.begin(), a.end());
	int x = 0;
	for (int v : a) {
		if (v == x) x++;
		else if (v > x) break;
	}
	return x;
}

int g(vector<int> v, int n)
{
	int cnt = 0;
	for (int i = 0; i < n; i++)
		if (v[i] == 0)
			cnt++;
	return cnt;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> t;
	while (t--)
	{
		cin >> n;
		vector<int> v(n);
		for (int i = 0; i < n; i++)
			cin >> v[i];
		int mex = f(v, n);
		int cnt0 = g(v, n);
//		cout << '*' << mex << endl;
		if (mex == 0)
		{
			cout << "NO" << endl;			
		}
		else if (mex == 1)
		{
			if (cnt0 == 1)
				cout << "YES" << endl;
			else
				cout << "NO" << endl;
		}
		else
		{
			cout << "YES" << endl;
		}
	}
	return 0;
}

C

对于每一组测试数据：

  1. 检查是否已有序：

    遍历字符串，看是否已有序，有序输出 Bob。

  2. 构造必杀技：

    如果无序，输出 Alice。接下来需要输出 Alice 的那一步操作。

    原字符串s，有序字符串t，对于s[i]!=t[i]，则i为需要移动的位置

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

int t;

void solve()
{
	
	int n;
	string s, t;
	cin >> n;
	cin >> s;
	
	t = s;
	sort(t.begin(), t.end());
	
	if (s == t)
	{
		cout << "Bob" << endl;
		return;
	}
//	cout << '*' << endl;
	vector<int> v;
	for (int i = 0; i < s.size(); i++)
		if (s[i] != t[i])
			v.push_back(i + 1);
	
	cout << "Alice" << endl;
	cout << v.size() << endl;
	for (auto &i : v)
		cout << i << ' ';
	cout << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> t;
	while (t--)
		solve();
	
	return 0;
}

D

1. 核心逻辑：什么是“更优 (Better)”？

根据题目定义，字符串 tt 比 ss 更优，意味着存在一个位置 ii，使得：

  • tt 和 ss 在 ii 之前的所有字符都相同。
  • 但是在位置 ii：s[i]=’)’s[i] = \text{')'}，而 t[i]=’(’t[i] = \text{'('}。
    • 注：在字典序中 ( 小于 )，所以此时 tt 的字典序更小。

结论：我们要做的就是枚举这个位置 ii，试图把原字符串 ss 中某个位置的 ) 变成 (。

2. 如何把位置 ii 的 ) 变成 (？

假设我们在 ss 的下标 ii 处遇到了一个 )。为了让子序列 tt 在这里变成 (，我们需要从 ss 的后面“借”一个 ( 过来。

  • 贪心策略：为了删掉的字符最少（即保留的长度最长），我们应该找离 ii 最近的下一个 (。
  • 假设这个最近的 ( 在位置 jj（代码中记为 nx[i]）。
  • 代价：因为 jj 是 ii 之后第一个出现的 (，说明 ii 和 jj 之间（包括 ii 本身，但不包括 jj）全都是 )。
    • 要把 jj 处的 ( 挪到 ii 的位置用，意味着我们要删除下标从 ii 到 j−1j-1 的所有字符（这些全是 )）。
    • 删除的右括号数量 = j−ij - i。

3. 维持 RBS 的平衡 (Balance)

仅仅把 ) 删掉换成 ( 是不够的，因为这会破坏括号序列的平衡。

  • 原状态：ss 是平衡的（左括号总数 = 右括号总数）。
  • 操作后：我们在 i…j−1i \dots j-1 这个区间删除了 k=j−ik = j - i 个右括号 )。
  • 后果：现在的序列中，右括号少了 kk 个，或者说左括号相对多出了 kk 个。序列不再平衡，无法闭合。
  • 补救措施：为了让总平衡归零，我们必须在后面（即位置 jj 之后）再删除 kk 个左括号 (。

判定条件：只要 jj 后面剩下的左括号数量足够多（≥k\ge k 个），这个方案就是合法的。

注：只要总数量够扣，删掉左括号是不会导致中间过程出现“右括号比左括号多”的非法情况的（因为删除左括号只会让前缀和变小，而我们是在后缀删，不会影响前面的合法性）。

4. 计算公式

如果我们选定位置 ii 进行操作，且最近的左括号在 jj：

  • 删除的 ) 数量 = j−ij - i
  • 必须删除的 ( 数量 = j−ij - i
  • 总共删除的字符数 = 2×(j−i)2 \times (j - i)
  • 最终子序列长度 = n−2×(j−i)n - 2 \times (j - i)

代码逻辑实现

为了实现上述逻辑，代码分为“预处理”和“枚举计算”两部分。

A. 预处理 (Preprocessing)

为了让检查过程在 O(1)O(1) 时间内完成，代码构建了两个辅助数组：

  1. nx 数组 (Next Open Bracket):
    • nx[i] 表示从下标 ii 开始（包含 ii），右边第一个 ( 的位置。
    • 如果 s[i]s[i] 本身是 (，则 nx[i] = i。
    • 如果 s[i]s[i] 是 )，则 nx[i] = nx[i+1]（继承后面的结果）。
    • 目的：快速找到上文提到的 jj。
  2. suf 数组 (Suffix Sum of Open Brackets):
    • suf[i] 表示从下标 ii 到字符串末尾，一共有多少个 (。
    • 目的：快速判断 jj 后面是否有足够的 ( 供我们删除以维持平衡。
1
2
3
4
5
6
7
8
// 代码对应部分
for(int i = n - 1; i >= 0; i--){
    if(s[i] == '(') nx[i] = i;      // 找到左括号，记录位置
    else nx[i] = nx[i + 1];         // 是右括号，问后面要位置
    
    if(s[i] == '(') suf[i] += 1;    // 统计后缀左括号数量
    suf[i] += suf[i + 1];
}

B. 枚举与计算 (Main Loop)

遍历每一个位置 ii，尝试把它作为“变好”的切入点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 代码对应部分
int ans = -1;
for(int i = 0; i < n; i++){
    // 只有当前是 ')' 且后面还有 '(' 时，才有可能通过替换变得"Better"
    if(s[i] == ')' and nx[i] <= n){ 
        
        int ig = nx[i] - i; // ig (ignore) 就是上文的 k = j - i
                            // 即需要删除的右括号数量
        
        // 核心检查：
        // nx[i] 是借用的那个 '(' 的位置 (即 j)。
        // 我们需要在 j 后面再删掉 ig 个 '('。
        // 所以检查：j 后面的左括号总数 (suf[nx[i] + 1]) 是否 >= ig
        if(suf[nx[i] + 1] >= ig){
            ans = max(ans, n - 2 * ig);
        }
    }
}