首页 > 其他 > 详细

积木问题

时间:2017-08-19 10:40:15      阅读:271      评论:0      收藏:0      [点我收藏+]

(赛码网的模拟考试题,这道题目挺有意思)

搭积木

时间限制:C/C++语言 1000MS;其他语言 3000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB

题目描述:

一天,小明买了许多积木回家,他想把这些积木拼接在一起。每块积木有两个接口,每个接口我们用一个数字标记,规定只有当两块积木有相同数字标记的接口时,这两块积木才可以通过该接口拼接在一起。举例,有两块积木,接口数字分别为1,2和3,4,那么这两块积木无法拼接;若两块积木接口数字分别为1,2和2,3,那么这两块积木可以通过由数字2标记的接口拼接在一起。现在小明知道所有积木的数量和每块积木接口的数字标记,你能告诉他他可以将所有积木拼接成一个整体么?

输入

第一行一个整数t,表示测试数组组数1≤t≤10;
接下来在每组测试数据中:
第一行一个整数n,表示积木的数量1≤n≤100000,
下面n行每行2个整数x,y,表示其中一块积木的两个接口的数字标记;1≤x,y≤100000;

输出

对于每组测试数据,输出”YES”,表示该组数据中的所有积木可以拼接成一个整体,”NO”表示不行。(注意输出不包括引号)

样例输入

2
3
1 2
2 3
4 5
6
1 2
2 3
3 5
4 5
4 6
5 1

样例输出

NO
YES

Hint

在第一组测试数据中,有3块积木,显然前两块是可以拼接在一起的,但是第3块无论如何也无法和前两块拼接,所以输出NO;第二组数据中我们可以这样拼接:5-1-1-2-2-3-3-5-5-4-4-6,因此输出YES。

思路:

先将每个积木的键值对用multimap排序(先都存起来的原因是积木可能乱序,为了排序.注意multimap插入时让小的标号在前面,因为multimap只针对键值排序),然后从头向尾处理,若可以连接,就更新尾端(由于两端均可能更新,故用deque维护).如果遇到和deque中两端数字均不同的积木,即不可链接.否则如果走完全部积木,即为可链接.

代码:

 1 /*搭积木
 2 时间限制:C/C++语言 1000MS;其他语言 3000MS
 3 内存限制:C/C++语言 65536KB;其他语言 589824KB
 4 题目描述:
 5 一天,小明买了许多积木回家,他想把这些积木拼接在一起。每块积木有两个接口,每个接口我们用一个数字标记,规定只有当两块积木有相同数字标记的接口时,这两块积木才可以通过该接口拼接在一起。举例,有两块积木,接口数字分别为1,2和3,4,那么这两块积木无法拼接;若两块积木接口数字分别为1,2和2,3,那么这两块积木可以通过由数字2标记的接口拼接在一起。
 6 现在小明知道所有积木的数量和每块积木接口的数字标记,你能告诉他他可以将所有积木拼接成一个整体么?
 7 输入
 8 第一行一个整数t,表示测试数组组数1≤t≤10;
 9 接下来在每组测试数据中:
10 第一行一个整数n,表示积木的数量1≤n≤100000,
11 下面n行每行2个整数x,y,表示其中一块积木的两个接口的数字标记;1≤x,y≤100000;
12 输出
13 对于每组测试数据,输出”YES”,表示该组数据中的所有积木可以拼接成一个整体,”NO”表示不行。(注意输出不包括引号)
14 样例输入
15 2
16 3
17 1 2
18 2 3
19 4 5
20 6
21 1 2
22 2 3
23 3 5
24 4 5
25 4 6
26 5 1
27 样例输出
28 NO
29 YES
30 
31 Hint
32 在第一组测试数据中,有3块积木,显然前两块是可以拼接在一起的,但是第3块无论如何也无法和前两块拼接,所以输出NO;第二组数据中我们可以这样拼接:5-1-1-2-2-3-3-5-5-4-4-6,因此输出YES。
33 */
34 
35 //思路:先将每个积木的键值对用multimap排序(先都存起来的原因是积木可能乱序,为了排序.注意multimap插入时让小的标号在前面,因为multimap只针对键值排序),然后从头向尾处理,若可以连接,就更新尾端(由于两端均可能更新,故用deque维护)
36 #include <iostream>
37 #include <map>
38 #include <deque>
39 #include <string>
40 
41 using namespace std;
42 
43 int main() {
44     int group;
45     cin >> group;
46     while (group--) {
47         string result = "YES";
48         int n;
49         cin >> n;
50         multimap<int, int> mymap;
51         int tmp1, tmp2;
52         while (n--) {
53             cin >> tmp1 >> tmp2;
54             if (tmp1 <= tmp2)
55                 mymap.insert(pair<int, int>(tmp1, tmp2));
56             else
57                 mymap.insert(pair<int, int>(tmp2, tmp1));
58         }
59         deque<int> judge;
60         multimap<int, int>::iterator it = mymap.begin();
61         judge.push_back((*it).first);
62         judge.push_back((*it).second);
63         ++it;
64         for (; it != mymap.end(); ++it) {
65             // cout << "judge.size()=" << judge.size() << endl;
66             // cout << "judge[0]=" << judge[0] << "judge[1]=" << judge[1] << endl;
67             if (judge[0] == (*it).first) {
68                 judge.pop_front();
69                 judge.push_front((*it).second);
70             }
71             else if (judge[1] == (*it).first) {
72                 judge.pop_back();
73                 judge.push_back((*it).second);
74             }
75             else if (judge[0] == (*it).second) {
76                 judge.pop_front();
77                 judge.push_front((*it).first);
78             }
79             else if (judge[1] == (*it).second) {
80                 judge.pop_back();
81                 judge.push_back((*it).first);
82             }
83             else {
84                 result = "NO";
85                 break;
86             }
87         }
88         result = (result == "NO") ? "NO" : "YES";
89         cout << result << endl;
90     }
91     return 0;
92 }

 

积木问题

原文:http://www.cnblogs.com/xiaoxi666/p/7392723.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!