A

由题可知，机器人能够到达的所有正整数坐标 $x$ ，必然与起点 $1$ 之间相差 $k$ 的非负整数倍。

因此，判断一个红点坐标 $a_i$ 可达，只需要判断 $a_i - 1 \equiv 0 \pmod k$ 是否成立即可，考虑直接模拟。

参考代码如下：

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

using ll = long long;

ll n, k, x, ret;

signed main () {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) 
		cin >> x, ret += ((x - 1) % k == 0);
	cout << ret << endl;
	return 0;
}

B

设当前数为 $a$ ，我们先考虑：一个数经过任意次操作 $a \leftarrow a \bmod x$ 后，最终能变成哪些值。

设 $c=\left\lfloor \frac{a-1}{2}\right\rfloor$ ，那么 $a$ 最终可达的值恰好是： $\{a\}\cup \{0,1,2,\dots,c\}$

也就是说，要么保持不变，还是 $a$ ；要么变成一个不超过 $\left\lfloor \frac{a-1}{2}\right\rfloor$ 的数。

证明：

对于任意 $0\le r\le \left\lfloor \frac{a-1}{2}\right\rfloor$ ，取 $x=a-r$ ，就有 $a\bmod x=r$ ，所以这些数都能得到。
如果一次操作后数值发生变化，那么余数一定小于原数的一半，因此不可能超过 $\left\lfloor \frac{a-1}{2}\right\rfloor$ 。

对每个 $a_i$ ，它可以被变成： $\{0,1,\dots,\left\lfloor \frac{a_i-1}{2}\right\rfloor\}\cup \{a_i\}$ 。

现在问题变成：能否从每个位置的可选集合中选一个数，使序列严格递增。

从左到右处理，设当前已经选到的数为 cur，对于当前的 $a_i$ ，记 $c=\left\lfloor \frac{a_i-1}{2}\right\rfloor$ ：

如果 cur < c，那么可以选 cur + 1；
否则如果 cur < a_i，只能选 a_i；
否则无解。

正确性：严格递增时，当前位置选得越小，后面越容易满足条件，所以每一步都选“最小可行值”即可。

参考代码：

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

using ll = long long;

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

    int n;
    cin >> n;

    ll cur = -1;
    for (int i = 1; i <= n; ++i) {
        ll a;
        cin >> a;
        ll c = (a - 1) / 2;

        if (cur < c)  ++cur;
        else if (cur < a) cur = a;
        else {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    return 0;
}

C

对于任意询问 $x$ ，若两个元素满足 $a_i \times a_j \ge x$ ，我们可视作这两个元素之间存在一条无向边，如果所有“不在正确排序位置”的元素都属于同一个连通块，我们就能在连通块内部通过多次交换实现任意重排，使数组有序。

考虑数组中的最大值 $M$ 。

若 $a_i \times M < x$ ，因为 $M$ 是最大值，所以对任意 $j$ 必然有 $a_i \times a_j \le a_i \times M < x$ ，故无法移动 $a_{i}$ 。
否则它与 $M$ 连通。对于任意与 $M$ 联通的两个不同元素 $a_{i}, a_{j}$ ，可以先后与 $M$ 交换使得交换 $a_{i}$ 与 $a_{j}$ 。

因此，我们证明了满足 $a_i \times M \ge x$ 的所有元素可以互相交换位置，下面考虑是否可以将其变为升序。

记原数组按升序排序后得到的数组为 $b$ ，则所有满足 $a_{i} \neq b_{i}$ 的 $a_{i}$ 均需要移动，否则无法将其变为升序。

若存在 $a_{i} \neq b_{i}$ ，记 $N$ 为最小的满足 $a_{i} \neq b_{i}$ 的元素，此时只需要检测 $N \times M \geq x$ 即可。若不满足，则 $N$ 必然无法通过交换去到其正确的位置，若满足，则代表所有 $a_{i} \neq b_{i}$ 的元素均可以通过交换回到其正确位置。

需要注意 $N$ 是否存在，参考代码：

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

using ll = long long;

ll n, q, x, a[100100], b[100100];
ll M = 0, N = 1000000000ll;

signed main () {
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) 
		cin >> a[i], b[i] = a[i];

	sort (b + 1, b + 1 + n), M = b[n];

	for (int i = 1; i <= n; ++i) 
		if (a[i] != b[i]) N = min(N, a[i]);

	if (N == 1000000000ll) {
		for (int i = 1; i <= q; ++i) cout << "Yes\n";
		return 0;
	}

	for (int i = 1; i <= q; ++i) 
		cin >> x, cout << (N * M >= x ? "Yes" : "No") << endl;
	return 0;
}

