19天梯杯旅游记

发表于 分类于 ， 阅读次数： 本文字数： 13k 阅读时长 ≈ 11 分钟

前言

我也不知道哪里来的一个天梯杯比赛，压根就没听过的比赛，也不知道是谁举办的！好不容易有机会能够去学校外比赛，那当然是选择公费旅游啦！
旅游目的地： 深圳 深职院
深圳我去的不多，毕竟省内还是广州跑的多。而且目的地还是分数线高出本科线超多的深职院，那更要体验一波了。听说硬件实力超强，但我感觉表面上确实挺好的，机子挺垃圾的。(或许这个锅应该比赛方去背)

顺便说句题外话，现在notepad++对Markdown语法支持变好了，起码有语法高亮了。

一波美图

说到这，肯定要先上一波图。
此次使用的图库由Github提供，BTW，真的让我很难相信国内的免费服务，各种坑。七牛云再见！
但不得不说这增加了我插入图片的难度！毕竟那次修改链接，修改的我快吐血！
在此，请允许我盗一波图！（如果有要求撤下的，请直接联系我）因为我的摄影角度太直男了，尽管技术还OK！















我自己的丑图就不放了，虽然我也传到了博客上，就看你能不能找到了。

比赛前

我记得比赛前我听到那个判作弊规则，我当场就想敲桌子。只不过我好像已经忘了为什么我要敲桌子了。
吃了个中午饭，没有想象中的好，可能期望值太高，然后就看到了一个令人窒息的画面。(亮点自寻)

比赛中

我敲桌子其实是没错的，那个垃圾考试客户端浏览器既然崩溃了，然后找人来扫码才进去的。
在此之前，我还发现那个排行榜不是实时的，报给工作人员，他们说就是这样。（无话可说）
毕竟我是裸考，考试中才发现原来那么多道题，因为我有点担心基础题分数不够，所以在那死磕。
但不得不说，这是我所有比赛中遇到字符串题最多的一场。差点要了我的命，欺负我不擅长使用C弄字符串题，还是高级语言好，Java组应该在那窃喜。如果用我的母语Pascal应该能更快搞定，只不过要是考试真的允许，估计我也不行，函数都忘得差不多了。

比赛后

我在排行榜竟然看到了身处UESTC的同学，L1全过，L2有一题没管过，L3没做。我敢肯定L3是没做，就他这水平AK不是问题。毕竟ganxi。
只不过我觉得挺惊讶他来打这个比赛的，难道也是来公费旅游的？？！！要不就是他们学校的人数不够，只好拿他这种顶级选手来凑数。

题解

L1-1 PTA使我精神焕发

搞笑题，我都有点不想贴代码了。

1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
using namespace std;

int main()
{
	cout << "PTA shi3 wo3 jing1 shen2 huan4 fa1 !";
	return 0; 
}

注意bits/stdc++.h在考场上有可能不能用，而且用了后Dev-Cpp的函数提示功能无法使用

L1-2 6翻了

考试时挂了1个点，只不过当时想复杂了点，我搞成一个词去判断是不是666了。所以，我也知道那会有点问题。
下面是复盘之后的AC代码
之所以i要循环到strlen(s)溢出，是要给最后一个字符过后的判断机会。如果最后字符有连续的666，也要修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

char s[1005];
int tot;

int main()
{
	cin.getline(s,sizeof s);
	for (int i=0;i<=(int)strlen(s);i ++)		//多判断一位
	{
		if (s[i]=='6') tot ++;
		else
		{
			if (tot>9) printf("27");
			else if (tot>3) printf("9");
			else if (tot>0)
				for (int j=0;j<tot;j++) printf("6");
			if (i!=strlen(s)) printf("%c",s[i]);
			tot = 0;
		}
	}
}

L1-3 敲笨钟

