Loading... > 做了一下师兄弄的XBMU_Lab_Test感觉对我这种小白还是很好的,正好今天有空,就来做了一下,顺便记录下解题过程。 ### Problem A([HDU1021](https://acm.hdu.edu.cn/showproblem.php?pid=1021)) **Problem Description** There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2). **Input** Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000). **Output** Print the word "yes" if 3 divide evenly into F(n). Print the word "no" if not. **Sample Input** ``` 0 1 2 3 4 5 ``` **Sample Output** ``` no no yes no no no ``` 这题用暴力是不行的,因为斐波那契数列的增长速度是惊人的,到第50个左右结果已经超过32位了(2^32),用long long int 也只有64位,所以暴力是解决不了的,这时候就应该取巧。 看到只用输出yes和no,可以猜到应该有一些规律在里面  写个计算斐波那契,打表出来看看,可以看到yes的出现是有规律的,遂直接写代码就A了: ```cpp #include <stdio.h> long int in; long long int axx[2]; int main() { while(scanf("%lld",&in) != EOF){ if(in%4==2)printf("yes\n"); else printf("no\n"); } return 0; } ``` ### Problem B ([HDU2032](https://acm.hdu.edu.cn/showproblem.php?pid=2032)) **Problem Description** 还记得中学时候学过的杨辉三角吗?具体的定义这里不再描述,你可以参考以下的图形: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 **Input** 输入数据包含多个测试实例,每个测试实例的输入只包含一个正整数n(1<=n<=30),表示将要输出的杨辉三角的层数。 **Output** 对应于每一个输入,请输出相应层数的杨辉三角,每一层的整数之间用一个空格隔开,每一个杨辉三角后面加一个空行。 **Sample Input** ``` 2 3 ``` **Sample Output** ``` 1 1 1 1 1 1 1 2 1 ``` 这题不难,直接算出杨辉三角就可以了,不过对输出的格式有一点要求,需要注意下输出 ```cpp #include<stdio.h> long long int yang[30][30]={0}; int main() { yang[0][0]=1; for(int i=1;i<30;i++){ for(int j=0;j<30;j++){ if(j==0) yang[i][j] = yang[i-1][j]; else yang[i][j]=yang[i-1][j-1]+yang[i-1][j]; } } int n=0; while(scanf("%d",&n) != EOF) { for(int i=0;i<n;i++){ for(int j=0;j<30;j++){ if(yang[i][j]==0)break; if(j==0)printf("%lld",yang[i][j]); else printf(" %lld",yang[i][j]); } printf("\n"); } printf("\n"); } return 0; } ``` ### Problem C ([HDU1716](https://acm.hdu.edu.cn/showproblem.php?pid=1716)) **Problem Description** Ray又对数字的列产生了兴趣: 现有四张卡片,用这四张卡片能排列出很多不同的4位数,要求按从小到大的顺序输出这些4位数。 **Input** 每组数据占一行,代表四张卡片上的数字(0<=数字<=9),如果四张卡片都是0,则输入结束。 **Output** 对每组卡片按从小到大的顺序输出所有能由这四张卡片组成的4位数,千位数字相同的在同一行,同一行中每个四位数间用空格分隔。 每组输出数据间空一行,最后一组数据后面没有空行。 **Sample Input** ``` 1 2 3 4 1 1 2 3 0 1 2 3 0 0 0 0 ``` **Sample Output** ``` 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 1123 1132 1213 1231 1312 1321 2113 2131 2311 3112 3121 3211 1023 1032 1203 1230 1302 1320 2013 2031 2103 2130 2301 2310 3012 3021 3102 3120 3201 3210 ``` 这个说白了就是全排列加判断,当然这个可以自己写个全排列出来,不过时间有限,使用std的next_permutation(arr, arr+size)函数会更快实现。 > ◆包含:#include`<algorithm>` > ◆描述:直接对数组操作,默认数值大小全排列(按字典序) > ◆函数: > ①求下一个(较大)的排列: > 函数模板:next_permutation(arr, arr+size); > 返回值为bool类型,当当前序列不存在下一个排列时,函数返回false,否则返回true,排列好的数在数组中存储 > ②求上一个(较小)的排列: > 函数模板:prev_permutation(arr, arr+size); > 返回值为bool类型,当当前序列不存在上一个排列时,函数返回false,否则返回true,排列好的数在数组中存储 这题值得注意的是输出格式,需要先判断下面是否结束,再输出空行,不然会卡格式错误。 ```cpp #include<stdio.h> #include<bits/stdc++.h> using namespace std; int main() { int a[4]={0,0,0,0},ac=0; while(1) { scanf("%d %d %d %d",&a[0],&a[1],&a[2],&a[3]); if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0)break; else if(ac==1)printf("\n"); sort(a,a+4); int noww = a[0]; while(1) { if(a[0]==0){ next_permutation(a,a+4); noww = a[0]; continue; } if(a[0]!=noww){ printf("\n"); noww=a[0]; } for(int i=0;i<4;i++) printf("%d",a[i]); //printf(" "); if(next_permutation(a,a+4)==0)break; else if(a[0]==noww)printf(" "); } ac=1; printf("\n"); } return 0; } ``` ### Problem D ([HDU1039](https://acm.hdu.edu.cn/showproblem.php?pid=1039)) **Problem Description** Password security is a tricky thing. Users prefer simple passwords that are easy to remember (like buddy), but such passwords are often insecure. Some sites use random computer-generated passwords (like xvtpzyo), but users have a hard time remembering them and sometimes leave them written on notes stuck to their computer. One potential solution is to generate "pronounceable" passwords that are relatively secure but still easy to remember. FnordCom is developing such a password generator. You work in the quality control department, and it's your job to test the generator and make sure that the passwords are acceptable. To be acceptable, a password must satisfy these three rules: It must contain at least one vowel. It cannot contain three consecutive vowels or three consecutive consonants. It cannot contain two consecutive occurrences of the same letter, except for 'ee' or 'oo'. (For the purposes of this problem, the vowels are 'a', 'e', 'i', 'o', and 'u'; all other letters are consonants.) Note that these rules are not perfect; there are many common/pronounceable words that are not acceptable. **Input** The input consists of one or more potential passwords, one per line, followed by a line containing only the word 'end' that signals the end of the file. Each password is at least one and at most twenty letters long and consists only of lowercase letters. **Output** For each password, output whether or not it is acceptable, using the precise format shown in the example. **Sample Input** ``` a tv ptoui bontres zoggax wiinq eep houctuh end ``` **Sample Output** ``` <a> is acceptable. <tv> is not acceptable. <ptoui> is not acceptable. <bontres> is not acceptable. <zoggax> is not acceptable. <wiinq> is not acceptable. <eep> is acceptable. <houctuh> is acceptable. ``` 这题主要还是要理清题意和判断顺序, 1.首先应该先判断字符串是否有元音字母 2.再判断是否有连续字母,并且去掉特例 3.判断3个连续元音,和连续辅音 这题没什么坑,输出也没太多要求,end结束即可。 ```cpp #include<stdio.h> #include<bits/stdc++.h> using namespace std; bool check_yuan(char c){ if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')return 1; else return 0; } bool check_lian(char a,char b,char c){ if(check_yuan(a)&&check_yuan(b)&&check_yuan(c))return 1; if(check_yuan(a)==0&&check_yuan(b)==0&&check_yuan(c)==0) return 1; return 0; } int main() { string in; while(1){ int resu = 1; cin>>in; if(in=="end")break; //检查是否含有元音 for(int i=0;i<in.size();i++){ if(check_yuan(in[i]))break; if(i==in.size()-1)resu=0; } //检查连续字母 if(resu) { for(int i=0;i<in.size()-1;i++){ if(in[i]==in[i+1]){ if(in[i]=='e'||in[i]=='o') continue; else { resu=0; //printf("%c %c\n",in[i],in[i+1]); break; } } } } //检查连续元音辅音 if(resu) { int len = in.size()-2; for(int i=0;i<len;i++){ if(check_lian(in[i],in[i+1],in[i+2]))resu =0; } } if(resu==1) cout<<'<'<<in<<'>'<<" is acceptable.\n"; else cout<<'<'<<in<<'>'<<" is not acceptable.\n"; } return 0; } ``` ### Problem E ([HDU1026](https://acm.hdu.edu.cn/showproblem.php?pid=1026)) **Problem Description** The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess. Now he gets into feng5166's castle. The castle is a large labyrinth. To make the problem simply, we assume the labyrinth is a N*M two-dimensional array which left-top corner is (0,0) and right-bottom corner is (N-1,M-1). Ignatius enters at (0,0), and the door to feng5166's room is at (N-1,M-1), that is our target. There are some monsters in the castle, if Ignatius meet them, he has to kill them. Here is some rules: 1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1). 2.The array is marked with some characters and numbers. We define them like this: . : The place where Ignatius can walk on. X : The place is a trap, Ignatius should not walk on it. n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster. Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position. **Input** The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole labyrinth. The input is terminated by the end of file. More details in the Sample Input. **Output** For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds), and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output. **Sample Input** ``` 5 6 .XX.1. ..X.2. 2...X. ...XX. XXXXX. 5 6 .XX.1. ..X.2. 2...X. ...XX. XXXXX1 5 6 .XX... ..XX1. 2...X. ...XX. XXXXX. ``` **Sample Output** ``` It takes 13 seconds to reach the target position, let me show you the way. 1s:(0,0)->(1,0) 2s:(1,0)->(1,1) 3s:(1,1)->(2,1) 4s:(2,1)->(2,2) 5s:(2,2)->(2,3) 6s:(2,3)->(1,3) 7s:(1,3)->(1,4) 8s:FIGHT AT (1,4) 9s:FIGHT AT (1,4) 10s:(1,4)->(1,5) 11s:(1,5)->(2,5) 12s:(2,5)->(3,5) 13s:(3,5)->(4,5) FINISH It takes 14 seconds to reach the target position, let me show you the way. 1s:(0,0)->(1,0) 2s:(1,0)->(1,1) 3s:(1,1)->(2,1) 4s:(2,1)->(2,2) 5s:(2,2)->(2,3) 6s:(2,3)->(1,3) 7s:(1,3)->(1,4) 8s:FIGHT AT (1,4) 9s:FIGHT AT (1,4) 10s:(1,4)->(1,5) 11s:(1,5)->(2,5) 12s:(2,5)->(3,5) 13s:(3,5)->(4,5) 14s:FIGHT AT (4,5) FINISH God please help our poor hero. FINISH ``` 这题相比普通迷宫题多了个打boos的设定,但貌似和普通迷宫题没啥,bfs加上优先队列来找最短耗时路径,然后再输出,时间问题就不做了,自己太菜了,写这种要写很久,有空再写了。 最后修改:2021 年 09 月 18 日 07 : 23 PM © 允许规范转载 赞赏 如果觉得我的文章对你有用,请随意赞赏 赞赏作者 支付宝微信