ABC293题解ABCDEG

A

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int n = s.size();
    s = ' ' + s;

    for (int i = 1; i <= n / 2; i++) {
        swap(s[i * 2], s[i * 2 - 1]);
    }

    for (int i = 1; i <= n; i++){
        cout << s[i];
    }
    return 0;
}

B

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        if (!b[i]) {
            b[a[i]] = 1;
        } 
    }

    vector<int> c;
    for (int i = 1; i <= n; i++) {
        if (!b[i]) c.push_back(i);
    }

    cout << c.size() << '\n';
    for (auto x : c) {
        cout << x << ' ';
    }
    return 0;
}

C

简单dfs

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int way[2][2] = { 0, 1, 1, 0 };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector e(n + 1, vector<int> (m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> e[i][j];
        }
    }

    int ans = 0;
    set<int> is;
    vector vis(n + 1, vector<int> (m + 1));
    auto dfs = [&](auto self, int x, int y) -> void {
        if (x == n && y == m) {
            ans++;
            return;
        }

        is.insert(e[x][y]);
        vis[x][y] = 1;
        for (int i = 0; i < 2; i++) {
            int dx = x + way[i][0];
            int dy = y + way[i][1];

            if (dx > 0 && dy > 0 && dx <= n && dy <= m && !vis[dx][dy] && !is.count(e[dx][dy])) {
                self(self, dx, dy);
            }
        }
        vis[x][y] = 0;
        is.erase(e[x][y]);
    };

    vis[1][1] = 1;
    is.insert(e[1][1]);
    dfs(dfs, 1, 1);
    
    cout << ans << '\n';
    return 0;
}

D - Tying Rope

观察题意， 发现绳子之间绑起来可以使用并查集模拟， 对于没绑起来的绳子并到一个集合，如果遍历到已经在同一个集合里的两个绳子绑起来，说明两个绳子打结（成圈了），打个标记即可，最后扫一遍统计答案

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (f[x] != x) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    DSU d(n + 1);
    vector<int> is(n + 1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        char l, r;
        cin >> a >> l >> b >> r;

        if (d.same(a, b)) {
            is[d.find(a)] = 1;
        } else {
            d.merge(a, b);
        }
    }

    vector<int> vis(n + 1);
    int c = 0;
    int g = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[d.find(i)]) continue;
        if (is[d.find(i)]) {
            c++;
        } else {
            g++;
        }
        vis[d.find(i)] = 1;
    }

    cout << c << ' ' << g << '\n';
    return 0;
}

E - Geometric Progression

给定整数 AA ， XX 和 MM ，求 ∑i=0X−1Aii=0∑X−1​Ai ，模 MM 。

题解：
可以学到很多东西， 首先用高中等比数列推出了答案是 $(A^q - 1) / (A - 1)$ ,直接使用乘法逆元（费马小定理）交上求一发，wa了13个，以为是精度问题，以前也没写过取模类，就去自己学习并写了一个板子如下：

struct ModInt {
    int x;
    static int mod;                          
    static vector<ModInt> Inv;

    ModInt(long long v = 0) { 
        x = int(v % mod);
        if (x < 0)
            x += mod;
    }
    
    ModInt operator + (const ModInt &other) const {
        int res = x + other.x;
        if (res >= mod)
            res -= mod;
        return ModInt(res);
    }
    
    ModInt operator - (const ModInt &other) const {
        int res = x - other.x;
        if (res < 0)
            res += mod;
        return ModInt(res);
    }
    
    ModInt operator * (const ModInt &other) const {
        return ModInt((long long)x * other.x);
    }
    
    ModInt pow(long long exp) const {
        ModInt res(1), base = *this;
        while(exp) {
            if(exp & 1)
                res = res * base;
            base = base * base;
            exp >>= 1;
        }
        return res;
    }
    
    ModInt inv() const {
        return pow(mod - 2);
    }
    
    ModInt operator / (const ModInt &other) const {
        return *this * other.inv();
    }
    
    static void getinv(int N) {
        Inv.resize(N + 1);
        Inv[1] = ModInt(1);
        for (int i = 2; i <= N; i++) {
            // inv[i] = (mod - mod / i) * inv[mod % i] mod mod
            Inv[i] = ModInt(mod - mod / i) * Inv[mod % i];
        }
    }
};

int ModInt::mod = 1;
vector<ModInt> ModInt::Inv; 
using Mint = ModInt;

之后使用取模类交上去，发现wa的地方一模一样，没招了做不出来。。。
错误原因是： 用乘法逆元直接求没办法保证除数和被除数互质，而逆元需要在互质的情况下才准确（不论是exgcd求还是费马）， 那么我们应该另辟蹊径。