挺有趣的一道题，换汤不换药，但是这次的汤比较新颖。
我用实力证明不需要记那些花里胡哨的函数，还不如自己手写来的快，来的好。
一个函数搞定字符串子串匹配，在借用c语言字符串数组的巧妙之处，强行插一个'\0'就能截断。
不需要把字符串捣鼓来捣鼓去的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;

const int M = 1005;
int n;
char s[M];

bool judge(char s[],char st[])
{
	for (int i=0;i+strlen(st)-1<strlen(s);i ++)
	{
		bool flag = 1;
		for (int j=0;j<strlen(st);j ++)
		{
			if (s[i+j]!=st[j])
			{
				flag = 0;
				break;
			}
		}
		if (flag) return 1;
	}
	return 0;
}

int find(char s[])
{
	int tot = 0;
	for (int i=strlen(s)-1;i>=0;i --)
	{
		if (s[i]==' ') tot ++;
		if (tot==3) return i+1;
	}
	return 0;
}

int main()
{
	//freopen("L1-3.in","r",stdin);
	scanf("%d\n",&n);
	while (n --)
	{ 
		cin.getline(s,sizeof s);
		if (judge(s,"ong,") && judge(s,"ong."))
		{
			s[find(s)] = '\0';
			cout << s << "qiao ben zhong." << endl;
		} else cout << "Skipped" << endl;
	}
	
}

L1-4 心理阴影面积

不知道为什么，我一上手这道题，就想用海伦公式，看到题目提示说可以很容易的加减出来，我才发现还是加减三角形、矩形容易。只不过这道题有除法，但是输出格式中并没有明确怎么输出小数。只不过这也无所谓，反正不限制提交次数(不罚时)，当然是怎么快怎么来。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;

int x,y;
double ans;

int main()
{
	cin >> x >> y;
	ans = 100*100/2-x*y*0.5-(100-x)*y-(100-x)*(100-y)*0.5;
	cout << ans; 
	return 0;
}

L1-5 新胖子公式

这题要注意的是公式是$\frac{体重(kg)}{身高(m)^2}$,mathjax那么好用，不知道为什么不用，就算是用纯文本的表示方式也要加个括号！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

double n,m,ans;

int main()
{
	cin >> n >> m;
	ans = 1.0*n/m/m;
	printf("%.1f\n",ans);
	if (ans>25) cout << "PANG" << endl;
	else cout << "Hai Xing" << endl;
	return 0;
}

L1-6 幸运彩票

没啥好说的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int T,n,x,y; 

int calc(int x)
{
	int ret = 0;
	while (x)
	{
		ret += x%10;
		x /= 10;
	}
	return ret;
}

int main()
{
	cin >> T;
	while (T--)
	{
		cin >> n;
		x = n/1000;
		y = n%1000;
		if (calc(x) == calc(y)) cout << "You are lucky!" << endl;
		else cout << "Wish you good luck." << endl; 
	}
}

L1-7 吃鱼还是吃肉

也没啥好说的，但是我在尽力想办法写简短清晰写，我也就只能做到这种程度了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

int T,sex,height,weight;

int main()
{
	cin >> T;
	while (T --)
	{
		cin >> sex >> height >> weight;
		if (sex==0)
		{
			if (height==129) cout << "wan mei!";
			if (height>129) cout << "ni li hai!";
			if (height<129) cout << "duo chi yu!";
			cout << " ";
			if (weight==25) cout << "wan mei!";
			if (weight>25) cout << "shao chi rou!";
			if (weight<25) cout << "duo chi rou!";
			cout << endl;
		} else
		{
			if (height==130) cout << "wan mei!";
			if (height>130) cout << "ni li hai!";
			if (height<130) cout << "duo chi yu!";
			cout << " ";
			if (weight==27) cout << "wan mei!";
			if (weight>27) cout << "shao chi rou!";
			if (weight<27) cout << "duo chi rou!";
			cout << endl;
		}
	}
	return 0;
}

L1-8 估值一亿的AI核心代码

