CodeForcesRound499(Div.2)

Codeforces Round #499 (Div.2)

A. Stages

题目大意:给你一个长度为\(n\)的字符串, 让你从其中拿出\(k\)个字符, 要求权值最小, 并且拿出的\(k\)个字符中,至少要有一个间隔

题解: 直接将字符串\(sort\)一下就好了,每次间隔一个取, 如果能取足\(k\)个那么就是满足条件的,否则就输出\(-1\)

PS : 这里的间隔取不是指的字母在序列中的位置,而是在\(26\)个字母中的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 5;
int n, k, ans;
char s[maxn];
int main(){
scanf("%d%d%s", &n, &k, s + 1);
sort(s + 1, s + 1 + n); int p = 1, l = 0;
while(k && p <= n){
if(s[p] - s[l] >= 2){
ans += s[p] - 'a' + 1;
k--; l = p;
} p++;
}
if(k)cout << "-1";
else cout << ans;
return 0;
}

B. Planning The Expedition

题目大意: 你有一些物品,每个物品都只有若干个,有\(n\)个人, 每个人只能吃同种物品,并且每天只吃一个,问你\(n\)个人最多能吃几天

题解: 我们考虑直接二分一个天数\(mid\),线性扫描所有物品,每种物品的数量\(k_i\), 有\(m\)种物品,则\(cnt = \sum_{i=1}^m\lfloor \frac{k_i}{mid} \rfloor\), 如果最后\(n\) \(\leq\) \(cnt\),就成立,否则不成立

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;
const int maxn = 1e3 + 5;
int n, m, a[maxn], bac[maxn], tmp[maxn];
inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}
inline bool check(int mid){
int x = n;
for(register int i = 1; i <= 100; i++)
x -= bac[i] / mid;
return x <= 0;
}
inline int binary(int l, int r){
int mid = (l + r) / 2, ans = 0;
while(l <= r){
mid = (l + r) / 2;
if(check(mid))l = mid + 1, ans = mid;
else r = mid - 1;
} return ans;
}
int main(){
n = read(); m = read();
if(n > m){
cout << "0";
return 0;
}
for(register int i = 1; i <= m; i++)bac[a[i] = read()]++;
cout << binary(1, 1000);
return 0;
}

C. Fly

题目大意: 你有一架飞机,质量为\(m\), 要求从\(1\)好星球飞到\(n\)星球, 在每个星球起飞或者降落都有一个系数\(k_i\), 起飞的耗油量为起飞前飞机质量和油的质量的和除以\(k_i\), 问你最少需要带多少油

题解: 再次考虑二分答案, 直接按照题目的意思模拟一下,判断最后的剩余的质量是否大于飞机的质量\(m\)

PS: 注意精度问题, \(eps = 1e-8\)即可, 否则会可能会\(T\)

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
const int inf = 1e9 + 7;
const double eps = 1e-8;
int n;
double m, a[maxn], b[maxn];
inline bool check(double mid){
double now = m + mid;
for(register int i = 1; i < n; i++){
now -= now / a[i];
now -= now / b[i + 1];
}
now -= now / a[n];
now -= now / b[1];
return now + eps >= m;
}
double binary(double l, double r){
double mid = (l + r) / 2, ans = 0;
while(l <= r + eps){
mid = (l + r) / 2;
if(check(mid))r = mid - eps, ans = mid;
else l = mid + eps;
} return ans;
}
int main(){
scanf("%d%lf", &n, &m);
for(register int i = 1; i <= n; i++){
scanf("%lf", &a[i]);
if(a[i] <= 1){
cout << "-1"; return 0;
}
}
for(register int i = 1; i <= n; i++){
scanf("%lf", &b[i]);
if(b[i] <= 1){
cout << "-1"; return 0;
}
}
printf("%.9lf", binary(0, double(inf)));
return 0;
}

D. Rocket

题目大意:一道交互题, 要你猜一个数字\(x\)\((x \leq m)\)\(m\)给出,并且回答机制是一种循环, 我们知道这个循环的长度为\(n\)\((n \leq 30)\), 这个序列是一个\(01\)序列, 如果是\(0\)那么回答的就是假话,是\(1\)回答的就是真话,要求最多询问六十次,求出这个数字

题解: 首先我们可以用\(n\)次询问确定这个\(01\)序列,然后再用剩余询问次数确定这个数字,我们的前\(n\)次询问每次都问\(m\), 如果问答大于就是说谎, 否则就是真话, 那么通过\(n\)次询问,\(01\)序列就确定下来了,然后就是普通的二分了

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
int n, m, a[maxn];
inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}
inline int check(int mid, int tot){
cout << mid << endl;
fflush(stdout);
int t;
cin >> t;
if(t == 0)exit(0);
if (a[(tot % n == 0) ? n : tot % n] == 0) t = -t;
return t;
}
int main(){
cin >> m >> n;
for(register int i = 1; i <= n; i++){
int t;
cout << m << endl;
fflush(stdout);
cin >> t;
if(t == 0)return 0;
else if(t == -1)a[i] = 1;
else a[i] = 0;
}
int l = 1, r = m, mid = (l + r) / 2, tot = n;
while(l <= r){
mid = (l + r) / 2;
int t = check(mid, ++tot);
if(t == -1) r = mid - 1;
else l = mid + 1;
}
return 0;
}

