题目大意：
有两个麦甜甜圈的店铺，第一个只单卖，价格是
a
a
a元一个，第二个店铺是整箱卖，一箱
b
b
b个
c
c
c元，只能整箱卖，问你在第一个店铺买多少甜甜圈比第二个店铺便宜，如果不能输出-1，问你在第二个店铺买多少甜甜圈比第一个店铺便宜，如果不能输出-1。
思路：
如果
a
<
c
:
a < c:
a<c:说明第一个店铺单价低于第二个店铺输出数量
1
1
1即可，否则
−
1
-1
−1。
如果
c
/
b
<
a
c/b<a
c/b<a:说明第二个店铺单价低于第一个店铺，把
b
b
b移过去，就是
a
∗
b
a*b
a∗b也就是数量
b
b
b个
a
a
a，输出
b
b
b即可，否则输出
−
1
-1
−1。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#include<iostream> using namespace std; typedef long long int ll; void solved(){ ll a,b,c;cin>>a>>b>>c; if(a < c){ cout<<"1"<<" "; }else { cout<<"-1"<<" "; } if(c >= a * b){ cout<<"-1"<<endl; }else{ cout<<b<<endl; } } int main(){ int t;cin>>t; while(t--)solved(); return 0; }
题目大意：
给你一个只包含
01
01
01的字符串，然后相邻的不同的字符可以被消除比如
01
,
10
01,10
01,10，然后Alica先手，Bob后手，问你最终谁能赢。
思路：
注意到这个字符串
01
01
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<iostream> #include<algorithm> #include<cstring> #include<stack> #include<string> using namespace std; void solved(){ string s;cin>>s; stack<char>st; int cnt = 0; for(int i = 0; i < s.size(); i++){ if(st.empty()){ st.push(s[i]); }else{ if(s[i] == '1'){ if(st.top() == '0'){ cnt++;st.pop(); }else{ st.push(s[i]); } }else{ if(st.top() == '1'){ cnt++;st.pop(); }else{ st.push(s[i]); } } } } if(cnt & 1)cout<<"DA"<<endl; else cout<<"NET"<<endl; } int main(){ int t;cin>>t; while(t--)solved(); return 0; }
题目大意：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16res = 0 for init = 0 to inf cur = init ok = true for i = 1 to |s| res = res + 1 if s[i] == '+' cur = cur + 1 else cur = cur - 1 if cur < 0 ok = false break if ok break
模拟这个程序。
思路：
直接模拟肯定会超时，注意到它每次都是从
1
1
1开始，那么肯定重复计算了很多次，我们可以直接
O
(
n
)
O(n)
O(n)把要计算的全部加上来，最后再加上整个字符串长度就好了，每个
c
u
r
<
0
cur<0
cur<0的地方加一下长度然后
i
n
i
t
+
+
转
化
为
c
u
r
=
0
init++转化为cur = 0
init++转化为cur=0这样就行了。
代码：
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/* * Author: zixi * Created Time: 2020/7/11 16:40:00 */ #include<iostream> #include<algorithm> #include<string> using namespace std; /* 3 --+- --- ++--+- */ typedef long long int ll; void solved(){ string s;cin>>s; ll res = 0; ll cur = 0; for(int i = 0; i < s.size(); i++){ if(s[i] == '+')cur++; else cur--; if(cur < 0){ res += (i + 1); cur = 0; } } res += s.size(); cout<<res<<endl; } int main(){ int t;cin>>t; while(t--)solved(); return 0; }
题目大意：
给你一个数组，你可以选择任意一个子数组进行翻转，求
m
a
x
(
Σ
(
a
i
)
)
，
i
为
偶
数
max(Σ(ai))，i为偶数
max(Σ(ai))，i为偶数。
思路：看到这个题目如果能想到最大子段和就可以秒了这题，事实上这就是一个最大字段和的变种，对于每个偶数位置的值，他只能前后翻转，然后我们可以预处理前后翻转的增量，然后做一个最大字段和，然后偶数位置的和+
m
a
x
(
d
e
l
t
a
1
,
d
e
l
t
a
2
)
max(delta1,delta2)
max(delta1,delta2)就是答案了。最大子段和就是一个子数组翻转的结果。
代码：
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#include<iostream> #include<algorithm> using namespace std; /* 3 5 17 6 4 4 4 7 19 5 13 11 12 13 5 1 213567876 */ const int maxn = 2e5 + 10; typedef long long int ll; ll a[maxn]; ll dp1[maxn],dp2[maxn]; void solved(){ int n;cin>>n; ll sum = 0; for(int i = 0; i < n; i++){ cin>>a[i]; if(i % 2 == 0)sum += a[i]; } for(int i = 0; i < n; i++){ if(i + 1 < n && i & 1){ dp1[i] = a[i] - a[i + 1]; }else if(i + 1 < n){ dp2[i] = a[i + 1] - a[i]; } } ll s = 0; ll delta1 = 0; for(int i = 0; i < n; i++){ if(s < 0){s = dp2[i];continue;} s += dp2[i]; delta1 = max(delta1,s); } s = 0; ll delta2 = 0; for(int i = 0; i < n; i++){ if(s < 0){s = dp1[i];continue;} s += dp1[i]; delta2 = max(delta2,s); } cout<<sum + max(delta1,delta2)<<endl; } int main(){ int t;cin>>t; while(t--)solved(); return 0; }
最后
以上就是背后苗条最近收集整理的关于Educational Codeforces Round 90 (Rated for Div. 2)(ABCD题解)的全部内容，更多相关Educational内容请搜索靠谱客的其他文章。
发表评论 取消回复