19天梯杯旅游记

前言

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

顺便说句题外话,现在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++ stringC语言 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怎么样。

参考

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