Problem A, B

纯模拟。

题解略

Problem C

高精度/结论。

做法1 结论

证明

$2*a=2*(\dfrac{x*y}{z}+\dfrac{y*z}{x}+\dfrac{x*z}{y})=(\dfrac{x*y}{z}+\dfrac{y*z}{x})+(\dfrac{x*y}{z}+\dfrac{x*z}{y})+(\dfrac{y*z}{x}+\dfrac{x*z}{y})$

$=y*(\dfrac{x}{z}+\dfrac{z}{x})+x*(\dfrac{y}{z}+\dfrac{z}{y})+z*(\dfrac{y}{x}+\dfrac{x}{y})$

已知 $\dfrac{x}{y}+\dfrac{y}{x}\geq2$

所以 $2*a\geq2*(x+y+z)=2*b$

从此可以知道 $a\geq b$

容易知道当 $x=y=z$ 时 $a=b$ 。

证明由 hnust_lixuyun 提供

做法2 高精度

x, y, z = map(int, input().split())
xy = x * y
xz = x * z
yz = y * z
xyz = x * y * z
b = x + y + z
b *= xyz
xy *= xy
xz *= xz
yz *= yz
a = xy + yz + xz
print('=' if a == b else '>' if a > b else '<')

Problem D

博弈论。

因为 Mercedes 是后手，有一种情况他是必赢的，也就是满足以下

$(x*k)^2+(x*k)^2\leq d^2$ 且 $((x+1)*k)^2+(x*k)^2\leq d^2$

也就是说每次 Mercedes 选择与 Parry 相反的操作，这样点最终将会在对角线上，且不能进行下一步操作，此时能保证 Mercedes 必胜。

如果不是这种情况怎么办，那么假设 Mercedes 还是选择一样的操作。我们考虑到达对角线上最远的点的后续操作，不可能又向上又向右，因为这样就不是对角线上最远的点。那么我们只能往一个方向走，我们可以证明最多只能走一步。

因为如果走两步则 $((x+2)*k)^2+(x*k)^2>2*((x+1)*k)^2$ 。此时可以往两个方向走，从而得证不可能走两步。

综上，这种走法，最后要么不能走，要么只能走一步。

如果不能走，则后手 Mercedes 必胜，上面已经证明。如果能走一步，那么 Parry 可以考虑随便走一步，此时如果 Mercedes 一直走的是相反的操作，那么就继续随便走，最终一定回到对角线上，并剩下一步操作，如果 Mercedes 选择相同的方向，那么此时 Parry 一直选择与 Mercedes 相反的操作，就可以做到自己走最后一步。

所以我们二分查找最大的 $k$ ，然后判断是否能再走一步就可以得出答案#。

Problem E

不会。

Problem F

树状数组。

我们先看操作一，单点修改。

我们先考虑 $a_p$ 的贡献，为 $\sum_{i=1}^n[a_i\leq \lfloor\dfrac{m}{a_p}\rfloor]$ ,

此时将 $a_p$ 改为 $x$ 的贡献，就是先减去 $a_p$ 修改前的贡献，再加上 $a_p$ 改为 $x$ 后的贡献。

所以对于操作一，只需要会计算 $\sum_{i=1}^n[a_i\leq \lfloor\dfrac{m}{a_p}\rfloor]$ 即可，

对于操作二，直接输出。

如何快速计算 $\sum_{i=1}^n[a_i\leq \lfloor\dfrac{m}{a_p}\rfloor]$

使用权值树状数组可以 $O(logn)$ 求出 $a_i\leq x$ 的数量。

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

// 2024 OneWan

int sum[1000005];
int lowbit(int x) {
	return x & -x;
}
void add(int x, int k) {
	while (x <= 1000000) {
		sum[x] += k;
		x += lowbit(x);
	}
}
int query(int x) {
	int res = 0;
	while (x) {
		res += sum[x];
		x -= lowbit(x);
	}
	return res;
}
int a[200005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q, m;
	cin >> n >> q >> m;
	long long ans = 0;
	for (int i = 1 ; i <= n ; i++) {
		cin >> a[i];
		add(a[i], 1);
		ans += query(m / a[i]);
	}
	while (q--) {
		int op;
		cin >> op;
		if (op == 1) {
			int pos, k;
			cin >> pos >> k;
			ans -= query(m / a[pos]);
			add(a[pos], -1);
			a[pos] = k;
			add(a[pos], 1);
			ans += query(m / a[pos]);
		} else {
			cout << ans << "\n";
		}
	}
	return 0;
}

