蓝桥冲刺31天之第七天

目录

A：三角回文数

B：数数

C：数组切分

D：倍数问题

---

一星陨落，黯淡不了星空灿烂；

一花凋零，荒芜不了整个春天。

如果命运是世界上最烂的编剧，

你就要争取做人生最好的演员。

即使生活在阴沟里，依然有仰望星空的权利。

A：三角回文数

 因为题目以及给定1+2+...+363=66066，所以在遍历的时候可以从363开始，因为不知道这个数在多少出现，所以可以不定结果，那么循环代码如下：

for(int i=363;;i++)

 接下来我们需要判定求和结果（1+i）*i/2>20220514,且该值为回文数，那么代码如下：

package 蓝桥冲刺31天A.第七天;import java.io.*;/*** @ClassName 三角回文数* @Description TODO* @Author 小怂很怂* @Date 2023/3/10 10:45* @Version 1.0**/
public class 三角回文数 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws Exception {for(int i=363;;i++){int k=i*(i+1)/2;if (k>20220514&&pd(k)){pw.println(k);pw.flush();return;}}}public static boolean pd(int k){String ss=k+"";int j=ss.length()-1;for (int i=0;i<=j;i++){//判定是否是回文数if (ss.charAt(i)!=ss.charAt(j)) return false;j--;}return true;}public static int nextInt() throws Exception {//int型st.nextToken();return (int) st.nval;}public static long nextLong() throws Exception {//long型st.nextToken();return (long) st.nval;}
}

B：数数

 通过遍历每一个数去求结果，建议电脑跑完后直接提交结果，会超时

package 蓝桥冲刺31天A.第七天;import java.io.*;/*** @ClassName 数数* @Description TODO* @Author 小怂很怂* @Date 2023/3/10 10:54* @Version 1.0**/
public class 数数 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws Exception {int count=0;for (int i=2333333;i<=23333333;i++){//遍历int t=i,s=0;for (int j=2;j*j<=t;j++){//判定这个数分解情况if (t%j==0){t/=j;s++;j--;}}if (t!=1) s++;//t！=1的情况下，t一定为质数if (s==12) count++;//满足s=12，则计数}pw.println(count);pw.flush();//必须加}public static int nextInt() throws Exception {//int型st.nextToken();return (int) st.nval;}public static long nextLong() throws Exception {//long型st.nextToken();return (long) st.nval;}
}

C：数组切分

 我们可以将每一个新放入的数产生后的连续区间看成一个整体：比如{3}，{3，2}，{1，3，2}这些都是一个整体，那么在计数的时候，就是去除这一个整体后，前面数的总和，例如：

或许有一点点绕，但是仔细想一下？ 

package 蓝桥冲刺31天A.第七天;import java.io.*;/*** @ClassName 数组切分* @Description TODO* @Author 小怂很怂* @Date 2023/3/10 11:48* @Version 1.0**/
public class 数组切分 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws Exception {int n=nextInt();int []arr=new int[n+1];for (int i=1;i<=n;i++) arr[i]=nextInt();int []dp=new int[n+1];dp[0]=1;for (int i=1;i<=n;i++){int min=n+1;int max=0;for (int j=i;j>=1;j--){max=Math.max(max,arr[j]);min=Math.min(min,arr[j]);if (max-min==i-j) dp[i]=(dp[i]+dp[j-1])%1000000007;}}pw.println(dp[n]);pw.flush();//必须加}public static int nextInt() throws Exception {//int型st.nextToken();return (int) st.nval;}public static long nextLong() throws Exception {//long型st.nextToken();return (long) st.nval;}
}

D：倍数问题

 看着像三数之和，那能不能像三数之和一样做？答案是可以的

我们先进行一次排序，因为优先大的数嘛，因为n<100000,所以如果采用O(n²)一定会超时，更何况还需要找第三个数，那么我们怎么做？题目给定了一个值K，且K<=1000，我们可以通过取模的方式，找到最多3*k个数，我们对于每一种模值只保留3个最大的数，然后遍历循环就成了O(3*k)³，这当然还是会超时的，如果我们在判定时直接结束某一次循环呢？因为数据是按照排序结果下来的，如果出现可选的最大的三个数<已经求得的最大值，我们是不是就可以不用再去进行计算了？因为再计算即使满足k的倍数，值也比最大值小

package 蓝桥冲刺31天A.第七天;import java.io.*;
import java.lang.reflect.Array;
import java.util.Arrays;/*** @ClassName 倍数问题* @Description TODO* @Author 小怂很怂* @Date 2023/3/10 11:21* @Version 1.0**/
public class 倍数问题 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws Exception {int n=nextInt();int k=nextInt();int []arr=new int[n];int []brr=new int[k*3];//存放%k结果的最大的三个数int []crr=new int[k];//%k的数的个数，只需要三个for (int i=0;i<n;i++) arr[i]=nextInt();Arrays.sort(arr);int s=0;for (int i=n-1;i>=0;i--){//从中选出3*k个数if (crr[arr[i]%k]<=2){//判断该模值是否到达3crr[arr[i]%k]++;brr[s]=arr[i];//存入s++;}if (s==3*k)break;//选完3*k个数就可以直接跳出了，没必要多进行计算}int count=0;for (int i=0;i<s-2;i++){if (brr[i]*3<=count) break;//最大的情况比已知结果小，跳出for (int j=i+1;j<s-1;j++){if (brr[i]+brr[j]*2<=count) break;//最大的情况比已知结果小，跳出for (int l=j+1;l<s;l++){if ((brr[i]+brr[j]+brr[l])%k==0){count=Math.max(count,brr[i]+brr[j]+brr[l]);break;}if (brr[i]+brr[j]+brr[l]<=count) break;//最大的情况比已知结果小，跳出}}}pw.println(count);pw.flush();//必须加}public static int nextInt() throws Exception {//int型st.nextToken();return (int) st.nval;}public static long nextLong() throws Exception {//long型st.nextToken();return (long) st.nval;}
}