E. Border

题目大意:我们有\(n\)种物品,每种物品都有一个价值\(val_i\), 并且都可以无限选择,问你在模\(k\)的意义下能够组成多少种不同的价值, 输出种类数, 并且输出方案

题解:由\(n\)个数的斐蜀定理可知,\(\sum_{i=1}^n a_ix_i = p \cdot gcd \{ x_i\}\) , 假如我们有三个物品 \(a_1x_1 + a_2x_2 +a_3x_3 = p\cdot gcd\{x_1, x_2, x_3\}\) , 这里的\(a_i\)可以为负数,但是题目中必须得选非负数个那我们转换一下

\(a_1x_1 +a_2x_2 +a_3x_3\)\(a_1x_1 + a_2x_2 + a_3x_3 + a_1' \cdot kx_1 + a_2' \cdot kx_2 + a_3' \cdot kx_3\) 在模\(k\) 的意义下是一样的所以这个定理在模意义下是可以用的, 所以本题就很简单了,答案就是\(t \cdot gcd\{x_i\}, t \in [0,n]\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int n, t, k;
inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}
inline int gcd(int x, int y){return y == 0 ? x : gcd(y, x % y);}
set<int>st;
int main(){
n = read(); k = read(); t = read();
for(register int i = 2; i <= n; i++)
t = gcd(t, read());
for(register int i = 0; i <= n; i++)
st.insert((i * t) % k);
cout << st.size() << endl;
for(set<int> :: iterator iter = st.begin(); iter != st.end(); iter++)
cout << (*iter) << " ";
return 0;
}

F. Mars rover

题目大意:我们有一棵二叉树,在所有的非叶子节点上有一个二进制运算符,由每个叶子节点向上合并到根节点可以得到一个值,问你修改每一个叶子节点的值时最后的答案是多少(每个叶子节点的权值都是\(0\)\(1\)),

题解:一遍\(dfs\)求出一开始的答案,再用一次\(dfs\)求出每次修改一个节点的权值会不会影响答案,关键是第二次\(dfs\)怎么写,我们考虑除了"与"和"或"其他的二进制运算符只要改变其儿子节点的权值就会改变自己的权值,既然知道了这一点我们特判一下就好了

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 1e9 + 7;
int n, ch[maxn][2], ok[maxn], w[maxn];
char s[maxn][5];
inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}
inline int check(int now, int x0, int x1){
switch(s[now][1]){
case 'A': return x0 & x1;
case 'O': return x0 | x1;
case 'X': return x0 ^ x1;
}
}
inline int dfs(int now){
if(~w[now])return w[now];
if(s[now][1] == 'N')return w[now] = dfs(ch[now][0]) ^ 1;
else return w[now] = check(now, dfs(ch[now][0]), dfs(ch[now][1]));
}
inline void dfs(int now, int de){
if(s[now][1] == 'N'){
ok[now] = de & 1;
if(s[ch[now][0]][1] != 'I')dfs(ch[now][0], ok[now]);
else ok[ch[now][0]] = ok[now];
}
else if(s[now][1] == 'X'){
ok[now] = de & 1;
if(s[ch[now][0]][1] != 'I')dfs(ch[now][0], ok[now]);
else ok[ch[now][0]] = ok[now];
if(s[ch[now][1]][1] != 'I')dfs(ch[now][1], ok[now]);
else ok[ch[now][1]] = ok[now];
}
else if(s[now][1] == 'O'){
ok[now] = de & 1;
if(s[ch[now][0]][1] != 'I')dfs(ch[now][0], ok[now] & (w[ch[now][1]] != 1));
else ok[ch[now][0]] = ok[now] & (w[ch[now][1]] != 1);
if(s[ch[now][1]][1] != 'I')dfs(ch[now][1], ok[now] & (w[ch[now][0]] != 1));
else ok[ch[now][1]] = ok[now] & (w[ch[now][0]] != 1);
}
else if(s[now][1] == 'A'){
ok[now] = de & 1;
if(s[ch[now][0]][1] != 'I')dfs(ch[now][0], ok[now] & (w[ch[now][1]] == 1));
else ok[ch[now][0]] = ok[now] & (w[ch[now][1]] == 1);
if(s[ch[now][1]][1] != 'I')dfs(ch[now][1], ok[now] & (w[ch[now][0]] == 1));
else ok[ch[now][1]] = ok[now] & (w[ch[now][0]] == 1);
}
}
int main(){
n = read();
memset(w, -1, sizeof(w));
for(register int i = 1; i <= n; i++){
scanf("%s", s[i] + 1);
if(s[i][1] == 'I')w[i] = read();
else if(s[i][1] == 'A' || s[i][1] == 'X' || s[i][1] == 'O')
ch[i][0] = read(), ch[i][1] = read();
else ch[i][0] = read();
} w[1] = dfs(1); dfs(1, 1);
for(register int i = 1; i <= n; i++)
if(s[i][1] == 'I')printf("%d", w[1] ^ ok[i]);
return 0;
}

Summary : 水题集合