Codeforces Round 1082 (Div. 2)A,B,C1,C2,D,E,F,G1,G2个人题解
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能够执行的移动构成。
思路
![
2.png]]
在草稿纸上画一下图，就可以发现非常明显的规律：
所有点都坐落在一些斜率为-1的平行线段上，这些线段所对应的直线可以表示为：
\
为了将直线限制为线段，再对\(x\)加以限制：
\\]
直接判断即可
代码
#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();
}C1. 失落的文明（简单版）
双指针
这是问题的简单版。两个版本之间的区别在于，在这个版本中，你只需为一个序列计算一个值。只有当你解决了这个问题的所有版本后，才能进行 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+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 == 'b')cout << "NO\n";
else {
for (int i = (n & 1);i < n - 1;i += 2) {
if (s == s && s != '?') {
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();
}D. 记忆数字
数学 #构造
有 \(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;
void solve() {
int n;cin >> n;
string s;cin >> s;
rep(i, 0, 3) {
rep(j, 0, 1) {
rep(k, 0, 3)e = 0;
}
}
e = e = 1;
e = 1;e = 1;
e = 1;e = 1;
e = e = 1;
vector<bool>dp(4);
if (n & 1)dp = 1;
else dp = 1;
rep(pos, 0, n - 1) {
vector<bool>ndp(4);
rep(i, 0, 3) {
if (!dp)continue;
if (s == 'a') {
rep(nxt, 0, 3) {
if (e)ndp = 1;
}
} else if (s == 'b') {
rep(nxt, 0, 3) {
if (e)ndp = 1;
}
} else {
rep(nxt, 0, 3) {
if (e)ndp = 1;
if (e)ndp = 1;
}
}
}
dp = ndp;
}
rep(i, 0, 3) {
if (dp) {
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();
}G2. 单调黑白矩阵 (困难版)
数学
这是该问题的困难版本。两个版本的区别在于，在这个版本中，\(n\) 和 \(q\) 的限制非常大。只有当你解决了该问题的所有版本后，才能进行 hack。
一个大小为 \(n \times n\) 的黑白矩阵是指一个具有 \(n\) 行和 \(n\) 列的矩阵，其中每个单元格都被涂成了黑色或白色。令黑白矩阵 \(C\) 中单元格 \((r, c)\) 的颜色表示为 \(C\)。
如果一个矩阵 \(C\) 满足以下条件，我们就称其为单调的：
不存在两行 \(1 \le i < j \le n\) 和两列 \(1 \le k < l \le n\) 满足以下三个条件：
[*]\(C = C\)；
[*]\(C = C\)；
[*]\(C \neq C\)。
现有一个大小为 \(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 + 1\)。
[*]sumR 增加 \(2 \times sufR + 1] + 1\)。（其中 \(sufR\) 即 \(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 = -5;
int last = -5, ans = 0;
rep(i, 1, n) {
cin >> a;
if (a > a + 1 || a <= last) {
ans++;
last = a;
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();
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 谢谢楼主提供！ 东西不错很实用谢谢分享 热心回复！ 东西不错很实用谢谢分享 感谢分享
页:
[1]