1927(923div3)

A. Make it White

只需要计算两边连续的白色，涂中间的即可。

void solve() {
    int n;
    string a;
    cin >> n >> a;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0;i < a.size();i++) {
        if (a[i] != 'W')break;
        else cnt1++;
    }
    for (int i = a.size() - 1;i >= 0;i--) {
        if (a[i] != 'W')break;
        else cnt2++;
    }
    cout << n - cnt1 - cnt2 << '\n';
}

B. Following the String

波利卡普丢失了由小写拉丁字母组成的长度为 n 的字符串 s ，但他仍然保留着它的痕迹。

字符串 s 的踪迹是一个由 n 个整数组成的数组 a ，其中 ai 是 si=sj 的索引 j （ j<i ）的个数。例如，字符串 abracadabra 的踪迹是数组 [ 0,0,0,1,0,2,0,3,1,1,4 ]。

给定一个字符串的踪迹，从中找出个字符串 s 。字符串 s 应该只由小写字母 a−z 组成。

tmp.first 记录下 某数字 的个数，tmp.second 记录该数组中所有等于 某数字 的下标

对于每个 tmp. second (这时每个下标的字母是不同的)，只需要从 a 开始一直枚举即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<char> s(n);
    vector<pair<int, list<int>>> tmp(n);
    for (int i = 0;i < n;i++) {
        cin >> a[i];
        tmp[a[i]].first++;
        tmp[a[i]].second.push_back(i);
    }
    
    for (auto [x, y] : tmp) {
        char ch = 'a';
        for (auto z : y) {
            s[z] = ch++;
        }
    }
    for (auto x : s)cout << x;
    cout << '\n';
}

C. Choose the Different Ones!

是否能从 a,b 数组中各选 k2 个数字使得刚好能组成 1−k

如果 1−k 中某数字没有，就肯定不可能，如果 1−k 都有，且 a,b 中都至少涉及到了一半的数字，则可以，否则不可能。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    set<int> a, b;
    for (int i = 0;i < n;i++) {
        int x;cin >> x;
        a.insert(x);
    }
    for (int i = 0;i < m;i++) {
        int x;cin >> x;
        b.insert(x);
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1;i <= k;i++) {
        if (a.count(i))cnt1++;
        if (b.count(i))cnt2++;
        if (!a.count(i) && !b.count(i)) {
            cout << "no\n";return;
        }
    }
    if (cnt1 >= k / 2 && cnt2 >= k / 2) {
        cout << "yes\n";
    } else {
        cout << "no\n";
    }
}

D. Find the Different Ones!

对于一个 a 数组，有 q 次询问：

若存在，输出这两个下标，若不存在输出 -1 -1

只需要计算出 ai 右边第一个和 ai 不同的下标即可。

void solve() {
    int n, q;
    cin >> n;
    vector<int> a(n);
    vector<int> left(n), right(n);

    for (int i = 0;i < n;i++) {
        cin >> a[i];
    }
    // left[0] = -1;//a[i]左边第一个和a[i]不同的下标
    // for (int i = 1;i < n;i++) {
    //     if (a[i] == a[i - 1]) {
    //         left[i] = left[i - 1];
    //     } else {
    //         left[i] = i - 1;
    //     }
    // }
    right[n - 1] = -1;
    for (int i = n - 2;i >= 0;i--) {
        if (a[i] == a[i + 1]) {
            right[i] = right[i + 1];
        } else {
            right[i] = i + 1;
        }
    }

    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        if (right[l] != -1 && right[l] <= r) {
            cout << l + 1 << " " << right[l] + 1 << '\n';
        } else {
            cout << "-1 -1\n";
        }
    }
    cout << '\n';
}

E. Klever Permutation

给你两个整数 n 和 k ( k≤n )，其中 k 是偶数。

你的任务是构造一个长度为 n 的 k 级排列。(k-level)

