【天梯赛】第四届团体程序设计天梯赛L2题解
L2-1 特立独行的幸福 （25分)
对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 1，就称该数为幸福数。1 是一个幸福数。此外，例如 19 经过 1 次迭代得到 82，2 次迭代后得到 68，3 次迭代后得到 100，最后得到 1。则 19 就是幸福数。显然，在一个幸福数迭代到 1 的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。例如 19 在区间[1, 100] 内就是一个特立独行的幸福数，其独立性为 2×4=8。
另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如 29 迭代得到 85、89、145、42、20、4、16、37、58、89、…… 可见 89 到 58 形成了死循环，所以 29 就不幸福。
本题就要求你编写程序，列出给定区间内的所有特立独行的幸福数和它的独立性。
输入格式：
输入在第一行给出闭区间的两个端点：1<A<B≤10^4
输出格式：
按递增顺序列出给定闭区间 [A,B] 内的所有特立独行的幸福数和它的独立性。每对数字占一行，数字间以 1 个空格分隔。
如果区间内没有幸福数，则在一行中输出 SAD。
输入样例 1：
10 40
输出样例 1：
19 8
23 6
28 3
31 4
32 3
注意：样例中，10、13 也都是幸福数，但它们分别依附于其他数字（如 23、31 等等），所以不输出。其它数字虽然其实也依附于其它幸福数，但因为那些数字不在给定区间 [10, 40] 内，所以它们在给定区间内是特立独行的幸福数。
输入样例 2：
110 120
输出样例 2：
SAD
思路：从A开始遍历，到B结束，如果当前数是幸福数，加入结果集合total，并保存当前数和其独立性，此后每次遍历其他数的时候，如果过程中得到了结果集合里的数，说明之前的数依赖当前的数，则删掉之前的数。每次遍历的时候再用一个集合判断是否循环。遍历结束时，把之前曾经是幸福数的每个数都遍历一下，出现在结果集合里的则是最终答案。
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include <string>
#include <vector>
#include<stack>
#include<cmath>
#include<set>
#include<string.h>
using namespace std;
int su(int n)
{
int j = sqrt(n);
for (int i = 2; i <= j; i++)
if (n%i == 0)
return 1;
return 2;
}
int ping(int n)
{
int res = 0;
for (int i = 0;; i++)
{
res += (n % 10)*(n % 10);
n /= 10;
if (n == 0)
break;
}
return res;
}
int main() {
int x, y;
cin >> x >> y;
int res[10001];
int w[10001];
int geshu = 0;
set<int> total;
bool yilai[10001];
memset(yilai, false, sizeof(yilai));
for (int i = x; i <= y; i++)
{
if (yilai[i])
continue;
int temp = i;
set<int> bianhuan;
bool yes = false;
if (i == 1)
yes = true;
while (temp != 1)
{
bianhuan.insert(temp);
temp = ping(temp);
if (bianhuan.count(temp) == 1)
break;
if (temp == 1)
{
yes = true;
break;
}
yilai[temp] = true;
if (total.count(temp) == 1)
total.erase(temp);
}
if (yes)
{
res[geshu] = i;
w[geshu] = su(i)*bianhuan.size();
total.insert(i);
geshu++;
}
}
if (geshu == 0)
cout << "SAD";
else
{
for(int i=0;i<geshu;i++)
if (total.count(res[i]) == 1)
{
cout << res[i] << " " << w[i] << endl;
}
}
}
L2-2 冰岛人
本人到现在还不知道到底该怎么做，改来改去也只有20分，等以后想到了解决方法再来更新。
L2-3 深入虎穴 （25分)
著名的王牌间谍 007 需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门…… 他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。
内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。
输入格式：
输入首先在一行中给出正整数 N（<10^5），是门的数量。最后 N 行，第 i 行（1≤i≤N）按以下格式描述编号为 i 的那扇门背后能通向的门：K D[1] D[2] ... D[K]
其中K是通道的数量，其后是每扇门的编号。
输出格式：
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。
输入样例：
13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0
输出样例：
12
思路：比赛的时候这道题我用了三种方法写，bfs，迪杰斯特拉，dfs，但最后最高也只得了18分，最后才知道，并不是默认1号门为入口，要找出入度为0的门作为入口，坑啊。之后直接dfs就行了，挺简单的。
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<cmath>
#include<set>
#include<string.h>
using namespace std;
vector<int> v[100001];
int maxx = 0;
int bian = 0;
void dfs(int i, int ju)
{
if (ju > maxx)
maxx = ju, bian = i;
for (int j = 0; j < v[i].size(); j++)
dfs(v[i][j], ju + 1);
}
int du[100001];
int main() {
memset(du, 0, sizeof(du));
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int k, t;
cin >> k;
for (int j = 0; j < k; j++)
{
cin >> t;
v[i].push_back(t);
du[t]++;
}
}
int start = 0;
for(int i=1;i<=n;i++)
if (du[i] == 0)
{
start = i;
break;
}
dfs(start, 1);
cout << bian;
}
L2-4 彩虹瓶 （25分)
彩虹瓶的制作过程（并不）是这样的：先把一大批空瓶铺放在装填场地上，然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。
假设彩虹瓶里要按顺序装 N 种颜色的小球（不妨将顺序就编号为 1 到 N）。现在工厂里有每种颜色的小球各一箱，工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色，就直接拆箱装填；如果不是，就把箱子先码放在一个临时货架上，码放的方法就是一箱一箱堆上去。当一种颜色装填完以后，先看看货架顶端的一箱是不是下一个要装填的颜色，如果是就取下来装填，否则去工厂里再搬一箱过来。
如果工厂里发货的顺序比较好，工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色，工厂按照 7、6、1、3、2、5、4 这个顺序发货，则工人先拿到 7、6 两种不能装填的颜色，将其按照 7 在下、6 在上的顺序堆在货架上；拿到 1 时可以直接装填；拿到 3 时又得临时码放在 6 号颜色箱上；拿到 2 时可以直接装填；随后从货架顶取下 3 进行装填；然后拿到 5，临时码放到 6 上面；最后取了 4 号颜色直接装填；剩下的工作就是顺序从货架上取下 5、6、7 依次装填。
但如果工厂按照 3、1、5、4、2、6、7 这个顺序发货，工人就必须要愤怒地折腾货架了，因为装填完 2 号颜色以后，不把货架上的多个箱子搬下来就拿不到 3 号箱，就不可能顺利完成任务。
另外，货架的容量有限，如果要堆积的货物超过容量，工人也没办法顺利完成任务。例如工厂按照 7、6、5、4、3、2、1 这个顺序发货，如果货架够高，能码放 6 只箱子，那还是可以顺利完工的；但如果货架只能码放 5 只箱子，工人就又要愤怒了……
本题就请你判断一下，工厂的发货顺序能否让工人顺利完成任务。
输入格式：
输入首先在第一行给出 3 个正整数，分别是彩虹瓶的颜色数量 N（1<N≤10^3）、临时货架的容量 M（<N）、以及需要判断的发货顺序的数量 K。
随后 K 行，每行给出 N 个数字，是 1 到N 的一个排列，对应工厂的发货顺序。
一行中的数字都以空格分隔。
输出格式：
对每个发货顺序，如果工人可以愉快完工，就在一行中输出 YES；否则输出 NO。
输入样例：
7 5 3
7 6 1 3 2 5 4
3 1 5 4 2 6 7
7 6 5 4 3 2 1
输出样例：
YES
NO
NO
思路：没啥好说的，直接读数，用一个stack模拟一下就行了。
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include <string>
#include <vector>
#include<stack>
#include<cmath>
#include<set>
#include<string.h>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < k; i++)
{
int a[1001];
for (int j = 0; j < n; j++)
cin >> a[j];
stack<int> s;
int now = 1;
for (int j = 0; j < n; j++)
{
if (a[j] == now)
{
now++;
if (s.empty())
continue;
while (!s.empty())
{
if (s.top() == now)
{
now++;
s.pop();
}
else
break;
}
}
else
{
s.push(a[j]);
if (s.size() > m)
break;
}
}
if (now == n + 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}