需要多加训练 Codeforces Round 913 (Div. 3) #div3
A Rook
比较简单 #cf800 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
using namespace std;
int t;
string a;
int main()
{
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin>>t;
while(t--)
{
cin>>a;
for (int i = 1; i <= 8;i++)
{
if(i==a[1]-48)
continue;
cout << a[0] << i << '\n';
}
for (int i = 'a'; i <= 'h';i++)
{
if(i==a[0])
continue;
cout << (char)i << a[1] << '\n';
}
}
}
B YetnotherrokenKeoard
- 遇到
b时，就将最后一个小写字母删除 #栈 #cf1000 - 遇到
B时，就将最后一个大写字母删除 - 如果已经没有满足要求的了，则忽略。 给定一个序列，在处理完所有按键后输出键入的字符串。 (\(1 \le t \le 1000\)), \(\sum\limits_{i=1}^t|a_{i}|\) \(\leq10^6\). \(\text{a is not null}\). 例如：ARaBbbitBaby->ity
我写的超时了，时间复杂度：\(O(n^2)\)
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
using namespace std;
int t;string a;
int main()
{
ios::sync_with_stdio(0), cin.tie(nullptr);
cin >>t;
while (t--)
{
cin >> a;
vector<char> b;
for (char c : a)
{
if (c == 'b')
{
for (int i = b.size() - 1; i >= 0; i--)
{
if (islower(b[i]))
{
b.erase(b.begin() + i);
break;
}
}
}
else if (c == 'B')
{
for (int i = b.size() - 1; i >= 0; i--)
{
if (isupper(b[i]))
{
b.erase(b.begin() + i);
break;
}
}
}
else
b.push_back(c);
}
for (char c : b)
cout << c;
cout << '\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
32//jiangly的代码
void solve() {
std::string s;
std::cin >> s;
std::vector<int> u, l;
for (int i = 0; i < s.size(); i++) {
if (s[i] == 'B') {
if (!u.empty()) {
u.pop_back();
}
} else if (s[i] == 'b') {
if (!l.empty()) {
l.pop_back();
}
} else if (std::isupper(s[i])) {
u.push_back(i);
} else {
l.push_back(i);
}
}
int i = 0, j = 0;
while (i < u.size() || j < l.size()) {
if (i < u.size() && (j == l.size() || u[i] < l[j])) {
std::cout << s[u[i++]];
} else {
std::cout << s[l[j++]];
}
}
std::cout << "\n";
}
C Removal of Unattractive Pairs
弗拉德找到了一个由 \(n\) 个小写字母组成的字符串 \(s\) ，他想让这个字符串越短越好。 #cf1100
- 只要它们不同，就可以从 \(s\) 中任意删除对相邻的字符。 通过任意数量的删除可以得到的最小长度是多少？ (\(1 \le t \le 10^4\))，(\(1 \le n \le 2 \cdot 10^5\)) ，\(\sum\limits{i=1}^t\mid s_{i}\mid\leq 2\cdot 10^5\)
例如：\(\text{aabc}\to \text{ac}\to \text{""}\).
考虑一个有限字符串: 只有两种情况 - 字符串中的所有字符都是相同的， -
可以删除某些字符对。 如果某个字符在字符串中出现的次数超过 \(\lfloor \frac{n}{2} \rfloor\)
，那么最终的字符串将始终只包含这个字符，
否则，无论删除顺序如何，我们都可以删除所有可能的字符对。 1
2
3
4
5//表述为：
if(2*maxs>size)
cout << 2 * maxs - size << '\n';
else
cout << size % 2 << '\n';ans = max(size % 2, 2 * (*max_element(num.begin(), num.end())) - size)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
string a; int t;
int main()
{
cin >> t;
while (t--)
{
vector<int> num(26,0);
int size;
cin >> size >> a;
for (auto v : a)
num[v - 'a']++;
sort(num.begin(), num.end());
cout << max(size % 2, 2 * (*max_element(num.begin(), num.end())) - size) << '\n';
}
}
D Jumping Through Segments
求一个最小的移动距离 \(k\) 使得能满足每次移动后都能在目标的 \([l, r]\) 区间内。 #cf1400 #二分 \(\text{example 1 }\boxed{\begin{align}&5\\&1 &5\\&3 &4\\&5 &6\\&8 &10\\&0 &1\end{align}}\to \min(k) \text{ is }8-1=7.\)
\(\text{example 2 }\boxed{\begin{align}&3\\&3 &8\\&10 &18\\&6 &11\end{align}}\min(k)\text{ is } \frac{10}{2}=5\)
在 \(\text{example 2}\) 中玩家可以采取以下行动：
- 从点 \(0\) 移动到点 \(5\)（\(3 \le 5 \le 8\)）;
- 从点 \(5\) 移动到点 \(10\)（\(10 \le 10 \le 18\)）;
- 从点 \(10\) 移动到点 \(7\)（\(6 \le 7 \le 11\)）。 请注意，对于最后一步，玩家可以选择不移动，仍然完成关卡。
在 \([1，10^{9}]\)
之间进行二分查找，直到找到最佳的 \(k\).
check 函数： 用于检查在给定长度为 \(k\)
的情况下，是否存在一种方式将所有的线段覆盖。 - 初始化 ll 和
rr 为 0，表示当前覆盖的区间的左右边界为0。 - 对于每个线段
\([a, b]\)： a.
计算当前覆盖的区间的左边界为
max (ll - k, a)，表示在保证覆盖的情况下，尽可能向左移动。
b. 计算当前覆盖的区间的右边界为
min (rr + k, b)，表示在保证覆盖的情况下，尽可能向右移动。
c. 如果当前覆盖的区间的左边界大于右边界，则返回
false，表示无法覆盖所有线段。 -
如果成功遍历了所有线段并且都能够被覆盖，则返回
true，表示存在一种方式将所有线段覆盖在长度为 \(k\) 的情况下。 check
函数的作用很重要，但是如何证明其正确性还是我的一个问题。
二分搜索：\(\text{我仍然没有想出来}\) 
将二维的 vector<vector<int>> 变为
vector<array<int, 2>> 节省了不少空间
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
using namespace std;
bool check(int k, vector<array<int, 2>> &seg)
{
int ll = 0, rr = 0;
for (auto [a,b] : seg)
{
ll = max(ll - k, a),rr = min(rr + k, b);
if (ll > rr) return false;
}
return true;
}
void solve()
{
int n;
cin >> n;
vector<array<int,2>> seg(n);
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
seg[i] = {a, b};
}
int l = -1, r = 1000000000;
while (r - l > 1)
{
int mid = (r + l) / 2;
if (check(mid, seg))
r = mid;
else
l = mid;
}
cout << r << endl;
}
int main()
{
int t;
cin >> t;
while(t--)
solve();
}
E Good Triples
给出 \(n\), 找出满足 \(a+b+c=n \cap f(a)+f(b)+f(c)=f(n)\) 的个数。\(f(x)\) 代表 \(x\) 各位数字之和。 #cf1600
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| ans | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 |
\(n\geq 10,ans(n)=\prod ans(n\text{的各位数字})\)
int x=n%10,ans *= (x + 1) * (x + 2) / 2,n/=10;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
int t, a[] = {1, 3, 6, 10, 15, 21, 28, 36, 45, 55};
int main()
{
cin >> t;
while (t--)
{
long long ans = 1;
int n;
cin >> n;
while (n)
ans *= a[n % 10], n /= 10;//ans *= (x + 1) * (x + 2) / 2,n/=10;//jiangly写的
cout << ans << '\n';
}
}
给定一个整数数组 \(a_1，a_2，\ldots，a_n\)。你可以用这个数组进行两种类型的操作： #cf1800
- shift：将数组的最后一个元素移到第一个位置，并将所有其他元素向右移动，因此您将获得数组 \(a_n，a_1，a_2，\ldots，a_{n-1}\)。
- Reverse：反转整个数组，所以你得到数组 \(a_n，a_{n-1}，\ldots，a_1\)。
你的任务是使用最少的操作数对数组进行非降序排序. 不可能则输出
-1.
让我们把数组写出来两次，然后计算数组增加和减少的部分。这样，我们就能找到能对数组进行排序的所有可能的移动。
>down: 非递增 - 如果从位置 st 开始，数组
a[st] 到 a[st + n - 1]
是非递增的，那么我们只需要将这部分序列移至数组的前部，然后反转整个数组即可。移位的次数就是
st + 1，反转的次数为
1，因为每次移位都会将最后一个元素放到第一个，所以这部分的最小操作次数就是
min(st + 1, n - st + 1)，代表了向左或者向右移位的次数。再反转一次，所以操作次数总合为
st + 1 或是 n - st + 1。 >up: 非递减 -
如果从位置 st 开始，数组 a[st] 到
a[st + n - 1]
是非递减的，我们只需要将这部分序列移至数组的前部即可。移位次数为
st + 1。然而，由于每次移位都会将最后一个元素放到第一个，所以需要再反转一次。这样总的操作次数就为
st + 2。另外一种情况就是，我们仍然可以选择向另一个方向移位，也就是从尾部的
n - st 个元素向后累推，然后反转一次，操作次数就是
n - st + 1。但是考虑到 st
的位置肯定是非降序的，因此可以直接将其移位至队首，然后反转整个数组，操作次数为
n - st。所以这部分的最小操作次数就是
min(st + 2, n - st)。
所以我们就得到了从各个位置开始，可以使得整个数组非降序的最小操作次数。再各种情况中取最小值，就是答案。
1
2
3
4
5//core：
when down:
ans = min({ans,st + 1, n - st + 1});
when up:
ans = min({ans, st + 2, n - st});
1 |
|
G Lights
[[浅谈基环树（环套树）]] (基环树：\(n\) 点 \(n\) 边的连通图) [[../../ACM/图论/基环树]] #cf2200 抽象为不懂的部分 输入的第一行包含一个整数 \(t\)（\(1≤t≤10^4\)）-测试用例的数量。
对于每个测试用例
- 第一行包含整数 \(n\)（\(2 \le n \le 10^5\)）-灯的数量。
- 第二行包含 \(n\) 个字符的字符串，灯的初始状态。字符“0”表示相应的灯关闭，“1”表示灯打开。
- 第三行包含 \(n\) 个整数 \(a_i\)（\(1 \le a_i \le n\)，\(a_i \neq i\)）-开关 \(i\) 改变灯 \(i\) 和灯 \(a_i\) 的状态。
保证所有测试用例的 \(n\) 之和不超过 \(2 \cdot 10^5\) 关闭所有的灯使用最少数量的开关，或者说这是不可能的。 对于每个测试用例
- 输出整数 \(k\)，即要使用的最小开关数，然后在单独的行中输出 \(k\) 开关列表。
- 无法关闭所有的灯，则输出 \(-1\)。
例如 \(n=5\), 字符串为 \(11101\) , \(a[5]=\{4, 3 ,4 ,2, 2\}\)
则： \(\text{k=3}\) ,开关顺序为 \(1,5,3\).
- 当选择 1 时，字符串变为 \(01111\)
- 当选择 5 时，字符串变为 \(00110\)
- 当选择 3 时，字符串变为 \(00000\)
官方题解：
让我们构建一个有向图，其中一条边从顶点 \(i\) 到顶点 \(a_i\) 。在这样的图中，每个顶点正好有一条边，每个相连的部分正好有一个循环。
首先，我们将关闭所有不属于循环的灯光；这种关闭顺序是唯一的：我们将移除所有没有边进入的已关闭顶点，然后关闭并移除已打开的顶点。
之后，只剩下循环的组成部分，其中一些可能还亮着灯。考虑从 \(i\) 到 \(a_i\) 循环中的任何一条边，我们要么按下开关 \(i\) ，要么不按。为了计算这些情况下的操作次数，我们将使用与之前相同的算法。
jiangly 的代码
1 |
|
官方的代码
1 |
|
疑惑
我到拓扑排序都是理解的，现在我把这个题目抽象一下，抽象为只有我不懂的部分。
抽象后的题目
Description
现给你一个图，这个图只含有环 (数量不唯一)，每个点都有它自己的状态 \(\{0,1\}\)，每次选定一个点之后，同时这个点绑定的点的状态也会随着改变。题目保证有解。
INput
输入第一行包含一个整数，代表点的个数。 输入第二行包含一个字符串，代表这个点的状态 输入第三行包含一个数组，代表改变这个点的状态后同时会被改变状态的节点，即绑定的节点。
Output
第一行输出使得每个节点的状态都变为 0
时，选定节点数目的最小值。 第二行输出方案情况
Sample Input
1
2
33
011
2 3 1
Sample Output
1
21
2
Notes
由于 2 节点绑定的是 3 节点，所以只需要选择 2
节点就可以使每个节点的状态都为 0 。
Code
1
/*...*/