B - Split?
题目:
有 7 列保龄球瓶,总共有 10 个球瓶,每一列有哪些球瓶给你了,现在有几个瓶倒了,问是否有满足以下两个条件:
1.编号为 1 的瓶倒了
2.有两列至少有一个瓶站着,且这两列中间有一列全倒了。
输入长度为 10 的字符串表示 10 个球瓶的状态,'0' 表示倒了;'1' 表示没倒。如果满足条件输出Yes,否则输出 No。初始保龄球瓶状态如下:
数据范围:
长度为10的字符串,仅由字符0,1组成。
思路:
暴力模拟,需要记录每一列现存的球瓶的个数;每个圆所属的列。然后:
首先判断是否球瓶1被选了,没被选直接No,如果被选了之后再:
1.根据输入的 10 个球瓶的初始状态,根据输入的球瓶状态更新每一列球瓶的个数;
2.用两重循环枚举两列,如果存在两列的各自现存的球瓶的个数都不为 0,则再在这两列之间枚举列,如果存在某列拥有球瓶的个数为 0,Yes。否则,No。
Code:
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
int row[11] = { 0,4,3,5,2,4,6,1,3,5,7 }; //数组row[i]表示第i个圆所在的列
int cnt[8] = { 0,1,1,2,2,2,1,1 }; //数组cnt[i]表示第i列圆的个数
void solve()
{
char s[11];
cin >> (s + 1); //输入10个圆的状态
if (s[1] == '1')return void(puts("No")); //第一个条件都不满足
else
{
for (int i = 1; i <= 10; i++) //更新每一列现存的圆个数
{
if (s[i] == '0')
cnt[row[i]]--; //表示第i个圆所在的第row[i]列的圆的个数cnt[row[i]]减1
}
}
for(int i = 1;i<=7;i++) //枚举两列中的前一列
for(int j = i+1;j<=7;j++) //枚举两列中的后一列
if (cnt[i] && cnt[j]) //如果出现两列各自现存的圆的个数都不为0
{
for (int k = i + 1; k < j; k++) //遍历这两列中间的列
if (cnt[k] == 0) //如果出现列中圆的个数为0,满足条件
return void(puts("Yes"));
}
puts("No");
}
int main()
{
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
吐槽:当时写这题时就是纯暴力,用运算符 | 预处理的,写得可麻烦还可容易写错。看了大大的模拟就很清晰,预处理分得也很细。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)