前言

这场的题目质量感觉还是很好的。再难一点的就没什么思路了。

好的题目，不局限于一种做法，例如这场的 $B$ 题，就有两种做法，本来还想再做出第三种，但是被厚膜哥证明出复杂度不可行。

B - Wonderful Array

题意

给定 $k$ 个数，然后给定 $n$, $m$, $x$。

定义 $b[]$ 为 $b_i =\begin {cases} x, & i = 0\\ b_{i-1} + a_{(i-1) \mod k}, & 0<i \le n\end {cases}$。

问有多少 $i(0 \le i < n)$，满足 $(b_i \mod m) \le (b_{i+1} \mod m)$.

做法一（针对这题没有多测）

对于 $x+y \le z$，如果 $x$ 固定，那么 $y$ 就要满足 $y \le z-x$。

考虑暴力，会出现 $k$ 轮循环一次的情况，对这 $k$ 个数排序，可以用二分快速找到有多少个数符合条件。

每一轮开始之前，所得到的 $x$ 都有可能不同，随之得到的新的 $b_i$ 也就可能不一样，所以会进行 $n/k$ 轮，偏偏 $n/k$ 的级别可能是 $1e9$，所以这样看似是不可做的。

优化 $n/k$，就是做法一的关键。

我们可以扩展 $k$ 的大小，扩展到 $1e6$ 级别，于是 $n/k$ 会被压缩到 $1e3$ 级别。而扩展 $k$，对答案是不影响的，这很显然。所以这样偷鸡成功。

但是对于多测，这样做还是很容易 $tle$ 的，毕竟一个很小的 $k$，经过扩展后复杂度仍会维持在 $1e3$ 左右。

做法二 （正解）

正难则反，考虑答案的补集，如果有 $(b_i \mod m) > (b_{i+1} \mod m)$，那么 $b_i / m$ $<$ $b_{i+1}/m$ 显然成立，并且$b_i / m$ $+1$ $=$ $b_{i+1}/m$。

所以对于所有的 $b_i$ 都 $/=m$，得到的数字是连续的。于是我们只要求出最后一个数字就好了。然后用 $n$ 减去它就得到了答案。

func solve() {
    k := read()
    a := make([]int, k + 1)
    sum := make([]int, k + 1)
    for i := 1; i <= k; i++ {
        a[i] = read()
    }
    n, m, x := read(), read(), read()
    x %= m
    for i := 1; i <= k; i++ {
        sum[i] = sum[i - 1] + a[i] % m
    }
    //  ans = b[n] / m
    c := n / k
    mo := n % k
    x += sum[k] * c + sum[mo]
    println(n - x / m)
}

C - Battle

题意

$Alice$ 和 $Bob$ 又开始取石子了，这次他们不能任意取，对于一堆，他们只能取 $p$ 的幂次。问 $Alice$ 能否胜利。

做法

非常无耻的 $SG$ 函数打表，然后规律是显而易见的。这里打表代码也一并放上来。

其实我这个打表写的不好，其实可以用线性 $dp$ 来打表的。

map<vector<int>, int> f;
int qpow(int x1, int n) {
    int ret = 1;
    __int128 x = x1;
    while(n) {
        if (n & 1) ret = ret * x;
        n >>= 1;
        x = x * x;
    }
    return ret;
}
int dfs(vector<int> v, int p) {
    if (f.count(v)) {
        return f[v];
    }
    bool ok = 0;
    for (auto &i : v) {
        if (i != 0) {
            ok = 1;
        }
    }
    if (!ok) {
        return 0;
    }
    set<int> s;
    for (int i = 0; i < v.size(); i++) {
        int x = v[i];
        for (int j = 0; j < 31; j++) {
            if (x >= qpow(p, j)) {
                v[i] = x - qpow(p, j);
                s.insert(dfs(v, p));
                v[i] = x;
            } else {
                break;
            }
        }
    }
    for (int i = 0; ; i++) {
        if (!s.count(i)) {
            return f[v] = i;
        }
    }
    return f[v] = 0;
}
string baoli(vector<int> v, int p) {
    int ans = dfs(v, p);
    if (ans > 0) return "GOOD";
    return "BAD";
}
string myans(vector<int> v, int p) {
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        if (p & 1) {
            if (v[i] & 1) ans ^= 1;
            else ans ^= 0;
        } 
        else {
            v[i] %= (p + 1);
            if (v[i] == 0) {
                ans ^= 0;
            } else if (v[i] == p) {
                ans ^= 2;
            } else if (v[i] == p - 1) {
                ans ^= 1;
            } else {
                if (v[i] & 1) ans ^= 1;
                else ans ^= 0;
            }
        }
    }
    if (ans > 0) return "GOOD";
    return "BAD";
}
void check(int flag) {
    srand(unsigned(time(0)));
    int n = 5, p = 7;
    if (flag) {
        n = 1;
        vector<int> v(n);
        for (int k = 1; k <= 100; k++) {
            v[0] = k;
            f.clear();
            cout << baoli(v, p) << " " << dfs(v, p) << "\n";
        }
        return;
    }

    cout << n << " " << p << "\n";
    vector<int> v(n);
    for (int k = 0; k < 100; k++) {
        int sum = 0;
        f.clear();
        for (int i = 0; i < n; i++) {
            v[i] = rand() % 10 + 1;
            cout << v[i] << " ";
            sum += v[i];
        }
        cout << "\n";
        cout << "sum = " << sum << "\n";
        cout << baoli(v, p) << "\n";
        if (myans(v, p) != baoli(v, p)) {
            cout << myans(v, p) << " " << "\n";
            cout << "cnm\n";
            return;
        }
    }
}
void solve()
{
    // check(0);
    int n, p;
    cin >> n >> p;
    vector<int> v(n);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> v[i - 1];
        // sum += v[i - 1];
    }
    cout << myans(v, p);
}

