试题 A: 数青蛙
“一只青蛙一张嘴，两只眼睛四条腿。两只青蛙两张嘴，四只眼睛八条腿。三只青蛙三张嘴，六只眼睛十二条腿。……二十只青蛙二十张嘴，四十只眼睛八十条腿。”
请问上面这段文字，如果完全不省略，全部写出来，从 1 到 20 只青蛙，总共有多少个汉字。
约定：数字 2 单独出现读成 “两”，在其他数里面读成 “二”，例如 “十二”。10 读作 “十”，11 读作 “十一”，22 读作 “二十二”。请只计算汉字的个数，标点符号不计算。
答案353
上限20只青蛙,腿最多80只,所以只需要考虑1~80的汉字个数即可.
个位数一位;11~19以及10的倍数两位;其余情况三位
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. using namespace std; 8. int n(int x){ 9. if(x<=10) return 1; 10. if(x%10==0) return 2; 11. if(x<20) return 2; 12. return 3; 13. } 14. int main(){ 15. int sum = 0; 16. for(int i = 1 ; i <=20 ; i ++){ 17. int a = i; 18. int b = i + i; 19. int c = i *4; 20. sum += 10; 21. sum += n(a)*2; 22. sum+=n(b) + n(c); 23. } 24. cout<<sum<<endl; 25. return 0; 26. }
试题 B: 互质
今年是 2020 年，今天是 10 月 18 日。
请问在 1 到 2020 中，有多少个数与 1018 互质。
答案:1008
因为是填空题,所以不需要考虑什么算法,直接暴力试就可
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. using namespace std; 8. 9. int gcd2(int a,int b){ 10. return b==0?a:gcd(b,a%b); 11. } 12. int main(){ 13. int sum = 0; 14. for(int i = 1 ; i <= 2020; i ++){ 15. if(gcd2(1018,i) == 1){ 16. sum ++; 17. } 18. } 19. cout<< sum <<endl; 20. return 0; 21. }
试题 C: 车牌
A 市的车牌由六位组成，其中前三位可能为数字 0 至 9，或者字母 A 至 F，每位有 16 种可能。后三位只能是数字 0 至 9。为了减少攀比，车牌中不能有连续三位是相同的字符。
例如，202020 是合法的车牌，AAA202 不是合法的车牌，因为前三个字母相同。
请问，A 市有多少个合法的车牌？
答案:3997440
总共情况为16*16*16*10*10*10
第一位第二位第三位字符一致,可以看做一位,有16种情况,第四位第五位第六位分别有10种情况
第一位16种情况,第二位第三位第四位一致,看做一位,有10种情况,第五位第六位分别有10种情况
第一位16种情况,第二位16种情况,第三第四第五位一致看做一位,有10种情况,第六位10种情况
第一位第二位第三位分别16种情况,第四位第五位第六位一致,看做一位,有10种情况
采用正难则反的思想,总数减去排除情况数,就是答案
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. using namespace std; 8. 9. int main(){ 10. int sum = 16*16*16*10*10*10; 11. sum -= 16*10*10*10; 12. sum -= 16*10*10*10; 13. sum -= 16*16*10*10; 14. sum -= 16*16*16*10; 15. cout<<sum<<endl; 16. return 0; 17. }
试题 D: Fibonacci 集合
小蓝定义了一个 Fibonacci 集合 F，集合的元素如下定义：
1. 最小的 5 个 Fibonacci 数 1, 2, 3, 5, 8 属于集合 F。
2. 如果一个元素 x 属于 F，则 3x + 2、5x + 3 和 8x + 5 都属于集合 F。
3. 其他元素都不属于 F。
请问，这个集合中的第 2020 小元素的值是多少？
答案 41269
标准深搜题,数字要求也不大,暴力即可
从最小的五个数开始搜索,把搜索到的数字置一,然后再找地2020个置一的数字即可
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. using namespace std; 8. int fx[100010]; 9. bool is[100010]; 10. void dfs(int n){ 11. if(n > 100000) return ; 12. is[n] = true; 13. dfs(n*3+2); 14. dfs(n*5+3); 15. dfs(n*8+5); 16. } 17. int main(){ 18. dfs(1); 19. dfs(2); 20. dfs(3); 21. dfs(5); 22. dfs(8); 23. int sum = 0; 24. for(int i = 1;i<=100010;i++){ 25. if(is[i]){ 26. sum ++; 27. cout<< sum << " ge = " << i<<endl; 28. if(sum == 2020){ 29. break; 30. } 31. } 32. } 33. return 0; 34. }
试题 E: 上升子串
小蓝有一个字母矩阵，他喜欢和小伙伴们在这个矩阵上玩一些游戏。今天，他打算玩找上升子串的游戏。游戏是合作性质的。小蓝和小伙伴们首先要在矩阵中指定一个位置，然后从这个位置开始，向上下左右相邻位置移动，移动必须满足所到达位置上的字母比当前位置大。小蓝和小伙伴们可以移动任意多次，也可以随时停下来，这样就找到了一个上升子串。只要子串在矩阵中的位置不同，就认为是不同的子串。
小蓝想知道，一共可以找到多少个上升子串。小蓝的矩阵很大，已经放在了试题目录下面，叫 inc.txt。为了更清楚的
描述问题，他还找了一个很小的矩阵用来解释。
例如，对于矩阵：
1. AB 2. BC
可以找到 4 个长度为 1 的上升子串、4 个长度为 2 的上升子串、2 个长度
为 3 的上升子串，共 10 个。
现在，请你对于小蓝的大矩阵，找到上升子串的数量。
答案未知
这题暴力过不去,比赛的时候跑了两个多小时,还在跑......
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. #include<queue> 8. using namespace std; 9. char a[102][102]; 10. int sum; 11. struct mu{ 12. int x; 13. int y; 14. char maxChar; 15. mu(int xx,int yy,char z){ 16. x = xx; 17. y = yy; 18. maxChar = z; 19. } 20. }; 21. bool check(int x){ 22. if(x<0 || x >= 100) return false; 23. return true; 24. } 25. void bfs(int x,int y){ 26. queue<mu> q; 27. q.push(mu(x,y,a[x][y])); 28. while(!q.empty()){ 29. mu mm = q.front(); 30. sum ++; 31. cout<<sum<<endl; 32. q.pop(); 33. if(check(mm.x - 1) && mm.maxChar < a[mm.x - 1][mm.y]){ 34. mu m2 = mu(mm.x - 1,mm.y,a[mm.x - 1][mm.y]); 35. q.push(m2); 36. } 37. if(check(mm.x + 1) && mm.maxChar < a[mm.x + 1][mm.y]){ 38. mu m3 = mu(mm.x + 1,mm.y,a[mm.x + 1][mm.y]); 39. q.push(m3); 40. } 41. if(check(mm.y + 1) && mm.maxChar < a[mm.x][mm.y + 1]){ 42. mu m4 = mu(mm.x,mm.y + 1,a[mm.x][mm.y + 1]); 43. q.push(m4); 44. } 45. if(check(mm.y - 1) && mm.maxChar < a[mm.x][mm.y - 1]){ 46. mu m5 = mu(mm.x,mm.y - 1,a[mm.x][mm.y - 1]); 47. q.push(m5); 48. } 49. } 50. } 51. int main(){ 52. sum = 0; 53. for(int i = 0 ; i < 100;i++){ 54. cin>>a[i]; 55. } 56. for(int i = 0 ; i < 100;i++){ 57. for(int j = 0 ; j < 100 ; j ++){ 58. bfs(i,j); 59. } 60. } 61. cout<<sum<<endl; 62. return 0; 63. }
试题 F: 日期识别
小蓝要处理非常多的数据，其中有一些数据是日期。在小蓝处理的日期中有两种常用的形式：英文形式和数字形式。英文形式采用每个月的英文的前三个字母作为月份标识，后面跟两位数字表示日期，月份标识第一个字母大写，后两个字母小写，日期小于 10 时要补前导 0。1 月到 12 月英文的前三个字母分别是 Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec。数字形式直接用两个整数表达，中间用一个空格分隔，两个整数都不写前导 0。其中月份用 1 至 12 分别表示 1 月到 12 月。
输入一个日期的英文形式，请输出它的数字形式。
1. 【样例输入】 2. Feb08 3. 【样例输出】 4. 2 8 5. 【样例输入】 6. Oct18 7. 【样例输出】 8. 10 18
话不多说,暴力
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. using namespace std; 8. void run(string s){ 9. if(s[0] == 'J' && s[1] == 'a' && s[2] == 'n'){ 10. printf("1 "); 11. } 12. else if(s[0] == 'F' && s[1] == 'e' && s[2] == 'b'){ 13. printf("2 "); 14. } 15. else if(s[0] == 'M' && s[1] == 'a' && s[2] == 'r'){ 16. printf("3 "); 17. } 18. else if(s[0] == 'A' && s[1] == 'p' && s[2] == 'r'){ 19. printf("4 "); 20. } 21. else if(s[0] == 'M' && s[1] == 'a' && s[2] == 'y'){ 22. printf("5 "); 23. } 24. else if(s[0] == 'J' && s[1] == 'u' && s[2] == 'n'){ 25. printf("6 "); 26. } 27. else if(s[0] == 'J' && s[1] == 'u' && s[2] == 'l'){ 28. printf("7 "); 29. } 30. else if(s[0] == 'A' && s[1] == 'u' && s[2] == 'g'){ 31. printf("8 "); 32. } 33. else if(s[0] == 'S' && s[1] == 'e' && s[2] == 'p'){ 34. printf("9 "); 35. } 36. else if(s[0] == 'O' && s[1] == 'c' && s[2] == 't'){ 37. printf("10 "); 38. } 39. else if(s[0] == 'N' && s[1] == 'o' && s[2] == 'v'){ 40. printf("11 "); 41. } 42. else if(s[0] == 'D' && s[1] == 'e' && s[2] == 'c'){ 43. printf("12 "); 44. } 45. if(s[3] != '0'){ 46. cout<<s[3]; 47. } 48. cout<<s[4]<<endl; 49. } 50. int main(){ 51. string str; 52. while(cin>>str){ 53. run(str); 54. } 55. return 0; 56. }
试题 G: 乘法表
九九乘法表是学习乘法时必须要掌握的。在不同进制数下，需要不同的乘
法表。
例如，四进制下的乘法表如下所示：
1. 1*1=1 2. 2*1=2 2*2=10 3. 3*1=3 3*2=12 3*3=21
请注意，乘法表中两个数相乘的顺序必须为样例中所示的顺序，不能随意
交换两个乘数。
给定 P，请输出 P 进制下的乘法表。
1. 【输入格式】 2. 输入一个整数 P。 3. 【输出格式】 4. 输出 P 进制下的乘法表。P 进制中大于等于 10 的数字用大写字母 A、B、 C、· · · 表示。 5. 【样例输入】 6. 4 7. 【样例输出】 8. 1*1=1 9. 2*1=2 2*2=10 10. 3*1=3 3*2=12 3*3=21 11. 12. 【样例输入】 13. 8 14. 【样例输出】 15. 1*1=1 16. 2*1=2 2*2=4 17. 3*1=3 3*2=6 3*3=11 18. 4*1=4 4*2=10 4*3=14 4*4=20 19. 5*1=5 5*2=12 5*3=17 5*4=24 5*5=31 20. 6*1=6 6*2=14 6*3=22 6*4=30 6*5=36 6*6=44 21. 7*1=7 7*2=16 7*3=25 7*4=34 7*5=43 7*6=52 7*7=61
【评测用例规模与约定】
对于所有评测数据，2 ≤ P ≤ 36。
使用栈进行进制转换即可,注意10以上进制的需要输出字符A-F
1. #include<iostream> 2. #include<string> 3. #include<cstring> 4. #include<algorithm> 5. #include<cmath> 6. #include<cstdio> 7. #include<stack> 8. using namespace std; 9. void printNum(int num,int p){ 10. stack<int> s; 11. while(num>0){ 12. s.push(num%p); 13. num/=p; 14. } 15. while(!s.empty()){ 16. if(s.top() > 9){ 17. printf("%c",'A'+ s.top() - 10); 18. } 19. else{ 20. cout<<s.top(); 21. } 22. s.pop(); 23. } 24. } 25. void run(int p){ 26. for(int i = 1 ; i < p ; i ++){ 27. for(int j = 1;j <= i;j ++){ 28. int sum = i * j; 29. if(j!=1){ 30. printf(" "); 31. } 32. if(i > 9){ 33. printf("%c",'A'+i-10); 34. }else{ 35. printf("%d", i); 36. } 37. printf("*"); 38. if(j > 9){ 39. printf("%c",'A'+j-10); 40. }else{ 41. printf("%d", j); 42. } 43. printf("="); 44. printNum(sum,p); 45. } 46. printf("\n"); 47. } 48. } 49. int main(){ 50. int p; 51. while(cin>>p){ 52. run(p); 53. } 54. return 0; 55. }
