Summary
Score: \(100+90+0+50+4=244\)
T1 减法操作
考虑对 \(n\) 分奇偶讨论：
- 偶数：显然 最小质因子 为 \(2\)，而每次减 \(2\) 后仍是偶数。所以偶数一定进行了 \(\dfrac n 2\) 次操作；
- 奇数：因为是奇数，所以 最小质因子 一定也是奇数，减去后则变为偶数，接着可以转化为偶数处理。
code
#include <cstdio>
long long n, ans;
int main () {
scanf("%lld", &n);
if (n & 1) {
for (long long i = 3; i * i <= n; i++)
if (!(n % i))
return printf("%lld", 1 + (n - i) / 2), 0;
ans = 1;
} else
ans = n / 2;
printf("%lld", ans);
return 0;
}
T3 染色
将颜色相同的一段子区间称做「一段」
则至少 \(N-K\) 段，才能使多出来的 \(K-1\) 个格子即使放在一起也只有 \(K\) 对相邻的格子。
考虑满足「满足相邻的同色格子 恰为 \(K\) 对」 的方案数。
不考虑染色，则有