A
编号为 \(n\) 的一定选，第二叠书在 \(1\sim n - 1\) 选最大的。
void solve() {
cin >> n;
for(int i = 1; i <= n; ++ i) {
cin >> a[i];
}
int ans = a[n];
int x = 0;
for(int i = 1; i < n; ++ i) {
x = max(x, a[i]);
}
cout << ans + x << '\n';
}
B
如果上来 \(b\) 就小于 \(a\)，那么 \(n\) 个馒头都用 \(a\)。否则看 \(b\) 什么时候小于 \(a\)，在他之前卖 \(b\)，之后卖 \(a\)。
void solve() {
ll n, a, b; cin >> n >> a >> b;
if(b <= a) {
cout << a * n << '\n';
}
else {
ll x = b - a;
ll y = n - x;
if(x >= n) {
cout << (b + (b - n + 1)) * n / 2 << '\n';
}
else {
cout << (b + (b - x + 1)) * x / 2 + a * y << '\n';
}
}
}
C
1300 太少了。
打表找的规律，有优美做法后补。
void solve() {
ll n, k;
cin >> n >> k;
ll mx = 0;
for(int i = 1; i <= n; ++ i) {
mx += abs(n - i + 1 - i);
}
if(k & 1 || k > mx) {
cout << "No\n";
return;
}
if(k == 0) {
cout << "Yes\n";
for(int i = 1; i <= n; ++ i) {
cout << i << " \n"[i == n];
}
return;
}
for(int i = 1; i <= n; ++ i) {
a[i] = 0;
}
k /= 2;
for(int i = 1; i <= (n + 1) / 2; ++ i) {
int tmp = n + 1 - 2 * i;
if(tmp >= k) {
a[i + k] = i;
int p = 1;
for(int j = i + 1; j <= n; ++ j) {
while(a[p]) {
++ p;
}
a[p] = j;
}
cout << "Yes\n";
for(int j = 1; j <= n; ++ j) {
cout << a[j] << " \n"[j == n];
}
return;
}
k -= tmp;
a[n - i + 1] = i;
/*
i + 1 --> n - i + 1
n + 1 - 2i
*/
}
}
D
首先，初始排名最大的不需要删人。
如果编号为 \(i\) 的人初始不是最大，必需要把 \(1\sim i - 1\) 全部删掉，否则分数加不到他头上。
此时 \(i\) 的总分为 \(\sum_{i = 1}^n a_i\)，检查这个数是否大于等于 \(i + 1\sim n\) 的最大值。
如果成立，那么 \(i\) 此时就是最大的，需要删 \(i - 1\) 次。
否则还要把 \(i + 1 \sim n\) 里最大的加到自己头上，需要删 \(i\) 次。
void solve() {
cin >> n >> c;
for(int i = 1; i <= n; ++ i) {
cin >> a[i];
}
a[1] += c;
suf[n + 1] = 0;
for(int i = n; i >= 1; -- i) {
suf[i] = max(suf[i + 1], a[i]);
}
int p = 0;
for(int i = 1; i <= n; ++ i) {
if(suf[1] == a[i]) {
p = i;
break;
}
}
ll cur = 0;
for(int i = 1; i <= n; ++ i) {
if(i == p) {
cout << 0 << ' ';
}
else if(a[i] + cur >= suf[i + 1]) {
cout << i - 1 << ' ';
}
else {
cout << i << ' ';
}
cur += a[i];
}
cout << '\n';
}
E
-
暴力怎么做？
贪心的用 \(s\) 的 \(0\) 使 \(t\) 的 \(1\) 先变多，再用 \(t\) 的 \(1\) 使 \(s\) 的 \(1\) 变多。
-
能影响 \(s_i \to 1\) 的有效范围是多少？
\(s_i\) 取决于 \(t_{i - 1}\) 和 \(t_{i + 1}\) 是否为 \(1\)。
\(t_{i - 1}\) 取决于 \(s_{i - 2}\) 和 \(s_i\) 是否为 \(0\)，而 \(s_{i - 2} = 0\) 只与原始序列有关。
因此 \(s_i\) 的值只与 \([i - 2, i + 2]\) 有关。
我们不妨使整个 \(s\) 操作变为 \(s'\)。
对于一个询问 \([l, r]\)，\([l + 2, r - 2]\) 最后结果肯定是与 \(s'\) 一致的。
然后再单独处理左右边界。