发现 $A^0 + A^1 + … + A^X$ 可以分以下两个情况讨论

• 奇数：

  $$S_n = \sum_{i=1}^{n} A_i \\ \quad = \sum_{i=1}^{\frac{n}{2}} A_i + \sum_{i=1}^{\frac{n}{2}} A_i \\ \quad = \left(\sum_{i=1}^{\frac{n}{2}} A_i\right)\left(A_{\frac{n}{2}+1}\right) \\ \quad = S_{\frac{n}{2}}\left(A_{\frac{n}{2}+1}\right)$$

• 偶数：

  $$S_n = \sum_{i=1}^{n} A_i \\ \quad = \sum_{i=1}^{n-1} A_i + A_n \\ \quad = S_{\frac{n-1}{2}} \left( A_{\frac{n-1}{2}+1} \right) + A_n$$

之后递归求解答案

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b, T mod) {
    T res = 1;
    for (; b; b /= 2, a = a * a % mod) {
        if (b % 2) {
            res = (res * a) % mod;
        }
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 A, X, M;
    cin >> A >> X >> M;

    auto F = [&](i64 x) -> i64 {
        if (x == 0) return 1;
        if (x == 1) return (A + 1) % m;
        if (x & 1) {
            return (F(x - 1) + power<i64>(A, x - 1, M)) % M;
        } else {
            return (1 + power<i64>(A, x / 2, M)) * F(x / 2) % mod;
        }
    };

    cout << F(X - 1) % M << '\n';
    return 0;
}

这样避免了求逆元。

G - Triple Index

给定一个长度为 NN 的正整数序列 (A1,A2,…,AN)(A1​,A2​,…,AN​) ，并查询该序列的 QQ 。

对于每个 q=1,2,…,Qq=1,2,…,Q ， qq \第一个查询将为您提供一个整数对 (lq,rq)(lq​,rq​) ；

输出整数三元组 (i,j,k)(i,j,k) 的个数，如下

• lq≤i<j<k≤rqlq​≤i<j<k≤rq​ ，和

—— Ai=Aj=AkAi​=Aj​=Ak​ 。

• 题解 : 莫队板子， 每次加入或删除一个元素，如果这个元素个数 >= 3了， 那么固定这个元素， 可能的情况是在剩下 (x - 1) 个元素选一个， 后再（x - 2） 个元素再选一个，由于次序升序，再除以二得到贡献， 贴上莫队板子即可

  #include<bits/stdc++.h>
  using namespace std;
  using i64 = long long;
  
  #define int long long 
  struct Query {
      int l, r, id;
  };
  
  signed main() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
  
      int n, q;
      cin >> n >> q;
  
      vector<int> a(n + 1);
      for (int i = 1; i <= n; i++) {
          cin >> a[i];
      }
  
      vector<Query> que(q);
      for (int i = 0; i < q; i++) {
          int l, r;
          cin >> l >> r;
          que[i] = { l, r, i };
      }
  
      int len = sqrt(n);
      ranges::sort(que, [&](const Query& p, const Query& q) {
          int as = (p.l - 1) / len + 1;
          int bs = (q.l - 1) / len + 1;
          if (as != bs) return as < bs;
          else return p.r < q.r;
      });
  
      i64 cur = 0;
      vector<int> cnt(1e6);
      auto add = [&](int pos) -> void {
          cnt[a[pos]]++;
          if (cnt[a[pos]] >= 3) {
              cur += (cnt[a[pos]] - 1) * (cnt[a[pos]] - 2) / 2;
          }
      };
  
      auto del = [&](int pos) -> void {
          if (cnt[a[pos]] >= 3) {
              cur -= (cnt[a[pos]] - 1) * (cnt[a[pos]] - 2) / 2;
          }
          cnt[a[pos]]--;
      };
  
      int nowr = 0, nowl = 1;
  
      vector<int> ans(q);
      for (auto &x : que) {
          auto [l, r, id] = x;
  
          while (nowr < r) {
              nowr++;
              add(nowr);
          }
          while (nowr > r) {
              del(nowr);
              nowr--;
          }
          while (nowl < l) {
              del(nowl);
              nowl++;       
          }
          while (nowl > l) {
              nowl--;
              add(nowl);
          }
  
          ans[id] = cur;
      }
  
      for (int i = 0; i < q; i++) {
          cout << ans[i] << "\n";
      }
      return 0;
  }

F - Zero or One

等待补题