🍄7.数的幂次
题目链接：数的幂次https://www.lanqiao.cn/problems/1181/learning/
考察快速幂的考点，这个考点还是比较重要且常考的。大家可以直接通过快速幂函数的公式套进去即可。大家复制下来背下来直接食用即可，类似gcd一样。
import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st = new StreamTokenizer(br); static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); public static void main(String[] args)throws Exception { int t=nextInt(); while(t-->0) { int n=nextInt(); int m=nextInt(); int p=nextInt(); out.write(check(n,m,p)+"\n"); } out.flush(); } //快速幂函数，赋值照用即可 static long check(long a,int k,int p) { long res=1; while(k>0) { //这样判断k的二进制最后一位是否是1 if((k&1)==1) res=res*a%p; k>>=1; a=(long)a*a%p; } return res; } // 读入整形（一个） public static int nextInt() throws Exception { st.nextToken(); return (int) st.nval; // nval 读入的是 double 类型 } // 读取字符串（一个） // 若读入的不是字符串，会 null public static String nextStr() throws Exception { st.nextToken(); return st.sval; } }
🌵8.最大乘积
题目链接：最大乘积https://www.lanqiao.cn/problems/629/learning/
还是全排列的问题，但是这里我们需要去考虑插入乘号的位置。乘号可以放在第一个数字之后，或者最后一个数字之前。然后我们去判断乘积是否符合数字1~9的排列情况，如果符合就在已保存的值中取更大值。大家最好把每一段的逻辑抽成一个方法去写，这样出错我们可以更容易的去排错。
import java.util.HashSet; import java.util.Set; public class 最大乘积 { static int max=0; static int[] arr= {1,2,3,4,5,6,7,8,9}; public static void main(String[] args) { dfs(0); System.out.println(max); } //全排列 static void dfs(int k) { if(k==9) { check(); return; } for(int i=k;i<arr.length;++i) { exch(i,k); dfs(k+1); exch(i,k); } } //插入乘号位置 static void check() { for(int i=1;i<=8;++i) { int a=test(arr,i); if(isOk(a)) { max=Math.max(a,max); } } } //获取乘积 static int test(int[] arr,int k) { int pre=0; int count1=0; while(k-->0) { count1=count1*10+arr[pre]; pre++; } int count2=0; for(int i=pre;i<arr.length;++i) { count2=count2*10+arr[i]; } return count1*count2; } //判断答案是否有且仅包含1~9 static boolean isOk(int n){ Set<Integer> set=new HashSet<>(); for(int i=1;i<=9;++i) set.add(i); while(n!=0) { int a=n%10; if(!set.contains(a)) return false; else set.remove(a); n/=10; } return set.size()==0; } //交换函数 static void exch(int a,int b) { int tmp=arr[a]; arr[a]=arr[b]; arr[b]=tmp; } }
🌴9.含二天数
小蓝特别喜欢 22，今年是公元 2020 年，他特别高兴，因为每天日历上都可以看到 22。
如果日历中只显示年月日，请问从公元 1900 年 1 月 1 日到公元 99 年 12 月 31 日，一共有多少天日历上包含 22。即有多少天中年月日的数位中包含数字 2。
题目：含2天数https://www.lanqiao.cn/problems/1038/learning/
还是同样的日期问题，调用我们的日期模板直接秒杀即可！
代码转换：
public class 含2天数 { static int[] M= {0,31,28,31,30,31,30,31,31,30,31,30,31}; public static void main(String[] args) { int ans=0; int y=1900,m=1,d=1; //先升日期再升值 while(y!=9999||m!=12||d!=31) { if(y%400==0||(y%4==0&&y%100!=0)){ M[2]=29; }else { M[2]=28; } d++; if(d>M[m]) { m++; d=1; } if(m>12) { m=1; y++; } if(check(y,m,d)) { ans++; } } System.out.println(ans); } static boolean check(int y,int m,int d) { while(y!=0) { if(y%10==2) return true; y/=10; } while(m!=0) { if(m%10==2) return true; m/=10; } while(d!=0) { if(d%10==2) return true; d/=10; } return false; } }
🌰 10.积木大赛
题目链接：积木大赛https://www.lanqiao.cn/problems/384/learning/
题目的本质是贪心。对于增加操作，我们也可以理解成将数组所有元素减到0的最少操作次数。我们可以将原数组分为n个递增的子数组，a[0,i],a[i+1,j],a[j+1,k]....。答案就是每段递增子序列的最大值减去除去第一段的每段的最小值之和。
代码转换：
import java.util.Scanner; public class 积木大赛 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int ans=0,last=0; for(int i=0;i<n;++i) { int a=sc.nextInt(); if(a>last) ans+=(a-last); last=a; } System.out.println(ans); } }
