Educational Round 51 题解

A Vasya And Password

统计一下三种字符的个数。

如果每种有多于 $1$ 个字符,将其替换为没出现过的字符。

B Relatively Prime Pairs

显然 $\gcd(i,i+1)=1$,直接输出即可。

C Vasya and Multisets

统计只出现 $1$ 次的数字有哪些,如果有偶数个,对半分配即可。

出现两次的数字要么一人拿一个,要么一个人全拿,不影响答案。

出现次数大于 $2$ 的数字,如果已经可以分配了就全部给一个人即可;如果第一种是奇数个,那么分配一个出现次数大于 $2$ 的。

D Bicolorings

自闭题T^T。

考虑 $dp[i][j][state]$ 表示遍历到第 $i$ 列,有 $j$ 个联通块,第 $i$ 列状态为 $state$ 的方案数。

时间复杂度 $O(nk)=O(n^2)$。

代码

A

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;

char s[maxn];

int main(){
int T; scanf("%d", &T);
while (T--){
scanf("%s", s);
int len = strlen(s);
int a = 0, b = 0, c = 0;
for (int i = 0; i < len; i++){
if (s[i] >= 'a' && s[i] <= 'z') a++;
if (s[i] >= 'A' && s[i] <= 'Z') b++;
if (s[i] >= '0' && s[i] <= '9') c++;
}
if (a && b && c) {
printf("%s\n", s);
}
else {
int flag = 0;
if (a > 1){
for (int i = 0; i < len && a > 1; i++){
if (s[i] >= 'a' && s[i] <= 'z') {
if (b == 0) {
s[i] = 'A'; b++; a--;
}
else if (c == 0){
s[i] = '0'; c++; a--;
}
}
if (a && b && c) {printf("%s\n", s); flag = 1; break;}
}
}
if (flag) continue;

if (b > 1){
for (int i = 0; i < len && b > 1; i++){
if (s[i] >= 'A' && s[i] <= 'Z') {
if (a == 0) {
s[i] = 'a'; a++; b--;
}
else if (c == 0){
s[i] = '0'; c++; b--;
}
}
if (a && b && c) {printf("%s\n", s); flag = 1; break;}
}
}
if (flag) continue;

if (c > 1){
for (int i = 0; i < len && c > 1; i++){
if (s[i] >= '0' && s[i] <= '9') {
if (b == 0) {
s[i] = 'A'; b++; c--;
}
else if (a == 0){
s[i] = 'a'; a++; c--;
}
}
if (a && b && c) break;
}
}
printf("%s\n", s);
}
}
return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;

ll l, r;

int main(){
scanf("%I64d%I64d", &l, &r);
puts("YES");
for (ll i = l; i < r; i += 2){
printf("%I64d %I64d\n", i, i + 1);
}
return 0;
}

C

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100 + 5;

int n, s[maxn], cnt[maxn], kind[maxn];

int main(){
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d", s + i);
cnt[s[i]]++;
}
int s1 = 0, s2 = 0, s3 = 0;
for (int i = 1; i <= 100; i++){
if (cnt[i] == 1) s1++;
if (cnt[i] >= 3) s2++;
}
if (s1 % 2 == 0){
puts("YES"); int a = s1 / 2;
for (int i = 0; i < n; i++){
if (cnt[s[i]] == 1) {
if (a) putchar('A'), a--;
else putchar('B');
}
else putchar('B');
}
}
else {
int a = s1 / 2, flag = 1;
if (s2){
puts("YES");
for (int i = 0; i < n; i++){
if (cnt[s[i]] == 1) {
if (a) putchar('A'), a--;
else putchar('B');
}
else if (cnt[s[i]] == 3 && flag){
putchar('A'); flag = 0;
}
else putchar('B');
}
}
else puts("NO");
}
return 0;
}

D

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ms(a,b) memset(a,b,sizeof(a))
#define lld I64d
#ifdef XLor
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { std::cout << '\n'; }
template < typename T, typename...Args >
void err(T a, Args...args){ std::cout << a << ' '; err(args...); }
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;
const ll mod = 998244353;

int n, k;
ll dp[maxn][maxn << 1][2][2] = {0};

int main(){
scanf("%d%d", &n, &k);
if (k == 1 || k == 2 * n){puts("2"); return 0;}
dp[1][1][0][0] = dp[1][1][1][1] = 1;
dp[1][2][0][1] = dp[1][2][1][0] = 1;
for (int i = 2; i <= n; i++){
for (int j = 1; j <= k; j++){
(dp[i][j][0][0] += dp[i - 1][j][0][0] + dp[i - 1][j - 1][1][1] + dp[i - 1][j][0][1] + dp[i - 1][j][1][0]) %= mod;
(dp[i][j][1][1] += dp[i - 1][j][1][1] + dp[i - 1][j - 1][0][0] + dp[i - 1][j][0][1] + dp[i - 1][j][1][0]) %= mod;
(dp[i][j][0][1] += dp[i - 1][j - 1][0][0] + dp[i - 1][j][0][1] + dp[i - 1][j - 1][1][1]) %= mod;
(dp[i][j][1][0] += dp[i - 1][j - 1][0][0] + dp[i - 1][j][1][0] + dp[i - 1][j - 1][1][1]) %= mod;
if (j >= 2) (dp[i][j][0][1] += dp[i - 1][j - 2][1][0]) %= mod, (dp[i][j][1][0] += dp[i - 1][j - 2][0][1]) %= mod;
dbg(i, j);
dbg(dp[i][j][0][0], dp[i][j][0][1], dp[i][j][1][0], dp[i][j][1][1]);
}
}
ll ans = 0;
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) (ans += dp[n][k][i][j]) %= mod;
printf("%lld", ans);
return 0;
}
  • 本文作者: XLor
  • 本文链接: https://xlor.cn/2018/9/edu51/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!