按照概念，延迟满足是指一种甘愿为更有价值的长远结果而放弃即时满足的抉择取向， 以及在等待期中展示的自我控制能力。相信许多人都看过一个实验，就是让小朋友独处，将若干糖果摆放在房间里，并且告诉他如果他可以在一段时间内不吃这些糖果，就可以得到更多的糖果，这个实验就考验了小朋友的延迟满足能力。在碎片信息盛行的当下，当我们考虑时间管理、自律等问题时，我认为本质上就是保持并提高延迟满足的能力，因为各种“短娱乐”内容就是在短时间内高效地刺激大脑，久而久之，能够静下心来花更多时间做更有价值的事情的能力就会逐渐被消磨。“延迟满足”并不是“不满足”，因此不断给予自己心理暗示，每当自己分心时，告诉自己应该做些什么才会得到更有价值的回报，或许是一个锻炼延迟满足能力的好方法。
E - Rook Path
题目链接： E - Rook Path
题意：
给定一个 $n\times m$ 网格，以及起点 $(x_1,y_1)$ 和终点 $(x_2,y_2)$ ，每一步可以从当前格子走到与当前格子处于同一行或同一列的任意一个格子，问有多少种方案走到终点。
解题思路：
网格很大，因此要想想是不是有很多格子计算时没有意义或者是重复的，手算一下样例，发现果然，整个网格在每一步的状态转移时，最多只有四种数，只需要维护起点、与起点同一行、与起点同一列、其它格子四种即可，然后直接用 DP 去转移一下就行。
代码如下：
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 998244353;
// assume -mod <= x < 2 * mod
int norm(int x) {
if (x < 0) {
x += mod;
}
if (x >= mod) {
x -= mod;
}
return x;
}
template<typename T, typename U>
T qp(const T &a, const U &b) {
assert(b >= 0);
T res = 1, x = a;
U p = b;
for (; p; p /= 2, x *= x) {
if (p % 2) {
res *= x;
}
}
return res;
}
class Mint {
public:
int x;
Mint(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(norm(mod - x));
}
Mint inv() const {
assert(x != 0);
return qp(*this, mod - 2);
}
Mint &operator*=(const Mint &rhs) {
x = (int) ((long long) x * rhs.x % mod);
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = norm(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = norm(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
vector<vector<Mint>> f(2, vector<Mint>(2));
f[0][0] = 1;
while (k--) {
vector<vector<Mint>> g(2, vector<Mint>(2));
g[0][0] = (n - 1) * f[1][0] + (m - 1) * f[0][1];
g[0][1] = f[0][0] + (n - 1) * f[1][1] + (m - 2) * f[0][1];
g[1][0] = f[0][0] + (m - 1) * f[1][1] + (n - 2) * f[1][0];
g[1][1] = f[0][1] + f[1][0] + (n - 2 + m - 2) * f[1][1];
swap(f, g);
}
Mint res = 0;
if (x1 == x2 && y1 == y2) {
res = f[0][0];
} else if (x1 == x2) {
res = f[0][1];
} else if (y1 == y2) {
res = f[1][0];
} else {
res = f[1][1];
}
cout << res.val() << '\n';
return 0;
}
C. BA-String
题目链接： C. BA-String
题意：
给定一个字符串，只有字符 $a$ 和星号，要将所有星号都换成 $[0,k]$ 个字符 $b$ 求字典序第 $x$ 小的字符串。
解题思路：
这题不难，但很巧妙，个人挺喜欢的。
首先是要将连续的星号一起来考虑，如果连续有 $c$ 个星号，那么这一段就能产生 $ck+1$ 个不同的情况，找出所有的连续段，总共能够产生的字符串数量就是 $(c_1k+1)\times\dots\times(c_mk+1)$ ，其中 $m$ 为段数，令 $limit_i=c_ik+1$ 。
然后因为找字典序时是从小找起的第 $x$ 个，因此尽量首先把靠后的星号换成 $b$ ，会更优。接着就是按照类似于进制数的思路处理了，从后往前，每次将当前的 $x$ 看作是 $limit_i$ 进制数，算出当前应该转换成多少个字符 $b$ ，然后将 $x$ 除以 $limit_i$ 下取整，直到处理完所有段，最后输出。
注意事项：
要先将 $x$ 减 $1$ ，因为整个字符串没有 $b$ 也是一个合法串，这个串是字典序排名第一的，问字典序排名第 $x$ 的串，实际上是问转化成进制数后的第 $x-1$ 个数，类似于十进制数中， $7$ 其实是第 $8$ 个数，排名第 $3$ 的数其实是 $2$ 。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, k;
long long x;
string s;
cin >> n >> k >> x >> s;
vector<int> limit;
for (int i = 0; i < n; i++) {
int j = i;
while (j < n && s[j] == '*') {
j++;
}
if (j > i) {
limit.emplace_back((j - i) * k + 1);
}
i = j;
}
int m = (int) limit.size();
vector<int> cnt(m);
// x 要先减去 1
x--;
for (int i = m - 1; i >= 0; i--) {
cnt[i] = (int) (x % limit[i]);
x /= limit[i];
}
// cc 为当前是第几段星号
for (int i = 0, cc = 0; i < n; i++) {
if (s[i] != '*') {
cout << s[i];
continue;
}
int j = i;
while (j < n && s[j] == '*') {
j++;
}
while (cnt[cc]--) {
cout << 'b';
}
cc++;
i = j - 1;
}
cout << '\n';
}
return 0;
}
D. Exact Change
题目链接： D. Exact Change
题意：
给定 $n$ 个物品，每个物品有特定的价格，只有 $1,2,3$ 元面额的钞票，请问最少带多少张，才能每个物品都可以恰好单独被凑出来。
解题思路：
一道很体现暴力美学的题目，一开始往贪心去想，但好像证明不了，于是错了，直接暴力即可。
要想带的数量尽量少，那么就尽量多带 $3$ 元的， $1,2$ 元的两种都是用来凑 $3$ 的余数的，因此 $3$ 张 $1$ 元肯定用 $1$ 张 $3$ 元代替， $3$ 张 $2$ 元肯定用 $2$ 张 $3$ 元代替， $1,2$ 元都不会携带超过 $2$ 张，所以直接枚举这两种钞票带多少张即可。对于某一种携带方案，检查所有物品，查验当前方案是否能够使得其价值减去当前方案可凑齐的尾数后，是非负数，且是 $3$ 的倍数，在所有物品中找出最多需要多少张 $3$ 元，更新答案即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &u : a) {
cin >> u;
}
int res = (int) 2e9;
for (int one = 0; one <= 2; one++) {
for (int two = 0; two <= 2; two++) {
int three = 0;
for (auto &u : a) {
int mn = (int) 2e9;
for (int i = 0; i <= one; i++) {
for (int j = 0; j <= two; j++) {
int left = u - i - 2 * j;
// 一定要是非负数
if (left >= 0 && left % 3 == 0) {
mn = min(mn, left / 3);
}
}
}
three = max(three, mn);
}
res = min(res, one + two + three);
}
}
cout << res << '\n';
}
return 0;
}
E. Replace the Numbers
题目链接： E. Replace the Numbers
题意：
有一空序列，进行 $n$ 次操作，每次操作为以下其中一种：
- 在序列后加入 $x$ ；
- 将序列中所有 $x$ 替换成 $y$ 。
解题思路：
方法一：
思路有点类似于格子染色问题，无论整个过程怎么染，最后是什么颜色，只跟最后一次染上的颜色有关。
对于第二种操作而言，它只会影响到在这次操作之前出现的所有 $x$ 。
定义一个数组 $who[i]$ ，表示当前的 $i$ 最终会被替换成 $who[i]$ ，初始时， $who[i]=i$ ，然后倒序处理所有操作。
对于第一种操作，直接加入 $who[x]$ ，第二种操作，将 $who[x]$ 赋值为 $who[y]$ 。
最后倒序输出序列。
方法二：
顺序处理每次操作，用一个二维数组 $pos$ 记录每个数在结果序列中出现的位置，对于第二种操作，将 $pos[x]$ 的所有数插入到 $pos[y]$ 里，如果 $pos[x]$ 的大小比 $pos[y]$ 大，要先交换一下两个数组，这样的交换并不是线性的，因此不会超时，跟启发式合并是一个思路。
方法一代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> type(n), x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> type[i] >> x[i];
if (type[i] == 2) {
cin >> y[i];
}
}
const int N = 500010;
vector<int> who(N);
iota(who.begin(), who.end(), 0);
vector<int> res;
for (int i = n - 1; i >= 0; i--) {
if (type[i] == 1) {
res.emplace_back(who[x[i]]);
} else {
who[x[i]] = who[y[i]];
}
}
int rn = (int) res.size();
for (int i = rn - 1; i >= 0; i--) {
cout << res[i] << " \n"[i == 0];
}
return 0;
}
方法二代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int q;
cin >> q;
const int N = 500010;
vector<vector<int>> pos(N);
int n = 0;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int x;
cin >> x;
pos[x].emplace_back(n);
n += 1;
} else {
int x, y;
cin >> x >> y;
if (x == y) {
continue;
}
if ((int) pos[x].size() > (int) pos[y].size()) {
swap(pos[x], pos[y]);
}
for (auto &u : pos[x]) {
pos[y].emplace_back(u);
}
pos[x].clear();
}
}
vector<int> res(n);
for (int x = 0; x < N; x++) {
for (auto &i : pos[x]) {
res[i] = x;
}
}
for (int i = 0; i < n; i++) {
cout << res[i] << " \n"[i == n - 1];
}
return 0;
}
D. New Year’s Problem
题目链接： D. New Year’s Problem
题意：
有 $n$ 个人， $m$ 家商铺，第 $j$ 个人去第 $i$ 家商铺可以买一个物品，价值为 $p_{ij}$ ，最多选择 $n-1$ 家商铺，求每个人恰好去一家商铺买一个物品，所有人的物品价值最小值最大是多少。
解题思路：
题目的输入有点绕，可以把题目的信息翻转一下，存一个矩阵 $a_{ij}$ ，表示第 $i$ 个人，去第 $j$ 家商铺可以获得的价值。然后根据题意，在所有选法当中，最多会选择 $n$ 家商铺，最终合法选择的商铺数量应该是 $min(m,n-1)$ ，当 $m\leq n-1$ ，任何选法都是合法的，而且一定存在重复选择商铺的情况；当 $m>n-1$ ，则一定要求至少两个人重复选择商铺。因此，一定会存在至少两个人选择同一家商铺。
这种问题其实是很典型的一个二分问题，二分一个临界点 $mid$ ，矩阵中大于等于 $mid$ 的值用 $1$ 表示，否则用 $0$ 表示，对于 $mid$ ，检查是否存在有重复商铺出现且是否每个人都能选择到一个价值至少为 $mid$ 的物品即可。
这场比赛被这 $1800$ 分的题被绕进去好久，然后这题后面的两道 $2000$ 分的题目秒出，我服了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> m >> n;
vector<vector<int>> a(n, vector<int>(m));
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
cin >> a[i][j];
}
}
auto check = [&](int x) -> bool {
// used[i] 标记第 i 家商铺是否已经被选过
vector<bool> used(m);
// repeat 标记是否存在商铺被重复选择
bool repeat = false;
for (int i = 0; i < n; i++) {
// flag 表示当前这个人是否能够选到价值至少为 x 的物品
bool flag = false;
for (int j = 0; j < m; j++) {
if (a[i][j] >= x) {
if (used[j]) {
repeat = true;
}
used[j] = true;
flag = true;
}
}
if (!flag) {
return false;
}
}
return repeat;
};
int l = 1, r = (int) 2e9;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
cout << r << '\n';
}
return 0;
}
F - Many Many Paths
题目链接： F - Many Many Paths
题意：
在一个坐标系上，给定两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$ ，求这两点形成的矩阵中所有点到 $(x_2,y_2)$ 的路径数之和。
解题思路：
两个点的坐标都是 $10^6$ 级别，因此不能暴力做，且只能枚举一个坐标。
通过题目给定的形式，应该要想到前缀和，设 $s[x][y]$ 为 $(0,0)$ 和 $(x,y)$ 形成的矩阵中所有点到 $(x,y)$ 的路径数之和，那么所求就是 $s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-1]$ ，剩下的问题就是如何高效计算 $s[x][y]$ 。
可以发现 $s[x][y]$ 实际上也等于 $(0,0)$ 和 $(x,y)$ 形成的矩阵中所有点到 $(0,0)$ 的路径数之和， $(0,0)$ 到 $(x,y)$ 的路径数为 $g[x][y]=C_{x+y}^{y}$ ，然后惊奇地发现 $g[x+1][y]=g[x][0]+g[x][1]+\dots+g[x][y]$ 。证明如下：
$g[x+1][y]=g[x][0]+g[x][1]+\dots+g[x][y]$
$g[x+1][y]=g[x][y]+g[x+1][y-1]$
$g[x+1][y-1]=g[x][y-1]+g[x+1][y-2]$
$\dots$
$g[x+1][0]=g[x][0]=1$
因此， $s[x][y]=g[1][y]+g[2][y]+\dots +g[x+1][y]$ 。
注意事项：
代码如下：
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = (int) 1e9 + 7;
// assume -mod <= x < 2 * mod
int norm(int x) {
if (x < 0) {
x += mod;
}
if (x >= mod) {
x -= mod;
}
return x;
}
template<typename T, typename U>
T qp(const T &a, const U &b) {
assert(b >= 0);
T res = 1, x = a;
U p = b;
for (; p; p /= 2, x *= x) {
if (p % 2) {
res *= x;
}
}
return res;
}
class Mint {
public:
int x;
Mint(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(norm(mod - x));
}
Mint inv() const {
assert(x != 0);
return qp(*this, mod - 2);
}
Mint &operator*=(const Mint &rhs) {
x = (int) ((long long) x * rhs.x % mod);
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = norm(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = norm(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
};
vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);
Mint C(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
while ((int) fact.size() < n + 1) {
fact.push_back(fact.back() * (int) fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n] * inv_fact[k] * inv_fact[n - k];
}
Mint Fact(int n) {
assert(n >= 0);
while ((int) fact.size() < n + 1) {
fact.push_back(fact.back() * (int) fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
auto s = [&](int x, int y) -> Mint {
Mint res = 0;
for (int i = 0; i <= x; i++) {
res += C(y + i + 1, i + 1);
}
return res;
};
Mint res = s(x2, y2) - s(x1 - 1, y2) - s(x2, y1 - 1) + s(x1 - 1, y1 - 1);
cout << res.val() << '\n';
return 0;
}
