本周进行了标准OI普及组模考测试
得分情况
| 题目名称 | 做法 | 预计得分 | 实际得分 |
|---|---|---|---|
| A 调酒大师 | 数学 | 60 | 0 |
| B 树上最小点覆盖 | 树形 | 100 | 5 |
| C 小信的数学题 | 暴力枚举 | 20 | 50 |
| D 小信的魔方 | 数学 | 10 | 0 |
点进第一题，发现是数学题，先写了5分钟的if、else，结果样例不对，后来我换了一种思路，因为果汁、白酒都是原料，本质没有区别，所以交换n和m没问题，那么我们就不妨把n设为少的，m设为多的，分别考虑全部的配方都是2+2的情况与1+3的情况，取max，样例过了，我就提交了
接下来我看第二题，发现是树的问题，而且很像树形DP，所以我就写了一个树形DP的模版，结果不会写状态转移方程了，思考了好久的方程还是错的
这时候我旁边的大聪明 @HIM 小声嘟囔：“第二题我暴力样例过了”，正加上我这是状态转移方程不对，我开始怀疑自己，是不是真的用暴力能过，随后我又看了一下数据范围，算了一下暴力的时间复杂度，发现并不会超时，所以我直接脑抽写了一个暴力代码样例过了直接提交，结果赛后只得了WA5分
接着我看第三题，嗯，好像也是一个数学题，后来发现不是，我思考了半天也只想到暴力，于是我开始写暴力，但是我发现用一堆要求，什么不同的数字、去掉前导0、数位向左对齐的，十分麻烦，我越写越迷糊，后来调试了1个小时，都快把我脑子炸了，还是没发现问题，我实在不想写了（因为当时感觉脑细胞用完了，脑子里全是一片空白），于是输出1骗分，没想到不可以总司令骗到了整整50分！
接着看向第四题，发现复杂的不得了，我当时处于昏头昏脑的状态，几乎没力气思考，所以输出了*骗分，但是可能因为我第3题骗了50分，所以这题我没骗到分
最后20分钟的时候我发现了我第一题代码的漏洞，就是处理不了5 3这组数据，正确输出是2，我只输出了1，于是我又加了一堆if和else，样例过了，提交上去，结果最后WA0分，真是令我大吃一惊……
题目讲解
一道数学题，我们可以先视果汁和白酒可以单独用，也可以混合用，那么答案就是(n + m) / 4，但是，现实很残酷，我们不能只用一种，两种必须都用到，那么我们就尽量少用而达到(n + m) / 4的效果，所以我们还要对n和m取min，那么答案就出来了：
ans = min((n + m) / 4, min(n, m))
所以这道题目就被我们简化成了一个语法题，直接套公式即可
code
while (t--) {
cin >> n >> m;
cout << min((n + m) / 4, min(n, m)) << endl;
}
一道树形DP的模板题，就是输入繁琐了一点
状态定义
我们设dp[i][0]为在i点不放小士兵的最少小士兵数量，dp[i][1]为在i点不放小士兵的最少小士兵数量
那么我们知道，在这个点放了小士兵，那么小士兵数量至少为1了，所以我们初始化dp[u][1] = 1
接着，我们想，如果这个点没有放小士兵，那么它的子节点就必须放小士兵，否则这个点就不能被观察到，所以dp[u][0] += dp[v][1]
如果我们在这个点放置了小士兵，那么下一个点就不一定必须放小士兵了，而是放和不放的最小值，所以dp[u][1] += min(dp[v][1], dp[v][0])
这样一来，我们的状态转移方程就全推完了
这样我们直接套模板即可
code
void dfs(int u, int fa) {
dp[u][0] = 0;//加不加没关系
dp[u][1] = 1;
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] += dp[v][1];
dp[u][1] += min(dp[v][1], dp[v][0]);
}
return;
}
我认为最复杂的一道题目，也是最简单的一道题目
没有什么优化算法，就是纯暴力枚举所有的字母代表的数字的情况，看看能不能使等式成立，成立的话就去res++
code
inline void solve() {
int idx = 0, res = 0;
for (auto i : st) {
cnt2[idx++] = i - 'A';
}
for (int i = 0; i <= 9; i++) {
a[i] = i;
}
do {
for (int i = 0; i < idx; i++) cnt[cnt2[i]] = a[i];
bool flag = false;
for (int i = 1; i <= n; i++) {
if (cnt[s[i][0] - 'A'] == 0) {
flag = true;
break;
}
}
if (flag) continue;
int sum = 0, ans = 0;
for (int i = 1; i < n; i++) {
int sum1 = 0;
for (ll j = 0; j < s[i].size(); j++) {
sum1 = sum1 * 10 + cnt[s[i][j] - 'A'];
}
sum += sum1;
}
for (int j = 0; j < s[n].size(); j++) ans = ans * 10 + cnt[s[n][j] - 'A'];
if (sum == ans) res++;
} while (next_permutation(a, a + 10));
int sum = 1;
for (int i = 1; i <= 10 - idx; i++) sum *= i;
cout << res / sum << endl;
}
这题有了思路以后就是非常简单
看一看每个数字原来应该存在于哪个位置，随后每次枚举行或者列，如果这个点不对就开始疯狂swap，注意行和列都要枚举
至于还原不了的情况，其实不用考虑，因为测试点很水，没有还原不了的情况
code
for (int i = 1 ; i <= n ; i++) {
for (int j = 1 ; j <= m ; j++) {
cin >> a[i][j];
cnt[i] = (a[i][j] + m - 1) / m;
cnt2[j] = (a[i][j] - 1) % m + 1;
}
}
int res = 0;
for (int i = 1 ; i <= n ; i++) {
while (cnt[i] != i) {
swap(cnt[i], cnt[cnt[i]]);
res++;
}
}
for (int i = 1 ; i <= m ; i++) {
while (cnt2[i] != i) {
swap(cnt2[i], cnt2[cnt2[i]]);
res++;
}
}