1. 遥控赛车
首先，每次移动相当于移动 米，但是浮点数不好算
我们可以把单位都换成分米，也就是每次移动 分米，目标距离为 分米
那么方案很简单，先一直向前移动到目标点，然后用 前进+后退 反复来回即可
那么显然在移动到目标点后，我们还需要偶数次的操作次数，所以直接判断 是否是偶数即可
注意要先判断 ，根本走不到目标距离那就是
#include<bits/stdc++.h> usingnamespacestd; intmain(){ freopen("car.in", "r", stdin); freopen("car.out", "w", stdout);int n, m;cin >> n >> m; m = m * 10;if(n < m) {cout << "No!"; } else { if((n - m) % 2 == 0) {cout << "Yes!"; } else {cout << "No!"; } }return0; }
2. 好冷好热好冷好热
如果按照时间模拟，直接维护可以达到的温度区间即可。
每一秒 ，然后如果有顾客进来就和顾客的 取个交就好。
过程中如果 了就直接结束就好。
考虑时间范围是 的时候怎么办。
因为人数只有 个，所以中间大段长度为 的无人时间，可以直接 就好，问题就解决了。
#include<bits/stdc++.h> usingnamespacestd;constint N = 1e5 + 3;structgyq {int t, l, r;} a[N];boolcmp(gyq a, gyq b){return a.t < b.t;}voidwork(){int n, m;scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d %d %d", &a[i].t, &a[i].l, &a[i].r); } sort(a + 1, a + n + 1, cmp);int l = m, r = m, t = 0;for (int i = 1, j; i <= n; i = j) {int nl = a[i].l, nr = a[i].r;// 合并相同时间的区间for (j = i + 1; j <= n && a[j].t == a[i].t; j++) {if (a[j].l > nl) nl = a[j].l;if (a[j].r < nr) nr = a[j].r; }// 如果区间无效if (nl > nr) {puts("NO");return; }// 扩展可能的时间范围int tf = a[i].t - t; l -= tf; r += tf;// 与当前时间区间取交集if (l < nl) l = nl;if (r > nr) r = nr;// 如果区间无效if (l > r) {puts("NO");return; } t = a[i].t; }puts("YES");return;}intmain(){ freopen("temp.in", "r", stdin); freopen("temp.out", "w", stdout);int T;scanf("%d", &T);while (T--) { work(); }return0;}
3. 最大子段和
发现答案只有三种情况：在前半段，在后半段，由前半段的最大后缀和后半段的最大前缀拼出来。
记 表示以 的结尾的前缀的答案， 表示以 开始的后缀的答案， 表示以 结尾的前缀的最大后缀， 表示以 开始的后缀的最大前缀。
则有
那么删去 以后的答案为 。
#include<bits/stdc++.h>#define int long longusingnamespacestd;int ans1[100010], mx1[100010], ans2[100010], mx2[100010];int n, a[100010];signedmain(){ freopen("big.in", "r", stdin); freopen("big.out", "w", stdout);scanf("%lld", &n);for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);for (int i = 1; i <= n; i++) { mx1[i] = max(mx1[i - 1], 0ll) + a[i]; ans1[i] = max(ans1[i - 1], mx1[i]); }for (int i = n; i >= 1; i--) { mx2[i] = max(mx2[i + 1], 0ll) + a[i]; ans2[i] = max(ans2[i + 1], mx2[i]); } ans1[0] = ans2[n + 1] = mx1[0] = mx2[n + 1] = -1e18;for (int i = 1; i <= n; i++)printf("%lld ", max(max(ans1[i - 1], ans2[i + 1]), mx1[i - 1] + mx2[i + 1]));}
4. 搬砖
做法一
设 ，若 或 ，可以证明删去这两列后的状态等价于原状态。
所以我们不断地消去可以消去的列即可，使用链表 + priority_queue 维护。
时间复杂度 。
做法二
假设我们只考虑 的奇偶性，横着放砖时不考虑 相等的限制，那么我们可以进行的操作就只有把两个相邻的相同的数取反。
注意到若一个相同的数的连续段长度为偶数，我们就能通过操作使得其全部为 或全部为 。
那么如果两个 之间有偶数个 ，我们就可以把这两个 和这偶数个 合成一段，并且这段的长度也是偶数，于是我们可以忽略这一段。
这类似于括号匹配的过程。如果对于 ，奇偶性为 的位置中下标为奇数和偶数的个数相等的话，就存在匹配，即存在解。
下面我们考虑怎么最小化 。枚举 的奇偶性，则我们可以钦定所有位置都要变为 ，根据上面的匹配过程容易计算出每个位置至少要放多少块横着的砖 ，而放竖着的砖肯定是用于补齐高度，所以答案就是 。
时间复杂度 。
#include<bits/stdc++.h>usingnamespacestd;constint N = 2e6 + 10;int n, mx, ans, a[N], b[N], top, st[N];intmain(){ freopen("brick.in", "r", stdin); freopen("brick.out", "w", stdout);scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]); mx = max(mx, a[i]); }if (n == 1) {printf("%d\n", a[1]);return0; } ans = mx;for (int i = 1; i <= n; ++i) { b[i] = (mx - a[i]) & 1; }for (int i = 1, j = 0; i <= n; ++i) {if (top && ((i - st[top]) & 1) && b[i] == b[st[top]]) { ans = max(ans, max(a[st[top]], a[i]) + j);if (top > 1) { j -= b[st[top - 1]] != b[st[top]]; } --top; } else { st[++top] = i;if (top > 1) { j += b[st[top - 1]] != b[st[top]]; } } }if ((n & 1) && top == 1) { ans += (ans - a[st[top]]) & 1; --top; }printf("%d\n", top ? -1 : ans);return0;}
5. 游戏
题意解释
小 和小 两人轮流处理一个整数集合，第 轮中，集合 根据是否为 倍数被分割为两部分，此时可以保留下其中一部分，扔掉另一部分，最终m轮后剩下数字和即为权值，小 希望最大化权值，小 则反之，博弈状态下问最终结果。
考察知识点：
搜索、思维
20%~40% 直接暴力
考虑暴力枚举每个人的决策，同时维护在前 轮决策下，当前的 集合，如果 ，那么立刻返回 。时间复杂度是 的，因为每次决策都会把 分成两个不交的集合，每个元素都只会向一侧递归，一共递归 层。
具体地，小 希望权值最小，而小 希望权值最大，因此在每一轮操作中，他们都会尽可能地选择最优的策略。我们可以构建一个数据结构来模拟每轮操作后的状态。为了满足这个需求，我们选择使用二叉树来构建这个模型。
数据结构设计
在代码中，我们定义了一个二叉树Tree，其中lc和rc数组分别表示树中每个节点的左子节点和右子节点。sum数组存储当前子树中所有节点的权值和。
插入操作
insert方法用于在树中插入一个新值。首先，我们检查当前节点是否存在，如果不存在，我们就创建一个新节点。然后，根据当前深度和给定的轮数参数b，我们决定应该在左子树还是右子树中继续插入。这里的逻辑是，如果当前值是b[dep]的倍数，我们就在右子树中继续插入，否则在左子树中插入。
查询操作
query方法用于查询在当前轮数下的最大或最小权值。首先，我们检查当前节点是否存在，如果不存在，直接返回0。然后，我们在左子树和右子树中分别查询权值，并根据当前轮数的奇偶性返回对应的值。如果当前轮数是奇数，表示小 正在操作，我们返回两个权值中的较小值；否则，表示小 正在操作，我们返回两个权值中的较大值。
主函数流程
- 首先，我们读取输入数据，包括初始集合的大小
n，操作轮数m，初始集合a和每轮的参数b。
由于每次决策都会把集合分成两个不交的集合，因此每个元素在递归中只会被处理一次。因此，这个算法的时间复杂度为。
100% 结论分析
考虑对于先手来说，每次进行决策，如果他选择集合大小更小的那一侧，那么每次操作集合大小至少减半，只需要 次操作就必定可以使答案为 ，考虑上“两人是轮流操作”的这个因素，所以当 的时候，答案不可能大于 。同理答案也不可能小于 （因为后手可以采取同样的策略），因此答案一定是 。于是只有在的时候才考虑进行搜索，保证了时间复杂度为 。
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;// 定义最大的集合和操作轮数constexprintN(20005);constexprintM(200005);int n, m;ll a[N], b[M], rt;// 定义一棵二叉树用于存储数据和进行查询structTree { ll sum[N * 30], lc[N * 30], rc[N * 30], tot; // lc, rc表示左右子节点// 插入数据到树中voidinsert(ll& p, ll dep, ll val){if (!p) p = ++tot;if (dep > m) return sum[p] += val, void(); insert((val % b[dep] ? lc : rc)[p], dep + 1, val); // 根据倍数进行左右分支 }// 查询权值ll query(ll p, ll dep){if (!p) return0ll;if (dep > m) return sum[p]; ll foo = query(lc[p], dep + 1); ll bar = query(rc[p], dep + 1);// 根据操作轮数的奇偶性返回权值return (dep & 1) ? min(foo, bar) : max(foo, bar); }} tr;intmain(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout);// 输入数据scanf("%d%d", &n, &m);if (m > 28) returnprintf("0\n"), 0; // 当操作次数超过28轮时，答案是0for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);for (int i = 1; i <= m; ++i) scanf("%lld", &b[i]);// 将数据插入到树中for (int i = 1; i <= n; ++i) tr.insert(rt, 1ll, a[i]);// 输出查询的权值printf("%lld\n", tr.query(rt, 1ll));return0;}
