首页 > itarticle > codeforces round 511 (div. 2) 题解

codeforces round 511 (div. 2) 题解

admin 1月 18, 2021 0

人傻题不会.jpg

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 (){
    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 %dn", 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 (){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        ans = max(ans, x + y);
    }
    printf("%dn", 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
 
#pragma G++ optimize(2)

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 (){
    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("-1n");
    else printf("%dn", ans);
    return 0;
}

D

题目链接

可以发现在格子处于一定大小，如$1times 6$和$2times 4$$的时候是可以做到基本填满的。所以我们就可以把整个棋盘切成多个小格，用这些小格的答案作为基去凑出整个棋盘的答案。
我用的$7times 7$以下所有格子的答案作为基，用这个应该就够了。

1
2


微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能