Problem G

打表。

通过 bfs 打表可得满足题目中性质且 $\leq10^{18}$ 的数是百万级别的。

也就是说我们可以先找符合性质的数，再来统计有多少小于等于 $x$ 的数。

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

// 2024 OneWan

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vector<long long> vec;
	queue<long long> que;
	for (int i = 10 ; i <= 99 ; i++) {
		if (abs(i / 10 - i % 10) == 2) {
			que.push(i);
		}
	}
	while (!que.empty()) {
		__int128 x = que.front();
		que.pop();
		vec.push_back((long long) x);
		int k = x % 10;
		for (int i = 0 ; i < 10 ; i++) {
			if (abs(k - i) == 2) {
				__int128 y = x * 10 + i;
				if (y <= 1000000000000000000LL) {
					que.push((long long) y);
				}
			}
		}
	}
	sort(begin(vec), end(vec));
	long long x;
	cin >> x;
	cout << (lower_bound(begin(vec), end(vec), x + 1) - begin(vec));
	return 0;
}

Problem H

二分答案。

求最小值的最大，可以使用二分答案。

我们二分最小值的取值 $mid$ ，那么所有小于 $mid$ 的歌，都需要提升响度至大于等于 $mid$ 。

我们只需要知道所有小于 $mid$ 的歌的频段的最大值和最小值即可。

然后通过遍历这个频段，求这些歌响度的最大值，因为响度不能大于0，所以这些歌都减去它们响度的最大值，可以让所有歌的响度尽可能变大，且不超过0。

最后遍历所有的歌，看响度的最小值是否大于等于 $mid$ 即可。

#include <bits/stdc++.h>
using namespace std;
 
// 2024 OneWan
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> a;
    for (int i = 0 ; i < n ; i++) {
        int x, y;
        cin >> x >> y;
        a.push_back({x, y});
    }
    sort(begin(a), end(a));
    auto check = [&](int mid) {
        int L = -1, R = -1;
        for (int i = 0 ; i < n ; i++) {
            if (a[i].second < mid) {
                if (L == -1) L = i;
                R = i;
            }
        }
        if (L == -1) {
            return true;
        }
        int mx = -1000000000;
        for (int i = L ; i <= R ; i++) {
            mx = max(mx, a[i].second);
        }
        for (int i = L ; i <= R ; i++) {
            if (a[i].second - mx < mid) {
                return false;
            }
        }
        return true;
    };
    int L = -1000000000, R = 0;
    while (L < R) {
        int mid = L + R + 1 >> 1;
        if (check(mid)) {
            L = mid;
        } else {
            R = mid - 1;
        }
    }
    cout << L << "\n";
    return 0;
}

Problem I

博弈论。

令数组中奇数的个数为 $cnt$ 。

当 $cnt=0$ 时，halo 无法选择，所以 halo 必败。

当 $cnt\%2=1$ 时，halo 可以选择整个数组全部拿完。

当 $cnt\%2=0$ 时，halo 可以取前 $cnt-1$ 个奇数，把一段全部拿完，剩下的只会有 1 个奇数，此时 parry 无论怎么操作都不能消除掉这个奇数，轮到下一轮 halo 可以全部拿完。

Problem J

模拟。

根据题意写出操作即可。

Problem K

不会。

Problem L

我们不直接翻转字符串，而是先统计各个操作。

操作1，我们只需要让我们的flag取反即可。

当字符串处于翻转状态时，操作2其实就是将c加在字符串最后面，操作3其实就是将c加在字符串最前面。

当字符串不处于翻转状态时，操作2将c加在字符串最前面，操作3将c加在字符串最后面。

