目录
A - Divide a Cuboid
显然长方体必须被平行于某个面切开，否则不满足要求。
枚举被哪个面切开，设这个面是 \(a \times b\)，不属于这个面的棱长为 \(c\)，如果可以从正中间切开，即 \(c \bmod 2 = 0\) 时就从正中间切开，红蓝块个数差值为 \(0\)。否则，\(c \bmod 2 = 1\)，从正中间偏移 \(0.5\) 格切开最优，红蓝块个数差值为 \(a \times b\)。
由于 \(a, b, c \ge 2\)，所以没有边界情况，放心计算三种情况取最小值即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
ll Solve(ll a, ll b, ll c) {
return (a & 1) ? (b * c) : 0ll;
}
int main() {
ll a = Read(), b = Read(), c = Read();
Write(min(Solve(a, b, c), min(Solve(b, a, c), Solve(c, a, b))));
return 0;
}
B - Colorful Slimes
\(N\) 很小，考虑枚举操作二次数 \(k\)，容易发现此时 \(i\) 号颜色的史莱姆可以由 \(j\) 号颜色的史莱姆变换而来，当且仅当 \((i - j + N) \bmod N \le k\)，即操作二次数小于等于 \(k\)（若进行 \(p\) 次操作，那么可以在 \(k - p\) 次操作后购买史莱姆）。
因此只需从 \(0 \sim N - 1\) 枚举 \(k\)，对所有数取向前 \(k\) 个数及其本身的最小值求和，再加上 \(k \cdot x\) 即可。
复杂度 \(O(N^2)\)，当然貌似可以用三分降到 \(O(N \log N)\)，但是我懒。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 2005;
int n;
ll a[N], b[N];
int main() {
int i, j;
ll x;
n = Read(), x = Read();
ll ans = LONG_LONG_MAX;
for(i = 1; i <= n; i++) {
a[i] = b[i] = Read();
}
for(i = 0; i < n; i++) {
ll res = 0;
for(j = 1; j <= n; j++) {
b[j] = min(b[j], a[(j - i + n - 1) % n + 1]);
res += b[j];
}
ans = min(ans, res + x * i);
}
Write(ans);
return 0;
}