NOIP 2004 提高算法题解
作者: | 更新日期:
涉及模拟、哈夫曼贪心、动态规划与搜索剪枝等算法。
本文首发于公众号：天空的代码世界，微信号：tiankonguse
零、背景
今天继续分享 2004 年 NOIP 提高题解。
一、津津的储蓄计划
题意：每个月妈妈会给津津 300 元零花钱，津津每个月有一定的花销，剩余的钱会按 100 元整的方式存到妈妈那里。
年底，妈妈会把存的钱按 20% 的利息全部返还给津津。
问是否会发生某个月津津零花钱不够花，此时输出第一个不够花的月数。
如果够花，输出最后带上利息津津共有多少钱。
思路：模拟
记录上个月把 100 元整存之后剩余的钱，加上新的 300 元，减去当月花销，就是剩下的钱。
int Process() {
int ans = 0;
int pre = 0;
for (int i = 0; i < n; i++) {
pre += 300;
pre -= nums[i];
if (pre < 0) {
return -(i + 1);
}
ans += pre / 100 * 100;
pre %= 100;
}
return ans + ans / 100 * 20 + pre;
}
二、合并果子
题意：有 n 堆果子，每次可以选择两堆合并为一堆，代价是两堆果子的个数之和。
经过 n-1 次合并后，就只剩一堆果子。
问怎么合并，总代价最小，输出总代价。
思路：哈夫曼贪心&双队列优化
这个是典型的哈夫曼合并问题，每次合并最小的两堆即可。
维护一个最小堆，模拟合并。
复杂度：O(n log(n))
ll ans = 0;
while (que.size() > 1) {
ll a = que.top();
que.pop();
ll b = que.top();
que.pop();
ans += a + b;
que.push(a + b);
}
printf("%lld\n", ans);
对于加强版数据，堆数为 N=10^7，模拟只能得 60 分。
分析特征，可以发现，对于合并后的果子数量是递增的。
故，如果新增一个合并后的序列，只需要把新合并的果子追加到序列后面即可。
复杂度：O(n)
ll ans = 0;
while (n > 1) {
n--;
ll x = PopMin();
ll y = PopMin();
ll cost = x + y;
ans += cost;
PushVal(cost);
}
双队列保持有序性即可。
ll PopMin() {
if (q2.empty()) {
ll x = q1.front();
q1.pop();
return x;
}
if (q1.empty()) {
ll x = q2.front();
q2.pop();
return x;
}
if (q1.front() <= q2.front()) {
ll x = q1.front();
q1.pop();
return x;
} else {
ll x = q2.front();
q2.pop();
return x;
}
}
void PushVal(ll x) {
if (q2.empty()) {
q2.push(x);
} else if (q1.empty()) {
q1.push(x);
} else if (q1.back() <= x) {
q1.push(x);
} else {
q2.push(x);
}
}
还有一个问题是最初的 n 堆果子怎么得到有序序列。
初始每堆果子个数不超过 V=10^5，故可以使用堆排序，把复杂度压缩到 max(N, V)。
for (int i = 0; i < n; i++) {
int v = read();
a[v]++;
}
for (int i = 0; i < kMaxVal; i++) {
while (a[i]) {
q1.push(i);
a[i]--;
}
}
三、合唱队形
题意：n 个同学站成一排，问至少淘汰几个同学，使得剩余同学的身高满足先升序再降序。
思路：枚举+动态规划
状态定义1：dpPre[i] i 作为最后一个同学，满足升序淘汰最少同学的数量。
状态定义2：dpSuf[i] i 作为第一个同学，满足降序淘汰最少同学的数量。
状态转移方程：
if(V[j] < V[i]){
dpPre[i]=min(dpPre[j] + i - j -1);
}
然后枚举峰值，两边的最优值求和。
int Solver(int mid) { // mid 为最高点
return DfsPre(mid) + DfsSuf(mid);
}
复杂度：O(n^2)
优化：LIS 可以使用二分查找加速。
复杂度：O(n log(n))
四、虫食算
题意：给三个 n 位的 n 进制数字，两个相加等于另外一个。
现在相同的数字被相同的字母代替，求每个字母对应哪个数字。
n的数据范围：
30% 小于 10。
50% 小于 15。
100% 小于 26。
思路：搜索+剪枝
很容易想到从后到前枚举每个字母的值，判断是否是答案。
复杂度：O(n!)
得分：70分。
bool Dfs1(const int p, const int carry) {
if (p == -1) {
if (carry == 0) {
return true;
} else {
return false;
}
}
const int c1 = s1[p] - 'A';
if (charToVal[c1] != -1) {
return Dfs2(p, carry);
}
for (int i = 0; i < n; i++) {
if (valToChar[i] == 0) {
charToVal[c1] = i;
valToChar[i] = c1;
if (Dfs2(p, carry)) {
return true;
}
charToVal[c1] = -1;
valToChar[i] = 0;
}
}
return false;
}
超时的原因是搜索树太大了，所以需要剪枝。
很容易想到一个剪枝：如果低位枚举一些字母后，某个高位三个字母的值也都确定时，我们可以快速判断是否合法。
例如 AAAADBA + BBBBECB = DEDFCCC。
A、B、C 三个字母确定后，很多位都可以判断是否成立的。
这个优化加上后，很可惜，只有80分。
// 不考虑进位，看高位是否冲突
bool Check(const int p) {
for (int i = 0; i <= p; i++) {
const int c1 = s1[i] - 'A';
const int c2 = s2[i] - 'A';
const int c3 = s3[i] - 'A';
const int v1 = charToVal[c1];
const int v2 = charToVal[c2];
const int v3 = charToVal[c3];
// case1: 最高位，不能进位
if (i == 0 && v1 != -1 && v2 != -1) {
if (v1 + v2 >= n) return false;
}
// case2: 进位与不进位都不行
if (v1 != -1 && v2 != -1 && v3 != -1) {
if ((v1 + v2) % n != v3 && (v1 + v2 + 1) % n != v3) return false;
}
// case3: 其中一个没有赋值，推导出来的值冲突
if (v1 != -1 && v2 != -1 && v3 == -1) {
const int val1 = (v1 + v2) % n;
const int val2 = (v1 + v2 + 1) % n; // 有进位
if (valToChar[val1] != 0 && valToChar[val2] != 0) return false;
}
}
return true;
}
还可以想到一个优化：先枚举出现次数多的字母。
字母出现次数越多，枚举一次被检查到冲突的概率也会更高。
得分：90分。
cnt.resize(n, 0);
maxPos.resize(n, -1);
for (int i = 0; i < n; i++) {
cnt[s1[i] - 'A']++;
cnt[s2[i] - 'A']++;
cnt[s3[i] - 'A']++;
// 如果次数相同，优先搜索后面的字符
maxPos[s1[i] - 'A'] = max(maxPos[s1[i] - 'A'], i);
maxPos[s2[i] - 'A'] = max(maxPos[s2[i] - 'A'], i);
maxPos[s3[i] - 'A'] = max(maxPos[s3[i] - 'A'], i);
}
valList.resize(n);
orderChar.reserve(n);
for (int i = 0; i < n; i++) {
valList[i] = n - 1 - i;
orderChar.push_back({cnt[i], maxPos[i], i});
}
valNum = n;
// 逆序排序
sort(orderChar.begin(), orderChar.end(), greater<tuple<int, int, int>>());
分析前面的剪枝，其中一个没有赋值的情况有三种，而上面只实现了一种。
把另外两种补齐，就可以得到 100 分了。
// 不考虑进位，看高位是否冲突
bool CheckNoConflict() {
int carry = 0;
int full = 1;
for (int i = n - 1; i >= 0; i--) {
const int c1 = s1[i] - 'A';
const int c2 = s2[i] - 'A';
const int c3 = s3[i] - 'A';
const int v1 = charToVal[c1];
const int v2 = charToVal[c2];
const int v3 = charToVal[c3];
if (full == 1 && v1 != -1 && v2 != -1 && v3 != -1) {
const int sum = v1 + v2 + carry;
const int val3 = sum % n;
const int carry3 = sum / n;
if (val3 != v3) return false;
carry = carry3;
continue;
}
full = 0;
carry = 0;
// case1: 进位与不进位都不行
if (v1 != -1 && v2 != -1 && v3 != -1) {
if ((v1 + v2) % n != v3 && (v1 + v2 + 1) % n != v3) return false;
}
// case2: 最高位，不能进位
if (i == 0 && v1 != -1 && v2 != -1) {
if (v1 + v2 >= n) return false;
}
// case3: v3 没有赋值，推导出来的值冲突
if (v1 != -1 && v2 != -1 && v3 == -1) {
const int val1 = (v1 + v2) % n;
const int val2 = (v1 + v2 + 1) % n; // 有进位
if (valToChar[val1] != 0 && valToChar[val2] != 0) return false;
}
// case4: V1 没有赋值，判断是否有冲突
if (v1 == -1 && v2 != -1 && v3 != -1) {
if (!CheckSubtractionOK(v3, v2, c1)) {
return false;
}
}
// case5: V2 没有赋值，判断是否有冲突
if (v1 != -1 && v2 == -1 && v3 != -1) {
if (!CheckSubtractionOK(v3, v1, c2)) {
return false;
}
}
}
// 全枚举完了，最后有进位
if (full == 1 && carry != 0) return false;
return true;
}
五、最后
这次比赛第二题哈夫曼贪心的加强版比较难，需要把最小堆转化为双队列才能通过。
而第四题搜索，剪枝需要写完整才能通过。
《完》
-EOF-
本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code
本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。
