1933(div3)

A. Turtle Puzzle: Rearrange and Negate

给你一个由 $n$ 个整数组成的数组 $a$ 。您必须对数组执行以下两个操作（先执行第一个操作，再执行第二个操作）：

你可以选择重新排列一下数组，且可以选择一个区间将区间内所有元素变号

在进行这两次操作（第一次，然后第二次）后，数组元素的最大和**是多少？

显然可以全部为正。

void solve() {
    int n;cin >> n;vector<int> a(n + 1);for (int i = 1;i <= n;i++)cin >> a[i];
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        ans += abs(a[i]);
    }
    cout << ans << '\n';
}

B. Turtle Math: Fast Three Task

给你一个数组 $a_{1}, a_{2}, \dots, a_{n}$ 。

在一次移动中，你可以执行以下两种操作中的任何一种。您可以执行任意次数的移动：

从数组中选择一个元素并将其从数组中移除。这样数组的长度会减少 $1$ ；
从数组中选择一个元素并将其数值增加 $1$ 。

如果当前数组为空，则不能再移动。

你的任务是找出使数组中的元素之和 $a$ 能被 $3$ 整除所需的最少**次移动。你可能需要走 $0$ 步。

注意空数组（长度为 $0$ 的数组）的元素之和等于 $0$ 。

我分类讨论的很乱，逻辑不够清晰，所以写了很久。

只对余数为 1 的数字来说，答案最多不超过 1
只对余数为 2 的数字来说，答案最多不超过 2

写的💩

void solve() {
    int n;cin >> n;vector<int> a(n + 1);vector<int> m(3, 0); for (int i = 1;i <= n;i++) { cin >> a[i]; m[a[i] % 3]++; }
    int ans = 0;
    if (m[1] == m[2]) {
        cout << 0 << '\n';return;
    }
    if (!m[1] && m[2]) {
        ans = m[2] % 3;
        cout << ans << '\n';
        return;
    }
    if (!m[2] && m[1]) {
        ans = min(m[1] % 3, (3 - m[1] % 3));cout << ans << '\n';return;
    }
    if (m[1] < m[2]) {
        m[2] %= 3;
        if (m[2] == 0){
            ans = min(m[1] % 3, (3 - m[1] % 3));
        } else if (m[2] == 1) {
            m[1]--;
            ans = min(m[1] % 3, (3 - m[1] % 3));
        } else {
            if (m[1] == 1) {
                cout << "1\n";return;
            } else {
                m[1] -= 2;
                ans = min(m[1] % 3, (3 - m[1] % 3));
            }
        }
    } else {
        int o = (m[1] - m[2]) % 3;
        ans = min(o % 3, (3 - o % 3));
    }
    cout << ans << '\n';
}

设总和为 sum

若 sum%3==0 则输出 0，

若 sum%3==2 则输出 1 (让某个数加 1 即可)，

若 sum%3==1，若存在一个 $a_{i}$ 使得 $a_{i} (\mod 3) = 1$ ,则将该元素删掉即可输出 1，否则只能输出 2

思路很简单，想的太复杂了。

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        sum += a[i];
    }
    
    if (sum % 3 == 0) {
        std::cout << 0 << "\n";
        return;
    }
    
    if (sum % 3 == 2) {
        std::cout << 1 << "\n";
        return;
    }
    
    for (int i = 0; i < n; i++) {
        if (sum % 3 == a[i] % 3) {
            std::cout << 1 << "\n";
            return;
        }
    }
    std::cout << 2 << "\n";
}

C. Turtle Fingers: Count the Values of k

给你三个正整数 $a$ 、 $b$ 和 $l$ ( $a, b, l \geq 0$ )。

可以证明，总有一种方法可以选择非负（即 $\geq 0$ ）的整数 $k$ 、 $x$ 和 $y$ ，使得 $l = k \cdot a^{x} \cdot b^{y}$ .

你的任务是找出所有这些方法中 $k$ 的不同可能值的个数。

