上周去银川拿了个牌牌，咕了一周，感谢y总，感谢AcWing。从接触到算法竞赛，一开始靠着满腔热情，只是不断找题刷题，不知道如何有效地学习算法，像个无头苍蝇一样，不是被虐就是在被虐的路上。
直到来到这里，才窥见算法的知识体系，体会到系统地学习是多么重要。来到AcWing后，加上自己的努力，我也从弱校弱队的算法竞赛小白选手，做到学院的集训队负责人，一路上拿到了不少奖项，真心享受算法学习和比赛带来的乐趣，这是我的大学生涯中浓墨重彩的一笔，如今在一定程度上也算证明了自己吧。
再次感谢y总提供的宝贵知识，祝AcWing越来越好。
甚至想问y总招不招实习生hh
D. Digits
题目链接： D. Digits
题意：
给定 $n$ 个数，选若干个数，使得这些数相乘的结果个位为 $d$ ，如果存在答案，则求最大的相乘结果的选择方案。
解题思路：
选择问题容易想到用背包处理，关键是如何确定最大的相乘结果，因为乘起来的结果很大。这里可以将乘法转化为加法，也就是取所有乘数对 $2$ 的对数，相加即可，因为乘法和加法都是单调的，因此可行。然后就是一个比较典型的求方案了。
代码如下：
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;
const double INF = 4e18;
int main()
{
int n, d;
cin >> n >> d;
vector<int> a(n);
for (auto &u : a) cin >> u;
vector<vector<double>> f(n + 1, vector<double>(10, -INF));
vector<vector<pair<int, int>>> g(n + 1, vector<pair<int, int>>(10, make_pair(-1, -1)));
f[0][1] = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < 10; j ++ )
{
double &t = f[i][j];
if (t == -INF) continue;
if (t > f[i + 1][j])
{
f[i + 1][j] = max(f[i + 1][j], t);
g[i + 1][j] = make_pair(i, j);
}
if (t + log2(a[i]) > f[i + 1][(j * a[i]) % 10])
{
f[i + 1][(j * a[i]) % 10] = max(f[i + 1][(j * a[i]) % 10], t + log2(a[i]));
g[i + 1][(j * a[i]) % 10] = make_pair(i, j);
}
}
int i = n, j = d;
if (f[i][j] <= 0) cout << "-1\n";
else
{
vector<int> res;
while (g[i][j].first != -1)
{
auto [x, y] = g[i][j];
if (f[x][y] != f[i][j]) res.emplace_back(a[i - 1]);
i = x, j = y;
}
cout << (int)res.size() << '\n';
for (auto &u : res) cout << u << ' ';
cout << '\n';
}
return 0;
}
C - Time Gap
题目链接： C - Time Gap
题意：
给定一些 $12$ 小时制的时刻，它们在 $24$ 小时制下有可能表示两种时刻，求所有可能的时刻序列中，时刻间隔最小值的最大值。
解题思路：
可以发现如果 $0$ 点或 $12$ 点，出现了两次或以上，那么答案一定为 $0$ ，因为这两个时刻在 $24$ 小时制也只能表示同一个时刻。
然后其它时刻，如果出现了三次或以上，答案也一定为 $0$ ，因为一定会有两个或以上的时刻重复。
剩下的情况，就可以用二进制枚举，求出某一时刻在 $24$ 小时制下表示的是哪个时刻了。
注意事项：
记得要考虑 $24$ 时。
代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n + 1), cnt(13);
cnt[0] = 1;
bool flag = true;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
cnt[a[i]] ++ ;
flag &= (cnt[a[i]] <= 2);
}
if (!flag || cnt[0] >= 2 || cnt[12] >= 2)
{
cout << "0\n";
return 0;
}
vector<int> b, c;
for (int i = 0; i <= 12; i ++ )
if (cnt[i] == 2)
{
b.emplace_back(i);
b.emplace_back(24 - i);
}
else if (cnt[i]) c.emplace_back(i);
int m = (int)c.size(), res = 0;
for (int mask = 0; mask < 1 << m; mask ++ )
{
int mn = 30;
vector<int> t = b;
for (int bit = 0; bit < m; bit ++ )
if ((mask >> bit) & 1) t.emplace_back(c[bit]);
else t.emplace_back(24 - c[bit]);
// 记得考虑 24
t.emplace_back(24);
sort(t.begin(), t.end());
for (int i = 0; i < (int)t.size() - 1; i ++ )
mn = min(mn, t[i + 1] - t[i]);
res = max(res, mn);
}
cout << res << '\n';
return 0;
}
B - Extension
题目链接： B - Extension
题意：
当前有一个 $a\times b$ 的网格，全是白色，每次可以往上添加一行，或者往右增加一列，然后在增加的一行或者一列中，选择一个格子涂黑，求最后可能的涂色方案数。
解题思路：
这题应该是最难的一道题，因为它有点抽象。
首先要观察到，假如当前网格，最上面一层，只有一个格子是黑色的，不妨规定它是网上增加的一行产生的，而往右增加列后，最上层（此时行数大于 $a$ ）一定是有多个黑色格子。
然后这时就可以定义一个 $f[i][j][k]$ ，表示当前网格规模是 $i\times j$ ，当 $k=1$ 时，表示最上层只有一个黑色格子，当 $k=0$ 时，表示还没有往上加层数，或者最上层有多个黑色格子的所有方案，属性是涂色的方案数。
如果可以往上增加层，那么 $f[i+1][j][1]+=f[i][j][k]\times j$ ，表示可以在新增加的一行中，选择任意一个格子涂色；如果可以往右增加列，按照上面的规定， $f[i][j+1][0]+=f[i][j][0]\times i+f[i][j][1]$ ，表示如果当前还没有增加新的行，或者最上面一层有多个黑色格子，就可以在新加的一列中任意选择一个格子涂色，如果最上面一层只有一个格子是黑色，那么就一定在右上角的格子涂色。
代码如下：
#include <iostream>
using namespace std;
const int N = 3010, mod = 998244353;
int a, b, c, d;
int f[N][N][2];
int main()
{
cin >> a >> b >> c >> d;
f[a][b][0] = 1;
for (int i = a; i <= c; i ++ )
for (int j = b; j <= d; j ++ )
{
int &t0 = f[i][j][0];
int &t1 = f[i][j][1];
if (i + 1 <= c)
{
f[i + 1][j][1] = (f[i + 1][j][1] + (long long)t0 * j) % mod;
f[i + 1][j][1] = (f[i + 1][j][1] + (long long)t1 * j) % mod;
}
if (j + 1 <= d)
{
f[i][j + 1][0] = (f[i][j + 1][0] + (long long)t0 * i) % mod;
f[i][j + 1][0] = (f[i][j + 1][0] + t1) % mod;
}
}
int res = (f[c][d][0] + f[c][d][1]) % mod;
cout << res << '\n';
return 0;
}
C - MAD TEAM
题目链接： C - MAD TEAM
题意：
有 $n$ 个人，选三个人组成一队，每个人有五个属性，对应队伍也有五个属性，每个属性分别三个人的对应属性的最大值，队伍的最终属性是队伍的五个属性的最小值。求队伍的最终属性的最大值。
解题思路：
结合之前归纳的屏蔽法，二分答案 $x$ ，对于每个人，每个属性用一个二进制位表示，如果小于 $x$ 则为 $0$ ，否则为 $1$ ，问题就转化成了从处理后的 $n$ 个数选 $3$ 个数，使得它们的或运算结果为 $31$ 。由于要做的是或运算，如果有重复的数可以忽略，因此可以直接用一个 set 来存下处理后的所有数，然后从 set 中枚举三个数检验即可。
代码如下：
#include <set>
#include <tuple>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<tuple<int, int, int, int, int>> p(n);
for (auto &[a, b, c, d, e] : p)
cin >> a >> b >> c >> d >> e;
auto check = [&](int x) -> bool
{
set<int> S;
for (auto &[a, b, c, d, e] : p)
{
int t = 0;
if (a >= x) t |= (1 << 0);
if (b >= x) t |= (1 << 1);
if (c >= x) t |= (1 << 2);
if (d >= x) t |= (1 << 3);
if (e >= x) t |= (1 << 4);
S.insert(t);
}
for (auto &x : S)
for (auto &y : S)
for (auto &z : S)
if ((x | y | z) == 31)
return true;
return false;
};
int l = 0, r = (int)1e9;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << r << '\n';
return 0;
}
F - Silver Fox vs Monster
题目链接： F - Silver Fox vs Monster
题意：
给定 $n$ 个怪兽，第 $i$ 个怪兽在 $x_i$ ，生命值为 $h_i$ ，每次可以放一个炸弹在 $x$ ，可以对 $[x-d,x+d]$ 的所有怪兽造成 $a$ 点伤害，求要使得所有怪兽的生命值都不为正数，至少需要多少次操作。
解题思路：
思路比较简单，直接贪心去考虑即可，也就是从左到右，对于当前怪兽位置 $x_i$ ，之前对它造成的伤害是 $cur$ ，如果它现在还活着，生命值为 $cur-h_i$ ，为了打败它，需要操作 $\lceil\frac{cur-h_i}{a} \rceil$ 次，为了更多地对后面的怪兽造成伤害，那么最好是在 $x_i+d$ 的位置放炸弹，对所有在 $[x_i,x+2\times d]$ 上的所有怪兽造成伤害。
坐标范围有点大，离散化一下即可，然后用树状数组来维护炸弹造成的范围伤害。
代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int n;
long long d, a;
long long idx[N];
long long tr[N];
pair<int, int> mon[N];
#define lowbit(x) (x & -x)
void add(int x, long long c)
{
for (int i = x; i < N; i += lowbit(i)) tr[i] += c;
}
long long get(int x)
{
long long res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> d >> a;
for (int i = 1; i <= n; i ++ )
{
int x, h;
cin >> x >> h;
mon[i] = {x, h};
}
sort(mon + 1, mon + 1 + n);
for (int i = 1; i <= n; i ++ ) idx[i] = mon[i].first;
long long res = 0;
for (int i = 1; i <= n; i ++ )
{
long long cur = get(i);
if (cur >= mon[i].second) continue;
int l = i, r = (int)(upper_bound(idx + 1, idx + 1 + n, mon[i].first + 2 * d) - idx - 1);
long long cnt = (mon[i].second - cur + a - 1) / a;
long long damage = cnt * a;
res += cnt;
add(l, damage), add(r + 1, -damage);
}
cout << res << '\n';
return 0;
}
D - Number of Amidakuji
题目链接： D - Number of Amidakuji
题意：
题意有些难以转述，直接看原题链接吧。
解题思路：
只要读懂了题意，其实就基本能想象得到用状压 DP 了，定义 $f[i][j][cur]$ 为处理到第 $i$ 层，小球从第 $j$ 根柱子上滑落，第 $i$ 层的状态是 $cur$ 的所有方案，属性是方案数。
然后枚举下一层的状态 $nxt$ ，当然要检查一下是否合法，也就是不能有连续的 $1$ ，然后根据题意来确定小球是滑落到第 $j-1$ 还是第 $j$ 还是第 $j+1$ 根柱子。
代码如下：
#include <iostream>
using namespace std;
const int N = 110, M = 10, mod = 1e9 + 7;
int n, m, k;
int f[N][M][1 << M];
int main()
{
cin >> n >> m >> k;
k -- ;
f[0][0][0] = 1;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
for (int cur = 0; cur < 1 << (m - 1); cur ++ )
for (int nxt = 0; nxt < 1 << (m - 1); nxt ++ )
{
int t = f[i][j][cur];
bool flag = true;
for (int bit = 0; bit < m - 2; bit ++ )
if (((nxt >> bit) & 1) && ((nxt >> (bit + 1)) & 1))
flag = false;
if (!flag) continue;
if ((j - 1 >= 0) && ((nxt >> (j - 1)) & 1))
{
f[i + 1][j - 1][nxt] = (f[i + 1][j - 1][nxt] + t) % mod;
}
else if ((j + 1 <= m - 1) && ((nxt >> j) & 1))
{
f[i + 1][j + 1][nxt] = (f[i + 1][j + 1][nxt] + t) % mod;
}
else
{
f[i + 1][j][nxt] = (f[i + 1][j][nxt] + t) % mod;
}
}
int res = 0;
for (int mask = 0; mask < 1 << (m - 1); mask ++ )
res = (res + f[n][k][mask]) % mod;
cout << res << '\n';
return 0;
}
聚聚金牌吗