放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

AOJ 0033 Ball《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 深度优先搜索

AOJ 0033 Ball

有一个形似央视大楼(Orz)的筒,从A口可以放球,放进去的球可通过挡板DE使其掉进B裤管或C裤管里,现有带1-10标号的球按给定顺序从A口放入,问是否有一种控制挡板的策略可以使B裤管和C裤管中的球从下往上标号递增。 

输入:

第一行输入数据组数N。接下来N行为N组具体数据,每组数据中有10个整数,代表球的放入顺序。 

输出:

对于每组数据,若策略存在,输出YES;若不存在,输出NO 

翻译来自http://blog.csdn.net/synapse7/article/details/14454885


bitset是我最爱的玩具,通俗易懂,方便好用。

#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{

	int n;
	cin >> n;
	while (n--)
	{
		int ball[10];
		
		for (int i = 0; i < 10; ++i)
		{
			cin >> ball[i];
		}

		bitset<10> direction;
		int all = 1024;
		while (all-- > 0)
		{
			direction = static_cast<bitset<10> >(all);
			bool perfect = true;
			int left = 0;
			int right = 0;
			for (int i = 0; i < 10; ++i)
			{
				if (direction[i])
				{
					if (ball[i] > left)
					{
						left = ball[i];
					}
					else
					{
						perfect = false;
						break;
					}
				}
				else
				{
					if (ball[i] > right)
					{
						right = ball[i];
					}
					else
					{
						perfect = false;
						break;
					}
				}
			}
			if (perfect)
			{
				break;
			}
		}
	
		if (all >= 0)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}

	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » AOJ 0033 Ball《挑战程序设计竞赛(第2版)》练习题答案

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    #include
    using namespace std;

    int n;
    int a[10];

    bool dfs(int i, int left, int right) {
    if (i == 9) return a[i] > left || a[i] > right;
    if (a[i] > left && dfs(i+1, a[i], right)) return true;
    if (a[i] > right && dfs(i+1, left, a[i])) return true;
    return false;
    }

    void solve() {
    if (dfs(0,0,0)) cout << "YES" << endl;
    else cout << "NO" <> n;
    for (int i = 0; i < n; i++) {
    for (int j = 0; j > a[j];
    }
    solve();
    }
    }

    haass6年前 (2018-10-23)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》