AtCoder Beginner Contest 296-526互联

295? 上周ECF玩去了，咕咕咕

A - Alternately (abc296 a)

题目大意

给定一个包含\(MF\)的字符串，问是否是 \(M,F\)交替出现的。

解题思路

判断相邻字母是否相等即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    auto check = [&](){
        for(int i = 0; i < n - 1; ++ i)
            if (s[i] == s[i + 1])
                return false;
        return true;
    };
    if (check())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}

B - Chessboard (abc296 b)

题目大意

给定一个仅包含一个*，其余都是.的二维\(8 \times 8\)的矩阵，要求输出该*的位置。从左到右依次编号 a,b,c,d,e,f,g,h，从下到上依次编号1,2,3,4,5,6,7,8

解题思路

按题意模拟即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int x, y;
    for(int i = 0; i < 8; ++ i){
        string s;
        cin >> s;
        int pos = s.find('*');
        if (pos != string::npos){
            x = 8 - i;
            y = 'a' + pos;
        }
    }
    cout << char(y) << x << '\n';

    return 0;
}

C - Gap Existence (abc296 c)

题目大意

给定一个数组\(A\)，问是否存在两个数，其差为 \(x\)。这两个数可以相等。

解题思路

特判\(x=0\)的情况，剩下的把所有数存到 \(set\)里，对于当前一个数 \(a\)，看看是否存在 \(a+x\)或 \(a-x\)即可。

实现是反过来的。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, x;
    cin >> n >> x;
    auto check = [&](){
        set<int> qwq;
        for(int i = 0; i < n; ++ i){
            int a;
            cin >> a;
            if (qwq.find(a) != qwq.end() || qwq.find(a) != qwq.end())
                return true;
            qwq.insert(a - x);
            qwq.insert(a + x);
        }
        return x == 0;
    };
    if (check())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}

D - M<=ab (abc296 d)

题目大意

给定\(n,m\)，问是否存在\(a,b \leq n\)，且 \(a \times b \geq m\)，输出最小的 \(a \times b\)

解题思路

从小到大\(a\)，则满足题意的最小的 \(b= \lceil \frac{m}{a} \rceil\)，容易发现会有多个\(a\)，其 \(b= \lceil \frac{m}{a} \rceil\)是相同的，而显然我们只考虑这一块中最小的\(a\)即可，然后再考虑下一块\(a\)，这一块的\(a\)会使得 \(B = b + 1\)，同样取最小的 \(a\)，依次考虑。

实际上就是对\(\lceil \frac{m}{a} \rceil\)进行数论分块，时间复杂度是\(O(\sqrt{m})\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL maxx = 1e18;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    LL n, m;
    cin >> n >> m;
    LL ans = maxx;
    LL l = 1, r;       
    while (l <= m) {
        r = m / (m / l);  
        LL ano = (m + l - 1) / l;
        if (l <= n && ano <= n)
            ans = min(ans, l * ano);
        l = r + 1;  
    }
    if (ans == maxx)
        ans = -1;
    cout << ans << '\n';

    return 0;
}

E - Transition Game (abc296 e)

题目大意

给定一个长度为\(n\)的数组 \(A\)，值域 \(1 \sim n\)。

对于 \(i = 1,2,\cdots, n\)，高桥和青木依次玩一个游戏：

青木先写一个数 \(k \in [1, n]\)。
高桥根据这个 \(k\)，再写一个数 \(x \in [1,n]\)。
令 \(x = A_x\)，执行\(k\)遍后，如果变成 \(i\)，则高桥获胜，否则青木获胜。

问高桥获胜的游戏数。

解题思路

首先建个图，有向边\(x \to A_x\)。变换操作就是在这样图上游走 \(k\)次，最后停在\(i\)号点就算胜利。

根据定义这是一个基环内向森林，即从任意点出发最后一定会走到一个环里。

容易发现如果\(i\)在一个环里的话是必赢的，高桥肯定可以选择环上的一个点走 \(k\)次到达 \(i\)。

而如果不在环上，则必寄了，因为青木只要写个 \(n\)，最后一定会走到环上的。事实上只要 \(k\)大过 \(i\)号点之前的点（反向图中可到达的点）的数量就寄了。

因此答案就是在环上的点的数量。

对该图跑一遍拓扑排序即可得到答案。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> edge(n);
    vector<int> du(n, 0);
    for(int i = 0; i < n; ++ i){
        int a;
        cin >> a;
        -- a;
        edge[i].push_back(a);
        du[a] ++;
    }
    queue<int> team;
    for(int i = 0; i < n; ++ i){
        if (du[i] == 0)
            team.push(i);
    }
    int ans = n;
    while(!team.empty()){
        int u = team.front();
        team.pop();
        -- ans;
        for(auto v : edge[u]){
            du[v] --;
            if (du[v] == 0)
                team.push(v);
        }
    }
    cout << ans << '\n';

    return 0;
}

