虽然学校课程很早就结束了，但是因为临近期末的一系列比赛，搁置了不少复习任务和大作业，各种繁琐的事项直到前两天才完全搞定，正式进入假期。看起来我应该还能再战一年，所以这段时间也还是要保持训练的。翻看我之前的文章可以发现我挺注重自己的状态的，状态经常起伏并不是好事，我只是通过关注自己的状态，不断提高自己的训练质量，并且缩短减少自己状态不好的周期。由于考试和大作业，有一段时间没有很系统地训练，那么就记录一下通常我是利用什么方法调节状态的吧。
直面状态下滑
首先要做好自己暂时变菜的心理准备，以前状态比较好的时候能够莽出来的题目现在可能不行了，有时会犯一些很傻的错误，面对一道难度不大的题要想很久，这些都是正常的，首先要从心理上去接受它，相信自己在一段时间后会变得更好。
一般来说，平时做题，如果是难度稍微高于自己能力的题目，我给自己设定的思考时间是在二十到三十分钟，如果完全没有头绪的话，就可以翻看题解了，那么在这段时间的话，可以稍微缩短时间，比如在十分钟到十五分钟。因为长时间不训练，做题能力有所下滑，继续拖下去会降低效率，而且在心理上也是一种折磨。
有些题目看了题解发现原来很简单，但自己就是想不出，也不必着急，认真把题目涉及的知识点、推导思路梳理清楚，这有利于将与这些知识点有关的内容都在脑海里回忆起来。这种情况，其实就是自己对这方面的知识或套路的熟练度不够，借着重新梳理的机会，更能够加深印象。
思维
做一道题，往往包括两步，一是思维，能够想到怎样做，二是码力，也就是把思路用代码实现，这里先说如何让思维重新充满活力。
首先翻看一下自己学过哪些知识点，算法书、博客、 AcWing 、 OI-WIKI 都很好地将大大小小的知识点归纳起来，搞清楚每个知识点有什么用，看看自己记录下的经典题目，借着自己写的题解，想明白题目是怎么做的。
找一些思维题、构造题来玩一下，大概 CF 1400-1600 的难度吧，有很多奇思妙想在做了一定数量的题目以后自然而然就会在大脑里形成一些思考的套路。
码力
说到码力的话，我会在思维逐渐找回感觉之后进行训练。我会找一些模板题，尤其是数据结构和图论的题目，不复制模板，而是自己从头打一遍，找打代码的感觉。这一部分其实我还行，我写题解的过程也是在训练码力，平时训练比赛时我都会用自己的代码模板，但博客里的代码都是全部手打的，所以平时练得也挺多的。
接着可以找一些以前做过的题目，难度比较大的，最好是思维和代码都比较难的，尝试去挑战一下，每天做一两题也足够了。这个过程本质上仍然是提高熟练度，就像 y 总经常提到的，一道题至少有六七成的代码都是重复出现的，做算法题就是把思路剖析清楚，把代码打得炉火纯青。
打比赛
打比赛是训练、学习新知识最好的方式之一，虽然状态不好的时候打比赛可能会有些煎熬，但打比赛有个好处就是能够让自己长时间沉浸式地专注思考，这对调节状态是非常有利的。打比赛不用在意分数，只需要努力做更多的题目即可。打比赛加上补题看似会占据一大段的时间，实际上它比用零碎的时间刷一堆简单题的效果更好。因此在调节状态的时候，每天开一场比赛是很有用的。
休息、运动、整理
做算法题长时间专注思考，脑力消耗会很大，非常不建议用熬夜来换取时间，如果熬夜是为了让自己“看起来很努力”那么就更不可取了，有规律且足够的睡眠是必要的。
运动方面的话，我比较喜欢有氧运动，比如跑步、游泳、篮球，保持和平时一样的频率就行，运动也有助于大脑运转的速度。
关于整理东西，可以看看何同学的这个 视频 ，无论是整理各种事物还是整理大脑里的内容，整理完成之后都有满满的快感，而且能够提高学习的效率。像我就会优先整理一下以前剩下要补的题，比如下面这些题目。另外写博客也是一种整理方式，把这段时间思考的东西记录下来，把挖的坑给补上，之后的时间就专注做题。
D - Factorization
题目链接： D - Factorization
题意：
有多少个长度为 $n$ 的序列，乘起来的积是 $m$ ？
解题思路：
将 $m$ 分解质因数，对于每个质因数，假设有 $y$ 个，实际上就是将它们分到 $n$ 个位置上，某些位置可以没有，这就是隔板法的应用，可以地加上 $n$ 个物品，在 $y+n-1$ 个位置上，加入 $n-1$ 个隔板，最后将每一部分的物品都减一就可以了。
代码如下：
#include <map>
#include <vector>
#include <iostream>
using namespace std;
const int N = 200010, mod = (int) 1e9 + 7;
long long fact[N], infact[N];
void init(int n)
{
fact[0] = infact[0] = 1;
fact[1] = infact[1] = 1;
for (int i = 2; i <= n; i ++ )
{
fact[i] = fact[i - 1] * i % mod;
infact[i] = (mod - mod / i) * infact[mod % i] % mod;
}
for (int i = 2; i < N; i ++ ) infact[i] = (long long) infact[i] * infact[i - 1] % mod;
}
long long C(int a, int b)
{
if (a < b) return 0;
return fact[a] * infact[b] % mod * infact[a - b] % mod;
}
map<int, int> get_fac(int x)
{
map<int, int> mp;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
mp[i] ++ ;
}
if (x > 1) mp[x] = 1;
return mp;
}
int main()
{
init(N - 1);
int n, m;
cin >> n >> m;
auto fac = get_fac(m);
long long res = 1;
for (auto &[x, y] : fac)
res = res * C(n + y - 1, n - 1) % mod;
cout << res << '\n';
return 0;
}
D. Love-Hate
题目链接： D. Love-Hate
题意：
共有 $m$ 个物品，有 $n$ 个人，给出每个人对每个物品是否喜欢，选出最大的物品子集，使得至少有 $\lceil \frac{n}{2} \rceil$ 个人喜欢这个子集的所有物品。
解题思路：
物品总数以及每个人最多喜欢的物品数都很小，应该往位运算的方向思考，但暴力的时间复杂度仍然是 $O(n^2)$ ，由于要使得至少一半人喜欢这个子集，因此联想到用随机化的算法，设最后的子集用一个整数表示为 $res$ ，那么经过 $50$ 次的枚举，几乎一定会枚举到某个人喜欢的物品集合， $res$ 为这个集合的子集。
对于枚举到的某个人的集，将它喜欢的物品找到，然后枚举这个集合的所有子集，统计其他人是否喜欢这些子集，最后用每个子集更新答案即可。
其中统计其他人是否喜欢这些子集，也不能用暴力，而需要用类似 DP 的方式。
代码如下：
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
return (rng() % (r - l)) + l;
}
int main()
{
int n, m, p;
cin >> n >> m >> p;
vector<long long> a(n);
for (int i = 0; i < n; i ++ )
{
string s;
cin >> s;
for (int j = 0; j < m; j ++ )
if (s[j] == '1')
a[i] |= (1LL << j);
}
int ans = 0;
long long res = 0;
for (int it = 0; it < 50; it ++ )
{
long long t = a[rand(0, n)];
vector<int> b;
for (int bit = 0; bit < m; bit ++ )
if ((t >> bit) & 1)
b.emplace_back(bit);
int sz = (int) b.size();
vector<int> cnt(1 << sz);
for (int i = 0; i < n; i ++ )
{
int mask = 0;
for (int bit = 0; bit < sz; bit ++ )
if ((a[i] >> b[bit]) & 1)
mask |= (1 << bit);
cnt[mask] ++ ;
}
for (int mask = 0; mask < 1 << sz; mask ++ )
for (int sub_mask = (mask - 1) & mask; sub_mask; sub_mask = (sub_mask - 1) & mask)
cnt[sub_mask] += cnt[mask];
for (int mask = 0; mask < 1 << sz; mask ++ )
if (2 * cnt[mask] >= n && __builtin_popcount(mask) > ans)
{
ans = __builtin_popcount(mask);
res = 0;
for (int bit = 0; bit < sz; bit ++ )
if ((mask >> bit) & 1)
res |= (1LL << b[bit]);
}
}
for (int j = 0; j < m; j ++ )
cout << ((res >> j) & 1);
cout << '\n';
return 0;
}
F1. Falling Sand (Easy Version)
题目链接： F1. Falling Sand (Easy Version)
题意：
建议直接看原题。
解题思路：
这题其实不难，对于所有互相影响的方格连线，找强连通分量，然后在强连通分量上连边，统计入度为 $0$ 的点即可，主要是记录一下自己的找强连通分量的模板。
代码如下：
#include <bits/stdc++.h>
using namespace std;
vector<int> findSCC(const vector<vector<int>> &g, int &id) {
int n = static_cast<int>(g.size());
int top = 0;
vector<int> comp(n, -1), in(n, -1), out(n, -1), stk(n + 1, -1), order;
function<int(int u)> tarjan = [&](int u) -> int {
assert(top >= 0 && top <= n);
stk[top++] = u;
int low = in[u] = (int) order.size();
order.push_back(u);
for (auto &v : g[u]) {
if (in[v] == -1) {
low = min(low, tarjan(v));
continue;
}
if (comp[v] == -1) {
low = min(low, in[v]);
}
}
if (low == in[u]) {
while (stk[top] != u) {
assert(top >= 0 && top <= n);
comp[stk[--top]] = id;
}
id++;
}
out[u] = (int) order.size() - 1;
return low;
};
for (int i = 0; i < n; i++) {
if (in[i] == -1) {
tarjan(i);
}
}
return comp;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<string> g(n);
for (auto &s : g) cin >> s;
vector<int> a(m);
for (auto &u : a) cin >> u;
int k = 0;
vector<vector<int>> id(n, vector<int>(m, -1));
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == '#')
id[i][j] = k ++ ;
vector<vector<int>> low(n, vector<int>(m, -1));
for (int i = n - 1; i >= 0; i -- )
for (int j = 0; j < m; j ++ )
{
if (i + 1 < n) low[i][j] = low[i + 1][j];
if (g[i][j] == '#') low[i][j] = id[i][j];
}
vector<vector<int>> sg(k);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (id[i][j] != -1)
{
int x = id[i][j];
if (i > 0 && id[i - 1][j] != -1) sg[x].emplace_back(id[i - 1][j]);
if (j > 0 && low[i][j - 1] != -1) sg[x].emplace_back(low[i][j - 1]);
if (j + 1 < m && low[i][j + 1] != -1) sg[x].emplace_back(low[i][j + 1]);
if (i + 1 < n && low[i + 1][j] != -1) sg[x].emplace_back(low[i + 1][j]);
}
int sn = 0;
auto sid = findSCC(sg, sn);
vector<int> din(sn);
// 这里要注意，只有不同的点才需要连边
for (int i = 0; i < k; i ++ )
for (auto &u : sg[i])
if (sid[u] != sid[i])
din[sid[u]] ++ ;
int res = 0;
for (auto &u : din) res += !u;
cout << res << '\n';
return 0;
}
E - Ring MST
题目链接： E - Ring MST
题意：
一开始有 $n$ 个点，没有边，给出 $m$ 种操作，每种操作包含一个 $a$ 和 $c$ ，其中 $c$ 代表花费，可以给 $x$ 和 $x+a\mod n$ 连一条边， $x$ 任选，操作的次数、顺序也任选，问是否能将所有点连成一棵树，若能，求最小花费。
解题思路：
贪心很容易想到，类似于最小生成树的做法，优先用花费较小的操作，一直用到不能用为止。
这题主要是想记录如果当前有 $cur$ 个连通分量，选用了 $a$ ，那么尽量连完边之后，就会剩下 $nxt=gcd(cur,a)$ 个连通分量。每次记录花费 $(cur-nxt)\times c$ 即可。
如果最后剩下的连通分量不是 $1$ ，那么就不能连成树。
代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(m);
for (auto &[x, y] : a) cin >> y >> x;
sort(a.begin(), a.end());
int cur = n;
long long res = 0;
for (auto &[y, x] : a)
{
int nxt = gcd(cur, x);
res += (long long) (cur - nxt) * y;
cur = nxt;
}
if (cur != 1) res = -1;
cout << res << '\n';
return 0;
}
D. Segment Tree
题目链接： D. Segment Tree
题意：
给定 $n$ 个线段，看成 $n$ 个点，若两个线段相交且不包含，则连上一条边，问最终是否为一棵树。
解题思路：
首先判断是一棵树的条件可以用并查集，看是否所有点都是连通的，而且恰好只有 $n-1$ 条边。
对于判断相交的区间问题，应该比较容易想到排序操作，注意本题的限制，首先是不相交不连边，其次是包含也不连边，可以考虑对所有点排序，然后枚举所有区间的起点（如果枚举到的是终点，则不理），用一个 set 保存所有枚举过的区间终点，对于当前枚举到这个区间的终点：
- 如果之前的区间终点小于当前区间起点，说明不相交，而且对于之后的区间，也不相交，则从
set中删掉； - 如果小于当前区间的终点，说明相交，连边即可；
- 如果大于当前区间，说明包含，退出循环。
如果连的边超过了 $n-1$ 则可以直接结束。
代码如下：
#include <bits/stdc++.h>
using namespace std;
class Dsu {
public:
vector<int> p, sz;
int n;
Dsu(int _n) {
n = _n + 1;
p.resize(n);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
inline int getSize(int x) {
return sz[x];
}
};
int main()
{
int n;
cin >> n;
vector<pair<int, int>> a(n);
vector<pair<int, int>> b;
for (int i = 0; i < n; i ++ )
{
int x, y;
cin >> x >> y;
a[i] = {x, y};
b.emplace_back(make_pair(x, i));
b.emplace_back(make_pair(y, i));
}
sort(b.begin(), b.end());
Dsu d(n);
set<pair<int, int>> S;
int cnt = 0;
for (auto &[x, id] : b)
{
if (S.count(make_pair(a[id].second, id))) continue;
// 删除不会用到的点
while ((int) S.size() > 0)
{
if ((*S.begin()).first < x) S.erase(S.begin());
else break;
}
for (auto &[y, bid] : S)
{
if (y > a[id].second) break;
d.unite(id, bid);
cnt ++ ;
}
if (cnt >= n) break;
S.insert(make_pair(a[id].second, id));
}
cout << (d.getSize(d.get(0)) == n && cnt == n - 1 ? "YES\n" : "NO\n");
return 0;
}
D - Snuke’s Coloring
题目链接： D - Snuke’s Coloring
题意：
在一张网格上，给出黑色点的坐标，问分别有多少个 $3\times 3$ 的网格包含 $0-9$ 个黑色格子。
解题思路：
因为整个网格非常大，而黑色格子刚刚好是 $10^5$ 级别，很显然应该从黑色格子入手。
为了方便，我们以左上角的格子坐标来唯一确定一个 $3\times 3$ 网格，对于每个黑色格子来说，它会给它左上角（包括自己）最多 $9$ 个格子贡献，那么就可以用哈希表计数了。
最后包含 $0$ 个黑色格子的个数要另外计算，一共有 $(n-2)\times (m-2)$ 个 $3\times 3$ 网格，减去包含了黑色格子的网格即可。
代码如下：
#include <map>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int n, m, k;
cin >> n >> m >> k;
map<pair<int, int>, int> mp;
for (int i = 0; i < k; i ++ )
{
int x, y;
cin >> x >> y;
for (int tx = x - 2; tx <= x; tx ++ )
for (int ty = y - 2; ty <= y; ty ++ )
if (tx >= 1 && ty >= 1 && tx + 2 <= n && ty + 2 <= m)
mp[{tx, ty}] += 1;
}
vector<long long> res(10);
for (auto &[x, y] : mp) res[y] ++ ;
res[0] = (long long) (n - 2) * (m - 2);
for (int i = 1; i < 10; i ++ ) res[0] -= res[i];
for (auto &u : res) cout << u << '\n';
return 0;
}
D - National Railway
题目链接： D - National Railway
题意：
给定一个 $n\times m$ 网格，两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的花费是两个点的曼哈顿距离乘以 $c$ 加上两个点的值，求哪两个点之间的花费最小。
解题思路：
直接暴力枚举不可取，可以从曼哈顿距离这里入手，定义一个 DP 数组 $f[i][j]$ 表示从左上角所有点走到 $(i,j)$ ，且不包含 $(i,j)$ 这个点的值的所有方案，属性是最小花费。最后枚举一下所有点即可。
这题比较简单，但我以往其实忽视了一个点，就是直接这样按照一个方向去枚举，是没有包含所有两两配对的情况的，还要进行一次按行对称变换才行。
代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, m;
long long c;
cin >> n >> m >> c;
vector<vector<long long>> a(n, vector<long long>(m));
for (auto &u : a)
for (auto &v : u)
cin >> v;
auto solve = [&]() -> long long
{
auto f = a;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
{
if (i + 1 < n) f[i + 1][j] = min(f[i + 1][j], f[i][j] + c);
if (j + 1 < m) f[i][j + 1] = min(f[i][j + 1], f[i][j] + c);
}
long long res = (long long) 4e18;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
{
// 这里记得加上一个 c
if (i > 0) res = min(res, a[i][j] + f[i - 1][j] + c);
if (j > 0) res = min(res, a[i][j] + f[i][j - 1] + c);
}
return res;
};
long long res = solve();
// 按行对称变换
for (int i = 0, j = n - 1; i < j; i ++ , j -- ) swap(a[i], a[j]);
res = min(res, solve());
cout << res << '\n';
return 0;
}
