2025 07 15 模拟赛题解
T1
水题一道，全场切
题面
请你判断是否存在正整数 \(n\)，使得 \(n^2\) 是 k 的倍数，且 \(n\) 不是 \(k\) 的倍数。如果存在，则输出最小的 \(n\)。不存在则输出 \(−1\)。
\(1 \le k \le 10 ^{12}\)
题解
我们先将 \(k\) 分解质因数，设质因子 \(p_i\) 的指数为 \(c_i\) ，那么我们 \(p_i\) 在 \(n\) 的指数就应该至少是 \(\lceil \frac {c_i} 2 \rceil\) ，那么就这样将 \(n\) 求出来，如果 \(n = k\) 无解，否则有解
T2
题面
小 Y 和小 E 选 \(n\) 个礼物，每个礼物有价值 \(a_i\) 。
两个人轮流选，小 Y 先手，并且每次小 Y 至少选一个礼物，小 E 必须选恰好一个礼物
\(1 \le n \le 10^6 , -10^9 \le a_i \le 10^9\)
题解
这道题我考场上想麻烦了，其实不用反悔贪心，反悔贪心会麻烦一些
我们其实可以大概感觉到，小 Y 只会在第一次选择超过一个数，后面都是两个人轮流取最大值
所以就是枚举一个前缀，后面轮流取，我们可以定义三个数组预处理出来，然后直接枚举，时间复杂度瓶颈在排序 \(O(n \log n)\)
T3
题面
给定两个字符串 \(S,T\) ，可以选择一个区间 \(l, r\) 进行翻转
求中翻转方案，使得 \(S = T\)
\(1 \le n \le 10^4\)
题解
这道题是个构造题，正解很简单，只需要从前向后扫描，看是否匹配，如果不匹配
- \(s[i] = 0\) ，向后暴力找到 \([i,j]\) 内出现两个 1，且 \(s[j] = 1\) 的 \(j\) ，而后翻转 \([i,j]\)
- \(s[i] = 1\) ，向后暴力找到 \([i,j]\) 内出现两个 1，且 \(s[j] = 0\) 的 \(j\) ，而后翻转 \([i,j]\)
T4
原
题面
考虑如下的两人游戏：
有一个由正整数组成的数组 \(b_1, b_2, \ldots, b_k\)。最开始，一个棋子放在数组的第一个格子里，并且 \(b_1\) 减 \(1\)。两位玩家轮流行动。每一回合，当前玩家需要执行以下操作：假设棋子当前在第 \(x\) 个格子，那么他需要选择一个 \(y \in [x, \min(k, x + m)]\)，满足 \(b_y > 0\)，然后将棋子移动到第 \(y\) 个格子，并将 \(b_y\) 减 \(1\)。如果无法进行有效的移动，则当前玩家输掉游戏。
你的任务如下：给定一个由 \(n\) 个正整数组成的数组 \(a\)，以及 \(q\) 个对其的操作。操作有两种类型：
- \(1\ l\ r\ d\) —— 对于每个 \(i \in [l, r]\)，将 \(a_i\) 增加 \(d\)；
- \(2\ l\ r\) —— 问如果在 \(a\) 的第 \(l\) 到第 \(r\) 个元素组成的子数组上进行上述游戏，假设双方都采取最优策略，谁会获胜。
题解
可以发现这道题中的 \(a_i\) 具体是多少我们并不关心，我们关心的只是它的奇偶性
因为对于一个位置，如果后手有必胜策略，先手原地不动，后手继续原地不动，直到 \(a_i < 2\) ，所以我们可以直接将 \(a_i\) 写成 \((a_i - 1) \bmod 2\) ，这里为什么要 -1 ？我当时看题解的时候就很不理解这个东西，其实是因为跳到这个点上的时候会消耗一次，那么对于第一个从这个格子开始移动的人，它的值就是 \(a_i - 1\)
假设现在询问 \(1\sim n\) 先手必胜还是必败，我们可以用 \(dp[i]\) 表示 \(i\) 这个位置先手 必胜/必败（0/1）
对于 \(a_i = 1\) ，先手一定必胜
-
如果后面 \(m\) 个格子有任意必败态，那么我们直接跳过去即可
-
如果后面 \(m\) 个格子没有必败态，那我们就原地不动，直到 \(a_i = 0\) ，这时后手不得不跳，那么先手就到达必胜态
对于 \(a_i = 0\)
- 如果后面 \(m\) 个格子有任意必败态，直接跳过去，即可达到必胜态
- 否则必败
这样的话，我们可以从后往前进行转移，也就得到了 \(O(nmq)\) 的做法
我们要想办法优化 dp 转移的过程，通过上面的过程，我们发现，对于一个位置来说，我们只需要知道 它右边 \(m\) 个位置的状态中有没有必败态，并且我们只会找到最近的那个转移，所以我们只需要用一个 \(dp[i]\) 表示第 \(i\) 个位置及其后面第一个必败态，因为我们每次询问一个区间，并且我们的操作也都是序列操作，所以我们可以把他搬到线段树上进行操作
对于一个询问区间，我们需要知道的是左端点的胜负情况，所以我们维护 \(dp[i]\) 表示 \([r + 1, r + m]\) 区间内 \(r + i\) 为必败态，\([l,l+m - 1]\) 中最右边的必败态位置 \(l - 1 + j\)
注意合并的时候和初始化的时候要搞清楚就可以了
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;namespace michaele {#define ls (p << 1)#define rs (p << 1 | 1)typedef long long ll;const int N = 2e5 + 10;int n, m, q;ll a[N];struct node {int f[10];node operator + (const node &o) const {node res;for (int i = 1; i <= m + 1; i++) res.f[i] = f[o.f[i]];return res;}};struct segment {int l, r, tag;node dp[2];} t[N << 2];void update (int p) {t[p].dp[0] = t[ls].dp[0] + t[rs].dp[0];t[p].dp[1] = t[ls].dp[1] + t[rs].dp[1];}void push_down (int p) {if (t[p].tag) {t[ls].tag ^= 1;t[rs].tag ^= 1;swap (t[ls].dp[0], t[ls].dp[1]);swap (t[rs].dp[0], t[rs].dp[1]);t[p].tag = 0;}}void build (int p, int l, int r) {t[p].l = l, t[p].r = r;t[p].tag = 0;if (l == r) {for (int i = 1; i <= m; i++)t[p].dp[0].f[i] = t[p].dp[1].f[i] = i + 1;if (a[l] == 1) {//先手必胜t[p].dp[1].f[m + 1] = m + 1;t[p].dp[0].f[m + 1] = 1;} else {//先手必败t[p].dp[1].f[m + 1] = 1;t[p].dp[0].f[m + 1] = m + 1;}return;}int mid = (l + r) >> 1;build (ls, l, mid);build (rs, mid + 1, r);update (p);}void modify (int p, int l, int r) {if (l <= t[p].l && t[p].r <= r) {t[p].tag ^= 1;swap (t[p].dp[0], t[p].dp[1]);return;}push_down (p);int mid = (t[p].l + t[p].r) >> 1;if (mid >= l) modify (ls, l, r);if (mid < r) modify (rs, l, r);update (p);}node query (int p, int l, int r) {if (l <= t[p].l && t[p].r <= r) {return t[p].dp[1];}push_down (p);int mid = (t[p].l + t[p].r) >> 1;node res;if (mid >= l && mid < r) res = query (ls, l, r) + query (rs, l, r);else if (mid >= l) res = query (ls, l, r);else if (mid < r) res = query (rs, l, r);return res;}void solve () {cin >> n >> m >> q;for (int i = 1; i <= n; i++) {cin >> a[i], a[i] = (a[i] & 1) ^ 1;}build (1, 1, n);for (int i = 1; i <= q; i++) {int op, l, r;ll d;scanf ("%d%d%d", &op, &l, &r);if (op == 1) {scanf ("%lld", &d);if (d & 1) modify (1, l, r);} else {node tmp = query (1, l, r);printf ((tmp.f[m + 1] == 1) ? "Bob\n" : "Alice\n");}}}
}int main () {michaele :: solve ();return 0;
}
T5：神话
题面
给定一个 \(k\) ，要求构造一个 \(n\) 个节点的带权树，构造出来的树要满足以下条件
- \(2 \le n \le 1 \times 10^3\)
- 树上节点编号 \(\in [1, n]\)
- 每条边的边权为一个 小于 \(k\) 的正整数
- 设 \(dis_{i,j}\) 表示树上 \(i,j\) 两点间的距离，那么需要满足 \(\forall i \in [1,n - 1], k \mid dis_{i,i + 1}\)
\(2 \le k \le 10^9\)
题解
这道题是个构造神题，我们要想办法构造出一个符合上述条件的树
我们可以先考虑一个比较简单的构造，像这样
我们可以不断在两边加点，每次加两个，最大权值也在不断增大，需要加 \(k - 1\) 次，大概 \(2k\) 个点，可以拿到一些部分分
考虑如何优化这个权值不断增大的过程，现在的问题是最大值的增长速率过于缓慢，我们可以换一种方式让它的增长速率变大，如下图
我们可以发现，如果我们这样构造，那么边的大小是不断倍增的，也就可以在很少的点数内接近 \(k\)
设 \(N - 1\) 在左侧，那我们现在的目标就是在左侧表示 \(k\) 的二进制位，但是我们发现上面的倍增过程是要换端的，考虑怎样就能不换端，我们可以将它在右边加的两个点移到左边来，像这样
这样，我们就实现了不换端的倍增，如果当前二进制位为 \(0\) 那么我们就在左边加，否则换到右边
手模一下，\(5 \to 101\)
\(7 \to 111\)
在模拟的过程中，我们能发现经过预处理，每个 \(k'\) 最低两位一定是 \(01\) 或者 \(11\) 那么我们就可以将前面 5 个点先加上，然后根据第 3 位二进制位判断这时候应该往哪里加，而且我们发现，我们只能用小于 \(k\) 的这些单个的二进制位拼凑出 \(k\) ，如果 \(k\) 的二进制位形如这样 \(10000\cdots\) ，那我们是没办法拼凑出来的，所以 \(k = 2^e\) 无解
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;namespace michaele {const int N = 1e5 + 10;int pw[N], st[N], cnt, top;struct node {int x, y, z;} ans[N];void work (int k) {top = cnt = 0;int x = k;while (x) {st[++top] = (x & 1);x >>= 1;}pw[0] = 1;for (int i = 1; i <= top; i++) pw[i] = pw[i - 1] << 1;ans[++cnt] = {0, 1, 1};ans[++cnt] = {0, 2, -1};ans[++cnt] = {0, 3, 1};ans[++cnt] = {1, 4, -2};ans[++cnt] = {1, 5, 2};int p0[2] = {5, 3}, dir = 0;int p1[2] = {1, 0};for (int i = 3; i <= top; i++) {int now = st[i], la = st[i - 1];if (now != la) {dir ^= 1;//这里不能写成，因为前面cnt加了，但是放到ans里的时候它的值并不会变//ans[++cnt] = {p0[dir], cnt, -pw[i - 1]};cnt++;ans[cnt] = {p0[dir], cnt, -pw[i - 1]};cnt++;ans[cnt] = {p0[dir], cnt, pw[i - 1]};p1[dir] = p0[dir];p0[dir] = cnt;} else {if (!p1[dir]) {cnt++;ans[cnt] = {p0[dir], cnt, -pw[i - 1]};cnt++;ans[cnt] = {p0[dir], cnt, pw[i - 1]}; p1[dir] = p0[dir];p0[dir] = cnt;}cnt++;ans[cnt] = {p1[dir], cnt, -pw[i - 2]};cnt++;ans[cnt] = {p1[dir], cnt, pw[i - 2]};cnt++;ans[cnt] = {p0[dir], cnt, -pw[i - 1]};cnt++;ans[cnt] = {p0[dir], cnt, pw[i - 1]};p1[dir] = p0[dir];p0[dir] = cnt;}}}void solve () {int k, mul = 1, num = 0;cin >> k;while (!(k & 1))k >>= 1, mul <<= 1;if (k == 1) {printf ("-1\n");return;}for (int i = 3; i * i <= k; i++) {if (k % i == 0) {num = i;break;}}if (num == 0) num = k;mul *= k / num;work (num);cout << cnt + 1 << endl;for (int i = 1; i <= cnt; i++) {auto tmp = ans[i];if (tmp.x > tmp.y) swap (tmp.x, tmp.y);if (tmp.x == 0) tmp.x = cnt + 1;printf ("%d %d %d\n", tmp.x, tmp.y, (tmp.z + num) % num * mul);}}
}int main () {// freopen("myth.in", "r", stdin);// freopen("myth.out", "w", stdout);michaele :: solve ();return 0;
}