THOI核心素养一题解
看得出来出了相当多锅（
由于 D 出锅严重，现已撤下，比赛延长 10min.还请各位海涵（
为什么延长 10min：18:25 吃饭（
比赛结果：
| 题目编号 | 题目名称 | 预计通过人数 | 实际通过人数 |
|---|---|---|---|
| A | \(\color{skyblue}\text{沙粒的记忆}\) | \(7\) | \(6\) |
| B | \(\color{blue}\text{远星的守望}\) | \(7\) | \(1\) |
| C | \(\color{purple}\text{国王的诞生}\) | \(7\) | \(4\) |
| E | \(\color{#FFBB50}\text{坏齿的舞曲}\) | \(2\) | \(0\) |
| F | \(\color{#B0DDAA}\text{山麓的回音}\) | \(2\) | \(0\) |
| EXTRA | \(\color{#FF5500}\text{群星的闪耀}\) | \(-\) | \(-\) |
A 沙粒的记忆
因为给出的数字和指数都是整数，所以指数只能是自然数（不小于 \(0\) 的整数）。
分析数据可知，在 \(a_i \le 10^{18}\) 的情况下，\(a_i\) 的各位数字之和最大是 \(9 \times 17\), 远小于 \(37^2\), 所以只需要判断 \(a_i\) 的各位数字之和是否等于 \(37^0\) 或 \(37^1\) 即可。时间复杂度 \(O(18 \cdot T\cdot N)\), 不过时限给得非常宽松，所以放过去了大部分没有优化的做法（
欢迎来暴踩标算：
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
ll T, n, a, ans;
int main() {
//freopen("THOI03A10.in", "r", stdin);
//freopen("THOI03A10.out", "w", stdout);
scanf("%lld", &T);
while(T--) {
scanf("%lld", &n);
while(n--) {
scanf("%lld", &a);
int x = 0;
while(a != 0) {
x += a % 10;
a /= 10;
if(x > 37) break;
}
if(x == 1 || x == 37) ++ans;
}
printf("%lld\n", ans);
ans = 0;
}
return 0;
}
B 远星的守望
经典的斐波那契数列（繁殖兔子问题），只不过换成了重返版
在以下内容中，我们称已经开始复制的奶牛为处于分裂期的奶牛。
不难看出，第 \(N-2\) 天的奶牛只有三种情况：已经进入分裂期的奶牛、将在第 \(N-1\) 天进入分裂期的奶牛和将在第 \(N\) 天进入分裂期的奶牛。
因此，当第 \(N\) 天时，第 \(N-2\) 天的奶牛全都已经处于了分裂期，并在这一天分裂出了一只奶牛。
所以第 \(N\) 天的奶牛数就是第 \(N-2\) 天的奶牛数（新分裂的奶牛）加上第 \(N-1\) 天的奶牛数（已经有的奶牛）。
得到递推式：
\[F(N) = F(N-1) + F(N-2) \]其中 \(F(0) = 0,F(1) = 1\), 因为第 \(0\) 天你还没有收到奶牛呢
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
const int N = 105;
ll T, x, y, f[N];
int main() {
//freopen("THOI03B10.in", "r", stdin);
//freopen("THOI03B10.out", "w", stdout);
scanf("%d", &T);
while(T--) {
scanf("%d%d", &x, &y);
f[1] = 1;
for(int i = 2; i <= x; ++i) f[i] = f[i - 1] + f[i - 2];
printf("%lld\n", f[x] - f[y]);
}
return 0;
}
C 国王的诞生
削了两次，现在已经是板上板了，call me 柏林以东（
01 背包板子。注意因为只要达到 \(M\) 就会昏厥，所以内层循环 j > w[i].
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
const int N = 1e5 + 5;
ll n, m, x[N], y[N], dp[N];
int main() {
//freopen("THOI03C10.in", "r", stdin);
//freopen("THOI03C10.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
for(int i = 1; i <= n; ++i) for(int j = m; j > y[i]; --j) dp[j] = max(dp[j], dp[j - y[i]] + x[i]);
printf("%d\n", dp[m]);
return 0;
}
E 坏齿的舞曲
要求奶量溢出最小，即已损失生命之和在不超过治疗量的情况下最大。考虑 01 背包。治愈一个小朋友的代价和收益都是这个小朋友的已损失生命。接下来考虑怎么记录治愈小朋友的个数。
可以把 dp 数组增开一维，大小为 \(2\), 使 \(dp_{j,0}\) 表示当前消耗的治疗量，\(dp_{j,1}\) 表示消耗 \(dp_{j,0}\) 点治疗量时，可以治愈的小朋友。于是有：
\[ dp_{j,0} = \left\{ \begin{array}{} dp_{j-w_i,0} + w_i & &dp_{j-w_i,0} > dp_{j,0}\\ dp_{j-w_i,0} + w_i & &dp_{j-w_i,0} \le dp_{j,0} \end{array} \right. \]\[ dp_{j,1} = \left\{ \begin{array}{} dp_{j-w_i,1} + 1 & &dp_{j-w_i,0} > dp_{j,0}\\ dp_{j-w_i,1} + 1 & &dp_{j-w_i,0} \le dp_{j,0} \end{array} \right. \]展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
const int N = 1e5 + 5;
ll n, m, x[N], dp[N][2];
int main() {
// freopen("THOI03F20.in", "r", stdin);
// freopen("THOI03F20.out", "w", stdout);
scanf("%d%d", &n, &m); m *= 6;
for(int i = 1; i <= n; ++i) scanf("%d", x + i);
for(int i = 1; i <= n; ++i) for(int j = m; j >= x[i]; --j) if(dp[j - x[i]][0] + x[i] > dp[j][0]) dp[j][0] = dp[j - x[i]][0] + x[i], dp[j][1] = dp[j - x[i]][1] + 1;
printf("%d\n", dp[m][1]);
return 0;
}
F 山麓的回音
因为只有一条路，所以可以搜索出路径，把所消耗的体力记作 \(V\), 所遇事件封进一个结构体加进 vector 里，最后对这个 vector 跑一个体积为 \(N-V\) 的 01 背包即可。
顺带一提，这个题全输出 \(0\) 可以拿 \(60pts\).
才不会告诉你们只有一条路是因为有多条我不会
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
struct task {
int a, b;
} d[105][105];
int n, m, h, x, y, c[105][105], v, dp[1005];
bool vis[105][105];
vector<task> e;
void dfs(int dx, int dy) {
if(dx < 1 || dx > n || dy < 1 || dy > m) return;
// cerr << dx << " " << dy << endl;
if(c[dx][dy] == -1) return;
// cerr << dx << " " << dy << endl;
if(vis[dx][dy]) return;
vis[dx][dy] = 1;
// cerr << dx << " " << dy << endl;
if(v + c[dx][dy] > h) return;
// cerr << dx << " " << dy << endl;
// cout << d[dx][dy].a << " " << v << endl;
v += c[dx][dy];
e.push_back(d[dx][dy]);
if(dx == x && dy == y) return;
dfs(dx - 1, dy);
dfs(dx, dy - 1);
dfs(dx + 1, dy);
dfs(dx, dy + 1);
}
int main() {
// freopen("THOI03E05.in", "r", stdin);
// freopen("THOI03E05.out", "w", stdout);
scanf("%d%d%d", &n, &m, &h);
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &d[i][j].a);
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &d[i][j].b);
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &c[i][j]);
// cout << c[1][2] << endl;
scanf("%d%d", &x, &y);
// e.push_back({-1, -1});
// cout << n << " " << m << endl;
dfs(n, m);
// cerr << "Antipathy world.\n";
for(int i = 1; i < e.size(); ++i) {
for(int j = h - v; j > e[i].b; --j) dp[j] = max(dp[j], dp[j - e[i].b] + e[i].a);
// cerr << e[i].a << " " << e[i].b << " a\n";
}
printf("%d\n", dp[h - v]);
return 0;
}
EXTRA 群星的闪耀
