5月26日 Codeforces 实战记录。（1468 -> 1559）
AC数2/5。
比赛跳转：Codeforces Round 948 (Div. 2)
题解
A. Little Nikita
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
return x * f;
}
int main(){
int t = read();
while(t--){
int n = read(), m = read();
if(n >= m && (n - m) % 2 == 0) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
|
B. Binary Colouring
分析：将 n 看作二进制形式，为保证相邻两位上必有一位是 0，在遇到连续的两位为 1 时，对低位的 1 做 +1 操作，同时在 res 中把这一位计入 -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
29
30
31
32
33
| #include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
return x * f;
}
int main(){
int t = read();
while(t--){
int n = read();
vector<int> res(40);
int cnt = 0;
while(n){
if(n & 1 && (n >> 1) & 1){
res[cnt] = -1;
n++;
}
else{
res[cnt] = n & 1;
}
n >>= 1;
cnt++;
}
cout << cnt << '\n';
for(int i = 0; i < cnt; i++) cout << res[i] << ' ';
puts("");
}
return 0;
}
|
打了一个手速场，C 题过不掉，但 A、B题过的还比较快。
（但是细节写错mle了一发，一发过的话进前2000了www）
C. Nikita and LCM
题意：从给出的 array 中，选出若干个数，使得他们的 lcm 不在该 array 中，求最多能选出多少个数。
分析：
- 首先判断能否全选，即所有数的 lcm 是否等于最大值。如果可以，输出 n。
（注意这一步判断时不能直接求出所有数的 lcm，会爆long long，应当求一步判断一次是否超出最大值。）
- 如果不行，表示所有数都是最大值的因子。接下来遍历最大值的所有除数，对于每一个除数，都检查是否有以该除数为 lcm 的子序列，如果有，更新最大能选出的个数。
完整代码：
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
return x * f;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int calc(vector<PII> &t, int d){
int LCM = 0, cnt = 0;
for(auto &i : t){
if(d % i.first == 0){
if(LCM == 0) LCM = i.first;
else LCM = lcm(LCM, i.first);
cnt += i.second;
}
}
if(LCM != d) cnt = 0;
return cnt;
}
void solve(){
int n = read();
vector<int>v(n);
for(auto &i : v) i = read();
int mx = *max_element(v.begin(), v.end());
int LCM = 1;
for(auto &i : v){
LCM = lcm(LCM, i);
if(LCM > mx){
cout << n << '\n';
return;
}
}
map<int, int>cnt;
for(auto &i : v) cnt[i]++;
vector<PII> t;
for(auto &i : cnt) t.emplace_back(i);
int res = 0;
for(int i = 1; i * i <= mx; i++){
if(mx % i) continue;
if(!cnt[i])
res = max(res, calc(t, i));
if(!cnt[mx / i])
res = max(res, calc(t, mx / i));
}
cout << res << '\n';
}
signed main(){
int t = read();
while(t--)
solve();
return 0;
}
|
有人跟我一样在 tutorial 里这一句话上挣扎，lmfao