我去特判了 !l || !(l % a == 0 && l % b == 0) 的情况，结果不给过，去掉就过了🥲

int qpow(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a;
        a = a * a;
        k >>= 1;
    }
    return res;
}
void solve() {
    int a, b, l;cin >> a >> b >> l;
    int x = 0, y = 0;
    while (l % qpow(a, x) == 0) {
        x++;
    }
    while (l % qpow(b, y) == 0) {
        y++;
    }
    x--, y--;
    set<int> s;
    for (int i = 0;i <= x;i++) {
        for (int j = 0;j <= y;j++) {
            if (l % (qpow(a, i) * qpow(b, j)) == 0) {
                s.insert(l / (qpow(a, i) * qpow(b, j)));
            }
        }
    }
    cout << s.size() << '\n';
}

D. Turtle Tenacity: Continual Mods

给定数组 $a_{1}, a_{2}, \dots, a_{n}$ ，判断是否有可能将其元素**重排为 $b_{1}, b_{2}, \dots, b_{n}$ ，从而得到 $b_{1} mod b_{2} mod \dots mod b_{n} \neq 0$ 。

这里的 $x mod y$ 表示 $x$ 除以 $y$ 的余数。另外，模运算是从左向右计算的。即 $x mod y mod z = (x mod y) mod z$ 。例如， $2024 mod 1000 mod 8 = (2024 mod 1000) mod 8 = 24 mod 8 = 0$ 。

只需要满足在去除掉最小公因数后的数组 1 的个数小于 2 即可。(非常简单)

void solve() {
    int n;cin >> n;vector<int> a(n);for (int i = 0;i < n;i++)cin >> a[i];
    sort(a.begin(), a.end());
    bool ok = true;
    for (int i = 2;i < n;i++) {
        if (a[i] % a[0] != 0) {
            ok = false;
        }
    }
    if (a[0] == a[1] && ok) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

E. Turtle vs. Rabbit Race: Optimal Trainings

艾萨克开始了他的训练。有 $n$ 条跑道可供使用， $i$ 条跑道（ $1 \leq i \leq n$ ）由 $a_{i}$ 个等长的部分组成。

给定一个整数 $u$ ( $1 \leq u \leq 10^{9}$ )，完成每一段都能使艾萨克的能力提高一个特定值，具体描述如下：

完成 $1$ （ $1$ -st）部分会使艾萨克的成绩提高 $u$ 。
完成 $2$ （nd）部分会使艾萨克的能力提高 $u - 1$ 。
完成 $3$ -rd 部分会使艾萨克的成绩提高 $u - 2$ 。
$\dots$
完成 $k$ -th 部分（ $k \geq 1$ ）会使艾萨克的成绩提高 $u + 1 - k$ 。 $u + 1 - k$ 的值可以是负数，这意味着完成额外的部分会降低艾萨克的成绩）。

您还得到了一个整数 $l$ 。您必须选择一个整数 $r$ ，使 $l \leq r \leq n$ 和艾萨克都能完成赛道 $l, l + 1, \dots, r$ 的个段（即总共完成 $l \leq r \leq n$ 个**段）。(即总共完成 $\sum_{i = l}^{r} a_{i} = a_{l} + a_{l + 1} + \dots + a_{r}$ 节）。

请回答下列问题：你所能选择的最佳 $r$ 是什么，能最大限度地提高艾萨克的成绩？

如果有多个 $r$ 可以最大限度地提高艾萨克的成绩，请选出小的 $r$ 。

为了增加难度，你需要回答 $q$ 个不同值的 $l$ 和 $u$ 。

Solution

二分/三分

三分板子题

由于这个题的收益是：当 $pre[r]-pre[l-1] \leq u (+) > u (-)$ 所以收益曲线是先上升后下降，只要找到最高点对应的 $r$ 即可。

#define int long long
void solve() {
    int n;cin >> n;vector<int> a(n + 1), pre(n + 1);for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)pre[i] = pre[i - 1] + a[i];
    int q;cin >> q;
    auto f = [&](int l, int r, int u) {//u u-1 u-2... u+1-k的等差数列前n项和
        return (u + u + 1 - pre[r] + pre[l - 1]) * (pre[r] - pre[l - 1]) / 2;
    };
    while (q--) {
        int L, u;cin >> L >> u;
        int l = L, r = n;
        while (l < r) {
            int lmid = l + (r - l) / 3;
            int rmid = r - (r - l) / 3;
            if (f(L, lmid, u) < f(L, rmid, u))l = lmid + 1;
            else r = rmid - 1;
        }
        cout << l << ' ';
    }
    cout << '\n';
}

i64 calc(int u, int x) {
    return 1LL * (u + u - x + 1) * x / 2;
}
 
void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::vector<int> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + a[i];
    }
    
    int q;
    std::cin >> q;
    
    while (q--) {
        int l, u;
        std::cin >> l >> u;
        l--;
        
        int j = std::lower_bound(s.begin() + l + 1, s.end(), s[l] + u) - s.begin();
        i64 ans = -1E18;
        int r = -1;
        if (j <= n) {
            if (calc(u, s[j] - s[l]) > ans) {
                ans = calc(u, s[j] - s[l]);
                r = j;
            }
        }
        if (j - 1 > l) {
            if (calc(u, s[j - 1] - s[l]) >= ans) {
                ans = calc(u, s[j - 1] - s[l]);
                r = j - 1;
            }
        }
        std::cout << r << " \n"[q == 0];
    }
}