出题者说这道题是扎实的字符串题，以至于我做到一半，害怕时间不够A不出来，就跑去做后面L2的题，结果因为后面的题目都太长，然后我很不幸的选择了一道需要很强阅读理解的题。就又滚回来做这道，考试时没有全部A出来。
像这种题就需要思路非常清晰，然后严格按照出题者说的做，比如我在考场就被I这个东西坑了，如果一个单词中有I，不需要转小写。
judge是用来判断是大写字母，小写字母，数字、标点符号还是空格的。
independ是用来判断是否是个独立的单词，也就是单词前后有空格，当然对于开头和结尾的单词需要特判，同时有些单词可能前后跟的是标点符号。
work按照要求去处理这些字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cstring>
using namespace std;

const int M = 1107;
int n;
char s[M];

int judge(char ch)
{
	if (ch>='A' && ch<='Z') return 1;
	if (ch>='a' && ch<='z') return 2;
	if (ch>='0' && ch<='9') return 3;
	if (ch==' ') return 4;
	return -1;
}

bool independ(char s[],char st[],int &k)
{
	int L = k,R = k+strlen(st)-1;
	if (L<0 || R>=strlen(s)) return 0;
	for (int i=0;i<(int)strlen(st);i ++)
		if (s[k+i] != st[i]) return 0;
	bool flag;
	if (L==0 || judge(s[L-1])==4 || judge(s[L-1])==-1) flag = 1; else flag = 0;
	if (R==strlen(s)-1 || judge(s[R+1])==4 || judge(s[R+1])==-1) flag &= 1; else flag = 0;
	if (flag) k=R;
	return flag;
	
}

void work(char s[])
{
	cout << "AI: "; 
	int len = strlen(s),L,R;
	for (int i=0;i<len;i ++)
		if (s[i]!=' ') 
		{
			L = i;
			break;
		}
	for (int i=len-1;i>=0;i ++)
		if (s[i]!=' ')
		{
			R = i;
			break;
		}
	//删除首尾空格
	char news[M]="";
	len = 0;															//新生成字符串长度
	for (int i=L;i<=R;i ++)
	{
		if (judge(s[i])==1 && s[i]!='I') s[i] = s[i]-'A'+'a';			//大写转小写
		if (s[i]=='?') s[i] = '!';										//？转！
		if (judge(s[i])==4 && len!=0 && news[len-1]==' ') continue;		//删除连续空格
		if (len!=0 && news[len-1]==' ' && judge(s[i])==-1) len --;		//删除标点符号前的空格
		news[len ++] = s[i];
	}
	for (int i=0;i<(int)strlen(news);i ++)
	{
		if (independ(news,"can you",i)) cout << "I can";
		else if (independ(news,"could you",i)) cout << "I could";
		else if (independ(news,"I",i) || independ(news,"me",i)) cout << "you";
		else cout << news[i];
	}
	//词汇替换
	cout << endl;
	//cout << news <<endl;
}

int main()
{
	//freopen("L1-8.in","r",stdin);
	scanf("%d\n",&n); 
	while (n --)
	{
		cin.getline(s,sizeof s);
		cout << s << endl;
		work(s);
	}
	return 0;	
}

L2-1 特立独行的幸福

L2一上来就是这道题，被出题者的概念绕晕了，还好看了示例就明白了，就是一条路走到底，看看有没有环，有环就标记-1。输出时在判断一下素数就好，也不需要筛什么素数，这种难度的题，想超时都难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;

const int N = 1e4+7;
int A,B;
int a[N],vis[N],p[N];

bool prime(int x)				//素数判断
{
	for (int i=2;i<=floor(sqrt(x));i ++)
	{
		if (x%i==0) return 0;
	}
	return 1;
}

int calc(int x)					//各位数字平方和
{
	int ret = 0;
	while (x)
	{
		int t = x%10;
		ret += t*t;
		x/=10;
	}
	return ret;
}

