Codeforces Round 508(DIv.2) (A, B, C, D)_codeforces 508 (div. 2)

A 模拟

题解：
用cnt[i][j]表示第字母i（0-25）在字符串（0-j）的出现次数。
然后枚举一下cnt[i][n-1]的最小值即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

const int maxn = 100005;
int cnt[26][maxn];
char s[maxn];
int n, k;

bool check(int x, int len){
    for(int i = 0; i < 26; i++){
        if(cnt[i][len] < x)
            return false;
    }
    return true;
}


int main(){
    int ans = 0x3f3f3f3f;
    scanf("%d%d", &n, &k);
    scanf("%s", s);
    for(int j = 0; j < 26; j++){
        if(s[0]-'A'==j){
            cnt[j][0] = 1;
        }
    }
    for(int i=1; i<n; i++){
        for(int j = 0; j< 26; j++){
            if(s[i]-'A'==j){
                cnt[j][i] = 1; 
            }
            cnt[j][i] += cnt[j][i-1];
        }
    }
    /*for(int i = 0; i < n; i++){
        for(int j = 0; j < 26; j++)
            printf("%d ", cnt[j][i]);
        printf("\n");
    }*/
    if(cnt[k-1][n-1] == 0){
        printf("0\n");
        return 0;
    }
    for(int i = 0; i < k; i++){
        ans = min(cnt[i][n-1], ans);
    }
    printf("%d\n", ans*k);
return 0;
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

B 构造

题解：
显然$sum_1+sum_2=sum =n*(n+1)/2$,且$gcd(sum_1, sum_2) > 1$,令$sum_1=k_1*d,sum_2=k_2*d$ 则$(k_1+k_2)*d=n*(n+1)/2$枚举$d(d>=2)$能整除$n*(n+1)/2$.令$k_1=1$即可构造。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define LL long long

using namespace std;

int n;
LL S;
LL a, b;


int main(){
    int flag = 0;
    int d;
    scanf("%d", &n);
    S = (n+1)*n;
    for(int i = 2; i <= n; i++){
        if(S % (2*i) == 0){
            flag = 1;
            d = i;
            break;
        }
    }
    //printf("%d\n", d);
    if(!flag){
        printf("No\n");
    }
    else{
        printf("Yes\n");
        int k1 = 1, k2 = S/2*d-1;
        printf("%d %d\n%d ", k1 ,d, n-1);
        for(int i = 1; i <= n; i++){
            if(i != d)
                printf("%d ", i);
        }
        printf("\n");
    }
return 0;
}
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
33
34
35
36
37
38
39
40
41

C 贪心 排序

题解：
把每人的分数排序，从大到小向下扫，对每个人，如果对面最大的比自己最大的大，删去对面。否则把自己的加上。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>


#define LL long long
using namespace std;

const int maxn = 100005;

int n;
int a[maxn], b[maxn];
LL A, B;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++){
        scanf("%d", &b[i]);
    }
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    int flag = 1;
    int i = n, j = n;
    while(i >= 0 && j >= 0){
        if(flag){
            if(a[i] >= b[j]){
                A += (LL)a[i];
                i--;
            }
            else{
                j--;
            }
            flag = 0;
        }
        else if(!flag){
            if(b[j] >= a[i]){
                B += (LL)b[j];
                j--;
            }
            else{
                i--;
            }
            flag = 1;
        }
    }
    printf("%I64d\n", A-B);
return 0;
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

D 贪心

题解：
有三种情况
1.有负数也有正数（0算”正数“）：先让负数去吃正数，最后剩一个正数再吃负数，这样答案就是所有数绝对值之和。
2.全负：用绝对值最小的负数去吃其他数可以把损失降到最小。设min为绝对值最小数的绝对值，sum为所有数绝对值之和，则答案是
$（-min-A-B-C-...）=-min+(-A-B-...)=-min+(sum-min)=sum-2*min$这个计算过程也可以证明贪心的正确性。
3.全正：和上同理，答案为$sum-2*min$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

#define LL long long
using namespace std;

int n;
int a[500005];
int pflag = 0, nflag = 0;
LL ans = 0;
int Min = 0x3f3f3f3f;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        if(a[i] >= 0) pflag = 1;
        if(a[i] < 0) nflag = 1;
        ans += abs(a[i]);
        Min = min(abs(a[i]), Min);
    }
    if(n == 1) printf("%d\n", a[1]);
    else{
        if(pflag && nflag)
            printf("%I64d\n", ans);
        else if( (!pflag && nflag) || (pflag && !nflag)){
            printf("%I64d\n", ans - Min * 2);
        }
        else printf("0\n");
    }
return 0;
}
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
33
34
35