B.Power Sequence
易知(c^{i})为递增序列，猜想当(a_{i}) 也为递增序列时总代价最小。
证明：假设有 (i < j, a_{i} leq a_{j})；
由 (|x| + |y| = max{|x + y|, |x - y|}) ：
(|a_{i} - c^{i}| + |a_{j} - c ^{j}| = max{|a_{i} + a_{j} - c_{i} - c_{j}|, |a_{i} - a_{j} - c^{i} + c^{j}| })；
(|a_{j} - c^{i}| + |a_{i} - c ^{j}| = max{|a_{i} + a_{j} - c_{i} - c_{j}|, |a_{j} - a_{i} - c^{i} + c^{j}| })；
由于(a_{j} - a_{i} geq 0, c^{j} - c^{i} > 0)，所以 (|a_{i} - c^{i}| + |a_{j} - c ^{j}| leq |a_{j} - c^{i}| + |a_{i} - c ^{j}|)
又由于c为指数级增长，所以暴力处理即可（n 小的时候 c 的可能性多，n 大的时候 c 的可能性小，依次枚举）
#include <bits/stdc++.h>
using namespace std;
#define maxn 200000
#define MAXC 1000000
#define int unsigned long long
#define INF 9123372036854775807LL
int n, a[maxn], ans = INF;
int read() {
int x = 0, k = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0', c = getchar(); }
return x * k;
}
int abs(int a, int b) {
if(a < b) return b - a;
else return a - b;
}
bool check(int c) {
int tans = 0; bool ret = 1;
for(int i = 0, t = 1; i < n; i ++, t *= c) {
tans = tans + abs(a[i], t);
if(a[i] < t && t - a[i] >= ans) {
ret = 0;
break;
}
}
ans = min(ans, tans);
return ret;
}
signed main() {
n = read();
for(int i = 0; i < n; i ++) a[i] = read();
sort(a, a + n);
for(int c = 1; c < MAXC; c ++)
if(!check(c)) break;
printf("%lld
", ans);
return 0;
}
C.Multiples of Length
试想：若对一个数可以进行两次操作，第一次加上 (p * a)，第二次加上 (q * b)， 其中(p, q) 为变量， (a, b) 为不相等的常数，则该数一定可以变为 (0)。
由此，我们可以得出思路：
1.若只有一个数字：修改一次后每次变化为(0)。
2.若有一个以上的数字：可以第一步把第一个数字变为 (0)。第二步对剩下的 (n - 1) 个数字进行操作。第三步再对全体 (n) 个数字进行操作（第一个数字为 (0)不变，等价于 (a = n - 1, b = n)）。联立方程对每一个 (a_{i}) 解出 (p, q) 输出。
#include <bits/stdc++.h>
using namespace std;
#define maxn 400000
#define int long long
int n, a[maxn], rec[maxn];
int read() {
int x = 0, k = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0', c = getchar(); }
return x * k;
}
signed main() {
n = read();
for(int i = 1; i <= n; i ++) a[i] = read();
printf("1 1
%lld
", -a[1]);
if(n == 1) {
printf("1 1
0
1 1
0
");
return 0;
}
printf("2 %lld
", n);
for(int i = 2; i <= n; i ++) {
int s = a[i] % n, t = (a[i] - s) / n;
printf("%lld", s * (n - 1));
if(i != n) printf(" "); else printf("
");
rec[i] = t + s;
}
printf("1 %lld
", n);
printf("0 ");
for(int i = 2; i <= n; i ++) {
printf("%lld", -rec[i] * n);
if(i != n) printf(" "); else printf("
");
}
return 0;
}
D.Stoned Game
记石头的总数为 (S)。A.若存在一堆石头数目超过 (frac{S}{2}) ，则先手获胜（只需要一直拿这一堆即可）。
B.若并非如此，则所有石头数目 (leq frac{S}{2})。
若石头的总数为偶数：若先手走完后为情况 A，则接下来的先手获得胜利，即后手胜利。若先手走完后仍为情况B，则此时后手可以随意选择一堆石头拿走一个（由于B的前提条件此时必然还有可以拿的石堆）。分析在这两步之前：(a_{i} leq frac{S}{2})，走完之后 (S' = S - 2, frac{S'}{2} = frac{S}{2} - 1)。由于第一步走完之后进入B的条件与此相同，可知再拿走第二个石子满足：(a_{i} leq frac{S'}{2})。是以后手总有路可走，直到先手走完后为情况A胜利为止。
若石头的总数为奇数：先手可以随便拿走一个，原先：(a_{i} leq frac{S - 1}{2})， 现(S' = S - 1)，总数变为偶数且仍为B情况。所以此时后手即先手胜利。
#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
int a[maxn];
int read() {
int x = 0, k = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0', c = getchar(); }
return x * k;
}
int main() {
int T = read();
while(T --) {
int n = read(), S = 0; bool mark = 0;
for(int i = 1; i <= n; i ++) a[i] = read(), S += a[i];
for(int i = 1; i <= n; i ++)
if(a[i] > (S >> 1)) { mark = 1; break; }
if(mark || (!mark && (S & 1))) printf("T
");
else printf("HL
");
}
return 0;
}