Codeforces405 B. Domino Effect

http://codeforces.com/problemset/problem/405/B

题意:给出n个骨牌倒的方向(左,右,不动),求最后保持直立的骨牌个数。

思路:我是花了很大的功夫才搞好了这道题

方法①:从左到右扫一遍,一个位置i最后直立,只有以下几种情况:(先找出i向左/右第一个原始不直立的点,记为l,r)

l空&r是R,r空&l是L,rl均空,l是L&r是R,l是R&r是L&i距离l和r相同。

方法②:连续的L或R可以等效成一个L或R,因此把题目所给等效成L和R交替出现,就好做了。

方法1代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 4000

int n,ans;
char a[maxn];



int main()
{
	//freopen("input.in","r",stdin);
	cin>>n;
	scanf("%s",a+1);
	for(int i=1;i<=n;i++)if(a[i]=='.')
	{
		int l,r;
		for(l=i-1;l>=1;l--)
		{
			if(a[l]!='.')break;
		}
		for(r=i+1;r<=n;r++)
		{
			if(a[r]!='.')break;
		}
		if(!l&&r==n+1||!l&&a[r]=='R'||r==n+1&&a[l]=='L')ans++;
		else if(l&&r<=n&&a[l]=='L'&&a[r]=='R')ans++;
		else if(l&&r<=n&&a[l]=='R'&&a[r]=='L'&&i-l==r-i)ans++;
	}
	cout<<ans;
	return 0;
}

 

全部评论

相关推荐

06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
那一天的Java_Java起来:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务