Problem - C - Codeforces

CF2200C Specialty String - 洛谷

题目描述

AksLolCoding 正在玩一个关于字符串 ss 的游戏，字符串长度为 nn。初始时，ss 只包含小写拉丁字母。

每一回合，AksLolCoding 可以选择一对整数 (i,j)(i, j)，满足：

  • 1≤i<j≤n1 \leq i < j \leq n；
  • si=sj≠∗s_i = s_j \neq *；
  • 对于所有 i<k<ji < k < j，有 sk=∗s_k = *。

如果不存在这样的 i,ji,j，则游戏结束。否则，AksLolCoding 令 si:=∗s_i := * 且 sj:=∗s_j := *。当游戏结束后，只有当 ss 的每一个字符都等于 ∗* 时，AksLolCoding 才获胜。请判断是否存在一种操作方式，使得 AksLolCoding 能够获胜。

注意：∗* 表示 ASCII 字符 42。

输入格式

第一行为一个整数 tt（1≤t≤1001 \leq t \leq 100），表示测试用例的数量。

每个测试用例的第一行为一个整数 nn（1≤n≤50001 \leq n \leq 5000），表示字符串的长度。

每个测试用例的第二行为一个仅由小写拉丁字母组成的字符串 ss。

所有测试用例中 nn 的总和不超过 50005000。

输出格式

对于每个测试用例，输出一行答案。如果 AksLolCoding 能够获胜，输出 “YES”（不带引号）；否则，输出 “NO”。

输出不区分大小写。例如，“yEs”、“yes”、“Yes” 和 “YES” 都被认为是正面回答。

题意解读

给定一个字符串，选择一对下标(i, j)满足：

  • 1≤i<j≤n1 \leq i < j \leq n；
  • si=sj≠∗s_i = s_j \neq *；
  • 对于所有 i<k<ji < k < j，有 sk=∗s_k = *。

（特别注意第三个条件，当时理解成了将所有i<k<ji < k < j中sks_k 改成∗*导致第一次提交直接wa了）

如果存在这样的下标对，则令si:=∗s_i := * 且 sj:=∗s_j := *，否则游戏结束。所有字符都是∗*时候获胜。

解题思路

可以联想到栈的括号匹配。如果栈顶与之匹配，就弹出栈顶，否则压入栈中,最后检查栈是否为空。

题解代码

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;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

bool check(int n, string s){
	stack<char> st;
	for (int i = 0; i < n; i++){
		if (!st.empty() && st.top() == s[i])
			st.pop();
		else
			st.push(s[i]);
	}
	if (st.size() > 0) return false;
	return true;
}

void sol(){
	int n; cin >> n;
	string s; cin >> s;
	if (check(n, s)) cout << "yes" << endl;
	else cout << "no" << endl;
}

int main(){
	IO
	int t; cin >> t;
	while (t--)
		sol();
	return 0;
}

CF2200D Portal

Problem - D - Codeforces

CF2200D Portal - 洛谷

题目描述

给你一个长度为 nn 的排列 pp。在位置 xx 和 yy（x<yx < y）各有一个传送门。

位置 ii 的传送门最初位于数组第 ii 个和第 (i+1)(i+1) 个元素之间。特别地，如果 i=0i=0，传送门位于第一个元素之前；如果 i=ni=n，传送门位于最后一个元素之后。

你可以无限次执行以下两种操作中的一种：

  1. 将某个传送门左侧紧邻的元素移除，并将其插入到另一个传送门右侧紧邻处。
  2. 将某个传送门右侧紧邻的元素移除，并将其插入到另一个传送门左侧紧邻处。

令 O\mathbf{\color{red}{\mathcal{O}}} 表示传送门。例如，若 p=[3,O,2,4,O,1]p = [3,\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}},1]：

  • 分别在左、右传送门使用操作 1，得到数组 [O,2,4,O,3,1][\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}},3,1] 和 [3,O,4,2,O,1][3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1]。
  • 分别在左、右传送门使用操作 2，得到数组 [3,O,4,2,O,1][3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1] 和 [3,1,O,2,4,O][3,1,\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}}]。

请找出你能够通过这些操作得到的排列中字典序最小的一个。注意，传送门在字典序比较中没有影响。

∗^{\text{∗}} 长度为 nn 的排列是一个长度为 nn 的数组，包含 11 到 nn 的每个整数各一次。

†^{\text{†}} 如果存在下标 ii 使得对于所有 1≤j<i1 \leq j < i 都有 aj=bja_j = b_j，且 ai<bia_i < b_i，则排列 aa 字典序小于排列 bb。

输入格式

第一行包含一个整数 tt（1≤t≤2⋅1041 \leq t \leq 2\cdot 10^4），表示测试用例个数。

每个测试用例的第一行包含三个整数 nn、xx、yy（1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^5，0≤x<y≤n0 \leq x < y \leq n）。

每个测试用例的第二行包含 nn 个整数 p1,p2,…,pnp_1, p_2, \dots, p_n，表示一个长度为 nn 的排列。

所有测试用例中的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例，输出一行 nn 个整数，表示你可以得到的字典序最小的排列。

题意解读

给定一个长度为n的排列，在中间放两个传送门，有以下两种操作：

  1. 将某个传送门左侧紧邻的元素移除，并将其插入到另一个传送门右侧紧邻处。
  2. 将某个传送门右侧紧邻的元素移除，并将其插入到另一个传送门左侧紧邻处。

可以无限次操作，找到字典序最小的一组输出。

解题思路

传送门将序列分为3个部分ABC就，观察发现：A不管怎么变都是内部在做循环移位；不管AC怎么变，AC两部分合起来都一样；那么就可以找到这个序列的变化规律，就是将B做循环移位，插在AC合并起来的序列中。

