Andrewei's Blog
0%

Codeforces #324(div.2)

发表于 更新于 分类于 ，

比赛题目链接：http://codeforces.com/contest/584

A题(Olesya and Rodion)

题目大意：

给定两个数字 n(1 <= n <= 100) 和 t(2 <= t <= 10) 输出一个长度为 n 的整数，使其可以被 t 整除。

解题思路：

就构造一下就可以了，我是特判了当 n == 1 的情况和 n == 2 且 t == 10 的情况，其余的直接构造成在 t 后面补零的情况。

参考程序：

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
53
54
55
56
57
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-07 00:23
# Filename: 		a.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;
const int MAXN = 1010;

int n, t;
int a[MAXN];

int main(){
    while(scanf("%d%d", &n, &t) != EOF){
        if(n == 1){
            int f = false;
            for(int i = 1; i < 10; i++)
                if(i % t == 0){
                    printf("%d\n", i);
                    f = true;
                    break;
                }
            if(!f) printf("-1\n");
        } else if(n == 2 && t == 10){
            int f = false;
            for(int i = 10; i < 99; i++)
                if(i % t == 0){
                    printf("%d\n", i);
                    f = true;
                    break;
                }
            if(!f) printf("-1\n");
        }else{
            printf("%d", t);
            int num = t == 10 ? 2 : 1;
            while(num < n) printf("0"), num++;
            printf("\n");
        }
    }
    return 0;
}

B题(Kolya and Tanya)

题目大意：

给定一个数 $n（1 <= n <= 10^5)$, 表示有 3n 个数，每个数的取值范围是[1, 3], 统计有多少个 $i(0 <= i < 3n)$，使 $a[i] + a[i + 1] + a[i + 2] != 6$, 所得答案模除 1e9 + 7。

解题思路：

数学问题，可以推出公式 ans = pow(3, 3 * n) - pow(7, n);

参考代码：

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
53
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-07 00:45
# Filename: 		b.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;
const int MOD = 1000000007;

long long multmod(long long a, long long b, long long mod){
    long long res = 0;
    while(b){
        if(b & 1) res += a, res %= mod;
        a += a, a %= mod, b >>= 1;
    }
    return res;
}

long long powmod(long long a, long long b, long long mod){
    long long res = 1;
    while(b){
        if(b & 1) res = multmod(res, a, mod);
        a = multmod(a, a, mod), b >>= 1;
    }
    return res;
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        long long res1 = powmod(3, 3 * n, MOD);
        long long res2 = powmod(7, n, MOD);
        long long ans = (res1 + MOD - res2) % MOD;
        printf("%I64d\n", ans);
    }
    return 0;
}

C题(Marina and Vasya)

题目大意：

有 2 个长度为 n 的字符串 str1，str2，求一个长度为n的字符串 str3，让str1跟 res 有 t 个字符不一样，str2 跟 res 也有 t 个字符不一样。答案不唯一。

解题思路：

先将 str1[i] == str2[i] 的位置初始化为 res[i] = str1[i] 同时统计相同的数目 num， 将 str1[i] != str2[i] 的位置初始化为 res[i] != str1[i] && res[i] != str2[i], 然后根据 n - num 与 t 的大小关系分两种情况讨论。

  1. 当 n - sum > t 时，说明相同的字符太少，需要构造出一些 str1[i] != str2[i] 位置的字符 res[i] 与 str1[i] 或 str2[i] 相同来满足条件.
  2. 当 n - sum < t 时，说明相同的字符太多，需要构造出一些 str1[i] == str2[i] 位置的字符 res[i] 与 str1[i] 和 str2[2] 不同来满足条件.
    最后在统计一下 res 与 str1 和 str2 的不同的数目来验证是否满足题意即可。

参考代码：

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-07 01:05
# Filename: 		c.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;
const int MAXN = 100100;

int n, t;
char str1[MAXN];
char str2[MAXN];
char res[MAXN];

char getChar(char c1, char c2){
    for(int i = 0; i < 26; i++)
        if(c1 != 'a' + i && c2 != 'a' + i) return 'a' + i;
    return '0';
}

int main(){
    while(scanf("%d%d", &n, &t) != EOF){
        scanf(" %s%s", str1, str2);
        int len = n;
        int num = 0;
        for(int i = 0; i < len; i++){
            if(str1[i] == str2[i]) res[i] = str1[i], num++;
            else res[i] = getChar(str1[i], str2[i]);
        }

        if(n - num > t){
            int cnt = n - num - t;
            int cnt1 = cnt;
            for(int i = 0; i < len; i++){
                if(str1[i] != str2[i] && res[i] != str1[i] && res[i] != str2[i] && cnt){
                    res[i] = str1[i], cnt--; 
                }
            }

            for(int i = 0; i < len; i++){
                if(str1[i] != str2[i] && res[i] != str1[i] && res[i] != str2[i] && cnt1){
                    res[i] = str2[i], cnt1--; 
                }
            }
        }else{
            int cnt = t - (n - num);
            for(int i = 0; i < len; i++)
                if(str1[i] == str2[i] && cnt)
                    res[i] = getChar(str1[i], str2[i]), cnt--;
        }
        res[n] = '\0';
        int num1 = 0, num2 = 0;
        for(int i = 0; i < n; i++){
            if(res[i] != str1[i]) num1++;
            if(res[i] != str2[i]) num2++;
        }

        if(num1 == t && num2 == t) printf("%s\n", res);
        else printf("-1\n");
    }
    return 0;
}

D题(Dima and Lisa)

题目大意：

给以个奇数 $n(3 <= n < 10^9$ ，需找到 k 个素数，让这 k(1 <= k <= 3) 个素数的和等于 n，题目保证有解。

解题思路：

这道题的原型其实是一个注明的定理—-三素数定理(具体点这里), 只不过这里已经明确告诉我们数据保证题目一定有解，没什么可说的直接暴力就 OK， 先枚举一下 n < 10 的情况，然后其他的直接猜想其他的数一定可以由三个素数相加得到，于是两层循环枚举直到找到解为止。

参考代码：

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
53
54
55
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-07 01:46
# Filename: 		d.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;

bool isPrime(int n){
    int end = sqrt((double)n) + 1;
    for(int i = 2; i <= end; i++)
        if(n % i == 0) return false;
    return true;
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        if(n == 3) printf("1\n3\n");
        else if(n == 5) printf("1\n5\n");
        else if(n == 7) printf("1\n7\n");
        else if(n == 9) printf("2\n2 7\n");
        else{
            printf("3\n");
            bool flag = true;
            for(int i = 3; i < n && flag; i += 2){
                if(!isPrime(i)) continue;
                for(int j = i; j < n && flag; j += 2){
                    if(!isPrime(j)) continue;
                    if(isPrime(n - i - j)){
                        printf("%d %d %d\n", i, j, n - i - j);
                        flag = false;
                    }
                }
            }
        }
    }
    return 0;
}