碎碎念：

马上就蓝桥杯了，赶紧临时抱佛脚看看真题

发现自己算法还是练的少，能理解但是写不出来是目前的大问题

第一次参加算法类的比赛，还是比较紧张的（因为算法不太行）

但是后期会继续多刷算法题的！！！

这篇写了A B C D E F G没写太难了 H写了40% 正解太难不会

目录

A.美丽的2 - 字符串处理

B.扩散 - 多源bfs

C.阶乘约数 - 阶乘数定理 数论 质数线性筛

D.本质上升序列 - dp 最长上升子序列变体

E.玩具蛇 - dfs

F.蓝肽子序列 - dp 最长公共上升子序列

H.画廊 - 贪心+模拟 40%

A.美丽的2 - 字符串处理

题目：

1~2020 有多少个年份数位包含2？

答案：563 

public class Main //主类 
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int res=0;for(int i=1;i<=2020;i++){String s=String.valueOf(i);if(s.indexOf('2')!=-1) res++;}System.out.println(res);}
}

B.扩散 - 多源bfs

题目：

思路：

答案：20312088

因为可以上下左右扩散，且最多扩散2020层，因此先将整个坐标处理成无负坐标的情况

也就是给横纵坐标均+2020，我们发现二维数组只要开到7000即可

接着将四个点入队并标记

进行bfs，如果该点是白的，入队标记并进行扩展

dist记录扩展层数，当扩展至2020层时结束扩展

最后遍历全图，统计已标记的点

