AtCoder Regular Contest (C, D) 解题报告

AtCoder Regular Contest (C, D) 专练解题报告……

081:
C: Make a Rectangle
给你一些棍子,从中取出4根组成长方形(包括正方形),问最大的组合面积
先排序,把权值相同的两根棒子捆在一起放进b数组,再排序选最大两个的乘积即为答案。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1e5 + 5;
int n, tot = 0;
LL ai[MAXN], b[MAXN];
void clean() {
}
void solve() {
clean();
for (int i = 1; i <= n; i++) cin >> ai[i];
sort(ai + 1, ai + 1 + n);
int flag = false;
for (int i = 1; i <= n; i++) {
if (ai[i] == ai[i + 1] && !flag) b[++tot] = ai[i], flag = true; else flag = false;
}
if (tot < 2) printf("0\n"); else {
sort(b + 1, b + 1 + tot);
cout << b[tot] * b[tot - 1] << endl;
}
}
int main() {
scanf("%d", &n), solve();
return 0;
}

D: Coloring Dominoes
给一个$2 \times n$的矩阵,上面已经放好了多米诺骨牌,你现在能刷3种颜色,相邻骨牌颜色要不同,求刷颜色的方案
因为就2列,所以不是两个躺着的骨牌一起放就是横着放的骨牌,组合一下,分类讨论4种情况,扫描一遍即可。最左边要先预处理,具体怎么分类讨论看这里

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MO = 1000000007;
int n, f;
LL tot;
char s1[60], s2[60];
void clean() {}
void solve() {
clean();
scanf("%s", s1 + 1), scanf("%s", s2 + 1);
if (s1[1] == s2[1]) tot = 3, f = 2; else if (s1[1] == s1[2]) tot = 6, f = 3;
while (f <= n) {
if (s1[f] == s2[f]) {
if (s1[f - 1] == s2[f - 1]) tot = (tot * 2) % MO;
//else if (s1[f - 1] == s1[f - 2]) tot = tot % MO;
f++;
} else if (s1[f] == s1[f + 1]) {
if (s1[f - 1] == s2[f - 1]) tot = (tot * 2) % MO;
else if (s1[f - 1] == s1[f - 2]) tot = (tot * 3) % MO;
f += 2;
}
}
printf("%lld\n", tot);
}
int main() {
scanf("%d", &n), solve();
return 0;
}

080:
C: 4-adjacent
给出一个序列$A$,要求排列这个序列,使得这个序列中对于所有的$i$,$A_i \times A_{i+1}$是4的倍数。
因为只有$2 \times 2=1 \times 4=4$,所以每个数如果他是4的倍数,那他对答案有贡献;如果不是但是2的倍数,也有贡献。我们把是2的倍数但不是4的倍数标记为2,是4的倍数标记为4,其他数标记为1。那么我们考虑没有2的情况,没有2就可以这样排列:1414141,那么显然是标记为4的个数+1大于标记为1的个数即为Yes。考虑有2的情况,有2就要把所有的2当做一个1排在后面,可以这样排列:141414222,所以标记为4的个数大于标记为1的个数就为Yes
(刚开始想的时候2那里的处理弄错了,没有减一,所以WA了两个点)

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n;
int tw, fr;
void clean() {
tw = fr = 0;
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
if (x % 4 == 0) fr++; else if (x % 2 == 0) tw++;
}
if (tw) {
if (fr >= n - tw - fr) {
printf("Yes\n");
} else printf("No\n");
} else if (fr + 1 >= n - tw - fr) {
printf("Yes\n");
} else printf("No\n");
}
int main() {
while (scanf("%d", &n) == 1) solve();
return 0;
}

D: Grid Coloring
给出一个网格,一些颜色,要给网格上色,并且每种颜色都要有且仅有指定个数的格子,求一种可行方案。
直接蛇形填充即可,因为蛇形保证四连通

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int h, w, n, mp[105][105], nowd = 0, nowi = 1, nowj = 0;
void clean() {
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
for (int j = 1; j <= x; j++) {
if (!nowd) {
nowj++;
if (nowj > w) nowj = w, nowi++, nowd = 1;
} else {
nowj--;
if (nowj <= 0) nowj = 1, nowi++, nowd = 0;
}
mp[nowi][nowj] = i;
}
}
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
printf("%d ", mp[i][j]);
}
printf("\n");
}
}
int main() {
scanf("%d%d%d", &h, &w, &n), solve();
return 0;
}

C: Cat Snuke and a Voyage
略,过于简单,裸最短路或者DFS
D: Decrease (Contestant ver.)

------ 本文结束 ------