CF1705 B, C, D1 题解
B. Making Towers
思路
观察题面上给第一个样例提供的图:
可以发现,如果我们要让某种颜色形成一个塔,除非多个相同颜色在 数组中挨在一起,可以直接向上排布。就一定需要在排布该颜色后,向两侧放一些其他颜色,然后又往相反方向放置,最后使得两个颜色相同的块在一条直线上,大概是下面这样:
⬆->->->A
⬆<-<-<-A<-<-<-⬆
A->->->⬆
1 2 ... z
其中, 表示一个颜色的塔,而箭头表示放置颜色块的路径。
观察发现,在放置两个 之间,需要放置偶数个其他颜色块,下面是解释:
假设第一个 的位置是 ,并且我们往右侧放置的其他颜色块的数量是(也可以是左侧) 。
那么为了把第二个 搞到 上,就需要在 和 这些位置上放置颜色块,共计 个块,因此是偶数(直接网上堆的话是 个,也是偶数)。
这就意味着,假设有两个相同的颜色块 和 ,它们在 数组中的位置分别是 和 。只有 为奇数时,才可能把 叠到 上面,或是 叠到 上。
并且,只有 和 的奇偶性不同, 才可能为奇数。
然后就可以使用 dp 的方法来解决这个题目,我们对每种颜色都重复一遍相同的 dp 过程(其实更像是递推)。设 为 数组中,使用 个该颜色的块最高能垒成多高的塔。
那么 就可以从 中转移而来( ),并且如前面所说 和 的奇偶性应该不同。
同时,我们需要找的是,最近的奇偶性不同的块,要不然可能造成浪费,或者是在前面已经放过的位置又放了一个块。
代码
//author: tzyt
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int c[n + 1];
vector<int> cpos[n + 1], ans(n + 1);
set<int> unqc; // 储存所有不同的颜色
for (int i = 1; i <= n; i++) {
cin >> c[i];
cpos[c[i]].push_back(i);
unqc.insert(c[i]);
}
int dp[n + 1];
for (int cur : unqc) {
fill(dp, dp + cpos[cur].size(), 1);
// 不管怎样,只要有块,总能垒成高度为 1 的塔
int mx = 1;
// dp[0 ~ cpos[cur].size()] 中最大的
int lstod = -1, lstev = -1;
// 最近的奇数位置和偶数位置,-1 为初始值
cpos[cur][0] & 1 ? lstod = 0 : lstev = 0;
// 判断第一个的奇偶性
for (int i = 1; i < cpos[cur].size(); i++) {
int lst = cpos[cur][i] & 1 ? lstev : lstod;
if (lst != -1)
dp[i] = dp[lst] + 1;
// lst 为第一个奇偶性不同的位置
mx = max(dp[i], mx);
cpos[cur][i] & 1 ? lstod = i : lstev = i;
// 更新最近的奇数位置和偶数位置
}
ans[cur] = mx;
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
}
C. Qpwoeirut And The City
思路
能发现,不管怎么样,城市中酷的房子最多有 个。
如果是奇数个的话,只有一种排布方法能达到这么多个酷的房子。也就是第一个样例展示的。
从第二个房子开始,把每个偶数位置的房子都搞成酷的,也就是酷和不酷的房子隔着出现。
计算把一个普通房子变成酷的房子的代价可以用如下方法:
inline ll calc_cost(int i, int* h) {
if (h[i] <= h[i - 1] || h[i] <= h[i + 1])
return max(h[i - 1], h[i + 1]) - h[i] + 1;
else
return 0;
}
也就是把当前的房子搞的比相邻的最高的房子还要高一格。
但是偶数个房子的情况就比较复杂了。这种情况下 一定等于 。
那么就会有 个不酷的房子,也就一定有两个连在一起出现的不酷的房子,而这两个连续的不酷的房子可以出现在任何位置,我们需要考虑所有的情况。
比如 那么有如下几种排布方式。
但是如果从头到尾的把所有情况都计算一遍,时间就不够了。
所以我们可以只计算从一种情况到另一种情况之间代价的变化量。
比如:
这个过程中,第六个房子从酷变为不酷,第七个房子从不酷变为酷。
假设我们当前正在把第 个房子从酷变为不酷,第 个房子从不酷变为酷。我们只需要调用前面的 calc_cost
减去 的价格再加上 的价格就行了。
//author: tzyt
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline ll calc_cost(int i, int* h) {
if (h[i] <= h[i - 1] || h[i] <= h[i + 1])
return max(h[i - 1], h[i + 1]) - h[i] + 1;
else
return 0;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int h[n + 1];
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
ll ans = 0, tmp = 0;
// 奇数情况的解法
for (int i = 2; i < n; i += 2) {
ans += calc_cost(i, h);
}
if (n & 1) {
cout << ans << '\n';
continue;
}
tmp = ans;
for (int i = n - 2; i >= 2; i -= 2) {
// 枚举连续 0 的位置
tmp -= calc_cost(i, h);
tmp += calc_cost(i + 1, h);
ans = min(ans, tmp);
}
cout << ans << '\n';
}
}
D1. Chopping Carrots (Easy Version)
思路
我们尝试设最小的 为 。那么 ,因为 最小为 ,那 就是 了。
在这个的基础上,我们再贪心的尝试让每个 都尽可能的接近 ,这样就可以尽可能的让最大的 更小。
这样我们就可以算出 ,因为 ,所以 。当然, 不能大于 ,并且如果 ,我们就让 。
然后我们去枚举每个可能的 ,并且计算该情况下的最大的 ,就能得到答案了。思路好像挺简洁,但是真的挺难想的,
代码
// author: tzyt
#include <bits/stdc++.h>
using namespace std;
#define IINF 0x3f3f3f3f
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int a[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = IINF;
int mxv = 0;
for (int mnv = 0; mnv <= a[1]; mnv++) {
// 枚举 mn
for (int i = 1; i <= n; i++) {
int p = min(k, (mnv ? (a[i] / mnv) : k));
// mnv ? (a[i] / mnv) : k 是因为 mnv 为 0 的情况
mxv = max(mxv, a[i] / p);
}
ans = min(ans, mxv - mnv);
}
cout << ans << '\n';
}
}