int dfs(int x)					//一条路走到底
{
	if (a[x]) return a[x];		//走过了，直接返回信息
	int next = calc(x);
	if (!vis[next])
	{ 
		vis[next] = 1;
		if (dfs(next) == -1) return a[x] = -1;	//走出了环，直接返回-1
		p[next] = 1;
		a[x] = dfs(next)+1;						//每走一步，记录步数
		vis[next] = 0;
	} else a[x] = -1;
	return a[x];
}

int main()
{
	a[1] = 1;
	scanf("%d%d",&A,&B);
	for (int i=A;i<=B;i ++)
		a[i] = dfs(i);
	bool flag = 0;
	for (int i=A;i<=B;i ++)
		if (a[i]>0 && !p[i]) flag = 1,printf("%d %d\n",i,(a[i]-1)*(1+prime(i)));	//这样写挺巧妙的吧
	if (!flag) printf("SAD\n");
}

L2-2 冰岛人

这是一道与树相关的题，没用到什么树的算法，只需要知道树这一概念即可A掉此题。
这道题我承认我的程序是有点问题的，但思路没啥大问题，最后通过特判过了那一个点。可以参考其他人AC的代码。
建树，找LCA，我看到有些人用并查集，其实可以不用。直接把所有的树根，指向虚拟化的根0。
首先读入时的字符串处理，直接砍掉后缀就好，顺便根据特征字符标记男女。
对这道题我用了C++的map，主要是为了方便映射字符串（名字）和对应的编号，对于C选手，可以选用更优雅的字符串hash，省去学习及使用C++ STL的烦恼。
后面发现C++ string转C语言 char *s可以不用string()强制类型转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstring>
#include <map>
#include <cmath>
using namespace std;

const int M = 125,N = 1e5+7;
int n,m,dep[N];
map <string,int> maps;
struct node
{
	char name[M],fname[M];
	int sex;
} h[N];

int gf(int x) {return maps[string(h[x].fname)];}

int LCA(int x,int y)							//垃圾一步步求LCA方法，想用logn方法我不拦你
{
	while (dep[x]>dep[y]) x = gf(x);
	while (dep[x]<dep[y]) y = gf(y);
	while (x!=y) x = gf(x),y = gf(y);
	return x;
}

int query(char s1[],char s2[],char s3[],char s4[])
{
	if (maps[string(s1)]==0 || maps[string(s3)]==0) return -2;
	int L = maps[string(s1)],R = maps[string(s3)];				//找节点编号
	if (h[L].sex==h[R].sex) return -1;							//同性恋
	
	int id = LCA(L,R);
	//if (id==L || id==R) return 0;
	if (dep[R]-dep[L]==4) return 1;								//特判代码，不然有一个点会挂
	if ((dep[L]-dep[id]<4 || dep[R]-dep[id]<4) && id) return 0; else return 1;
	//判断两个人与他们最近公共祖先的关系，相差了几代
}

int dfs(int x)		//生成每个人所处于树的深度
{
	if (x==0) return 1;
	if (dep[x]) return dep[x];
	return dep[x] = dfs(gf(x))+1;
}

int main()
{
	//freopen("L2-2.in","r",stdin);
	cin >> n;
	for (int i=1;i<=n;i ++)
	{
		cin >> h[i].name >> h[i].fname;
		char ch = h[i].fname[strlen(h[i].fname)-1];
		if (ch=='m' || ch=='n') h[i].sex = 1; else h[i].sex = 0;
		if (ch=='m' || ch=='f') h[i].fname[strlen(h[i].fname)-1] ='\0';
		if (ch=='n') h[i].fname[strlen(h[i].fname)-4] = '\0';
		if (ch=='r') h[i].fname[strlen(h[i].fname)-7] = '\0';
		maps[string(h[i].name)] = i;								//映射此人名字及其编号
		//cout << h[i].name << " " << h[i].fname << " " << h[i].sex << endl;
	}
	//字符串处理，标记男女
	for (int i=1;i<=n;i ++)
		dfs(i);
	//为了生成每个人所在树的深度。也就是有多少个祖先
	cin >> m;
	for (int i=1;i<=m;i ++)
	{
		char s1[M],s2[M],s3[M],s4[M];
		cin >> s1 >> s2 >> s3 >> s4;
		int t = query(s1,s2,s3,s4);
		if (t==-2) cout << "NA" << endl;
		if (t==-1) cout << "Whatever" << endl;
		if (t==0) cout << "No" << endl;
		if (t==1) cout << "Yes" << endl; 
	}
	return 0;
}