F. Turtle Mission: Robot and the Earthquake

给出一个矩阵，0 代表是空地，1 代表有石头，现在发生了地震，所有的石头每秒向上移动一个单位，且在竖直方向上是循环移动的，可以走的路径有上下右，要求不能和移动的石头碰撞，现在问从 0 0 到 n-1 m-1 的最短时间，若无解输出-1

特别的，最后一列没有石头

Solution

BFS

可以将题目转化一下，相当于人每秒向下移动一个单位，石头不动

则路径有：不动，向下移动两个单位 $(x + 2) (\mod n) (y)$ ，向右下方移动 $(x + 1) (\mod n) (y + 1)$

bfs 可以算到最后一列，在这时，因为石头在动，所以到达最后一列时，终点也在动，需要先算终点的位置，看直接向上或直接向下哪个更块，在可以取到的答案中取最小即可。

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    queue<pair<int, int>> q;
    vector<vector<int>> dis(n, vector<int>(m, -1));
    q.emplace(0, 0);
    dis[0][0] = 0;
    while (q.size()) {
        auto [x, y] = q.front();
        q.pop();
        if (y < m - 1 && a[(x + 1) % n][y + 1] == 0 && dis[(x + 1) % n][y + 1] == -1) {
            dis[(x + 1) % n][y + 1] = dis[x][y] + 1;
            q.emplace((x + 1) % n, y + 1);
        }
        if (a[(x + 1) % n][y] == 0 && a[(x + 2) % n][y] == 0 && dis[(x + 2) % n][y] == -1) {
            dis[(x + 2) % n][y] = dis[x][y] + 1;
            q.emplace((x + 2) % n, y);
        }
    }
    /*------------1-------------*/
    int ans = -1;
    for (int i = 0;i < n;i++) {
        int res = dis[i][m - 1];
        if (res != -1) {
            if (res % n != (i + 1) % n) {
                res += (i + 1 - res % n + n) % n;
            }
            if (ans == -1 || ans > res) {
                ans = res;
            }
        }
    }
    cout << ans << '\n';
    /*------------2-------------*/
    int ans = 1e9;
    for (int i = 0;i < n;i++) {
        if (dis[i][m - 1] == -1)continue;
        int end = (n - 1 + dis[i][m - 1]) % n;
        ans = min(ans, dis[i][m - 1] + min((end - i + n) % n, (i - end + n) % n));
    }
    if (ans == 1e9)ans = -1;
    cout << ans << '\n';
}

