Codeforces Round #695 (Div. 2)
A. Wizard of Orz
题意
一排 个屏幕最初都是 0，每秒同时加 1，9 的下一位回到 0。可以先暂停一个屏幕，距离它 的屏幕再过 秒暂停，问最后从左到右能组成的最大数字串。
思路
先让第一位尽量大，取 9。第二位只能和它差 1，能取到的最大值就是 8，所以在第二个屏幕显示 8 时暂停它。
往右每远一格就晚停一秒，后面依次是 9,0,1,2,...。长度为 1 时输出 9，其他情况从 98 开始接，时间 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int t, n;
int main() {
cin >> t;
while(t--) {
cin >> n;
if(n == 1) printf("9\n");
else if(n == 2) printf("98\n");
else {
printf("98");
for(int i = 3, j = 9; i <= n; i++) {
printf("%d", j);
j++;
if(j == 10) j = 0;
}
puts("");
}
}
return 0;
}B. Hills And Valleys
题意
一个位置严格大于左右两边是山峰，严格小于左右两边是山谷，首尾不算。最多修改一个数，问山峰和山谷的总数最少能剩多少。
思路
改 只会影响 这三个位置，其他地方不用重算。先把原来的峰谷数记下来，再枚举修改点，找最多能消掉几个。
这里试左右邻居各自减 1、相等、加 1 这几种值。最优时把当前数改成某个邻居就够了：既能抹平当前的峰谷，也不会比继续把它推向同一侧更差。每次只重算附近三个位置，试完恢复。
改首尾最多消掉旁边一个峰谷，单独计入。 时总能改到 0，整体时间 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 3e5 + 17;
int t, n, a[maxn], ans, v[maxn], s[maxn];
inline int pos(int x) {
if(a[x] > a[x - 1] && a[x] > a[x + 1]) return 1;
else if(a[x] == a[x - 1] || a[x] == a[x + 1]) return 2;
else if(a[x] < a[x - 1] && a[x] < a[x + 1]) return -1;
return 0;
}
inline int val(int x) {
if(x == 1 || x == n) return 0;
return (abs(pos(x)) == 1) ? 1 : 0;
}
inline int ck(int x) {
return val(x - 1) + val(x) + val(x + 1);
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
ans = 0;
for(int i = 0; i <= n + 2; i++) a[i] = 0, v[i] = 0, s[i] = 0;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
if(n <= 4) {
printf("0\n");
continue;
}
for(int i = 1; i <= n; i++) v[i] = val(i);
for(int i = 1; i <= n; i++) s[i] = v[i - 1] + v[i] + v[i + 1];
// for(int i = 1; i <= n; i++) printf("%d%c", v[i], " \n"[i == n]);
if(v[2] || v[n - 1]) ans = max(ans, 1);
for(int i = 2; i < n; i++) {
int st = a[i];
for(a[i] = a[i - 1] - 1; a[i] <= a[i - 1] + 1; a[i]++) {
int tmp = ck(i);
// for(int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
// if(a[i] == 6) printf("%d %d\n", tmp, s[i]);
if(tmp < s[i]) ans = max(ans, s[i] - tmp);
}
for(a[i] = a[i + 1] - 1; a[i] <= a[i + 1] + 1; a[i]++) {
int tmp = ck(i);
if(tmp < s[i]) ans = max(ans, s[i] - tmp);
}
a[i] = st;
}
ans *= -1;
for(int i = 1; i <= n; i++) ans += v[i];
printf("%d\n", ans);
}
return 0;
}