如果在所有长度为 k 的连续线段的总和中（其中正好有 n−k+1 个线段），那么这个排列就叫做 k 级排列。(其中正好有 n−k+1 个），任意两个和相差不超过 1 ，那么这个排列就叫做 k 级排列。

k 级序列，首先构造一个长度为 n−k+1 的数组 s ，其中 si=∑j=ii+k−1pj ，即 i /th 元素等于 pi,pi+1,…,pi+k−1 的和。

有： max(s)−min(s)≤1 .

找出长度为 n 的任意个 k 级排列。

Solution

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int cnt = 0;
    for (int i = 0;i < k;i++) {
        if (i % 2 == 0) {
            for (int j = i;j < n;j += k) {
                a[j] = ++cnt;
            }
        } else {
            for (int j = (n - 1) - (n - 1 - i) % k;j >= 0;j-=k) {
                a[j] = ++cnt;
            }
        }
    }
    for (auto x : a) {
        cout << x << " ";
    }
    cout << '\n';
}

官方题解：

要构建一个排列组合，我们需要观察一个重要的现象： si 不能等于 si+1 （即它们至少相差 1 ）。由于数组 s 只能包含两个不同的值，所以它的形式总是 [x,x+1,x,x+1,…] 或 [x,x−1,x,x−1,…] 。

让我们构建第一种形式的排列。

为了构造这样的排列，我们将遍历从 1 到 k 的所有位置 i ，并在位置 i,i+k,i+2⋅k,… 中填充排列。

void solve() {
    int n, k;cin >> n >> k;
    int l = 1, r = n;
    vector<int> ans(n);
    for (int i = 0;i < k;i++) {
        for (int j = i;j < n;j += k) {
            if (i % 2 == 0) {
                ans[j] = l;l++;
            } else {
                ans[j] = r;r--;
            }
        }
    }
    for (auto i : ans)cout << i << " ";cout << '\n';
}

F. Microcycle

给定一个无向加权图，图中有 n 个顶点和 m 条边。图中每对顶点之间最多有一条边，图中不包含循环（从顶点到自身的边）。该图不一定连通。

如果图中的循环不经过同一个顶点两次，也不包含同一条边两次，那么这个循环就叫做简单循环。

请找出该图中最轻边的权重最小的简单循环。

就是找所有环里面权值最小的，输出权值和这个环的顺序遍历

Solution

判环(并查集/tarjan)，DFS

F_哔哩哔哩_bilibili

如果 u,v 的根是一样的，即在一个联通块内，若含有 u,v 边则判定有环，将这条边去掉后，遍历 u→v 输出即可。

要保证输出的是最小的权值，则需要将输入的图按权值降序处理，后面每次遇到了环，则能保证这时的权值是这个环里最小的。

int fa[200010];
int find(int u) {
    if (fa[u] != u)return fa[u] = find(fa[u]);
    return fa[u];
}
int merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v)return 1;
    fa[u] = v;
    return 0;
}
vector<int> e[200001];

void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;++i)fa[i] = i, e[i].clear();
    vector<tuple<int, int, int>> a(m + 1);
    for (int i = 1;i <= m;i++) {
        int u, v, w;cin >> u >> v >> w;
        a[i] = {u,v,w};
    }
    sort(a.begin() + 1, a.begin() + 1 + m, [](auto x, auto y) {
        return get<2>(x) > get<2>(y);
        });//将 w 降序排列输入
    int mn = 1e9, id = 0;
    for (int i = 1;i <= m;i++) {
        auto [u, v, w] = a[i];
        if (merge(u, v) && w < mn) {//如果有环，且权值更小
            mn = w;id = i;
        }
    }

    cout << mn << ' ';

    for (int i = 1;i <= m;i++) {
        if (i == id)continue;
        auto [u, v, w] = a[i];
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int> ans, vis(n + 1, 0);

    auto dfs = [&](auto self, int u, int tag) {
        vis[u] = 1;
        ans.push_back(u);
        if (u == tag) {
            cout << ans.size() << "\n";
            for (int x : ans)cout << x << " ";
            cout << "\n";
            return;
        }
        for (int v : e[u])
            if (!vis[v])self(self, v, tag);
        ans.pop_back();
    };
    auto [u, v, w] = a[id];
    dfs(dfs, u, v);
}

G. Paint Charges

DP
(待更 …)