本周进行了标准OI普及组模考测试
得分情况
| 题目名称 | 做法 | 预计得分 | 实际得分 |
|---|---|---|---|
| A 小信倒油 | 模拟 | 100 | 40 |
| B 小信的基因重组 | 数组哈希 | 10 | 0 |
| C 小信的蜂巢交通 | 并查集 | 0 | 10 |
| D 小信的翘课计划 | DP | 10 | 10 |
点进第一题，题目描述很模糊，有点读不懂，后来理解了一会儿明白了题目大意
直接排个序，随后每个油壶对应每个油桶即可
可惜我理解错了题目的意思，以为一个油壶可以分别倒在不同的油桶里面，结果同时60分
接着看第二题，嗯，一开始以为是子序列，所以用map写了一遍，样例不对，后面才发现是字串，就很烦
想要暴力骗分，结果最小测试点都要 O(80^4) ，会超时，后来实在不会输出0骗了0分
接着看第三题，没看多久我就想：这太简单了吧！不就是最小生成树模版或者并查集模版吗？
于是我写了半天，样例不过，我调了两年半都没过，后来想：是不是只能用并查集？我又吭哧吭哧写了一个并查集的做法，样例没过，后来我终于看到原来是有向图！！！
所以我不废了，只好输出样例，居然骗了10分
赛后我看好多人用并查集和最小生成树过了，样例过于水了，他们都是用无向图的思路过的，呜呜呜呜呜呜呜呜呜呜 \times 114514
最后看第四题，嗯~~~，看了半天题目都没看懂，想不出来样例1为什么输出3，最后又双叒叕输出-1不可以总司令骗了10分
总结：
题目理解能力不够，像第一题就因为没有理解而逝去了60分
阅读题目不够仔细，第二题理解成子序列，第三题以为是无向图，花费了大量的时间却一筹莫展，导致后面的题没多少时间思考了
题目讲解
A 小信倒油
很简单，前提是你完全理解了题目意思
正解就是用输入完升序排序
枚举每一个油壶（油杯），看看装不装得下，装不下直接输出-1，否则 res=min(res,a[i] *1.0/i)
最后输出 res 即可
code
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
if (a[i] > i) {
cout << -1;
return 0;
}
res = min(res, a[i] * 1.0 / i);
}
B 小信的基因重组
一点也不简单，主要是想不到思路
其实是数组哈希！把 vector 数组放进 map 里面！！！
先枚举第一个字符串的所有字串，用一个数组 cnt 存储每个字母出现的次数，随后 mp[cnt] = true
接着枚举第二个字符串的每一个字串（长度从长到短），看看 mp[cnt2]有没有，有的话直接输出！
code
for (int i = min(len1, len2); i >= 1; i--) {
map <vector<int>, int> mp;
vector<int> cnt1(26);
for (int j = 0; j < i; j++) {
cnt1[s1[j] - 'a']++;
}
mp[cnt1] = 1;
for (int j = i ; j < len1; j++) {
cnt1[s1[j] - 'a']++;
cnt1[s1[j - i] - 'a']--;
mp[cnt1] = 1;
}
vector<int> cnt2(26);
for (int j = 0; j < i; j++) {
cnt2[s2[j] - 'a']++;
}
if (mp.count(cnt2)) {
cout << i << "\n";
return 0;
}
for (int j = i ; j < len2; j++) {
cnt2[s2[j] - 'a']++;
cnt2[s2[j - i] - 'a']--;
if (mp.count(cnt2)) {
cout << i << "\n";
return 0;
}
}
}
C 小信的蜂巢交通
简单！（因为样例过水，当做无向图即可）
我使用并查集的思路做的， 枚举每一个点，如果加上这条边会成环，那当然不加（也就是删掉，也是最小生成树的思路）输出，注意这里只需要输出 m-n\times 2 个答案即可
code
int sum = m - 2 * n;
for (int i = 1 ; i <= m ; i++) {
if (sum == 0) return 0;
if (find(s[i].first) == find(s[i].second)) {
cout << s[i].first << " " << s[i].second << " ";
sum--;
} else {
bing(s[i].first, s[i].second);
}
}
D 小信的翘课计划
呃呃呃，是个世纪难题DP，根本不会~~~呜呜呜