A
分类讨论。
可以分成$(a, a, b)$的形式，但是实际上还是分成$(1, 1, n-2)$或者$(1, 2, n-3)$更快。
我是很蠢的选了前者。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
int main(){
int n;
cin >> n;
int k = n / 3, p = n - k - k;
if(k % 3 == 0) {
if(p % 3 == 1) k++, p -= 2;
else k--, p += 2;
}else if(p % 3 == 0) {
if(k % 3 == 1) k++, p -= 2;
else k--, p += 2;
}
printf("%d %d %d\n", k, k, p);
return 0;
}
B
观察可以发现，直线方程可以写成$y=-x+d$。而直线过点的时候可以保证答案最小，所以只要计算所有点中横纵坐标和的最大值即可。1
2
3
4
5
6
7
8
9
10
11
12
13
using namespace std;
int n, ans = 0;
int main(){
cin >> n;
for(int i = 1; i <= n; ++i){
int x, y;
scanf("%d%d", &x, &y);
ans = max(ans, x + y);
}
printf("%d\n", ans);
return 0;
}
C
先求出这个GCD，然后：
方法一
对每一个数除掉GCD，这样新的GCD就变成了$1$。我们只要让去掉一些数之后GCD大于$1$即可。可以枚举小于等于的质数，然后对每一个数判断是不是这个质数的倍数。保证尽量多的数是某一个质数的倍数即可。本质上是做质因数分解。
这么做会超时。
方法二
在方法一的基础上变换思路，考虑所有大于GCD的数，利用埃氏筛法求出其倍数的个数，和答案比较。
方法三
在方法一的基础上用线性筛优化质因数分解的过程。
在这一题中我们可以看出筛法和质因数分解之间的紧密联系，这对于某一类的数论题目很有启发意义。
以下代码基于方法二。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using namespace std;
int n, maxi = 0, mk[15000005] = {0};
bool vd[15000005] = {0};
int gcd(int x, int y){
return (!y) ? x : gcd(y, x % y);
}
int main(){
int g;
scanf("%d%d", &n, &g);
maxi = g, mk[g]++;
for(int i = 2; i <= n; ++i) {
int t;
scanf("%d", &t);
if(g != 1) g = gcd(t, g);
maxi = max(maxi, t);
mk[t]++;
}
int ans = n;
for(int i = g + 1; i <= maxi; ++i){
if(!vd[i]){
int cnt = 0;
for(int j = i; j <= maxi; j += i)
vd[j] = 1, cnt += mk[j];
ans = min(ans, n - cnt);
}
}
if(ans == n) printf("-1\n");
else printf("%d\n", ans);
return 0;
}
D
可以发现在格子处于一定大小，如$1\times 6$和$2\times 4$$的时候是可以做到基本填满的。所以我们就可以把整个棋盘切成多个小格，用这些小格的答案作为基去凑出整个棋盘的答案。
我用的$7\times 7$以下所有格子的答案作为基，用这个应该就够了。1
2