F - Simultaneous Swap (abc296 f)

题目大意

给定两个数组\(A,B\)，每次交换选择 \(i,j,k\)，交换 \(A_i,A_j\)， \(B_i,B_k\)。

问最后两个数组能否相等。

解题思路

首先两个数组的各个数字的数量一定要相等。

然后假设可以交换到相等，然后我们令\(j=k\)，这样就可以将两者交换成递增的顺序，方便之后考虑。（就是说可以先对数组 \(A\)排个序，数组\(B\)跟随变动，不会影响到可不可行）

此时考虑数组\(A\)递增的情况下怎么操作，将数组\(B\)也变得递增，且数组 \(A\)不动。

一个朴素的思想就是能否找到一个元操作，即经过这个操作，数组\(A\)不变，且数组\(B\)跟像数组 \(A\)了。

考虑从左到右第一个 \(A_{i_1} \neq B_{i_1}\)的位置，考虑\(j_1,k_1\)取什么值。很显然\(k_1\)要满足\(B_{k_1} = A_{i_1}\)，这样经过这次交换，数组 \(B\)就能更像数组 \(A\)了。但由于\(A_{i_1}\)和 \(A_{j_1}\)交换了，下一个操作我们得换回来，但不该过多影响到\(B\)。

下一个操作，我们令\(i_2 = j_1\)，即上一个操作中的 \(j_1\)，而 \(j_2 = i_1\)，此时会交换 \(A_{j_1}\)和 \(A_{i_1}\) ，即又交换回来了。而这个操作我们会交换\(B_{i_2}\)和 \(B_{k_2}\)，即\(B_{j_1}\)和 \(B_{k_2}\)，如果说 \(B_{j_1} = B_{k_2}\)，那么经过这次操作不会影响到数组\(B\)，此时 \(j_1\)和 \(k_2\)的值也确定了。

我们就找到了一个元操作，经过这个操作，数组\(A\)不变，且数组\(B\)多了一个位置和数组 \(A\)相同，然后我们依次进行元操作，就能变成一样了。前提是存在两个相等的数。

即如果有出现了两次及以上的数，则必可以。

那就剩下各个数都仅出现一次的情况，我们找不到满足 \(B_{j_1}=B_{k_2}\)的情况，那就只能经过这次操作，使得数组\(B\)进一步更像数组\(A\)，即选择 \(j_1 = x\)， \(B_{k_2} = A_{j_1}\)，其中\(x\)是下一个 \(A_x \neq B_x\)的位置。即经过这次操作，还原了数组 \(A\)的影响，且数组 \(B\)又有一位和数组 \(A\)相同了。

即另一个元操作，数组 \(A\)不变，数组 \(B\)多了两个位置和数组\(A\)相同。但由于交换了两次，数组\(B\)的逆序数的奇偶性是不改变的，由于数组\(A\)是递增的，其逆序数为\(0\)。因此只有数组 \(B\) 的逆序数也为偶数时，才可以交换到和数组\(A\)一样的，否则不可以。

综上，

两个数组各个数字的数量不同，则No
存在一个数字出现大于\(1\)次，则 Yes
两个数组的逆序数奇偶性相同，则Yes，不同则No

统计逆序数就用归并或者树状数组就可以了。

最后一个情况是手玩以下例子发现的

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

template <typename T>
class fenwick {
    public:
    vector<T> fenw;
    int n;
    LL tot;

    fenwick(int _n) : n(_n) {
        fenw.resize(n);
        tot = 0;
    }

    void modify(int x, T v) {
        while (x < n) {
            fenw[x] += v;
            x |= (x + 1);
        }
        tot += v;
    }

    T get(int x) {
        T v{};
        while (x >= 0) {
            v += fenw[x];
            x = (x & (x + 1)) - 1;
        }
        return v;
    }
};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    map<int, int> cnt;
    map<int, int> acnt;
    vector<int> A(n), B(n);
    for(int i = 0; i < n; ++ i){
        int a;
        cin >> a;
        cnt[a] ++;
        acnt[a] ++;
        A[i] = a;
    }
    for(int i = 0; i < n; ++ i){
        int b;
        cin >> b;
        cnt[b] --;
        B[i] = b;
    }
    auto nixu = [&](){
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int a, int b){
                return A[a] < A[b];
        });
        fenwick<LL> cc(n + 1);
        LL ans = 0;
        for(auto &i : id){
            ans += cc.tot - cc.get(B[i]);
            cc.modify(B[i], 1);
        }
        return ans;
    };
    auto check = [&](){
        for(auto &i : cnt)
            if (i.second != 0)
                return false;
        for(auto &i : acnt)
            if (i.second > 1)
                return true;
        return nixu() % 2 == 0;
    };
    if (check())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}