D

因为每条边的方向仅影响其两个端点的出度，且树的结构具备无后效性，考虑树上 DP。

题目要求的是平方和最大化。对于某个节点 $u$ ，假设我们为其分配了 $k$ 个指向子节点的边（即 $u \to v$ ），那么它从子节点获得的局部出度就是 $k$ 。由于是在不同子节点的决策中做选择，为了在固定 $k$ 的情况下让子树贡献的权值总和最大，我们可以优先选择那些“改变方向后能带来最大收益”的子节点。

任选一个节点（如节点 $1$ ）作为根节点，将无根树转化为有根树。对于节点 $u$ ，它与父节点 $p$ 之间只有一条边，这条边的方向会决定 $u$ 的基础出度是 $0$ 还是 $1$ 。故定义状态：

$dp_{u,0}$ ：设父子边方向为 $p \to u$ ，以 $u$ 为根的子树能获得的最大平方和。
$dp_{u,1}$ ：设父子边方向为 $u \to p$ ，以 $u$ 为根的子树能获得的最大平方和。

对于 $u$ 的任意子节点 $v$ ，我们有两种决策：

$u \to v$ ： $u$ 的出度 $+1$ 。此时对 $v$ 而言，其父子边为指向自己，因此子树 $v$ 的最大贡献为 $dp_{v,0}$ 。
$v \to u$ ： $u$ 的出度 $+0$ 。此时对 $v$ 而言，其父子边为指向父节点，因此子树 $v$ 的最大贡献为 $dp_{v,1}$ 。

若我们选择 $u \to v$ 而不是 $v \to u$ ，子树 $v$ 贡献的变化量为 $\Delta_v = dp_{v,0} - dp_{v,1}$ ，为了求出最优解，我们：

预先假设所有子节点都指向 $u$ （即选择 $v \to u$ ），此时基础贡献和 $B = \sum dp_{u,1}$ 。
将所有子节点的差值 $\Delta_v$ 放入数组并降序排序。
枚举 $u$ 指向子节点的数量 $k$ （ $0 \le k \le \text{子节点总数}$ ）。为了让贡献最大，我们贪心地取排序后前 $k$ 大的 $\Delta_v$ 求和，记为 $S_k$ 。
在枚举过程中，动态维护最大值：
- $dp_{u,0} = \max_{k} \{ B + S_k + k^2 \}$
- $dp_{u,1} = \max_{k} \{ B + S_k + (k+1)^2 \}$

因为根节点没有父亲，故答案即为 $dp_{1,0}$ ，直接输出即可。

参考代码：

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int ll

const int N = 200000 + 10;
const int inf = 1e9 + 7;
using namespace std;

int read () {
	int x = 0, k = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') k = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * k;
}

int n, u, v, dp[N][2]; 
vector<int> G[N]; 

void dfs (int u, int p) {
	int S = 0, C = 0; vector<int> D;
	for (int v: G[u]) if (v != p) dfs(v, u), S += dp[v][1], D.push_back(dp[v][0] - dp[v][1]);
	sort(D.begin(), D.end(), greater<int>());
	dp[u][0] = S, dp[u][1] = S + 1;
	for (int k = 1; k <= D.size(); ++k) {
		C += D[k - 1];
		dp[u][0] = max(dp[u][0], S + C + k * k);
		dp[u][1] = max(dp[u][1], S + C + (k + 1) * (k + 1));
	}
}

signed main() {
	n = read();
	for (int i = 1; i < n; ++i) u = read(), v = read(), G[u].push_back(v), G[v].push_back(u);
	dfs(1, 0), cout << dp[1][0] << endl;
	return 0;
}

E

设某一个合法子段的元素为 $x_1, x_2, \dots, x_m$ ，其按位与的和为 $A$ ，按位异或的和为 $X$ 。

性质1：合法的子段长度 $m$ 必须是偶数。

若子段长度 $m$ 为奇数，对于任意二进制位 $k$ ：若 $A$ 的第 $k$ 位为 $1$ ，说明子段内所有元素的第 $k$ 位均为 $1$ 。由于 $m$ 是奇数，奇数个 $1$ 异或必定为 $1$ ，所以 $X$ 的第 $k$ 位也为 $1$ 。