L2-3 深入虎穴

首先点名表扬我们2队第1，怒A此题，不给1队一点颜面。
这道题确实如出题着所说有坑，你要先找到入度为0的点，从哪一个口进入，然后找深度最深的节点。
当你会了搜索，你可以靠搜索完成70%的方案种类算法题%，然而效率是最差的。
我存树是采用存图的做法，用的模拟链表，照顾C语言选手，实际上一直以来我都是很少用C++ STL的，除非是因为我懒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <stack>
using namespace std;

const int N = 1e5+7;
int rd[N],e[N],a[N];
int ans,maxx,tot,n,m;

struct node
{
	int y,next;
} h[N];

void add(int x,int y)				//给图加边
{
	tot ++;
	h[tot].y = y;
	h[tot].next = e[x];
	e[x] = tot;
}

void dfs(int dep,int x)				//搜索走每一条边
{
	a[x] = dep;
	for (int i = e[x];i;i = h[i].next)
	{
		dfs(dep+1,h[i].y);
	}
}

int main()
{
	//freopen("L2-3.in","r",stdin);

	cin >> n;
	for (int i=1;i<=n;i++)
	{
		cin >> m;
		for (int j=1;j<=m;j ++)
		{
			int t;
			cin >> t;
			add(i,t);
			rd[t] ++;
		}
	}
	for (int i=1;i<=n;i ++)
		if (!rd[i]) dfs(1,i);
	for (int i=1;i<=n;i ++)
	{
		if (a[i]>maxx) 			//找最大值记录编号
		{
			maxx = a[i];
			ans = i;
		}
	}
	cout << ans << endl;
	return 0;	
}

L2-4 彩虹瓶

考场上我看此题AC率挺高，就做了此题，结果发现废话了一堆，就是判断给定的入栈顺序，能否顺利出栈。并限定栈的大小。
考试时挂了挺多的，我也不明白为啥，只不过我是用C++ stack，复盘直接用数组模拟的栈就过了。
嗯！或许C++ STL不够友好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <stack>
using namespace std;

const int N = 1e3+7;
int n,m,k;
int s[N];

int main()
{
	//freopen("L2-4.in","r",stdin);
	cin >> n >> m >> k;
	for (int i=1;i<=k;i ++)
	{
		int now = 0;
		bool flag = 1;
		s[0] = 0;
		for (int i=1;i<=n;i ++)
		{
			if (s[0]>m) flag = 0;
			while (s[0] && s[s[0]]==now+1) now ++,s[0] --;		//弹出栈顶元素，while有可能会出去很多元素
			int t;
			cin >> t;
			if (t==now+1) 										//是否不用存到栈中，直接出去
			{
				now ++;
				continue;
			}
			s[++ s[0]] = t;										//压栈
		}
		while (s[0] && s[s[0]]==now+1) now ++,s[0] --;
		//结束了在执行出栈操作一次
		flag = flag && !s[0];
		if (flag) cout << "YES" << endl; else cout << "NO" << endl;
	} 
	return 0;	
}

L3

等网上的大佬做吧
前面两题还好，后面那道题，幸亏没机会见此题，我高数也才刚学到偏导，这么大的数据量C++都要读入优化了，不知java怎么样。

参考

在知乎上似乎找到了出题者，顺着这位出题者的思路就容易写出代码了
知乎