Codeforces Educational Codeforces Round 106 (Rated for Div. 2) A—C题解

比赛传送门：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代码：

#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代码

#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代码

#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 Educational Codeforces Round 106 (Rated for Div. 2) A—C题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。