小月的字符集
依次检查就完了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
char s[3];
char a,b;
for(int i=0;i<3;i++) cin >> s[i];
cin >> a >> b;
for(int i=0;i<3;i++){
if(s[i]!=a && s[i]!=b){
cout << s[i];
break;
}
}
return 0;
}
|
小月的十六进制
一开始的错解
一开始没看数据，企图直接用atoi。当然改成atoll和long long这题也是过不去的，这个是错解。
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string x;
cin >> x;
int k,num;
cin >> k;
int dec=stoi(x, nullptr, 16);
num=pow(2,k);
if(dec%num==0){
cout << "YES";
}
else{
cout << "NO";
}
return 0;
}
|
正确方式
十六进制的基数是2^4，也就是说每个十六进制位会对应4个二进制位。想让一个数被2的k次幂整除，当且仅当这个数的二进制表示的末尾有至少k个0。
那如何算这个数的二进制形式末尾有多少个0呢！？
首先，刚刚说过了，一个十六进制位对应4个二进制位，所以十六进制数末尾有一个0，相当于二进制数的末尾有4个0。假设十六进制数末尾有m个0，那么他就贡献了4*m个0。
然后去找第一个非零位。如果这个数可以被2整除n次，我们就称他贡献了n个0。
那么此刻问题就转换成了，判断4*m+n是否大于等于k
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
| #include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string x;
int k;
cin >> x >> k;
if (k == 0) {
cout << "YES" << endl;
return 0;
}
int zero=0;
int n=x.size();
char s;
for(int i=n-1;i>=0;i--){
if(x[i]=='0'){
zero++;
}
else{
s=x[i];
break;
}
}
if(zero==n){
cout << "YES";
return 0;
}
zero*=4;
int num;
if(s>'0' && s<='9'){
num=s-'0';
}
else if(s>='a' && s<='f'){
num=s-'a'+10;
}
else{
num=s-'A'+10;
}
while(num>0 && num%2==0){
zero++;
num/=2;
}
if(zero>=k){
cout << "YES";
}
else{
cout << "NO";
}
return 0;
}
|
小月的对局
如果Bob想赢，那么无论Alice按什么顺序出牌，Bob都要给每一张Alice的牌配上一张互质的牌，并且每张牌只用一次。
那么问题就变成了，对于Alice的每张牌，Bob是否可以找到对应的牌与它互质。如果可以的话Bob胜利，反之Alice胜利。
那么就变成了二分图的匹配问题喵。
左边n个点是Alice的牌，右边n个点是Bob的牌。如果gcd(a[i],b[j])==1，就在i和j之间连边。
然后求最大匹配，如果最大匹配等于n，Bob赢，反之Alice赢。
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 <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> g(n);
vector<int> match(n,-1);
vector<bool> vis(n);
vector<int> a(n);
vector<int> b(n);
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<n;i++) cin >> b[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(__gcd(a[i],b[j])==1){
g[i].push_back(j);
}
}
}
function<bool(int)> dfs=[&](int u)->bool{
for(int v:g[u]){
if(vis[v]) continue;
vis[v]=true;
if(match[v]==-1 || dfs(match[v])){
match[v]=u;
return true;
}
}
return false;
};
int cnt=0;
for(int i=0;i<n;i++){
fill(vis.begin(),vis.end(),false);
if(dfs(i)) cnt++;
}
if(cnt==n) cout << "Bob";
else cout << "Alice";
return 0;
}
|
小月的地砖
重点就在于如何安排，可以让每一列中的1尽量均匀。
我们把第i个1放到第i%m列里，这样之后每列的1只有可能有两种情况：
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin >> n >> m;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
int cur=0;
for(int i=0;i<n;i++){
string row(m,'0');
for(int j=0;j<a[i];j++){
row[cur]='1';
cur=(cur+1)%m;
}
cout << row <<'\n';
}
return 0;
}
|