若 $A$ 的第 $k$ 位为 $0$ ， $X$ 的该位可能为 $0$ 或 $1$ 。

因此在任何位上， $A$ 的位值总是小于等于 $X$ 的位值，作为一个整数 $A$ 绝不可能严格大于 $X$ 。故合法子段长度必须是偶数。如果全局 $n$ 为奇数，无论怎么划分必定存在奇数长度的子段，直接输出 -1。

性质2：对于偶数长度子段， $A > X$ 等价于存在某个位 $H$ ，使得 $A$ 的第 $H$ 位为 $1$ ，且 $X$ 在第 $H$ 位及更高的位上均为 $0$ 。

由于 $m$ 为偶数，若 $A$ 在第 $H$ 位为 $1$ （即所有元素第 $H$ 位均为 $1$ ），那么 $X$ 的第 $H$ 位必定是 $0$ 。此时要保证 $A > X$ 整体成立， $X$ 在严格高于 $H$ 的位上绝对不能有 $1$ 。这也意味着，对于原数组的前缀异或和数组 $P$ ， $X \gg (H+1) = 0$ ，即等价于 $P_i \gg (H+1) = P_j \gg (H+1)$ 。

定义 $dp_i$ 为前 $i$ 个元素最多能被划分成的合法子段数量。一段 $[j+1, i]$ 满足条件，当且仅当存在一个位 $k$ ，使得：

区间内所有元素的第 $k$ 位均为 $1$ （即连续的 $1$ 且未被 $0$ 打断）。
$P_i \gg (k+1) = P_j \gg (k+1)$ 。
$i \equiv j \pmod 2$ 。

我们为每个位 $k$ 以及奇偶性维护一个哈希表，键为 $P \gg (k+1)$ ，值为最大的 $dp$ 值。

当遍历到 $a_i$ 时：

如果 $a_i$ 的第 $k$ 位是 $1$ ：将 $dp_{i-1}$ 存入对应哈希表，并利用 $P_i \gg (k+1)$ 查询合法的最大 $dp_j$ 来更新 $dp_i$ 。
如果 $a_i$ 的第 $k$ 位是 $0$ ：直接清空该位 $k$ 对应的哈希表。

参考代码：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

const int N = 300005;

int n, a[N], P[N], dp[N];
gp_hash_table<int, int> mp[30][2];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n;
    
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        P[i] = P[i - 1] ^ a[i];
        dp[i] = -1;
    }

    if (n & 1) {
        cout << -1 << "\n";
        return 0;
    }

    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int k = 0; k < 30; ++k) {
            if ((a[i] >> k) & 1) {
                if (dp[i - 1] != -1) {
                    int v = P[i - 1] >> (k + 1), o = (i - 1) & 1;
                    auto it = mp[k][o].find(v);
                    if (it == mp[k][o].end()) mp[k][o][v] = dp[i - 1];
                    else it->second = max(it->second, dp[i - 1]);
                }
                int v = P[i] >> (k + 1), o = i & 1;
                auto it = mp[k][o].find(v);
                if (it != mp[k][o].end()) {
                    dp[i] = max(dp[i], it->second + 1);
                }
            } else {
                mp[k][0].clear();
                mp[k][1].clear();
            }
        }
    }
    
    cout << dp[n] << "\n";
    return 0;
}

F

由题可知，图中的边分为两类：

加法边： $(a_i + a_j) \bmod m = 0$ ，即 $a_i \equiv r \pmod m$ 且 $a_j \equiv (m-r) \pmod m$ 。
乘法边： $a_i \times a_j \le k$ 。

为了简化连通块的统计，我们挖掘这两类边的性质。设当前数组中存在的最小值为 $mn$ 。

性质1：合法的乘法边一定形成一个最小值连通块。

若 $mn^2 \le k$ ，令阈值 $L = \left\lfloor \frac{k}{mn} \right\rfloor$ 。那么值域在 $[1, L]$ 内的所有存在的点，必然同属一个极大的连通块（我们称之为主连通块）。

性质2：加法边相对是独立的。

