比赛传送门：https://codeforces.com/contest/1499
A.Domino on Windowsill(水题)
题目大意：
共t组测试数据，每组数据包含n，k1，k2，w，b五个数据。其中k1表示第一行中从1-k1个的所有色块都是白色，其余全是黑色。同样的，k2表示第二行中1-k2个的所有色块都是白色的，其余全是黑色。w是白色多米诺的数量，b是黑色多米诺的数量。每两个连续的白色块能放一个白色多米诺，每两个连续的黑色块能放一个黑色多米诺。问能否放完所有的黑色、白色多米诺。
思路：
统计白色块和黑色块的个数，分别除以2，然后和w，b进行比较即可。
AC代码：
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#include<bits/stdc++.h> #define ll long long using namespace std; int main() { int t=0; cin>>t; while(t--) { int n=0,k1=0,k2=0; int a[2][1005]={0}; int w=0,b=0; cin>>n>>k1>>k2; cin>>w>>b; int numw=0; for(int i=1;i<=k1;i++) { a[0][i] = 1; numw++; } for(int i=1;i<=k2;i++) { a[1][i] = 1; numw++; } int numb = 2*n-numw; numw/=2; numb/=2; if(numw>=w&&numb>=b) { cout<<"Yes"<<endl; } else cout<<"No"<<endl; } return 0; }
B. Binary Removals（思维）
题目大意
给你一个二进制字符串，你能从中删除多个数字（但是任意两个被删除的数字不能是连续的），问是否能够通过删除使得整个字符串是排好序的？（后面的数字>=前面的数字）
思路
本题其实很简单，如果连续两个1后面出现了连续的两个0，则永远无法满足排好序的情况。其余的情况均能通过删除使得数串满足要求。
AC代码
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#include<bits/stdc++.h> #define ll long long using namespace std; int main() { int t=0; cin>>t; while(t--) { int flag1=0,flag2=0; string a; cin>>a; int temp=0; for(int i=0;i<a.length()-1;i++) { if(a[i]=='1'&&a[i+1]=='1') { flag1=1; temp=i+1; break; } } for(int i=temp;i<a.length();i++) { if(a[i]=='0'&&a[i+1]=='0') { flag2=1; break; } } if(flag1==1&&flag2==1) { cout<<"No"<<endl; } else cout<<"Yes"<<endl; } return 0; }
C. Minimum Grid Path（贪心）
题目大意
给你数字n，让你从（0，0）走到（n，n），你只能向右或者向上走。下面给你n个数字，代表你每一次转向后下一个方向所有路径的单位花费。问如何走能够使得总花费最小？
思路
既然是从（0，0）走到（n，n），那么就意味着无论如何都要向右走n个单位，向上走n个单位。这里我们不妨从左向右遍历所有的单位花费，然后找到每个位置的最小值。这个最小值的计算方法如下：让从0到当前位置的单位花费都走一步，剩余的路径全让最小花费走完。
这里要注意的一点是，因为向右向上这两个方向是独立的，所以在考虑最小花费的时候应该分奇偶讨论，在两个方向上分别按照上述的方法计算最小值，求出总花费的最小值即可。
AC代码
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<bits/stdc++.h> #define ll long long using namespace std; int main() { int t=0; cin>>t; while(t--) { static ll a[100005]={0}; ll n=0; cin>>n; ll ans=0; for(ll i=1;i<=n;i++) { scanf("%lld",&a[i]); } //ji是一个方向 ou是另外一个方向 //mnji代表直到当前位置为止，这个方向上的最小值；mnou代表另一个方向 ll ji=0,mnji=0,ou=0,mnou=0; ji = a[1];ou = a[2];mnji = a[1];mnou = a[2];//初始化 ans=(a[1]+a[2])*n; for(int i=3;i<=n;i++) { if(i&1) { ji+=a[i];//只让它走一步 mnji = min(mnji,a[i]);//更新最小值 } else { ou+=a[i]; mnou = min(mnou,a[i]); } ans = min(ans,ji+mnji*(n-(i+1)/2)+ou+mnou*(n-i/2));//计算总花费 } cout<<ans<<endl; } return 0; }
最后
以上就是苹果刺猬最近收集整理的关于Codeforces Educational Codeforces Round 106 (Rated for Div. 2) A—C题解的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复