G. Turtle Magic: Royal Turtle Shell Pattern

给出一个 $n \times m$ 的网格，有 $q$ 次查询，每次可以选择一个单元格 $(r_{i}, c_{i})$ 然后选择一个形状放入该形状的幸运饼干，进行该操作后该单元格就不再为空。

问在剩余单元格中放置饼干满足（没有三个连续的单元格 (水平方向、垂直方向和对角线方向)包含相同形状的饼干）的方法数 $(\mod 998244353)$

Solution

找规律/打表

$n = 5, m = 5$ 的 8 种方法：

只能两个连着放，如果一个一个间隔放，则一定有矛盾

最多只能有 8 种方式，4 种横着，4 种竖着。

(待更 $\dots$ )

搜索可行方案

    const int n = 5;

    int a[n][n];
    auto dfs = [&](auto self, int x, int y) {
        if (x == n) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    std::cerr << a[i][j];
                }
                std::cerr << "\n";
            }
            std::cerr << "---\n";
            return;
        }
        if (y == n) {
            return self(self, x + 1, 0);
        }
        for (int t = 0; t < 2; t++) {
            a[x][y] = t;
            if (x >= 2 && a[x][y] == a[x - 1][y] && a[x][y] == a[x - 2][y]) {
                continue;
            }
            if (y >= 2 && a[x][y] == a[x][y - 1] && a[x][y] == a[x][y - 2]) {
                continue;
            }
            if (x >= 2 && y >= 2 && a[x][y] == a[x - 1][y - 1] && a[x][y] == a[x - 2][y - 2]) {
                continue;
            }
            if (x >= 2 && y + 2 < n && a[x][y] == a[x - 1][y + 1] && a[x][y] == a[x - 2][y + 2]) {
                continue;
            }
            self(self, x, y + 1);
        }
    };
    dfs(dfs, 0, 0);

int get(int x, int y, int t) {
    if (t >= 4) {
        return get(y, x, t - 4);
    }
    return (t & 1) ^ (x & 1) ^ (((t >> 1) + y) >> 1 & 1);
}

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;

    int ok[8];
    for (int i = 0; i < 8; i++) {
        ok[i] = 1;
    }

    std::cout << std::count(ok, ok + 8, 1) << "\n";

    while (q--) {
        int x, y;
        std::string shape;
        std::cin >> x >> y >> shape;
        x--, y--;

        for (int i = 0; i < 8; i++) {
            if (get(x, y, i) != (shape == "circle")) {
                ok[i] = 0;
            }
        }
        std::cout << std::count(ok, ok + 8, 1) << "\n";
    }
}

void solve(int tc) { 
  int n, m, q;
  cin >> n >> m >> q;
  bool b[8] = {1, 1, 1, 1, 1, 1, 1, 1};
  int ans = 8;
  cout << ans << '\n';
  while(q--) {
    int r, c;
    cin >> r >> c;
    string shape;
    cin >> shape;
    if((r + (c+1) / 2) % 2) {
      b[0] &= (shape == "circle");
      b[1] &= (shape == "square");
    }
    else {
      b[0] &= (shape == "square");
      b[1] &= (shape == "circle");
    }
    if((r + c / 2) % 2) {
      b[2] &= (shape == "circle");
      b[3] &= (shape == "square");
    }
    else {
      b[2] &= (shape == "square");
      b[3] &= (shape == "circle");
    }

    if((c + (r+1) / 2) % 2) {
      b[4] &= (shape == "circle");
      b[5] &= (shape == "square");
    }
    else {
      b[4] &= (shape == "square");
      b[5] &= (shape == "circle");
    }
    if((c + r / 2) % 2) {
      b[6] &= (shape == "circle");
      b[7] &= (shape == "square");
    }
    else {
      b[6] &= (shape == "square");
      b[7] &= (shape == "circle");
    }
    ans = 0;
    for(int i = 0; i < 8; i++) ans += b[i];
    cout << ans << '\n';
  }
}