Codeforces Round 444 (Div. 2)

Posted on | In ,

目录

  • A.Div. 64(implementation)
  • B.Cubes for Masha(brute force)
  • C.Solution for Cube(brute force, implementation)
  • D.Ratings and Reality Shows(data structures, two pointers)
  • E.Little Brother(binary search, geometry)
  • F.Row of Models

A.Div. 64

思路

题意是给一个二进制的01串，判断能否通过去掉一些数字使其能被64整除（移除数字后必须为正整数）。很显然在最后一个1后有至少6个0就能使其被64整除。

代码

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
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cctype>
#include <sstream>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1+1)


using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	string str;
	while (cin >> str) {
		int i = 0,zero=0;
		while (i<str.length()&&str[i] == '0')i++;
		i++;
		while (i < str.length()) {
			if (str[i] == '0')zero++;
			i++;
		}
		if (zero >= 6)cout << "yes" << "\n";
		else cout << "no" << "\n";
	}
	return 0;
}

B.Cubes for Masha

思路

题意是给出n个6面魔方，每个面上有一个0-9之中的数字，我们希望能用这n个魔方拼出从1到x之间所有的整数。找出最大的x（不一定要使用所有魔方）。通过观察我们发现3个魔方不可能拼出比99更大的数(考虑到要拼出99需要1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9已经有18个数，而0又是必须的)。所以我们暴搜从1-99的数。

代码

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
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cctype>
#include <sstream>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1+1)


using namespace std;
int vis[3];
set<int> dict[3];
int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n,t;
	while (cin >> n) {
		ms(vis, 0);
		for (int i = 0;i < 3;i++)dict[i].clear();
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < 6;j++) {
				cin >> t;
				dict[i].insert(t);
			}
		}
		for (int i = 1;i <= 99;i++) {
			int num = i % 10,flag=1;
			for (int j = 0;j < 3;j++) {
				if (dict[j].find(num) != dict[j].end()) {
					vis[j] = 1;
					for (int k = 0;k < 3;k++) {
						if (i / 10 == 0||(!vis[k] && dict[k].find(i / 10) != dict[k].end())) {
							flag = 0;
							break;
						}
					}
					vis[j] = 0;
				}
				if (!flag)break;
			}
			if (flag) {
				cout << i-1 << "\n";
				break;
			}
		}
	}
	return 0;
}

C.Solution for Cube

思路

题意很简单，能否一步还原222的魔方，模拟。考虑到各种对称的状态，我们只需要模拟6种旋转即可。

代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cctype>
#include <sstream>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1+1)


using namespace std;
int mcube[24],cube[24];
int cmd[3][8] = {
	{13,14,5,6,17,18,21,22},
	{2,4,6,8,10,12,23,21},
	{1,2,18,20,12,11,15,13}
};
void switchs (int i,int d) {
	if (d) {
		int t1 = cube[cmd[i][0]-1], t2=cube[cmd[i][1]-1];
		for (int j = 0;j <= 4;j += 2) {
			cube[cmd[i][j] - 1] = mcube[cmd[i][j + 2] - 1], cube[cmd[i][j + 1]-1] = mcube[cmd[i][j + 3] - 1];
		}
		cube[cmd[i][6] - 1] = t1, cube[cmd[i][7] - 1] = t2;
	}
	else {
		int t1 = cube[cmd[i][6] - 1], t2 = cube[cmd[i][7] - 1];
		for (int j = 0;j <= 4;j += 2) {
			cube[cmd[i][j + 2] - 1] = mcube[cmd[i][j] - 1], cube[cmd[i][j + 3] - 1] = mcube[cmd[i][j + 1] - 1];
		}
		cube[cmd[i][0] - 1] = t1, cube[cmd[i][1] - 1] = t2;
	}
}
bool judge() {
	for (int i = 0;i < 6;i++) {
		int temp = cube[i * 4];
		for (int j = 1;j < 4;j++) {
			if (cube[i * 4 + j] != temp)return false;
		}
	}
	return true;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	while (cin >> mcube[0]) {
		for (int i = 1;i < 24;i++)cin >> mcube[i];
		int flag = 0;
		if (!flag) {
			memcpy(cube, mcube, sizeof(mcube));
			switchs(0, 0);
			if (judge())flag = 1;
		}
		if (!flag) {
			memcpy(cube, mcube, sizeof(mcube));
			switchs(0, 1);
			if (judge())flag = 1;
		}
		if (!flag) {
			memcpy(cube, mcube, sizeof(mcube));
			switchs(1, 0);
			if (judge())flag = 1;
		}
		if (!flag) {
			memcpy(cube, mcube, sizeof(mcube));
			switchs(1, 1);
			if (judge())flag = 1;
		}
		if (!flag) {
			memcpy(cube, mcube, sizeof(mcube));
			switchs(2, 0);
			if (judge())flag = 1;
		}
		if (!flag) {
			memcpy(cube, mcube, sizeof(mcube));
			switchs(2, 1);
			if (judge())flag = 1;
		}
		if (flag)cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}
	return 0;
}

D题后待补题。。