package text;import java.util.*;public class Text //主类 
{static int N=7000;static int[][] dist=new int[N][N];static int[][] st=new int[N][N];static int[]dx= {0,0,1,-1};static int[]dy= {1,-1,0,0};public static void main(String[] args){Scanner sc=new Scanner(System.in);Queue<PII> q=new LinkedList<>();q.offer(new PII(2020,2020));q.offer(new PII(4040,2031));q.offer(new PII(2031,2034));q.offer(new PII(4020,4020));st[2020][2020]=1;st[4040][2031]=1;st[2031][2034]=1;st[4020][4020]=1;while(!q.isEmpty()){PII t=q.poll();int x=t.x,y=t.y;if(dist[x][y]==2020) break;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(st[nx][ny]==1) continue; //如果该格子已经是黑色 说明已经做过扩散st[nx][ny]=1;q.offer(new PII(nx,ny));dist[nx][ny]=dist[x][y]+1;}}int res=0;for(int i=0;i<7000;i++)for(int j=0;j<7000;j++) if(st[i][j]==1) res++;System.out.print(res);}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}

C.阶乘约数 - 阶乘数定理 数论 质数线性筛

题目：

思路：

答案：39001250856960000

定理如下：

• 任意一个正整数x均能表示成若干个质数乘积形式
• 

则x的约数个数res为

为何要+1？ 

因为可以将x看成

 后面括号内的乘积看作一个数

• 我们先通过线性筛筛出1~100内的所有质数
• 再将100！中每一个数用这些质数表示，记录每个质数的指数，按照上述公式相乘即可得到答案

public class Text //主类 
{static int N=110;static int[] prime=new int[N];static int[] st=new int[N];static int[] cnt=new int[N]; //记录质数的指数public static void get_prime(int x){int cnt=0;for(int i=2;i<=x;i++){if(st[i]==0) prime[cnt++]=i;for(int j=0;prime[j]<=x/i;j++){st[prime[j]*i]=1;if(i%prime[j]==0) break;}}}public static void init(){for(int i=2;i<=100;i++) if(st[i]==0) cnt[i]=1;//将所有质数的指数初始化为1 后面乘的时候就不用+1}public static void main(String[] args){Scanner sc=new Scanner(System.in);get_prime(100);init();//for(int x:prime) System.out.print(x+" ");for(int i=2;i<=100;i++) //对于100！中每一个数，均用这些质数表示{int x=i; for(int j=2;j<=100;j++)if(st[j]==0) while(x%j==0){cnt[j]++;x/=j;}}//res=(a1+1)*(a2+1)*……*(ak+1)long res=1;for(int i=2;i<=100;i++) if(st[i]==0)res*=cnt[i];System.out.print(res);}
}

D.本质上升序列 - dp 最长上升子序列变体

题目：

思路：

答案：3616159

f[i]表示以第i个字符结尾的本质不同的递增子序列个数

则答案即为f[0]~f[n-1]之和

当s[i]≠s[j]，f[i]+=f[j]

当s[i]=s[j]，f[i]=0 （存在的递增子序列与前面出现过的重复）

举个栗子：

s="abcab"

f[0]=1        【"a"】

f[1]=2        【"b"  "ab"】也就是f[2]=1，f[2]+=f[1]

f[2]=4       【"c"  "ac"  "bc"  "abc"】也就是f[3]=1，f[3]+=f[1]，f[3]+=f[2]

f[3]=0       【无】 跟前面计算的重复了

f[4]=0       【无】 跟前面计算的重复了

import java.util.*;public class Text //主类 
{static int N=210;static int[] f=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);String s="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";for(int i=0;i<200;i++){f[i]=1; //只有自己的时候for(int j=0;j<i;j++)if(s.charAt(i)==s.charAt(j)) f[i]=0;else if(s.charAt(i)>s.charAt(j)) f[i]+=f[j];}int res=0;for(int i=0;i<200;i++) res+=f[i];System.out.print(res);}
}

E.玩具蛇 - dfs

题目：

思路：

答案：552

16个格子，枚举每一个格子作为放1的起点进行dfs，列出所有情况

dfs(x,y,num) num记录已放好的格子数，当nums==16时说明一种新的方案已形成

记得还原现场

import java.util.*;public class Text //主类 
{static int N=4;static int[][] g=new int[N][N];static int[] dx={0,0,1,-1},dy= {1,-1,0,0};static int res;public static void dfs(int x,int y,int num){if(num==16) {res++;return;}for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx<0||nx>=4||ny<0||ny>=4||g[nx][ny]==1) continue;g[nx][ny]=1;dfs(nx,ny,num+1);g[nx][ny]=0;}}public static void main(String[] args){Scanner sc=new Scanner(System.in);for(int i=0;i<4;i++)for(int j=0;j<4;j++) //以每一个方格作为1的起点 进行答案枚举{for(int k=0;k<4;k++) Arrays.fill(g[k],0);g[i][j]=1;dfs(i,j,1);}System.out.print(res);}
}

F.蓝肽子序列 - dp 最长公共上升子序列

题目：

思路：

把最长公共子序列中每一个字符改成每一个字符串即可

f[i][j] 字符串数组a的前i个字符串和b的前j个字符串最长公共子序列长度

只要处理一下按大写字母分割的字符串至字符串数组即可

最长公共子序列模板：【蓝桥杯集训26】线性DP（4 / 4）_Roye_ack的博客-CSDN博客

import java.util.*;public class Main //主类 
{static int N=1100;static int[][] f=new int[N][N]; //f[i][j] 字符串数组a的前i个字符串和b的前j个字符串最长公共子序列长度static int res;static String[] a=new String[N],b=new String[N]; public static int init(String s,String[] a){int idx=0,cnt=1;for(int i=0;i<s.length();i++)if(i==0) continue;else if(Character.isUpperCase(s.charAt(i))){a[cnt++]=s.substring(idx,i);idx=i;}a[cnt]=s.substring(idx);return cnt;}public static void main(String[] args){Scanner sc=new Scanner(System.in);String s1=sc.next();String s2=sc.next();int n=init(s1,a);int m=init(s2,b);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j]=Math.max(f[i-1][j],f[i][j-1]);if(a[i].equals(b[j])) f[i][j]=f[i-1][j-1]+1;}System.out.print(f[n][m]);}
}

H.画廊 - 贪心+模拟 40%

题目：

思路：

这题正解是dp，但是我现在水平达不到这个，所以先不整理100%的dp代码

每次都计算当前点x，y与左右两边点的距离，选择距离近的点走

直到把两边都走完，最后走到终点

import java.util.*;public class Main //主类 
{static int N=550;static int[] la=new int[N],ra=new int[N];static int l,r,d,w;static double res;public static void main(String[] args){Scanner sc=new Scanner(System.in);l=sc.nextInt();r=sc.nextInt();d=sc.nextInt();w=sc.nextInt();for(int i=0;i<l;i++) la[i]=sc.nextInt();for(int i=0;i<r;i++) ra[i]=sc.nextInt();double stx=(double)w/2;double sty=0.0;int li=0,ri=0;while(li<l||ri<r){double ld=0x3f3f3f3f,rd=0x3f3f3f3f;if(li<l){double x=stx-0;double y=sty-la[li];ld=Math.sqrt(x*x+y*y);}if(ri<r){double x=stx-w;double y=sty-ra[ri];rd=Math.sqrt(x*x+y*y);}if(ld<rd){res+=ld;stx=0;sty=la[li];li++;}else{res+=rd;stx=w;sty=ra[ri];ri++;}}//最后一幅作品到终点double x=stx-(double)w/2;double y=sty-d;res+=Math.sqrt(x*x+y*y);System.out.printf("%.2f",res);}
}