为帮助高校学子进一步加深对蓝桥杯省赛试题的了解,协助各学校发掘校内软件人才,选拔优秀的竞赛选手,提升学校的竞赛质量,大赛组委会特举办第十四届蓝桥杯大赛个人赛(软件类)校内模拟赛。
统领:
这个模拟赛总体上还是比较简单的,难度大概没有2022蓝桥杯的一半吧,做它的初衷是因为我没参加过蓝桥杯,模拟赛也几乎没有参加。所以抽个时间想试试流程结果就是整整四个小时只能刚好把前八个题做对。后面两道题,想到了随机数骗分,但均以失败告终。可想而知正式比赛的话,应该不会太乐观。
但至少应该再挣扎一下。
目录:
- 1.进制位数:
- 2.跑步:
- 3.项数
- 4.山谷
- 5.矩阵拆分
- 6.核酸天数
- 7.元音大写
- 8.充电能量
- 9.全相等三角形
- 10.最小表示
- 总结:
1.进制位数:
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
问题描述:
十进制整数 2在十进制中是 1 位数,在二进制中对应 10 ,是 2位数。
十进制整数 22在十进制中是 2位数,在二进制中对应 10110,是 5 位数。
请问十进制整数 2022在二进制中是几位数?
解题:
答案 :11
本题算是签到题,但我却楞了好一会,不知如何写代码。还是对二进制掌握不到位。
最后是想到2^10 = 1024
才反应过来答案。
其实仔细想想,10进制逢10进1,二进制讲就是逢 2进1,怎么判断10进制位数,就怎么判断2进制位数一样的模式。
代码如下:
import java.util.*;public class Main { public static int solve(int n){ int cnt = 0; while(n > 0){ n /= 2; cnt ++ ; } return cnt; } public static void main(String[] args) { System.out.println(solve(2022)); }}
2.跑步:
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
问题描述:
小蓝每周六、周日都晨跑,每月的 1、 11、 21、 31日也晨跑。其它时间不晨跑。
已知 2022 年 1月 1日是周六,请问小蓝整个 2022 年晨跑多少天?
解题:
答案 :138
这道题怎么说呢,我忘记平年,闰年的判别方法了,更惨的是1,3,5,7,8,10,腊,31天永不差。其中腊月我忘记是哪个月了我对蓝桥杯常考类型还是不够熟悉。这道题我放在倒数第二个写的,蒙的365天,腊月是12月。结果还是做对了,我想这大概就是运气吧,希望正真赛场上也是如此。
这里补上自己欠下来的知识点:
1.闰年:366天
2.能被4整除且不能被100整除(如2004年是闰年,而1900年不是)
3.能被400整除(如2000年是闰年)
4.闰年2月有29天
5.腊月:12月
代码:
import java.util.*;public class Main{ public static void main(String[] args){ int a[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int data = 5; int day = 0; int b[] = new int[4]; int sum = 0; b[0] = 1; b[1] = 11; b[2] = 21; b[3] = 31; for(int i = 1; i <= 12; i ++) { for(int j = 1; j <= a[i]; j ++) { day = (j + data) % 7; if(day == 6 || day == 0) sum ++; else for(int k = 0; k < 4; k ++) if(b[k] == j) sum ++; } data = (data + a[i]) % 7; } System.out.println(sum);}}
3.项数
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
问题描述:
解题:
答案:91380
从前三题就可以看出,这个模拟并不是很难,哎但是在这里我又又又卡住了太久没用double
了默认int sum = 0半天得不出来变量,问题出在电脑计算1 / 2 = 0,所以得用1.0 / 2 才能得到我们想要的 0.5。。自己真是太SB
了。
代码:
import java.util.*;public class Main{ public static void main(String[] args){ double sum = 1; int i = 1; while(sum <= 12) { i ++; sum = sum + 1.0 / i; } System.out.print(i);}}
4.山谷
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
问题描述:
给定一个字母矩阵,如果矩阵中的某个位置不在四条边上,而且该位置上的字母小于其上下左右四个位置的字母,则称为一个山谷。
例如,对于如下矩阵
DDDDD
CADCE
FFFFA
共有两个山谷,位于第二行第二列和第四列。请注意第二行第三列和第三行第五列都不是山谷。
对于如下 30 行 60 列的字母矩阵,请问有多少个山谷?
PHQGHUMEAYLNLFDXFIRCVSCXGGBWKFNQDUXWFNFOZVSRTKJPREPGGXRPNRVYSTMWCYSYYCQPEVIKEFFMZNIMKKASVWSRENZKYCXFXTLSGYPSFADPOOEFXZBCOEJUVPVABOYGPOEYLFPBNPLJVRVIPYAMYEHWQNQRQPMXUJJLOOVAOWUXWHMSNCBXCOKSFZKVATXDKNLYJYHFIXJSWNKKUFNUXXZRZBMNMGQOOKETLYHNKOAUGZQRCDDIUTEIOJWAYYZPVSCMPSAJLFVGUBFAAOVLZYLNTRKDCPWSRTESJWHDIZCOBZCNFWLQIJTVDWVXHRCBLDVGYLWGBUSBMBORXTLHCSMPXOHGMGNKEUFDXOTOGBGXPEYANFETCUKEPZSHKLJUGGGEKJDQZJENPEVQGXIEPJSRDZJAZUJLLCHHBFQMKIMWZOBIWYBXDUUNFSKSRSRTEKMQDCYZJEEUHMSRQCOZIJIPFIONEEDDPSZRNAVYMMTATBDZQSOEMUVNPPPSUACBAZUXMHECTHLEGRPUNKDMBPPWEQTGJOPARMOWZDQYOXYTJBBHAWDYDCPRJBXPHOOHPKWQYUHRQZHNBNFUVQNQQLRZJPXIOGVLIEXDZUZOSRKRUSVOJBRZMWZPOWKJILEFRAAMDIGPNPUUHGXPQNJWJMWAXXMNSNHHLQQRZUDLTFZOTCJTNZXUGLSDSMZCNOCKVFAJFRMXOTHOWKBJZWUCWLJFRIMPMYHCHZRIWKBARXBGFCBCEYHJUGIXWTBVTREHBBCPXIFBXVFBCGKCFQCKCOTZGKUBMJRMBSZTSSHFROEFWSJRXJHGUZYUPZWWEIQURPIXIQFLDUUVEOOWQCUDHNEFNJHAIMUCZFSKUIDUBURISWTBRECUYKABFCVKDZEZTOIDUKUHJZEFCZZZBFKQDPQZIKFOBUCDHTHXDJGKJELRLPAXAMCEROSWITDPTPCCLIFKELJYTIHRCQAYBNEFXNXVGZEDYYHNGYCDRUDMPHMECKOTRWOSPOFGHFOZQVLQFXWWKMFXDYYGMDCASZSGOVSODKJGHCWMBMXRMHUYFYQGAJQKCKLZNAYXQKQOYZWMYUBZAZCPKHKTKYDZIVCUYPURFMBISGEKYRGZVXDHPOAMVAFYRARXSVKHTQDIHERSIGBHZJZUJXMMYSPNARAEWKEGJCCVHHRJVBJTSQDJOOTGPKNFPFYCGFIEOWQRWWWPZSQMETOGEPSPXNVJIUPALYYNMKMNUVKLHSECDWRACGFMZKGIPDFODKJMJQWIQPUOQHIMVFVUZWYVIJGFULLKJDUHSJAFBTLKMFQRMYJFJNHHSSQCTYDTEAMDCJBPRHTNEGYIWXGCJWLGRSMEAEARWTVJSJBAOIOJLWHYPNVRUIHOSWKIFYGTYDHACWYHSGEWZMTGONZLTJHGAUHNIHREQGJFWKJSMTPJHAEFQZAAULDRCHJCCDYRFVVRIVUYEEGFIVDRCYGURQDREDAKUBNFGUPROQYLOBCWQXKZMAUSJGMHCMHGDNMPHNQKAMHURKTRFFACLVGRZKKLDACLLTEOJOMONXRQYJZGINRNNZWACXXAEDRWUDXZRFUSEWJTBOXVYNFHKSTCENAUMNDDXFDMVZCAUTDCCKXAAYDZSXTTOBBGQNGVVPJGOJOGLMKXGBFCPYPCKQCHBDDZWRXBZMQRLXVOBTWHXGINFGFRCCLMZNMJUGWWBSQFCIHUBSJOLLMSQSGHMCPHELSOTFLBGSFNPCUZSRUPCHYNVZHCPQUGRIWNIQXDFJPWPXFBLKPNPEELFJMT
解题:
答案:276
这道题就比较中规中矩了,也不是很难。数据量也不大,思路就是我们找矩阵内部得点(边界不算),看看是不是上下左右都比这个点大,是的话就计数,否者就不计数。
代码:
import java.util.*;public class Main{ public static char a[][]; public static void main(String[] args){ a = new char[30][60]; b = new char[4]; Scanner sc = new Scanner(System.in); for(int i = 0; i < 30; i ++) { a[i] = sc.nextLine().toCharArray(); } for(int i = 0; i < 30; i ++) for(int j = 0; j < 60; j ++) dfs(i, j); System.out.print(sum); } public static char b[]; public static int sum = 0; public static void dfs(int i, int j) { int fx[] = {-1, 1, 0, 0}; int fy[] = {0, 0, -1, 1}; int fxx = 0, fyy = 0; if(i > 0 && i < 29 && j > 0 && j < 59) { for(int k = 0; k < 4; k ++) { fxx = i + fx[k]; fyy = j + fy[k]; b[k] = a[fxx][fyy]; } if(check(i, j)) sum ++; } } public static boolean check(int i, int j) { for(int k = 0; k < 4; k ++) { if(b[k] <= a[i][j]) return false; } return true; }}
5.矩阵拆分
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
问题描述:
小蓝有一个 100 行 100 列的矩阵,矩阵的左上角为 1 。其它每个位置正好比其左边的数大 2,比其上边的数大 1 。
例如,第 1 行第 2 列为 3,第 2 行第 2 列 为 4,第 10 行第 20列为 48。
小蓝想在矩阵中找到一个由连续的若干行、连续的若干列组成的子矩阵,使得其和为 2022,请问这个子矩阵中至少包含多少个元素(即子矩阵的行数和列数的乘积)。
解题思路:
答案:12
这道题对我来说就有难度了,但是我有思路,代码比较多,所以我放在最后一道题去做,运气比较好,写对了。
思路:
每一个点都看一下,看从这个点开始遍历矩阵看是否等于2022,如果等于的话再记录一下面积就欧克了。最后输出最小的那个面积就行了。判别矩阵的方法,和我写过的这个题完全一样:最大子矩阵。
代码:
import java.util.*;public class Main{ public static int a[][]; public static void main(String[] args){ a = new int[100][100]; for(int i = 0; i < 100; i ++) { for(int j = 0; j < 100; j ++) { if(i == 0 && j == 0) { a[i][j] = 1; continue; } if(j == 0) { a[i][j] = a[i - 1][j] + 1; continue; } a[i][j] = a[i][j - 1] + 2; } } for(int i = 50; i < 100; i ++) for(int j = 50; j < 100; j ++) { minone = Integer.MAX_VALUE; int bf = a[i][j]; dfs(i, j, a[i][j]); a[i][j] = bf; lastmin = Math.min(lastmin, minone); mini = Integer.MAX_VALUE; minj = Integer.MAX_VALUE; maxi = Integer.MIN_VALUE; maxj = Integer.MIN_VALUE; } System.out.println(lastmin);} public static int minone = Integer.MAX_VALUE; public static int lastmin = Integer.MAX_VALUE; public static int mini = Integer.MAX_VALUE; public static int minj = Integer.MAX_VALUE; public static int maxi = Integer.MIN_VALUE; public static int maxj = Integer.MIN_VALUE; public static void updata(int x, int y) { mini = Math.min(x, mini); minj = Math.min(y, minj); maxi = Math.max(x, maxi); maxj = Math.max(y, maxj); } public static void dfs(int i, int j, int sum) { a[i][j] = 200; updata(i, j); if(sum == 2022 && check()) { minone = Math.min(minone, (maxj - minj + 1) * (maxi - mini + 1)); return; } if(sum > 2022) return; int fx[] = {-1, 1, 0, 0}; int fy[] = {0, 0, -1, 1}; int fxx = 0, fyy = 0; for(int k = 0; k < 4; k ++) {fxx = i + fx[k];fyy = j + fy[k];int bmi = mini;int bmj = minj;int bxi = maxi;int bxj = maxj;if(check()) {if(fxx >= 50 && fxx <= 99 && fyy >= 50 && fyy <= 99 && a[fxx][fyy] != 200) { int bf = a[fxx][fyy];dfs(fxx, fyy, sum + bf);a[fxx][fyy] = bf; }}else {if(fxx >= mini && fxx <= maxi && fyy >= minj && fyy <= maxj && a[fxx][fyy] != 200) {int bfr = a[fxx][fyy];dfs(fxx, fyy , sum + bfr);a[fxx][fyy] = bfr;}}mini = bmi;minj = bmj;maxi = bxi;maxj = bxj; } } public static boolean check() { for(int i = mini; i <= maxi; i ++) for(int j = minj; j <= maxj ; j ++) if(a[i][j] != 200) return false; return true; }}
在遍历的时候我没有从1 ~ 100 开始遍历,说实话我有赌的成分,一是因为矩阵靠后的数比较大,所以最小值应该是在最后面,二是因为从1开始的话,子矩阵面积估计会很大如果子矩阵面积为30,运行量大概是T = 10000*4^20 * 20 / 10^9 = …s 太大了。
如果从50开始遍历的话假设子矩阵面积为13左右:t = 50 * 50 * 4^8 * 10 / 10^9 = 1.6 s
离谱的是题目给的题解,是枚举法,代码量比我少时间复杂度比我的还低,我明天一定要学习一下。这里直接给出大佬的答案:
import java.util.*;public class Main { static int [][] a = new int [150][150]; static int [][] sum = new int [150][150]; public static int calc(int x1 , int y1 , int x2 , int y2){ return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]; } public static void main(String[] args) { a[1][1] = 1; for(int i = 2 ; i <= 100 ; i ++) a[1][i] = a[1][i - 1] + 2; for(int i = 2;i <= 100;i++) for(int j = 1;j <= 100;j++) a[i][j] = a[i - 1][j] + 1; for(int i = 1;i <= 100;i++){ for(int j = 1;j <= 100;j++) sum[i][j] = sum[i][j - 1] + a[i][j]; for(int j = 1;j <= 100;j++) sum[i][j] += sum[i - 1][j]; } int ans = 100 * 100; for(int i = 1;i <= 100;i++) for(int j = 1;j <= 100;j++) for(int k = i;k <= 100;k++) for(int l = j;l <= 100;l++) if(calc(i, j, k, l) == 2022) ans = Math.min(ans,(k - i + 1) * (l - j + 1)); System.out.println(ans); }}
我本以为dfs + 回溯能解决一切爆搜。只能说好不容易认真一次,我输的很彻底给我点时间,我一定会把这个方法学会。
6.核酸天数
问题描述:
如果周一做核酸,周二显示核酸天数为 1 天,周三显示 2 天,以此类推,周六显示 5 天,周日显示 6 天。
小蓝在某一天做了一次核酸,请问他的核酸显示为几天。已知做核酸和查看核酸不是在同一天,而且相差不超过 6 天(显示的数为 1 到 6 之间的数)。
输入格式:
输入第一行包含一个整数 s ,表示小蓝做核酸是周几。 s 为 1 到 6 依次表示周一到周六, s 为7 表示周日。
第二行包含一个整数 t ,表示查看核酸是周几。 t 为 1 到 6 依次表示周一到周六, t 为 7表示周日。
输出格式:
输出一行包含一个整数,表示答案。
样例输入:
5
2
样例输出:
4
解题:
嗯,编程签到题,代码如下:
import java.util.*;public class Main{ public static void main(String []args){ Scanner cin = new Scanner(System.in); int s = cin.nextInt() , t = cin.nextInt(); if(s > t) System.out.println(t + 7 - s); else System.out.println(t - s); }}
7.元音大写
问题描述:
输入一个由小写英文字母组成的字符串,请将其中的元音(a,e,i,o,u) 转换成大写,其它字母仍然保持小写。
输入格式:
输入一行包含一个字符串。
输出格式:
输出转换后的字符串。
样例输入:
lanqiao
样例输出:
lAnqIAO
解题:
我只能说模拟赛让你放松警惕,正式比赛重拳出击框框打击你。
代码如下:
import java.util.*;public class Main{ public static void main(String[] args){ char a[] = {'a', 'e', 'i', 'o', 'u'}; Scanner sc = new Scanner(System.in); String s = ""; String s1 = sc.nextLine(); out :for(int i = 0; i < s1.length(); i ++) { for(int j = 0; j < 5; j ++) { if(a[j] == s1.charAt(i)) { s = s + (char)(a[j] - 32); continue out; } } s = s + s1.charAt(i); } System.out.print(s);}}
8.充电能量
问题描述:
小蓝有一个充电器,可以使用不同的电压和电流充电。
给定充电器工作的记录,请计算在这个记录期间总共通过充电传输了多少电能。
输入格式:
输入第一行包含一个整数 n , 表示记录的条数。
接下来 n 行,每行包含一个时刻 T 和两个非负整数 U,I,表示在时刻 T 充电电压变为 U(单位伏),电流变为 I(单位 A)。最后一行满足 U 和 I 均为 0 0,在前面的行中也可能出现 U、I 为 0 0 的情况。其中时间表示为 HH:MM:SS 的格式,时分秒分别用两位十进制数表示(补前导零)。
输入保证时刻依次递增且在 00:00:00 至 23:59:59 的区间内,不用考虑跨过零点充电的情况。
输出格式:
输出一个整数,表示总共通电的电能为多少焦耳,其中 1 焦耳等于 1 伏乘以1 安乘以 1 秒。
样例输入:
3
12:00:00 12 1
12:01:02 5 2
12:01:10 0 0
样例输出:
824
解题思路:
这道题的坑还是有的,只是刚好撞到我擅长的东西上了。String类的题我刷的还是很多的,所以对我来说并不难。
这里填一下坑:
1. int n = sc.nextInt();
会产生换行,得单独用一个nextLine(),吞掉
2. split("\\s+") 可以删掉连在一起的空格。
不管是一个还是两个空格,只要连在一起都可以删掉,不过要注意是”\\“不要写成除法符号!
代码:
import java.util.*;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String s1 = sc.nextLine(); String a[][] = new String[n + 1][]; String b[][] = new String[n + 1][]; for(int i = 0; i < n; i ++) { String s = sc.nextLine(); a[i] = s.split("\\s+"); b[i] = a[i][0].split(":"); } int sum = 0; int hh = 0; int mm = 0; int ss = 0; int ww = 0; int tt = 0; for(int i = 1; i < n; i ++) { ss = Integer.parseInt(b[i][2]) - Integer.parseInt(b[i - 1][2]); mm = Integer.parseInt(b[i][1]) - Integer.parseInt(b[i - 1][1]); hh = Integer.parseInt(b[i][0]) - Integer.parseInt(b[i - 1][0]); tt = hh * 3600 + mm * 60 + ss; ww = Integer.parseInt(a[i - 1][1]) * Integer.parseInt(a[i - 1][2]); sum = sum + tt * ww; } System.out.print(sum);}}
后面两道题我就不会了,混分的话,把案例带入,但是没混到分。我想到了用Random
类产生随机数,看能不能碰对一两个,虽然还是没混到分但是闲着也是闲着。
Random r = new Random();
r.nextInt(100)
随机产生[0, 100)内的数
后面两个题直接给出官方答案了,有时间我也看看解题方法。
9.全相等三角形
问题描述:
给定一个字母矩阵,定义一个 LQ 三角形为某行中连续的几个字母、某列中连续的几个字母和一条 45度的斜线中连续的几个字母组成的等腰直角三角形的边缘部分,其中每条边上的字母数量相等且至少为 2 。
例如,对于下面的字母矩阵中,所有的字母 L 组成一个 LQ 三角形,所有字母 Q 组成了一个 LQ 三角形,所有字母 C也组成了一个 LQ 三角形。
如果一个 LQ 三角形边上的所有字母相等,则称为一个全相等三角形。以三个例子都是全相等三角形。
给定一个字母矩阵,请求其中有多少个全相等三角形。
输入格式:
输入第一行包含两个整数 n,m,分别表示字母矩阵的行数和列数。
接下来 n 行,每行 m 个大写字母,为给定的矩阵。
输出格式:
输出一行,包含一个整数,表示答案。
样例输入 1:
3 4
AAAA
ALAQ
ALQQ
样例输出 1:
4
样例输入 2:
6 7
AAAAAAA
ALLLLLA
ALQQLAA
ALQLAAC
ALLAACC
ALAACCC
样例输出 2:
23
代码:
import java.util.*;public class Main { static int n, m, res; static int[][] a = new int[110][110]; static int[][][] r = new int[110][110][26]; static int[][][] c = new int[110][110][26]; static int[][][] d1 = new int[110][110][26]; static int[][][] d2 = new int[110][110][26]; public static int get1(int x , int y , int len){ return r[x][y][a[x][y]] - r[x - len][y][a[x][y]]; } public static int get2(int x , int y , int len){ return c[x][y][a[x][y]] - c[x][y - len][a[x][y]]; } public static int get3(int x , int y , int len){ return d1[x][y][a[x][y]] - d1[x - len][y + len][a[x][y]]; } public static int get4(int x , int y , int len){ return d2[x][y][a[x][y]] - d2[x - len][y - len][a[x][y]]; } public static int check1(int x , int y , int len){ if(x - len + 1 < 1 || y + len - 1 > m) return 0; if(get1(x , y , len) == len && get2(x , y + len - 1 , len) == len && get4(x , y + len - 1 , len) == len) return 1; return 0; } public static int check2(int x , int y , int len){ if(x - len + 1 < 1 || y - len + 1 < 1) return 0; if(get1(x , y , len) == len && get2(x , y , len) == len && get3(x , y - len + 1 , len) == len) return 1; return 0; } public static int check3(int x , int y , int len){ if(x + len - 1 > n || y - len + 1 < 1) return 0; if(get1(x + len - 1 , y , len) == len && get2(x , y , len) == len && get4(x + len - 1 , y , len) == len) return 1; return 0; } public static int check4(int x , int y , int len){ if(x + len - 1 > n || y + len - 1 > m) return 0; if(get1(x + len - 1 , y , len) == len && get2(x , y + len - 1 , len) == len && get3(x + len - 1 , y , len) == len) return 1; return 0; } public static void main(String[] args) { Scanner cin = new Scanner(System.in); n = cin.nextInt(); m = cin.nextInt(); for(int i = 1 ; i <= n ; i ++) { String tmp = cin.next(); for(int j = 0 ; j < tmp.length() ; j ++) { a[i][j + 1] = tmp.charAt(j) - 'A'; for(int k = 0 ; k <= 25 ; k ++) c[i][j + 1][k] = c[i][j][k]; c[i][j + 1][a[i][j + 1]] ++ ; } } for(int j = 1 ; j <= m ; j ++) for(int i = 1 ; i <= n ; i ++){ for(int k = 0 ; k <= 25 ; k ++) r[i][j][k] = r[i - 1][j][k]; r[i][j][a[i][j]] ++ ; } for(int val = 2 ; val <= n + m ; val ++) for(int i = 1 ; i <= n ; i ++){ int j = val - i; if(j < 1 || j > m) continue ; for(int k = 0 ; k <= 25 ; k ++) d1[i][j][k] = d1[i - 1][j + 1][k]; d1[i][j][a[i][j]] ++; } for(int val = 0 ; val < n + m ; val ++) for(int i = 1 ; i <= n ; i ++){ int j = m - val + i; if(j < 1 || j > m) continue; for(int k = 0 ; k <= 25 ; k ++) d2[i][j][k] = d2[i - 1][j - 1][k]; d2[i][j][a[i][j]] ++ ; } for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= m ; j ++) for(int len = 2 ; len <= Math.min(n , m) ; len ++){ res += check1(i , j , len) + check2(i , j , len) + check3(i , j , len) + check4(i , j , len); } System.out.println(res); }}
10.最小表示
问题描述:
小蓝有一个由大写字母 ABCDEF 组成的字符串 S ,长度为 n,字符串的下标依次为 0 到 n−1 。
小蓝按照如下方法生成一个无限长的字符串:
选定一个 0 到 n−1 之间的数,作为初始下标。 从初始下标开始,将下标对应的字符加入到字符串的结尾,将字符的序号(A 到 F 依次对应 1 到 6 )与下标相加作为新的下标值,如果下标大于等于 n,将其对 n 求余。
重复此过程,即得到无限长的字符串。例如,对于字符串 ACDF,当初始下标是 0 时,生成的字符串为:
ACACACACAC 再如,对于字符串 DCBA,当初始下标是 1 时,生成的字符串为: CDDDDDDDDD给定小蓝的字符串 S,请问当初始下标为多少时,生成的字符串最小。
输入格式:
输入一行包含一个字符串。
输出格式:
输出一行,包含一个整数,为所求的下标,如果有多个下标满足要求,输出最小的那个。
样例输入 1:
DCBA
样例输出 1:
3
样例输入 2:
AAAA
样例输出 2:
0
代码:
import java.util.*;public class Main { static String s = ""; static int n; static int[] vis = new int[1000010]; public static int get(int x){ return (x + s.charAt(x) - 'A' + 1) % n; } public static int minShow(String s){ n = s.length(); int i = 0 , j = 1 , len = 0 , _i = 0 , _j = 1; vis[0] = vis[1] = 1; while(i < n && j < n && len < n){ int t = s.charAt(_i) - s.charAt(_j); if(t == 0) { _i = get(_i); _j = get(_j); len ++; } else { if(t > 0) { int x = i; while(x != _i) { vis[x] = 1 ; x = get(x); } while(vis[i] == 1) i ++ ; vis[i] = 1; } else { int x = j; while(x != _j) { vis[x] = 1; x = get(x); } while(vis[j] == 1) j ++; vis[j] = 1; } _i = i ; _j = j; } } return Math.min(i , j); } public static void main(String[] args) { Scanner cin = new Scanner(System.in); s = cin.next(); System.out.println(minShow(s)); }}
总结:
蓝桥杯改革成两道填空,8道编程的模式。
虽然本次模拟和正真的比赛相差的还是很远,好在也学到了一些基本的做题流程:
1.即把代码量少,思路清晰的最先做
2.将代码量相对较多或者有机会做对的题目放在第二波做
3.最后对完全不会的题进行最后的混分
当然上述是最理想的状态希望在考试中也能在也能像现在总结的一样游刃有余。
本次的不足也很明显,即枚举法也要学一学,有时候dfs + 回溯代码量太大了,时间复杂度也不占优势,一定要把枚举法练熟,成为我爆搜手段的一部分,还有就是蓝桥杯常考知识,也要抽空学习,例如排序,求质数,这类数论知识我都忘的差不多了。接下来就是试试掌握迪杰斯特拉算法,和剪枝。