I - Tree

题意

给定一棵树，对于这棵树有两种操作：

操作一，选定树上两个点 $x,y$，对 $x$ 到 $y$ 的路径上的边权，都异或 $z$。

操作二，问树上的点 $x$ 连接的两条边，异或和是多少。

思路

容易发现 $x,y$ 中间的点的答案不会受到修改操作的影响，所以修改端点的答案即可。

func solve() {
    n, q := read(), read()
    f := make([]int, n + 1)
    for i := 1; i <= n - 1; i++ {
        x, y, w := read(), read(), read()
        f[x] ^= w
        f[y] ^= w
    }
    for i := 1; i <= q; i++ {
        op := read()
        if op == 1 {
            x, y, w := read(), read(), read()
            f[x] ^= w
            f[y] ^= w
        } else {
            x := read()
            println(f[x])
        }
    }
}

K-Split

题意

给定一个数组 $a[]$，对数组也有两种操作：

操作一，将 $a_i$ 修改为 $a_{i+1} - a_{i} + a_{i - 1}$

操作二，询问答案，将数组分为 $k$ 个部分，每部分对答案的贡献是这个部分中的最大值减去最小值。问答案的最小值。

思路

如果先不管修改的部分，我们尝试求解询问的答案。

可以发现数组有 $n-1$ 个间隔，我们舍弃掉其中前 $n-k$ 大，就完成了询问答案的操作。

然后或许就能发现这题的神奇之处了，修改操作，只是交换了左右两个间隔，对答案并没有影响。一开始我也没发现这个性质，是想着这样或许会有什么公式，于是推了下式子：

x y z
x-y, y-z

x x-y+z z
y-z, x-y

就发现了这题的奥妙了。

func solve() {
    n := read()
    a, b, sum := make([]int, n + 1), make([]int, n), make([]int, n)
    for i := 1; i <= n; i++ {
        a[i] = read()
    }
    for i := 1; i < n; i++ {
        b[i] = a[i] - a[i + 1]
    }
    sort.Slice(b[1:], func(i, j int) bool {
        return b[i + 1] < b[j + 1]
    })
    for i := 1; i < n; i++ {
        sum[i] = sum[i - 1] + b[i]
    }
    m := read()
    for i := 1; i <= m; i++ {
        op := read()
        if op == 0 {
            read()
        } else {
            k := read()
            k--
            println(sum[n - 1 - k])
        }
    }
}

J - Function

题意

给定 $n$ 个二次函数，其中二次项系数都是 $1$。接着给定两个操作：

操作一，添加一个新的二次函数。

操作二，问所有的二次函数里面，经过给定的 $x$，得到的 $y$ 的最小值是多少。

做法

很显然是个优雅的暴力，只要在给定的 $x$ 周围遍历一遍，取最小的答案就好了。这个范围，300 到 500 够够的，而且也不会 $tle$。

func solve() {
    n := read()
    b := make([]int, n + 1)
    for i := 1; i <= n; i++ {
        b[i] = read()
    }
    m := read()
    for m > 0 {
        op := read()
        if op == 0 {
            A, B := read(), read()
            b[A] = min(b[A], B)
        } else {
            A := read()
            ans := int(1e18)
            for i := max(1, A - 500); i <= min(A+100, n); i++ {
                ans = min(ans, (A - i) * (A - i) + b[i])
            }
            println(ans)
        }
        m--
    }
}

L - Zhang Fei Threading Needles - Thick with Fine

太简单了，签到题。输出 $n-1$

n = int(input())
print(n - 1)

A - Drill Wood to Make Fire

题意很长，说了大堆的废话，是关于原始人取火的。

func solve() {
    a, b, c := read(), read(), read()
    if b * c >= a {
        println("1")
    } else {
        println("0")
    }
}