贪心得做，B循环移位直到最小元素X到达序列首位，将B插在AC合并起来后最后一个小于X的元素后面，最后输出这个三个部分组成的序列。

题解代码

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

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

void sol(){
	int n, x, y; cin >> n >> x >> y;
	vector<int> p(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> p[i];
	vector<int> a, k, b;
	//用b数组存构造最小的B
	for (int i = x + 1; i <= y; i++)
		k.push_back(p[i]);
	int t = 0, len = k.size();
	for (int i = 1; i < len; i++)
		if (k[i] < k[t])
			t = i;
	b.resize(len);
	for (int i = 0; i < len; i++)
		b[(i - t + len) % len] = k[i];
	//a数组存AC两部分	
	for (int i = 1; i <= x; i++)
		a.push_back(p[i]);
	for (int i = y + 1; i <= n; i++)
		a.push_back(p[i]);
	//找到插入点,将b插入到a中合并输出
	int r = b[0];
	int i = 0;
	for (;i < (int)a.size(); i++){
		if (a[i] >= r)
			break;
		cout << a[i] << ' ';
	}
	for (auto g : b)
		cout << g << ' ';
	for (; i < (int)a.size(); i++)
		cout << a[i] << ' ';
	cout << endl;
}

int main(){
	IO
	int t; cin >> t;
	while (t--)
		sol();
}

CF2200E Divisive Battle

Problem - E - Codeforces

CF2200E Divisive Battle - 洛谷

题目描述

Alice 和 Bob 正在玩一个数组 aa 上的游戏，初始时 aa 包含 nn 个正整数，Alice 先手。

每次轮到某个玩家时，如果 aa 是非递减的 ∗^{\text{∗}}，游戏立即结束。否则，该玩家可以从数组中选择一个元素 xx，以及正整数 y,zy, z，满足 1<y,z<x1 < y, z < x 且 x=yzx = yz，然后将数组中的 xx 替换为 yy 和 zz（在 xx 的原位置，顺序任意）。如果没有这样的操作可执行，游戏结束。

一旦游戏结束，如果 aa 是非递减的，则 Bob 获胜；否则 Alice 获胜。请判断如果双方都采用最优策略，谁将获胜。

∗^{\text{∗}} 若对于所有 1≤i≤m−11 \leq i \leq m-1 都有 ai≤ai+1a_i \leq a_{i+1}，其中 mm 为 aa 的长度，则称 aa 是非递减的。

输入格式

第一行包含一个整数 tt（1≤t≤1041 \leq t \leq 10^4），表示测试用例组数。

每组数据的第一行包含一个整数 nn（1≤n≤1051 \leq n \leq 10^5）。

每组数据的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n（1≤ai≤1061 \leq a_i \leq 10^6）。

所有测试用例中 nn 之和不超过 10510^5。

输出格式

对于每个测试用例，输出一行。如果 Alice 获胜，输出 “Alice”；如果 Bob 获胜，输出 “Bob”。判题系统区分大小写。

题意解读

Alice 和 Bob 正在玩一个数组 aa 上的游戏，Bob想要序列非递减，Alice不想要。每次轮到某个玩家时，如果 aa 是非递减的 ∗^{\text{∗}}，游戏立即结束。否则，该玩家可以从数组中选择一个元素 xx，以及正整数 y,zy, z，满足 1<y,z<x1 < y, z < x 且 x=yzx = yz，然后将数组中的 xx 替换为 yy 和 zz（在 xx 的原位置，顺序任意）。如果没有这样的操作可执行，游戏结束。两人都进行最优操作。判断谁最终可以获胜。

解题思路

如果序列原本就是升序的，则Bob获胜；如果序列中有元素满足不是质数的幂次方（一定可以分解出至少两种不同的质因子，降序排列就可以使得Alice必胜，可以参考样例3）则Alice必胜；最后将所有可以写成质数的幂次方的数都替换成底数，如果仍然升序则Bob获胜，否则Alice获胜。

如何判断是否是质数的幂次方可以使用分解质因数的方法，如果分解出来的数都是同一个数，则这个数就可以写成质数的幂次方。注意特判本来就是质数和1的情况。

题解代码

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
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

bool cmp(int a, int b){
	return a > b;
}
//判断是否是质数
bool isp(int x){
	if (x < 2) return false;
	if (x == 2) return true;//注意顺序问题
	if (x % 2 == 0) return false;
	for (int i = 3; i * i <= x; i += 2)
		if (x % i == 0)
			return false;
	return true;
}
//判断是否满足质数的幂次方,记录分解出来质因子的哈希表，方便后续找底数
map<int, int> check(int x){
	map<int, int> mp;
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0)
			while (x % i== 0){
				mp[i]++;
				x /= i;
			}
	if (x > 1) mp[x]++;
	return mp;
	
}

void sol(){
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	auto b = a;
	sort(b.begin(), b.end());
    //情况1
	if (a == b){
		cout << "Bob" << endl;
		return;
	}
    //情况2
	else{
		for (int i = 0; i < n; i++){
			if (!isp(a[i]) && a[i] != 1){
				auto t = check(a[i]);
				if (t.size() == 1)
					a[i] = t.begin() -> first;
				else{
					cout << "Alice" << endl;
					return;
				}
			} 
		}
		vector<int> d = a;
		sort(d.begin(), d.end());
        //情况3
		if (a == d){
			cout << "Bob" << endl;
			return;
		}
		else{
			cout << "Alice" << endl;
			return;
		}
	}
}

int main(){
	IO
	int t; cin >> t;
	while (t--)
		sol();
}