1907

#刷题

Codeforces Round 913 (Div. 3) #div3

A Rook

#cf800
比较简单

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

#栈 #cf1000

遇到 b 时，就将最后一个小写字母删除
遇到 B 时，就将最后一个大写字母删除
如果已经没有满足要求的了，则忽略。
给定一个序列，在处理完所有按键后输出键入的字符串。
( $1 \leq t \leq 1000$ ), $\sum_{i = 1}^{t} | a_{i} |$ $10^{6}$ . $a is not null$ .
例如：ARaBbbitBaby->ity

我写的超时了，时间复杂度： $O (n^{2})$

#include <bits/stdc++.h>
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';
    }
}

为了解决这个问题，有必要快速支持删除。为此，可以保持两个堆栈：

一个具有大写字母的位置，
一个具有小写字母的位置。
在删除时，需要以某种方式标记该位置的字符不应该被输出。

//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 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

#cf1100
弗拉德找到了一个由 $n$ 个小写字母组成的字符串 $s$ ，他想让这个字符串越短越好。

只要它们不同，就可以从 $s$ 中任意删除对相邻的字符。
通过任意数量的删除可以得到的最小长度是多少？
( $1 \leq t \leq 10^{4}$ )，( $1 \leq n \leq 2 \cdot 10^{5}$ ) ， $\sum_{i = 1}^{t} ∣ s_{i} ∣\leq 2 \cdot 10^{5}$ .
例如： $aabc \to ac \to ""$ .

考虑一个有限字符串: 只有两种情况

字符串中的所有字符都是相同的，
可以删除某些字符对。
如果某个字符在字符串中出现的次数超过 $⌊ \frac{n}{2} ⌋$ ，那么最终的字符串将始终只包含这个字符，
否则，无论删除顺序如何，我们都可以删除所有可能的字符对。

//表述为：
 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)

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

#cf1400 #二分
求一个最小的移动距离 $k$ 使得能满足每次移动后都能在目标的 $[l, r]$ 区间内。
$example 1 \begin{aligned} 5 \\ 1 & 5 \\ 3 & 4 \\ 5 & 6 \\ 8 & 10 \\ 0 & 1 \end{aligned} \to min (k) is 8 - 1 = 7.$

example 2 \begin{aligned} 3 \\ 3 & 8 \\ 10 & 18 \\ 6 & 11 \end{aligned} min (k) is \frac{10}{2} = 5

$example 2$ 玩家可以采取以下行动：

从点 $0$ 移动到点 $5$ （ $3 \leq 5 \leq 8$ ）;
从点 $5$ 移动到点 $10$ （ $10 \leq 10 \leq 18$ ）;
从点 $10$ 移动到点 $7$ （ $6 \leq 7 \leq 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 函数的作用很重要，但是如何证明其正确性还是我的一个问题。

二分搜索： $我仍然没有想出来$
Pasted image 20231213195628.png
将二维的 vector<vector<int>> 变为 vector<array<int, 2>> 节省了不少空间

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

#cf1600
给出 $n$ , 找出满足 $a + b + c = n \cap f (a) + f (b) + f (c) = f (n)$ 的个数。 $f (x)$ 代表 $x$ 各位数字之和。

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, a n s (n) = \prod a n s (n 的各位数字)$

int x=n%10,ans *= (x + 1) * (x + 2) / 2,n/=10;

#include <bits/stdc++.h>
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';
    }
}

F Shift and Reverse

#cf1800
给定一个整数数组 $a_{1} ， a_{2} ， \dots ， a_{n}$ 。你可以用这个数组进行两种类型的操作：

shift：将数组的最后一个元素移到第一个位置，并将所有其他元素向右移动，因此您将获得数组 $a_{n} ， a_{1} ， a_{2} ， \dots ， a_{n - 1}$ 。
Reverse：反转整个数组，所以你得到数组 $a_{n} ， a_{n - 1} ， \dots ， 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)。
所以我们就得到了从各个位置开始，可以使得整个数组非降序的最小操作次数。再各种情况中取最小值，就是答案。

//core：
when down:
ans = min({ans,st + 1, n - st + 1});
when up:
ans = min({ans, st + 2, n - st});

#include <bits/stdc++.h>
using namespace std;
int t, n;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        vector<int> a(2 * n, 0);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        copy(a.begin(), a.begin() + n, a.begin() + n);
        if (is_sorted(a.begin(), a.begin() + n))// spj
        {
            cout << '0' << '\n';
            continue;
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; i++) // down
        {
            int st = i, cnt = 1;
            while (i <= 2 * n - 1 && a[i] >= a[i + 1])
                i++, cnt++;
            if (cnt >= n)
                ans = min(ans,min(st + 1, n - st + 1));
        }
        for (int i = 0; i < n; i++) // up
        {
            int st = i, cnt = 1;
            while (i <= 2 * n - 1 && a[i] <= a[i + 1])
                i++, cnt++;
            if (cnt >= n)
                ans = min(ans, min(st + 2, n - st));//(if(!st)ans=0;)<->(spj)
        }
        if (ans == INT_MAX)
            cout << "-1" << '\n';
        else
            cout << ans << '\n';
    }
}

G Lights

#cf2200
浅谈基环树（环套树） (基环树： $n$ 点 $n$ 边的连通图) 基环树
 抽象为不懂的部分
输入的第一行包含一个整数 $t$ （ $1 \leq t \leq 10^{4}$ ）-测试用例的数量。
对于每个测试用例

