#809 div2
https://codeforces.com/contest/1706
A:
题目:
现在你有一个长度为 m 的字符串,并且有一个长度为 n 的序列。
现在你可以执行 n 次操作,两种情况
1.将下标为 ai 的字符替换为 A
2.将下标为 (m + 1 - ai) 替换为 A
现在让你执行多次操作,使得最终得到的字符串字典序最小,输出最小字典序的字符串
思路:
枚举 n 次操作,每次比较两个位置,最优肯定是先替换下标小的为A,但是如果已经有A,那么就替换另一个
代码
void solved()
{
string s;
cin >> n >> m;
for(int i = 0; i < m; i++) s+= 'B';
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++)
{
int a1 = a[i], b = m + 1 - a[i];
int now;
if(s[a1 - 1] == 'B'&& s[b - 1] == 'B') now = min(a1, b);
else
{
if(s[a1 - 1] == 'B') now = a1;
else now = b;
}
s[now - 1] = 'A';
}
cout << s << endl;
}
B:
题目:
现在你有一个长度为 n 的颜色序列,第 i 块颜色为 ci。
你现在要按如下操作放置方块。
第一块放在 (0, 0)
其他块可以放在上一块放置位置的上左右位置。
现在让你输出一个长度为 n 的序列,第 i 个位置你需要输出颜色为 i 的最优组成塔的高度。每一个颜色都是独立的。
思路:
对于每个颜色单独考虑。
假设已经放置了一个颜色方块作为第一个,如果我们还想放下一个相同颜色的方块在他的上面,要么下一个就是相同颜色的。
要么距离下一个相同颜色中间差了偶数个方块,那么我们可以实现放在他的上面。假如说中间差了奇数个,那么我们不用考虑他,把它当作不同颜色的为下一次方块做铺垫。
代码
void solved()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], ans[i] = 0, pos[i] =0;
for(int i = 1; i <= n; i++)
{
int x = a[i];
if(pos[x] == 0) pos[x] = i, ans[x] = 1;
else if((i - pos[x] - 1 ) % 2 == 0) ans[x]++, pos[x] = i;
}
for(int i = 1; i <= n; i++) cout << ans[i] << " ";
cout << endl;
}
C:
题目:
现在有 n 个建筑,每个建筑存在一个高度。我们定义如果一个建筑严格大于两边的建筑,那么这个建筑是好建筑。
特别的第 1 个和第 n 个一定不是好建筑。
现在你可以对任意一个建筑增加高度,但是代价是相同的。
现在让你构造好的建筑最多但是代价最小是多少?
思路:
我们将 n 分成奇偶。
不难发现奇数情况时,我们只有一种构造使得构造好的建筑最多。
所以我们只用讨论偶数情况。
不难发现偶数情况时候,必定存在两个连续的空位不是好的建筑,从而变成奇数情况。
所以我们就枚举一下两个空位的情况。
并且通过前缀和来维护间隔增加的代价。
对于两个空位前面的来说,是从 0 1 0 1 0 1,这样的序列开始的。
对于两个空位后面的来说,从 1 0 1 0 1 0 , 这样的序列,所以我们维护一个从前往后和一个从后往前的即可
代码
void solved()
{
cin >> n;
for(int i = 0; i <= n + 5; i++) qz0[i] = 0, hz1[i] = 0, w[i] = 0;
for(int i = 1; i <= n; i++) cin >> a[i];
int cnt = 0;
for(int i = 2; i <= n - 1; i++)
{
int mxx = max(a[i - 1], a[i + 1]);
if(mxx >= a[i]) w[i] = mxx + 1 - a[i];
}
for(int i = 1; i <= n; i++)
{
if(cnt % 2 == 0) qz0[i] = qz0[i - 1];
else qz0[i] = qz0[i - 1] + w[i];
cnt++;
}
for(int i = n; i >= 1; i--)
{
if(cnt % 2 != 0) hz1[i] = hz1[i + 1] + w[i];
else hz1[i] = hz1[i + 1];
cnt++;
}
if(n % 2 != 0)
{
cout << qz0[n] << endl;
return;
}
int ans = 1e18;
for(int i = 1; i <= n; i += 2)
{
ans = min(ans, qz0[i - 1] + hz1[i + 2]);
}
cout << ans << endl;
}
D1
题目:
现在给出了你一个长度为 n 的序列,和一个 k。
现在你需要构造一个 p 数组。
现在我们需要找到 max[ai / pi] - min[ai / pi] 的最小值。
思路:
观察得到数据范围很小,我们可以暴力。
我们不妨枚举其中的最大值,这样我们只需要让最小值尽可能最大就行。
找最小值时候可以二分找到尽可能接近最大值的,因为满足二段性。
代码
void solved()
{
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
if(k > a[n])
{
cout << 0 << endl;
return ;
}
int ans = 1e9;
for(int mxx = a[n] / k; mxx <= a[n]; mxx++)
{
int minn = 1e9;
bool flag = true;
for(int j = n ; j >= 1; j--)
{
if(a[j] / k > mxx)
{
flag = false;
break;
}
int l = 1, r = k;
while(l < r)
{
int mid = l + r >> 1;
if(a[j] / mid <= mxx) r = mid ;
else l = mid + 1;
}
minn = min(minn, a[j] / r);
}
if(flag)
{
ans = min(ans, mxx - minn);
}
}
cout << ans << endl;
}