河南省第十三届ICPC大学生程序设计竞赛——I题 七便士(不是深搜)

河南省第十三届ICPC大学生程序设计竞赛——I题 七便士(不是深搜)

        相信看过这道题的人,首先都会想到DFS的解法,那么呢,这个想法是没错的,而且官方给的题解我记得没错的话,也是这个解法,而我要分享的是一个不一样的解法。

        首先思路的话我们需要先解读一下题意,简单来说,而最后能不能放进去7个硬币就是看已经放上的硬币是不是连在一起的,如果是那就可以,如果不是那就输出No了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,j,k,biao,sum,sum1;		
	int c[10];	
	char b[10];
	c[1]=1;c[2]=4;c[3]=7;c[4]=2;c[5]=5;c[6]=8;c[7]=3;c[8]=6;
	cin>>n;
	while(n--)
	{
		biao=0;
		sum=0;sum1=0;
		for(i=1;i<9;i++)
			cin>>b[i];
		for(i=1;i<9;i++)//记录已有硬币的总数 就是1的个数 
		{
			if(b[i]=='1')
			sum1++;
		}
		if(sum1>=1)
		for(i=1;;i++)// 判断所有的硬币是不是连在一起的 
		{
			int j=i-1;
			if(j==0)
				j=8;
			if(biao>0&&b[c[i]]=='1')
				sum++;
			if(b[c[i]]=='1'&&b[c[j]]=='0'&&biao==0)
			{
				sum++;
				biao++;
			}
			else if(biao>0&&b[c[i]]!='1')
				break;
			if(i==8)
				i=0;
		}
		if(sum==sum1)
		cout<<"Yes"<<endl;
		else
		cout<<"No"<<endl;
	}
	return 0;
} 

        代码其实很简单,而我感觉当时有点麻烦的就是两个数组的嵌套, 从而构成了题目上的七便士的循环。

上一篇:2021 ICPC 江西省大学生程序设计竞赛 H Hearthstone So Easy


下一篇:河南十三届ICPC部分题解