第一行包含整数 $n$ （ $2 \leq n \leq 10^{5}$ ）-灯的数量。
第二行包含 $n$ 个字符的字符串，灯的初始状态。字符“0”表示相应的灯关闭，“1”表示灯打开。
第三行包含 $n$ 个整数 $a_{i}$ （ $1 \leq a_{i} \leq 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}$
则： $k=3$ ,开关顺序为 $1, 5, 3$ .

当选择 1 时，字符串变为 $01111$
当选择 5 时，字符串变为 $00110$
当选择 3 时，字符串变为 $00000$

官方题解：
让我们构建一个有向图，其中一条边从顶点 $i$ 到顶点 $a_{i}$ 。在这样的图中，每个顶点正好有一条边，每个相连的部分正好有一个循环。

首先，我们将关闭所有不属于循环的灯光；这种关闭顺序是唯一的：我们将移除所有没有边进入的已关闭顶点，然后关闭并移除已打开的顶点。

之后，只剩下循环的组成部分，其中一些可能还亮着灯。考虑从 $i$ 到 $a_{i}$ 循环中的任何一条边，我们要么按下开关 $i$ ，要么不按。为了计算这些情况下的操作次数，我们将使用与之前相同的算法。

jiangly 的代码

#include <bits/stdc++.h>
using namespace std;
int n, _;
string s;
void solve()
{ // jiangly的代码
    cin >> n >> s;
    vector<int> a(n), deg(n),ans;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i]--, deg[a[i]]++;
    }
    //topsort
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (!deg[i])
            q.push(i);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();

        if (s[x] == '1')
        {
            s[x] = '0';
            s[a[x]] ^= 1;
            ans.push_back(x);
        }
        if (--deg[a[x]] == 0)
            q.push(a[x]);
    }
    //end topsort
    //core
    for (int i = 0; i < n; i++)
    {
        if (!deg[i])
            continue;
        int j = i, t = 0, len = 0, res = 0;
        while (deg[j])
        {
            if (s[j] == '1')
                t ^= 1;
            res += t;
            deg[j] = 0;
            j = a[j];
            len += 1;
        }
        if (t == 1)
        {
            cout << -1 << "\n";
            return;
        }
        for (int k = 0; k < len; k++)
        {
            if (s[j] == '1')
                t ^= 1;
            if (t == (res < len - res))
                ans.push_back(j);
            j = a[j];
        }
    }
    //end core
    cout << ans.size() << "\n";
    for (auto x : ans)
        cout << x + 1 << " ";
    cout << '\n';
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> _;
    while (_--)
        solve();
}

官方的代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<bool> s(n);
    {
        string ss;
        cin >> ss;
        for (int i = 0; i < n; i++)
            s[i] = ss[i] - '0';
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i], a[i]--;

    vector<int> res;
    vector<int> d(n);
    for (int i = 0; i < n; i++)
        d[a[i]]++;
    vector<int> z;
    for (int i = 0; i < n; i++)
        if (d[i] == 0)
            z.push_back(i);

    for (int i = 0; i < z.size(); i++)
    {
        int x = z[i];
        int y = a[x];
        if (s[x])
        {
            res.push_back(x);
            s[x] = !s[x];
            s[y] = !s[y];
        }
        d[y]--;
        if (d[y] == 0)
            z.push_back(y);
    }

    vector<bool> u(n);
    for (int i = 0; i < n; i++)
    {
        if (s[i] && !u[i])
        {
            int x = i;
            vector<int> p;
            vector<bool> ps;
            int c = 0;
            while (!u[x])
            {
                p.push_back(x);
                ps.push_back(s[x]);
                c += s[x];
                u[x] = true;
                x = a[x];
            }
            int k = p.size();
            p.push_back(x);
            ps.push_back(s[x]);
            if (c % 2 == 1)
            {
                cout << -1 << '\n';
                return;
            }
            vector<int> v1;
            vector<bool> ps1 = ps;
            for (int j = 0; j < k; j++)
            {
                if (j == 0 || ps1[j])
                {
                    v1.push_back(p[j]);
                    ps1[j] = !ps1[j];
                    ps1[j + 1] = !ps1[j + 1];
                }
            }
            vector<int> v2;
            vector<bool> ps2 = ps;
            for (int j = 0; j < k; j++)
            {
                if (j != 0 && ps2[j])
                {
                    v2.push_back(p[j]);
                    ps2[j] = !ps2[j];
                    ps2[j + 1] = !ps2[j + 1];
                }
            }
            if (v1.size() < v2.size())
                for (auto x : v1)
                    res.push_back(x);
            else
                for (auto x : v2)
                    res.push_back(x);
        }
    }
    cout << res.size() << "\n";
    for (auto x : res)
        cout << x + 1 << " ";
    cout << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
}

疑惑

我到拓扑排序都是理解的，现在我把这个题目抽象一下，抽象为只有我不懂的部分。

抽象后的题目

Description

现给你一个图，这个图只含有环(数量不唯一)，每个点都有它自己的状态 ${0, 1}$ ，每次选定一个点之后，同时这个点绑定的点的状态也会随着改变。题目保证有解。

INput

输入第一行包含一个整数，代表点的个数。
输入第二行包含一个字符串，代表这个点的状态
输入第三行包含一个数组，代表改变这个点的状态后同时会被改变状态的节点，即绑定的节点。

Output

第一行输出使得每个节点的状态都变为 0 时，选定节点数目的最小值。
第二行输出方案情况

Sample INput

3
011
2 3 1

Sample Output

1
2

Notes

由于 2 节点绑定的是 3 节点，所以只需要选择 2 节点就可以使每个节点的状态都为 0 。