最后统一输出即可。

Problem M

树状数组。

固定了 $x$ 的区间，那么所有线段的左端点都会在 $x=L$ 上，右端点都会在 $x=R$ 上。

这样我们判断两条线段 $(x_1,y_1),(x_2,y_2)$ 是否相交只需要判断是否存在 $x_1\leq x_2$ 且 $y_1\geq y_2$ 或 $x_1\geq x_2$ 且 $y_1\leq y_2$ 即可。

这是一个典型的二维偏序问题，我们可以通过从小到大枚举 $x$ ，将枚举过的 $x$ 所对应的 $y$ 插入树状数组，就可以快速查找 $x$ 小 $y$ 大的数量即与当前线段相交的线段。

这里要注意的是，如果几个线段端点相交，需要特判，最后将所有线段的左端点计数，利用组合数 $C_n^2$ 计算对数即可，右端点同理。

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

#define int long long
const int N = 2000000;
int sum[N + 5];
int lowbit(int x) {
    return x & -x;
}
void add(int x, int k) {
    while (x <= N) {
        sum[x] += k;
        x += lowbit(x);
    }
}
int query(int x) {
    int res = 0;
    while (x) {
        res += sum[x];
        x -= lowbit(x);
    }
    return res;
}
pair<long long, long long> seg[N + 5];
void solve() {
    int n;
    cin >> n;
    int L, R;
    cin >> L >> R;
    vector<long long> idxY(1, -1000000000000000000LL);
    for (int i = 1 ; i <= n ; i++) {
        int k, b;
        cin >> k >> b;
        long long x = 1LL * k * L + b;
        long long y = 1LL * k * R + b;
        //cerr << x << " " << y << "\n";
        idxY.push_back(y);
        seg[i] = {x, y};
    }
    sort(begin(idxY), end(idxY));
    idxY.resize(unique(begin(idxY), end(idxY)) - begin(idxY));
    map<long long, vector<int>> mp;
    for (int i = 1 ; i <= n ; i++) {
        auto [x, y] = seg[i];
        y = lower_bound(begin(idxY), end(idxY), y) - begin(idxY);
        seg[i] = {x, y};
        mp[x].push_back(y);
    }
    long long ans = 0;
    {
        for (auto &[x, y] : mp) {
            for (auto &z : y) {
                ans += query(N) - query(z);
            }
            for (auto &z : y) {
                add(z, 1);
            }
        }
        for (int i = 1 ; i <= n ; i++) {
            add(seg[i].second, -1);
        }
    }
    {
        map<long long, int> cnt;
        for (int i = 1 ; i <= n ; i++) {
            cnt[seg[i].first]++;
        }
        for (auto &[x, y] : cnt) {
            ans += y * (y - 1) / 2;
        }
         
    }
    {
        map<int, int> cnt;
        for (int i = 1 ; i <= n ; i++) {
            cnt[seg[i].second]++;
        }
        for (auto &[x, y] : cnt) {
            ans += y * (y - 1) / 2;
        }
    }
    if (L == R) ans /= 2;
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Problem N

换根DP。

如果我们固定了根，那么黑色节点的儿子可以是黑色也可以是白色，而白色节点的儿子只能是白色。

当某个点为白色的方案数为1。

当某个点为黑色方案数为所有儿子的白色方案和黑色方案的和的乘积。

当1为黑色的情况，我们可以一遍dfs求出答案。

然后考虑换根，父节点的黑色方案需要变化，为父节点所有连边节点的白色和黑色方案和的乘积除上这个子节点的白色和黑色方案。

因为模数不一定为质数，这里不能使用逆元，

我们考虑一种前后缀积的做法，

令 $sumL$ 为前缀积， $sumR$ 为后缀积，那么 $\dfrac{\prod_{i=L}^Ra[i]}{a[x]}=sumL[x-1]*sumR[x+1]$ ，

我们以 $O(size(son))$ 的复杂度计算出前缀后缀积，这样我们可以 $O(1)$ 求出此时父节点黑色的方案树，那么这个子节点的答案就是子节点黑色的方案乘上父节点黑色和白色方案的和。

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

// 2024 OneWan

vector<int> adj[100005];

long long dp[100005][2];
int ans[100005];
long long m;
void dfs1(int u, int p) {
	dp[u][1] = dp[u][0] = 1;
	for (auto &to : adj[u]) {
		if (to == p) continue;
		dfs1(to, u);
		dp[u][0] *= dp[to][0];
		dp[u][1] *= dp[to][0] + dp[to][1];
		dp[u][0] %= m;
		dp[u][1] %= m;
	}
}
void dfs2(int u, int p) {
	vector<int> vec;
	for (auto &to : adj[u]) {
		vec.push_back(to);
	}
	int len = vec.size();
	vector<long long> sumL(len), sumR(len);
	if (len) {
		sumL[0] = dp[vec[0]][0] + dp[vec[0]][1];
		for (int i = 1 ; i < len ; i++) {
			sumL[i] = sumL[i - 1] * (dp[vec[i]][0] + dp[vec[i]][1]) % m;
		}
		sumR[len - 1] = dp[vec[len - 1]][0] + dp[vec[len - 1]][1];
		for (int i = len - 2 ; i >= 0 ; i--) {
			sumR[i] = sumR[i + 1] * (dp[vec[i]][0] + dp[vec[i]][1]) % m;
		}
	} else {
		return;
	}
	int idx = -1;
	for (auto &to : adj[u]) {
		idx++;
		if (to == p) continue;
		{
			long long x = 1, y = 1;
			if (idx - 1 >= 0) {
				x = sumL[idx - 1];
			}
			if (idx + 1 < len) {
				y = sumR[idx + 1];
			}
			long long res = x * y % m;
			ans[to] = dp[to][1] * (res + 1) % m;
			dp[u][1] = res;
		}
		dfs2(to, u);
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n >> m;
	for (int i = 1 ; i < n ; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs1(1, 0);
	ans[1] = dp[1][1];
	dfs2(1, 0);
	for (int i = 1 ; i <= n ; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}

Problem O

字符串哈希。

因为 $n\leq1000$ ，所以我们枚举区间左端点 $L$ ,然后 $R$ 从 $L$ 一次往后递推，只需要 $O(n^2)$ 就可以枚举所有区间。

对于每个区间进行判断 $g(f(s))=f(s)$ 。

可以知道 $g(str)$ 有意义，当且仅当 $str$ 中只包含字符'0'、'1'、'6'、'8'、'9'。

所以我们选取的 $a_i$ 都必须只包含这些字符，这里我们 $O(|str|)$ 预处理。

然后 $g(f(str))=f(str)$ 的意思，其实就是 $f(str)$ 一定是个"回文"串，因为只有"回文"，翻转后才会和自己相等。这里的"回文"，指的是翻转后还需要颠倒字符。

我们使用字符串哈希即可 $O(1)$ 判断是否是"回文"。

以下代码省略字符串哈希模版

int pL[1005], pR[1005];
bool has[1005];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string str;
    for (int i = 1 ; i <= n ; i++) {
        string s;
        cin >> s;
        str += s;
        has[i] = true;
        for (auto &x : s) {
            if (x != '1' && x != '0' && x != '8' && x != '6' && x != '9') {
                has[i] = false;
            }
        }
        pL[i] = pR[i - 1] + 1;
        pR[i] = pL[i] + s.size() - 1;
    }
    string rev = str;
    reverse(begin(rev), end(rev));
    for (auto &x : rev) {
        if (x == '9') {
            x = '6';
        } else if (x == '6') {
            x = '9';
        }
    }
    int len = str.size();
    Hash<Two> a(str), b(rev);
    str = " " + str;
    rev = " " + rev;
    int ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        int L = pL[i];
        for (int j = i ; j <= n ; j++) {
            if (!has[j]) {
                break;
            }
            int R = pR[j];
            if (a.get(L, R) == b.get(len - R + 1, len - L + 1)) {
                ans = max(ans, j - i + 1);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

西安理工大学2024年程序设计校赛（校外同步赛）非官方题解