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。然后，我们在左子树和右子树中分别查询权值，并根据当前轮数的奇偶性返回对应的值。如果当前轮数是奇数，表示小  正在操作，我们返回两个权值中的较小值；否则，表示小  正在操作，我们返回两个权值中的较大值。

主函数流程

1. 首先，我们读取输入数据，包括初始集合的大小n，操作轮数m，初始集合a和每轮的参数b。
2. 接下来，我们将初始集合中的所有数字插入到树中。
3. 最后，我们查询并输出在所有轮数结束后的权值。

由于每次决策都会把集合分成两个不交的集合，因此每个元素在递归中只会被处理一次。因此，这个算法的时间复杂度为。

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;}