2017广东工业大学程序设计竞赛初赛 题解&源码(A,水 B,数学 C,二分 D,枚举 E,dp F,思维题 G,字符串处理 H,枚举)
2017广东工业大学程序设计竞赛初赛 题解&源码(A,水 B,数学 C,二分 D,枚举 E,dp F,思维题 G,字符串处理 H,枚举)
Problem A: An easy problem
Description
Peter Manson owned a small house in an obscure street. It was a weather-beaten tenement of wood, containing some six or eight rooms, all of which, with one exception, were given over to dirt, cobwebs, gloom, and desolation. Peter might readily have let the rooms which he did not require for his own use, but so profound was his distrust of human nature, that not even the prospect of receiving rent for the empty rooms could overcome his apprehension of being robbed by neighbors under the same roof. For Peter trusted not his money to banks or railroads, but wanted to have it directly under his own eye or within his reach. As for investing his gold in the luxuries of life, or even in what were generally considered its absolute necessaries, we have already seen that Peter was no such fool as that. A gold eagle was worth ten times more to him than its equivalent in food or clothing.
With more than his usual alacrity, old Peter Manson, bearing under his cloak the fresh loaf which he had just procured from the baker on such advantageous terms, hastened to his not very inviting home.
Drawing from his pocket a large and rusty door-key, he applied it to the door. It turned in the lock with a creaking sound, and the door yielding to Peter's push he entered.
The room which he appropriated to his own use was in the second story. It was a large room, of some eighteen feet square, and, as it is hardly necessary to say, was not set off by expensive furniture. The articles which came under this denomination were briefly these,—a cherry table which was minus one leg, whose place had been supplied by a broom handle fitted in its place; three hard wooden chairs of unknown antiquity; an old wash-stand; a rusty stove which Peter had picked up cheap at an auction, after finding that a stove burned out less fuel than a fireplace; a few articles of crockery of different[18] patterns, some cracked and broken; a few tin dishes, such as Peter found essential in his cooking; and a low truckle bedstead with a scanty supply of bedclothes.
Are you tired of reading this long passage?Now,I’m giving you a task which is nothing to do with the passage.ahhh~Please sort this string “cpteca”,make the first letter be upper-letter.
Input
Output
Sample Input
Sample Output
HINT
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=0
分析：标准签到题，(⊙o⊙)…，直接输出Accept，A不大写的人不知道什么心态
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <iostream>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <set>
10 #include <stack>
11 #include <map>
12 using namespace std;
13 int main()
14 {
15 puts("Accept");
16 return 0;
17 }Problem B: Tmk吃汤饭
Description
前段时间天气寒冷，所以tmk喜欢上了吃汤饭。
众所周知，三饭二楼的汤饭分点餐和取餐两个窗口，一位蜀黍负责点餐窗口，一位蜀黍负责煮汤，一位蜀黍负责打饭，点餐需要1分钟，每一份需要煮5分钟，同一时间最多可以煮4份。
有一天，tmk来到三饭二楼，发现汤饭取餐窗口没人，但点餐窗口却排满了人，原来卖汤饭的蜀黍刚刚开始工作，tmk无聊的数了数排队人数，刚好n个人。
Tmk想知道如果这个时候自己排到队尾，需要多久才能取到汤饭，由于我们广工大学生素质比较高，所以没人插队，当然tmk也不会插队，而且他们意志坚定，所以不会中途而废。
现在，假设除了点餐和煮汤的时间，其他时间忽略不计，tmk想让你算一下他需要等多久才能取到汤饭。
Input
第一行一个T(0<T<=10000)，表示有多少组数据。
接着每行有一个n(0<=n<=10000)，表示tmk到三饭二楼时点餐窗口排队的人数。
Output
对于每个n，输出一个整数表示tmk多久能取到汤饭。
Sample Input
2
0
4
Sample Output
6
11
HINT
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=1
分析：很有规律的一个序列，我没去推公式而是直接打的表…公式应该是 (n/4+1)*5+(n%4+1)
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <iostream>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <set>
10 #include <stack>
11 #include <map>
12 using namespace std;
13 const int maxn = 10050;
14 int a[maxn];
15 int main()
16 {
17 a[0] = 6;
18 for(int i=1;i<maxn;i++)
19 {
20 a[i] = a[i-1]+1;
21 if(i%4==0)
22 a[i]++;
23 }
24 int t;
25 scanf("%d",&t);
26 while(t--)
27 {
28 int n;
29 scanf("%d",&n);
30 printf("%d\n",a[n]);
31 }
32 return 0;
33 }Problem C: 进击的调查兵团
Description
自从Wall.Rose被钢铁巨人再次攻陷之后，人类圈只剩下最后一道防线Wall.Sina。司令官终于按耐不住，决定下达三笠将军直接从105期和106期的训练兵团中召集一批毕业生进入调查兵团进行对巨人的反击战。
105期的毕业生有N个人，106期的有M个人。为了方便三笠将军的挑选，两个训练团的教官都提交了当时毕业生的毕业成绩，成绩按从小到大排行。即105期第i成绩小的毕业生的成绩为A[i]，106期第j成绩小的毕业生的成绩为B[j]，满足A[0]<A[1]<…<A[N-2]<A[N-1]，B[0]<B[1]<…B[M-2]<B[M-1]。而且为了体现历届毕业生成绩的差异，保证了A[i] != B[j]{0<=i<N, 0<=j<m}.
现在三笠将军对这A，B两份成绩单中挑选Q次人员。在每次挑选中，会从A[L1..R1]和B[L2..R2]中选出成绩第k小的毕业生出来。三笠这样的挑选纯粹为了好玩，所以那Q次挑选的人中有可能存在重复。
为了能尽快选出反击战人员，司令官决定派你尽快得出人员名单。
Input
第一行输入一个整数T，表示有T组数据，对于每组数据
第一行包含3个整数，105期毕业生人数N(<=10^5)，106期毕业生人数M(<=10^5)，三笠的挑选次数Q(<=10^4)。
第二行包含N个整数A[i](0<=A[i]<2^31)，
第三行包含M个整数B[i](0<=B[i]<2^31)。
第4..Q+3行中，每行有5个整数，L1，R1，L2，R2，k (0<=L1<=R1<N, 0<=L2<=R2<M, 1<=k<=R1-L1+R2-L2+2)。
Output
对于每次挑选，输出一个整数，表示A[L1..R1]和B[L2..R2]中第k小的成绩。
Sample Input
1
5 5 4
1 3 5 7 8
2 4 6 9 10
0 4 0 4 7
3 4 1 3 2
2 2 1 1 1
0 3 0 3 6
Sample Output
7
6
4
6
HINT
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=2
分析：
二分答案，二分答案出来以后在二分查找在每个序列里有多少个小于等于他的，stl是个好东西
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <iostream>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <set>
10 #include <stack>
11 #include <map>
12 using namespace std;
13 const int maxn = 1e5+100;
14 int a[maxn];
15 int b[maxn];
16 int main()
17 {
18 int t;
19 scanf("%d",&t);
20 while(t--)
21 {
22 int n,m,q;
23 scanf("%d %d %d",&n,&m,&q);
24 for(int i=0;i<n;i++)
25 scanf("%d",&a[i]);
26 for(int i=0;i<m;i++)
27 scanf("%d",&b[i]);
28 while(q--)
29 {
30 int l1,r1,l2,r2,k;
31 scanf("%d %d %d %d %d",&l1,&r1,&l2,&r2,&k);
32 int l = min(a[l1],b[l2]),r = max(a[r1],b[r2]);
33 while(l<r)
34 {
35 int mid = l+((r-l)/2);
36 int pos1 = lower_bound(a+l1,a+r1+1,mid)-a;
37 if(a[pos1]==mid)
38 pos1++;
39 int pos2 = lower_bound(b+l2,b+r2+1,mid)-b;
40 if(b[pos2]==mid)
41 pos2++;
42 if(pos1+pos2<k+l1+l2)
43 l = mid+1;
44 else
45 r = mid;
46 }
47 printf("%d\n",l);
48 }
49 }
50 return 0;
51 }Problem D: TMK的航拍图像
Description
这下糟了，TMK他竟然获得了一次玩无人机的机会，TMK兴奋得像个孩子，拿着无人机摆弄了起来。
于是TMK的无人机上天了，飞得非常高，偏偏今天天气还很好，无人机的航拍非常清晰。TMK把他的无人机开到了最高，从上帝视角拍下了照片，然后结束了他年轻的无人机生涯。
TMK发现这张照片上，所有的建筑物都变成了点，这些点能描述成二维平面上的点，有些点会在同一条直线上，于是TMK想要求出在这张照片上能画出多少条不同的直线，使得这些直线经过至少两个点。TMK把这个问题扔给了Maple，Maple把这个问题扔给了YFQQ。现在，YFQQ把这个问题扔给了你。
Input
第一行有一个整数T，代表有T组数据(1<=T<=50)
每组数据一开始有一个整数n，表示照片上有n个二维坐标点(0<=n<=200)
接下来n行，每行有两个整数x,y，代表点的坐标，保证点不重合(-10000<=x,y<=10000)
Output
每组数据输出一个整数，为不同的直线的数量
Sample Input
1
4
1 1
2 1
3 1
2 2
Sample Output
4
HINT
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=3
分析：
没有重点，那么所有可能的线段是n*(n-1)/2,由于问的是直线，所以枚举两个点，判断是否和其他点相交如果相交就ans––
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <iostream>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <set>
10 #include <stack>
11 #include <map>
12 using namespace std;
13 const int maxn = 2e5+10;
14 struct point
15 {
16 int x,y;
17 }a[maxn];
18 int n,m;
19 int x_mul(point p0,point p1,point p2)
20 {
21 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
22 }
23 int main()
24 {
25 //freopen("a.in","r",stdin);
26 int t;
27 scanf("%d",&t);
28 while(t--)
29 {
30 int n;
31 scanf("%d",&n);
32 for(int i=0;i<n;i++)
33 scanf("%d %d",&a[i].x,&a[i].y);
34 int ans = n*(n-1)/2;
35 for(int i=0;i<n;i++)
36 {
37 for(int j=i+1;j<n;j++)
38 {
39 for(int k=0;k<n;k++)
40 {
41 if(k>=i && k<=j)
42 continue;
43 if(x_mul(a[k],a[i],a[j])==0)
44 ans--;
45 }
46 }
47 }
48 printf("%d\n",ans);
49 }
50 return 0;
51 }Problem E: 绕远路
Description
TMK他果然又迟到了，虽然YFQQ已经习惯了，但是Maple还是毅然决然地跑去实验室要走回宿舍去。
Maple来到了楼下，当即决定要走一条足够长的路回宿舍去。Maple给他可以走的n个点从1到n分别编号，其中实验室在点1，宿舍在点n。这n个点中由m条双向通行的道路相连。
Maple规定，当他到达某个点时，他不会再走到比这个点编号小的点，而当他选择了一条路后，他会径直沿着这条路走直到到达这条路的终点。有一些路会从一个点连向自己，代表Maple可以从这个点出发绕一圈回来，两个点钟可能会有多条不同的路。Maple想要走这些路直到到达宿舍，当他到达宿舍时，他会马上停下来。但是，因为Maple有体力的限制，他走的路的总长度不能超过k，否则他就会累死。
现在给出了这些双向路相连的点和他的长度，求问Maple从实验室走到宿舍在不累死的前提下最长能走多长。
Input
第一行一个整数T，代表有T组数据(1<=T<=20)
每组数据一开始有三个整数n,m,k，代表有n个点，m条路，Maple最多能走的长度为k
接下来有m行，每一行三个整数u,v,l，代表点u到点v有一条双向路，长度为l
(2<=n<=2000,0<=m<=3000,1<=k<=3000)(1<=u,v<=n,1<=l<=6000)
Output
每组数据输出一个整数，为题目所求。
若Maple回不了宿舍或回宿舍之前一定会累死，那么输出-1。
Sample Input
2
5 6 7
1 2 1
3 2 2
5 1 5
3 4 4
4 5 4
1 4 2
3 3 999
1 2 4
2 2 10
3 2 3
Sample Output
6
997
HINT
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=4
分析：
dp题，dp[i][n]表示到点i长度为n是否可行，状态转移方程为：dp[tmp.v][tt] |= dp[i][tt-tmp.w],tmp.v到i之间有条长度为tmp.w的边
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <iostream>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <set>
10 #include <stack>
11 #include <map>
12 using namespace std;
13 const int maxn = 5000+40;
14 struct node
15 {
16 int v,w;
17 node() {}
18 node(int _v,int _w)
19 {
20 v = _v;
21 w = _w;
22 }
23 };
24 vector<node>G1[maxn],G2[maxn];
25 int dp[maxn][maxn];
26 int main()
27 {
28 int t;
29 scanf("%d",&t);
30 while(t--)
31 {
32 memset(dp,0,sizeof(dp));
33 int n,m,k;
34 scanf("%d %d %d",&n,&m,&k);
35 for(int i=1;i<=n;i++)
36 G1[i].clear(),G2[i].clear();
37 while(m--)
38 {
39 int u,v,l;
40 scanf("%d %d %d",&u,&v,&l);
41 if(u!=v)
42 {
43 if(u>v)
44 swap(u,v);
45 G1[u].push_back(node(v,l));
46 }
47 else
48 G2[u].push_back(node(v,l));
49 }
50 dp[1][0] = 1;
51 for(int i=1;i<=n;i++)
52 {
53 for(unsigned j=0;j<G2[i].size();j++)
54 {
55 node tmp = G2[i][j];
56 for(int tt=tmp.w;tt<=k;tt++)
57 dp[i][tt] |= dp[i][tt-tmp.w];
58 }
59 for(unsigned j=0;j<G1[i].size();j++)
60 {
61 node tmp = G1[i][j];
62 for(int tt=tmp.w;tt<=k;tt++)
63 dp[tmp.v][tt] |= dp[i][tt-tmp.w];
64 }
65 }
66 int ans = -1;
67 for(int i=0;i<=k;i++)
68 {
69 if(dp[n][i])
70 ans = i;
71 }
72 printf("%d\n",ans);
73 }
74 return 0;
75 }Problem F: 密码锁
Description
tmk听说小黄车可以包学期，于是兴奋了把小黄车包了，为了赚回本，所以tmk天天骑。
最近小黄车换了新锁，每次开锁都需要把数字旋转到对应的密码位置(每个位置都是0~9的循环，9的下一位是0，可以顺着转也可以逆着转)，比如原始的数字为”1234”，而密码是”5678”，那么每一圈移动的格数之和最少等于4+4+4+4=16次，由于tmk比较聪明，所以tmk每次开锁都让每一圈移动的格数之和最小。
tmk的记忆力也是十分了得，他记住了这段时间骑过的所有小黄车的密码和原始数字，他想知道他总共转了多少格，但是tmk很懒，所以这个艰巨的任务就交到了你的手里。
Input
第一行一个整数T(0<T<=100)，表示有多少组数据。
每组数据第一行一个整数n(0<=n<=100)，表示tmk最近骑了多少次小黄车。
接着n次骑车的数据：
Ai，Bi，Ci，Di，中间有空格隔开，表示密码锁的密码。
ai，bi，ci，di，中间有空格隔开，表示密码锁的原始数字。
其中0<= Ai，Bi，Ci，Di，ai，bi，ci，di <=9，且均为整数
Output
对于每组数据，输出一个数字，表示tmk总共转了多少格。
Sample Input
1
1
3 6 5 3
9 4 9 5
Sample Output
12
HINT
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=5
分析：
每个齿轮转到想要的位置最少步数为：min((Ai-ai+10)%10,(ai-Ai+10)%10)
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <iostream>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <set>
10 #include <stack>
11 #include <map>
12 using namespace std;
13 const int maxn = 10050;
14 int a[maxn];
15 int main()
16 {
17 int t;
18 scanf("%d",&t);
19 while(t--)
20 {
21 int n;
22 scanf("%d",&n);
23 int ans = 0;
24 while(n--)
25 {
26 int a1,b1,c1,d1;
27 int a2,b2,c2,d2;
28 scanf("%d %d %d %d",&a1,&b1,&c1,&d1);
29 scanf("%d %d %d %d",&a2,&b2,&c2,&d2);
30 ans += min((a1-a2+10)%10,(a2-a1+10)%10);
31 ans += min((b1-b2+10)%10,(b2-b1+10)%10);
32 ans += min((c1-c2+10)%10,(c2-c1+10)%10);
33 ans += min((d1-d2+10)%10,(d2-d1+10)%10);
34 }
35 printf("%d\n",ans);
36 }
37 return 0;
38 }Problem G: 知识来源于分解
Description
有东西在乱窜。我往下看，发现了一只小个的白色生物，用后腿站立着，嗅闻着我的躯体。它吸引了我的注意。
你有什么用途？
我分析这个生物。品红色热能光束一闪而过，它曾颤动的地方扬起尘埃。
哺乳动物...夜行习性...无可挑剔的听觉。难以置信的弱小。但它们的繁殖能力如此强大。
“唔，”我喃喃自语。希望能发现更加复杂的物体；那些东西把我给迷住了。
消化并学习：这是我的目的。和我一起旅行的其它来客都很原始：杀死并吃掉，杀死并吃掉。我需要收集所有可用的信息——收获更多有价值的资源。
终于，我们偶然发现了一座被摧毁的城市，仅有一座古朴的塔楼还完好地保留着。这座塔楼似乎受到了保护……或者是有意留下的。我解构了废墟的成分。我的分析指出，这个地区曾经是一个强大的魔法国度；如此强大的破坏力以它为目标，我丝毫不感到意外。有某些东西对这座塔楼感兴趣。在其它来客正在四散搜刮时，我进入了城堡。
神秘的仪器散落各处。我检测了一件。又一道品红色热能光束一闪而过，尘埃再次扬起。
时光机器...启动需要解开谜题...天呐，我需要仔细瞧瞧。
“Given a string s of length n, and integer k, return the length of the longest substring that contains exactly k distinct characters.”
T组数据...string只包含大小写字母...找不到返回0。这道题成功吸引了我。
Input
第一行输入一个整数T，表示有T组数据，
接下来T行，每一行一个字符串s和一个整数k(T<=666, length(s)<=10^6, 0=<k<=52)
Output
对于每一组数据，输出一个答案。
Sample Input
3
abcd 2
aaabbbcc 2
aa 3
Sample Output
2
6
0
HINT
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=6
分析：尺取维护答案
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <iostream>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <set>
10 #include <stack>
11 #include <map>
12 using namespace std;
13 const int maxn = 1e6+10;
14 char a[maxn];
15 int vis[100];
16 int main()
17 {
18 int t;
19 cin>>t;
20 while(t--)
21 {
22 int n,k;
23 scanf("%s %d",a,&k);
24 n = strlen(a);
25 int ans = 0;
26 int l = 0,r = 0,cnt = 0;
27 memset(vis,0,sizeof(vis));
28 while(n-l>ans)
29 {
30 while(r<n)
31 {
32 if(vis[a[r]-'A'])
33 vis[a[r]-'A']++;
34 else
35 {
36 if(cnt+1>k)
37 break;
38 else
39 cnt++;
40 vis[a[r]-'A']++;
41 }
42 r++;
43 }
44 if(cnt == k)
45 ans = max(ans,r-l);
46 vis[a[l]-'A']--;
47 if(vis[a[l]-'A']==0)
48 cnt--;
49 l++;
50 }
51 printf("%d\n",ans);
52 }
53 return 0;
54 }Problem H: 找正方形
Description
在一个字符地图中，能否找到有#围成的正方形的，如果找到则输出YES，没有则NO。（正方形内部无需填满#，面积至少是4，地图大小不超过20*20）
合法情况1:
####
#$$#
#$##
####
合法情况2:
####
##$$
$$$$
$$$$
合法情况3
####
#$$#
#$$#
####
不合法情况
####
#$$#
#$$$
####
Input
第一行一个整数T，表示有多少组数据
对于每组数据：
第一行为两个整数n，m表示地图大小n行和m列(0<n,m<=20)
Output
如果找到，输出”YES”(不包括引号)，否则输出’NO”(不包括引号)
Sample Input
2
4 4
####
#$$#
#$##
####
4 4
####
#$$#
#$$$
####
Sample Output
YES
NO
HINT
题目链接：http://gdutcode.sinaapp.com/problem.php?cid=1053&pid=7
分析：找到一点’#’，枚举正方形长度，判断是否合法
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <iostream>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <set>
10 #include <stack>
11 #include <map>
12 using namespace std;
13 const int maxn = 1e6+10;
14 char a[25][25];
15 bool slove(int x,int y,int n)
16 {
17 for(int i=x;i<=x+n;i++)
18 {
19 if(a[i][y]!='#')
20 return false;
21 if(a[i][y+n]!='#')
22 return false;
23 }
24 for(int i=y;i<=y+n;i++)
25 {
26 if(a[x][i]!='#')
27 return false;
28 if(a[x+n][i]!='#')
29 return false;
30 }
31 return true;
32 }
33 int main()
34 {
35 int t;
36 scanf("%d",&t);
37 while(t--)
38 {
39 int n,m;
40 scanf("%d %d",&n,&m);
41 for(int i=0;i<n;i++)
42 scanf("%s",a[i]);
43 int flag = 0;
44 for(int i=0;i<n;i++)
45 {
46 for(int j=0;j<m;j++)
47 {
48 if(a[i][j]=='#')
49 {
50 for(int k=1;k<=n-1-i;k++)
51 {
52 if(i+k>=n || j+k>=n)
53 break;
54 if(slove(i,j,k))
55 flag = 1;
56 }
57 }
58 }
59 }
60 if(flag)
61 puts("YES");
62 else
63 puts("NO");
64 }
65 return 0;
66 }腾讯云开发者
