A. 跑酷设计
数学
今天，Alex想为Steve设计一个跑酷训练场。一个跑酷训练场是平面上整数坐标的序列 \(p_0→p_1→…→p_k\)。其中，相邻的一对坐标称为一次移动，记作 \(p_{i-1}→p_i\)。
Alex知道Steve只能执行以下类型的移动：
- \((x_i,y_i)→(x_i+2,y_i+1)\)；
- \((x_i,y_i)→(x_i+3,y_i)\)；
- \((x_i,y_i)→(x_i+4,y_i-1)\)。
注意Steve不会执行任何其他类型的移动。例如，Steve可以执行 \((0,0)→(2,1)\) 和 \((2,1)→(5,1)\)，但绝不会执行诸如 \((2,1)→(3,2)\)、\((3,0)→(5,-1)\) 或 \((4,-1)→(6,-1)\) 的移动（即使它们看起来可能很简单）。
你被给定了平面上的一个整数坐标 \((x,y)\)。
请判断是否存在一个跑酷训练场 \(q_0,q_1,…,q_k\) 满足以下条件：
- \(q_0=(0,0)\)；
- \(q_k=(x,y)\)；
- 该跑酷训练场仅由Steve能够执行的移动构成。
思路
![[Pasted image 2026022510284
2.png]]
在草稿纸上画一下图，就可以发现非常明显的规律：
所有点都坐落在一些斜率为-1的平行线段上，这些线段所对应的直线可以表示为：
\[y=-x+k\ ,\ k\%3==0\ ,\ k\in Z\]
为了将直线限制为线段，再对\(x\)加以限制：
\[x\in[2k,4k]\]
直接判断即可
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define int ll
- #define rep(i,a,b) for(int i=(a);i<=(b);i++)
- #define per(i,a,b) for(int i=(a);i>=(b);i--)
-
-
- void solve() {
- int x, y;cin >> x >> y;
- if ((x + y) % 3 != 0)cout << "NO\n";
- else {
- int k = (x + y) / 3;
- if (x >= 2 * k && x <= 4 * k)cout << "YES\n";
- else cout << "NO\n";
- }
- }
-
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- int t = 1;
- cin >> t;
- while (t--)solve();
- }
双指针
这是问题的简单版。两个版本之间的区别在于，在这个版本中，你只需为一个序列计算一个值。只有当你解决了这个问题的所有版本后，才能进行 hack。
我们定义一个生成包含 \(m+k\) 个整数的序列的算法如下：
首先，接收一个包含 \(m\) 个整数的序列 \(x\) 作为输入。如果 \(k=0\)，立即终止并返回序列 \(x\)。
然后，选择任意索引 \(1 \leq i \leq |x|\)，并在元素 \(x_i\) 之后立即插入 \((x_i+1)\)。
如果 \(x\) 中恰好包含 \(m+k\) 个整数，则终止并返回序列 \(x\)。否则，返回第二步。
爱丽丝知道，一个古代文明曾使用这个算法来安全地隐藏他们的秘密。爱丽丝想了解他们想要隐藏的知识，但从算法的输出推断输入并非易事。
给定一个包含 \(n\) 个整数的序列 \(a\)，确定可以给定作为算法输入以生成 \(a\) 的最短序列的长度。
思路
经过观察，每个元素都有一个位于左侧、可以生成自己的最小元素，我们把这个元素叫做关键元素
以样例为例子：
\[\begin{align}\begin{array}{l}&9&&8&&9&&2&&3&&4&&4&&5&&3 \\&9&\bigg|&8&&9&\bigg|&2&&3&&4&&4&&5&&3\end{array}\end{align}\]
我们可以把序列拆分为三段，每段内的元素的关键元素就是这段的左端点，而左端点本身的关键元素不存在，可以记作0
我们从左到右遍历序列，将当前的关键元素记作\(last\)
如果发现\(a>a[i-1]+1\)或者\(a\leq last\)，那么当前元素都不能由\(last\)生成，需要新开一个段
此时对关键元素为\(last\)的段进行结算，\(ans++\)，更新\(last=a\)即可
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define int ll
- #define rep(i,a,b) for(int i=(a);i<=(b);i++)
- #define per(i,a,b) for(int i=(a);i>=(b);i--)
-
-
- void solve() {
- int n;cin >> n;
- string s;cin >> s;
- if ((n & 1) && s[0] == 'b')cout << "NO\n";
- else {
- for (int i = (n & 1);i < n - 1;i += 2) {
- if (s[i] == s[i + 1] && s[i] != '?') {
- cout << "NO\n";
- return;
- }
- }
- cout << "YES\n";
- }
- }
-
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- int t = 1;
- cin >> t;
- while (t--)solve();
- }
数学 #构造
有 \(2n\) 张卡片，上面写着数字 \(1, 1, 2, 2, \dots, n, n\)。换句话说，对于所有 \(j=1, 2, \dots, n\)，都恰好有 \(2\) 张写着数字 \(j\) 的卡片。每张卡片的正面只写有一个数字。
你将玩一个翻牌游戏。最初，所有 \(2n\) 张卡片都背面朝上（没有数字的一面）放置。在每一轮中，你恰好翻开两张卡片。如果这两张卡片的数字相同，你就丢弃这两张卡片；否则，你将它们翻回原来的位置。当所有 \(2n\) 张卡片都被丢弃时，你就赢了。请注意，你不需要同时翻开两张卡片，因此你可以在看到第一张卡片的数字后，再决定第二张卡片的选择。
考虑以下用于玩游戏的“贪心”算法。最初，\(2n\) 张卡片被随机排列成一排。然后你在每一轮的策略如下：
- 如果有两张你之前翻开过且数字相同的卡片，翻开这两张卡片。
- 否则，翻开目前为止第一张\(^*\)从未被翻开过的卡片。假设这张卡片上的数字是 \(x\)。
- 随后，如果还有另一张你之前翻开过且数字为 \(x\) 的卡片，翻开那张卡片。
- 否则，翻开目前为止（包括本轮）第一张\(^*\)从未被翻开过的卡片作为第二张。
可以证明，该算法的策略在每一轮都是唯一确定的。
你必须解决关于上述算法的以下问题：
给定 \(n\) 和 \(k\)，请找到一种 \(2n\) 张卡片的排列方式，使得上述算法恰好需要 \(k\) 轮才能赢得游戏。
此外，如果不存在这样的排列方式，请报告。
思路
先考虑最少的轮数和最多的轮数
如果按照\(1,1,2,2,3,3,\dots ,n,n\)的方式进行排列，此时轮数最少，答案为\(n\)
如果按照\(2,1,3,2,4,3,\dots ,n,n-1,n,1\)排列，此时轮数最多，答案为\(n+n-1\)
为什么这样排轮数最多呢？
对于每个数字，选取与他相同的数字必定会消耗一轮，也就是消耗\(n\)轮，剩余的操作都是多余的操作，我们需要尽可能最大化多余的操作数
因此必定不能让玩家轻易地选到两个相同的
按照上述方法排列，每次必须要翻开两个新的卡才会发现一对相同的（1次多余操作），并且翻新卡的操作与选取相同的操作互不影响，则两两选会多出n-1次多余操作，这样能够使得多余操作最大化
因此可以先对\(k\)的范围进行判断，\(n\leq k\leq 2n-1\)
接下来需要想办法控制多余操作次数
观察到，如果记\(f(n)\)为最大化操作次数后长度为\(n\)的序列，那么\(f(n),f(n-1),f(n-2)\dots\)存在递推，他们的前缀是相同的
比如：
\[\begin{align}&f(4)=\{ 2,1,3,2,4,3,4,1 \}\\ \\&f(5)=\{ 2,1,3,2,4,3,5,4,5,1 \}\\ \\&f(6)=\{ 2,1,3,2,4,3,5,4,6,5,6,1 \}\end{align}\]
那么，如果想要在\(n=6\)的时候只多操作3次，那么其实等价于在\(f(4)\)的基础上最小化操作次数，因为\(f(4)\)的多余操作数为3：
\[\{ 2,1,3,2,4,3,4,1,5,5,6,6 \}\]
因此我们可以通过改变序列前缀的方式来控制多余操作次数，后缀直接将两个相同元素放一起就行
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define int ll
- #define rep(i,a,b) for(int i=(a);i<=(b);i++)
- #define per(i,a,b) for(int i=(a);i>=(b);i--)
-
- bool e[4][2][4];
-
- void solve() {
- int n;cin >> n;
- string s;cin >> s;
- rep(i, 0, 3) {
- rep(j, 0, 1) {
- rep(k, 0, 3)e[i][j][k] = 0;
- }
- }
- e[0][0][1] = e[0][0][2] = 1;
- e[1][0][3] = 1;e[1][1][0] = 1;
- e[2][0][3] = 1;e[2][1][0] = 1;
- e[3][1][1] = e[3][1][2] = 1;
- vector<bool>dp(4);
- if (n & 1)dp[0] = 1;
- else dp[1] = 1;
- rep(pos, 0, n - 1) {
- vector<bool>ndp(4);
- rep(i, 0, 3) {
- if (!dp[i])continue;
- if (s[pos] == 'a') {
- rep(nxt, 0, 3) {
- if (e[i][0][nxt])ndp[nxt] = 1;
- }
- } else if (s[pos] == 'b') {
- rep(nxt, 0, 3) {
- if (e[i][1][nxt])ndp[nxt] = 1;
- }
- } else {
- rep(nxt, 0, 3) {
- if (e[i][0][nxt])ndp[nxt] = 1;
- if (e[i][1][nxt])ndp[nxt] = 1;
- }
- }
- }
- dp = ndp;
- }
- rep(i, 0, 3) {
- if (dp[i]) {
- cout << "YES\n";
- return;
- }
- }
- cout << "NO\n";
- }
-
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- int t = 1;
- cin >> t;
- while (t--)solve();
- }
数学
这是该问题的困难版本。两个版本的区别在于，在这个版本中，\(n\) 和 \(q\) 的限制非常大。只有当你解决了该问题的所有版本后，才能进行 hack。
一个大小为 \(n \times n\) 的黑白矩阵是指一个具有 \(n\) 行和 \(n\) 列的矩阵，其中每个单元格都被涂成了黑色或白色。令黑白矩阵 \(C\) 中单元格 \((r, c)\) 的颜色表示为 \(C[r, c]\)。
如果一个矩阵 \(C\) 满足以下条件，我们就称其为单调的：
不存在两行 \(1 \le i < j \le n\) 和两列 \(1 \le k < l \le n\) 满足以下三个条件：
- \(C[i, k] = C[j, l]\)；
- \(C[j, k] = C[i, l]\)；
- \(C[i, k] \neq C[j, k]\)。
现有一个大小为 \(n \times n\) 的黑白矩阵 \(M\)，最初所有单元格均为白色。请处理 \(q\) 个如下类型的查询：
- \(r \ c\)：将矩阵 \(M\) 中单元格 \((r, c)\) 的颜色修改为黑色。然后，判断 \(M\) 是否为单调矩阵。
对于每个查询，保证单元格 \((r, c)\) 在查询前的颜色为白色。
请注意，更新是持久的。换句话说，一个查询中的颜色修改会影响后续的所有查询。
思路
本题思路是询问\(Gemini\)得来，其中有许多组合数学的专业知识
在 Hard 版本中，\(N, Q\) 达到了 \(2 \cdot 10^6\)，简单版的 Bitset \(O(QN/64)\) 已经彻底跑不动了，我们需要一个 \(O(N+Q)\) 的“降维打击”做法。
破题点：利用平方和作为“指纹”判定单调性
这里涉及到一个组合数学的硬核结论：Gale-Ryser 定理。
- 理论值：共轭分拆 (Conjugate Partition)
设行黑格数序列为 \(R\)。我们定义一个理论上的列分布 \(R^*\)：\(R^*_k\) 表示“黑格子数量 \(\ge k\) 的行数”。
- 定理推论：矩阵单调 \(\iff\) 实际的列黑格数序列 \(C\) 是理论序列 \(R^*\) 的一个排列。
- 指纹识别：主控性与平方和
在数学上，列分布 \(C\) 的“集中度”永远不会超过 \(R^*\)。
- 只要列分布的平方和 \(\sum C_i^2\) 达到了理论上限 \(\sum (R^*_i)^2\)，那么 \(C\) 就一定是 \(R^*\) 的一个排列，矩阵也就一定是单调的。
具体维护：
我们只需要实时维护两个“指纹”：
- sumC：实际每一列黑格数的平方和 \(\sum (cntC_j)^2\)。
- sumR：理论共轭序列的平方和 \(\sum (R^*_k)^2\)。
利用平方差公式 \((x+1)^2 - x^2 = 2x+1\)，我们可以在 \(O(1)\) 时间更新：
- 涂黑 \((r, c)\) 时：
- sumC 增加 \(2 \times cntC[c] + 1\)。
- sumR 增加 \(2 \times sufR[cntR[r] + 1] + 1\)。（其中 \(sufR[k]\) 即 \(R^*_k\)，表示当前黑格数 \(\ge k\) 的行数）。
只要 sumC == sumR，答案就是 YES。
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define int ll
- #define rep(i,a,b) for(int i=(a);i<=(b);i++)
- #define per(i,a,b) for(int i=(a);i>=(b);i--)
-
-
- void solve() {
- int n;cin >> n;
- vector<int>a(n + 1);
- a[0] = -5;
- int last = -5, ans = 0;
- rep(i, 1, n) {
- cin >> a[i];
- if (a[i] > a[i - 1] + 1 || a[i] <= last) {
- ans++;
- last = a[i];
- continue;
- }
- }
- cout << ans << '\n';
- }
-
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- int t = 1;
- cin >> t;
- while (t--)solve();
- }
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
