目录
写在前面
比赛地址：https://codeforces.com/contest/1844。
什么？你怎么知道我连 C 都没过掉了一伯伍拾昏？
吐槽一下马娘前期甚至动画第一季都没出之前的很多个人角色曲，听起来就是很无聊的动漫 op 风。比如进王的这首：
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=557581172&auto=0&height=66" width="330"></iframe>感觉给哪个笨蛋阳光系角色都能用。但游戏出了之后的所有角色曲就有很强的角色特点。比如多伯老师的这首：
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1918915928&auto=0&height=66" width="330"></iframe>太阳神的辣妹儿风：
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1992357134&auto=0&height=66" width="330"></iframe>千代汪的软萌：
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1929090405&auto=0&height=66" width="330"></iframe>啊，至福——
A
\(a+b\) Problem。
B
显然有贡献的区间必须包含 1，为使尽可能多的区间包含 1 则应将其放到最中间。
在此基础上，一个包含 1 的区间无贡献则必须包含 2、3，则可以将 2、3 放到两端尽量避免这种情况出现。
发现此时除了整个数列之外所有包含 1 的区间均有贡献，显然已是最优解。
C
我是傻逼。
byd 什么都贪只会害了你！
\(T\) 组数据，每组数据给定一长度为 \(n\) 的数列 \(c\)，现在要对该数列进行若干次操作，每次操作可以选择数列中的某个数 \(c_i\)，将 \(c_{i - 1}, c_{i}, c_{i + 1}\) 从数列中删去，再将 \(c_{i - 1} + c_{i + 1}\) 插入到三者原来的位置。若 \(c_{i - 1}\) 或 \(c_{i + 1}\) 不存在则仅将 \(c_i\) 删去。
经过若干次操作后数列中仅剩一个数，最大化这个剩余的数的值。
\(1\le T\le 10^4\)，\(1\le n\le 2\times 10^5\)，\(-10^9\le c_i\le 10^9\)，\(\sum n\le 2\times 10^5\)。
1S，256MB。
首先猜到肯定和奇偶性有关。
多手玩一下可以发现，若 \(i\) 为偶数，将 \(c_i\) 删去后，位于奇数位置的 \(c_{i - 1}\) 与 \(c_{i + 1}\) 被合并，在新的数列中 \(c_{i - 1} + c_{i + 1}\) 仍然位于奇数位置。则对于两个分别位于奇数和偶数位置的数，不存在一种方案可以使它们的贡献可以合并从而保留到最后的答案中。
于是仅考虑分别合并原数列中奇数和偶数位置的贡献。可以通过在两端删数直接抛弃某些数的贡献，则答案为：
\[\max\left\{ \sum_{1\le i\le n, i\operatorname{odd}} \max(c_{i}, 0), \sum_{1\le i\le n, i\operatorname{even}}\max{(c_i, 0)}\right\} \]D
\(T\) 组数据，每组数据给定一个整数 \(n\)，要求构造一个长度为 \(n\) 的仅包含小写字母的字符串 \(s\)，要求将该字符串按照从上到下从左到右的顺序填充进一个 \(w\times h(w\times h = n)\) 的矩阵后，满足每个格子内的字符与上下左右格子中的字符均不相同，且字符串中的字符种类数最少。
\(1\le T\le 10^4\)，\(1\le n\le 10^6\)，\(\sum n\le 10^6\)。
2S，256MB。
设 \(n\) 的因数为 \(c_1, c_2, \dots, c_k\)，则对于 \(s_i\)，与它不同的位置应为 \(\{x | x = s_i \plusmn c_j, 1\le j\le k\}\)。
放到一个 \(\frac{n}{c_j}\times c_j\) 的矩阵里考虑一下，因为 \(c_j\) 中包含 \(n\)，则一个字符串合法等价于相邻两行同一列的位置不同，即 \(i \bmod{c_j}\) 相同的 \(s_i\) 不同。
则一种构造方案是令 \(s_i:=i\bmod c\)，\(c\) 为最小的不能整除 \(n\) 的数。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 1e6 + 10;
//=============================================================
char ans[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
int n = read(), c = 1;
while (c < n && n % c == 0) ++ c;
for (int i = 1; i <= n; ++ i) ans[i] = (i - 1) % c + 'a';
ans[n + 1] = 0;
printf("%s\n", ans + 1);
}
return 0;
}
E
\(T\) 组数据，每组数据给定整数 \(n, m, k\)，对于一个 \(n\times m\) 的矩阵，若满足下列三条条件，则称之为“妈妈生的”：
- 矩阵每个格子中均为字母
A, B, C其中之一。- 每个 \(2\times 2\) 的小矩形中均包含
A, B, C三个字母。- 两个相邻格子中字母不同。
在此基础上给定 \(k\) 个限制，每组限制均为 \((x_1, y_1, x_2, y_2)\) 的形式，表示格子 \((x_1, y_1)\) 与 \((x_2, y_2)\) 中的字母相同。保证 \((x_1, y_1)\) 与 \((x_2, y_2)\) 为一个 \(2\times 2\) 的小矩形对角线上的两个格子。
\(1\le T\le 10^3\)，\(2\le n, m\le 2 \times 10^3\)，\(1\le k\le 4\times 10^3\)，对于每条限制保证 \(x_1\le x_2\)，所有限制互不相同，\(\sum n,\sum m\le 2\times 10^3\)，\(\sum k\le 4\times 10^3\)。
1S，256MB。
手玩一下先。什么构造场妈的。
由给定条件，相邻的格子中字母不同，且每个 \(2\times 2\) 的小矩形中均包含三个字母，则每个小矩形中一定有一条对角线上的字母相同，并且另一条对角线上字母不同。
把 A, B, C 抽象成 \(0, 1, 2\)，将矩阵格子看做结点，相邻结点连边，尝试从图论和数学方面找找关系，对于一个 \(2\times 2\) 的小矩阵中的两条水平的边，记其边权值为右侧元素减去左侧元素模三的值；同理记两条竖直的边权值为下侧元素减去上侧元素模三的值。由于相邻的两个格子值不同，则边权值仅有 1 或 2 两种取值。分别比较两种边的边权值……您猜怎么着？相等！真是绝了！
我们将同一行的节点向下引出的竖直边称为一组竖直边，将同一列的结点向右引出的水平边称为一组水平边，显然水平边共有 \(m - 1\) 组，竖直边共有 \(n - 1\) 组。根据传递性，则一个矩阵是“妈妈生的”，等价于每组竖直边中边权值相等，每组水平边中边权值相等。
再考虑 \(k\) 条限制，发现它们也能等价成边权值相同的形式：对于一条限制 \((x_1, y_1, x_2, y_2)\)：若 \(x_2 = x_1 + 1, y_2 = y_1 + 1\)，则小矩阵中水平边权与竖直边权不同；若 \(x_2 = x_1 + 1, y_2 = y_1 - 1\)，则小矩阵中水平边权与竖直边权相同。
问题变为给每组边赋边权值使得满足上述条件，再抽象成 \(n + m - 2\) 个存在两个变量相等/不等关系的布尔变量赋值的问题，将上述限制看成 \(k\) 条双向边直接 DFS 黑白染色即可。
总复杂度 \(O(n + m + k)\)。
也可以再直接将每条边看做结点直接对节点数为 \(O(n\times m)\) 的图做黑白染色……太暴力了没卡罢了。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 1e4 + 10;
const int kM = 2e4 + 10;
//=============================================================
int n, m, k, flag, col[kN];
int edgenum, head[kN], v[kM], w[kM], ne[kM];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Add(int u_, int v_, int w_) {
v[++ edgenum] = v_;
w[edgenum] = w_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Init() {
n = read(), m = read(), k = read();
edgenum = 0;
for (int i = 1; i <= n - 1 + m - 1; ++ i) {
head[i] = 0;
col[i] = -1;
}
flag = 0;
for (int i = 1; i <= k; ++ i) {
int x1 = read(), y1 = read(), x2 = read(), y2 = read(), miny = std::min(y1, y2);
if (x2 == x1 + 1 && y2 == y1 + 1) {
Add(x1, n - 1 + miny, 1), Add(n - 1 + miny, x1, 1);
} else {
Add(x1, n - 1 + miny, 0), Add(n - 1 + miny, x1, 0);
}
// printf("---%d %d\n", x1, n - 1 + miny);
}
}
void Dfs(int u_, int col_) {
if (col[u_] != -1) {
if(col_ != col[u_]) flag = 1;
return ;
}
col[u_] = col_;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i], w_ = w[i];
Dfs(v_, col_ ^ w_);
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
for (int i = 1; i <= n - 1 + m - 1; ++ i) {
if (col[i] == -1) Dfs(i, 0);
if (flag) break;
}
printf("%s\n", flag ? "NO" : "YES");
}
return 0;
}
F1
\(T\) 组数据，每组数据给定整数 \(n, c\)，给定一长度为 \(n\) 的数列 \(a\)，要求将数列重新排列得到数列 \(b\)，最小化权值：
\[\sum_{i = 1}^{n - 1} \left| b_{i + 1} - b_{i} -c\right| \]求数列 \(b\)。如果存在多种数列 \(b\) 的形态，则输出字典序最小的形态。
\(1\le T\le 10^3\)，\(1\le n\le 5\times 10^3\)，\(-10^9\le c\le 10^9\)，\(1\le a_i \le 10^9\)，\(\sum n\le 5\times 10^3\)。
3S，256MB。
\(c=0\)？太典了，直接升序排序，既权值最小又字典序最小。
\(c\ge 0\)？发现还是升序排序就可以。可以画个图看下，如果出现非升序的峰谷一定不会更优。
于是考虑 \(c\le 0\)。由 \(c\ge 0\) 可类推降序排序时可以取到权值的最小值，考虑在此基础上进行调整使得字典序最小。
考虑贪心地往每个位置填数来构造 \(b\)。对于一个已经确定的 \(b\) 的前缀，显然将剩余的 \(a\) 中的数降序排序扔到后面一定可以最小化权值，考虑是否可以将剩余的 \(a\) 中的数其中某个较小的数调整到最前面，其余仍然降序排序。发现调整后仅有被调整的数和当前最大的数附近的贡献被影响了，可以 \(O(1)\) 算，于是直接从小到大枚举每个数尝试进行调整，并记录调整前后对权值贡献的差值。当差值为 0 说明可在不影响权值情况下使字典序更小，贪心地调整即可。
每次填数都需要 \(O(n)\) 地检查是否可以调整并 \(O(n)\) 地后移元素，总复杂度 \(O(\sum n^2)\) 级别。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 5e3 + 10;
//=============================================================
int n, c, a[kN], ans[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool cmp(int fir_, int sec_) {
return fir_ > sec_;
}
int Calc(int lth_, int pos_) {
int ret = -abs(a[pos_] - a[pos_ - 1] - c);
if (pos_ < n) ret += -abs(a[pos_ + 1] - a[pos_] - c) + abs(a[pos_ + 1] - a[pos_ - 1] - c);
if (lth_ > 1) ret += -abs(a[lth_] - a[lth_ - 1] - c) + abs(a[pos_] - a[lth_ - 1] - c);
ret += abs(a[lth_] - a[pos_] - c);
return ret;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), c = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
if (c >= 0) {
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++ i) printf("%d ", a[i]);
printf("\n");
continue;
}
std::sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++ i) {
int pos = i;
for (int j = n; j > i; -- j) {
if (!Calc(i, j)) {
pos = j;
break;
}
}
for (int j = pos; j > i; -- j) std::swap(a[j], a[j - 1]);
}
for (int i = 1; i <= n; ++ i) printf("%d ", a[i]);
printf("\n");
}
return 0;
}
F2
题面同上，但是 \(1\le T\le 10^4\)，\(1\le n\le 2\times 10^5\)，\(\sum n\le 2\times 10^5\)。
可以用数据结构维护来快速得到调整的位置，然后用链表进行位置的调整。
总复杂度 \(O(\sum n\log n)\) 级别。
咕。
学到了什么
- 多手玩。
- 充要的数学抽象是一个有启发性的方向。
- 注意是充要的情况下，否则可能会寄。