对于满足 $(r + r') \bmod m = 0$ 的一对余数（伴侣对）：

如果这对余数在数组中均存在相应的元素（当 $r = r'$ 时要求元素个数 $\ge 2$ ），它们之间会形成完全二分图（或完全图），内部完全连通。
如果这对伴侣中存在 $\le L$ 的元素，即 $\min(\min_{v \equiv r} v, \min_{v \equiv r'} v) \le L$ ，那么这整个完全二分图都会因为那个 $\le L$ 的元素被接入主连通块。
- 如果这对伴侣的最小值 $> L$ ，那么它们不仅内部连通，而且绝对无法产生任何乘法边。因此它们形成一个独立的连通块。

基于以上性质，图中的连通块总数可以严格划分为以下三部分之和：

主连通块：如果 $mn \le L$ ，存在一个主连通块，贡献为 $1$ ；否则为 $0$ 。
独立伴侣对：满足合法配对条件，且整对的最小值 $> L$ 的加法伴侣对数量。
孤立点：所有值 $> L$ 且没有加法伴侣的点。这类点不会有任何连边，每一个实例都会单独构成一个连通块。

考虑单点修改操作：

我们使用全局 set 维护最小值 $mn$ ；使用挂载在每个余数上的 set 维护该余数的最小值。
同时使用树状数组动态维护“配对的最小值”，用于以 $O(\log V)$ 的复杂度快速查询 $>L$ 的独立伴侣对数量。
使用值域分块维护每个余数类在各个值域块中的元素个数。当某伴侣对的状态发生翻转时，可以在 $O(V/B)$ 内更新“拥有伴侣元素的总数”，并在 $O(V/B + B)$ 的时间内查询 $\le L$ 的拥有伴侣的元素个数。

时间复杂度为 $O(q \sqrt{V} + q \log V)$ 。

参考代码：

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

using ll = long long;
const int V = 100000, N = 100005, B = 316, S = 320;

int n, m, q, a[N], cnt[N], c[N], C[N][S], sg[S], pm[N];
ll k;
bool ck[N], ***];
set<int> mnv[N], mng;

struct BIT {
    int tr[N];
    inline void add(int i, int d) { for (; i <= V; i += i & -i) tr[i] += d; }
    inline int qry(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += tr[i];
        return s;
    }
} al, pr;

inline void upd (int v, int d) {
    int r = v % m, b = v / B, r2 = (m - r) % m, P = min(r, r2);
    
    cnt[v] += d;
    if (d == 1 && cnt[v] == 1) mng.insert(v), mnv[r].insert(v);
    else if (d == -1 && cnt[v] == 0) mng.erase(v), mnv[r].erase(v);
    
    al.add(v, d), c[r] += d, C[r][b] += d;
    if (ck[r]) sg[b] += d;

    bool nv = (r == r2) ? (c[r] >= 2) : (c[r] > 0 && c[r2] > 0);
    int npm = nv ? (r == r2 ? *mnv[r].begin() : min(*mnv[r].begin(), *mnv[r2].begin())) : 0;
    bool ov = vp[P];

    if (ov != nv || (nv && npm != pm[P])) {
        if (ov) pr.add(pm[P], -1);
        if (nv) pr.add(npm, 1);
        pm[P] = npm;
    }

    if (ov != nv) {
        vp[P] = ck[r] = ck[r2] = nv;
        int lim = V / B;
        for (int i = 0; i <= lim; ++i) {
            int dt = C[r][i] + (r != r2 ? C[r2][i] : 0);
            sg[i] += nv ? dt : -dt;
        }
    }
}

inline int calc () {
    if (mng.empty()) return 0;
    ll mn = *mng.begin();
    int L = min((ll)V, k / mn), gc = 0, sg_L = 0, fb = L / B, lim = V / B;
    
    for (int i = 0; i <= lim; ++i) gc += sg[i];
    for (int i = 0; i < fb; ++i) sg_L += sg[i];
    for (int v = fb * B; v <= L; ++v) if (ck[v % m]) sg_L += cnt[v];
    
    return (mn <= L ? 1 : 0) + (n - gc) - (al.qry(L) - sg_L) + pr.qry(V) - pr.qry(L);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k >> q;
    
    for (int i = 1; i <= n; ++i) 
        cin >> a[i], upd(a[i], 1);
    
    cout << calc() << "\n";
    
    for (int i = 1; i <= q; ++i) {
        int p, x;
        cin >> p >> x;
        upd(a[p], -1), upd(a[p] = x, 1);
        cout << calc() << "\n";
    }
    
    return 0;
}

牛客练习赛151题解

A

B

C

D

E

F