这题对时间要求很高，很多复杂度高的算法都不能使用首先是判断是否为质数，传统判断方法不能用，会超时，应当使用埃氏筛然后是判断不重复的数量，如果使用Set就会超时，应当使用布尔数组来存储存在情况总体来说，这题还是很看重时间复杂度优化的 import java.util.Arrays; import java.util.Scanner; import java.util.HashSet; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=...

这题纯是考察异或和的性质，如果一个序列能够拆分成两个异或和相等的序列，假设这两个序列的异或和为x，那么x^x=总的序列和y，而根据异或的性质，x^y=x，也就是异或可交换，那么y==0即可，所以直接判断y是否为0就能判断最终答案下面程序中如果使用dfs，那么只能过一个测试点，其它都会超时 import java.util.ArrayList; import java.util.Scanner; public class Main { static ArrayList<ArrayList<Integer>> res; static boolean flag; public...

去年做这题时，我对BigInteger的用法还不太熟练，但是知道该使用这个，一直以为这题结果就是A*B，觉得是这道题让自己止步省二，如今算法水平已经提升了很多，再一次看这道题，发现没那么简单，终于算是释怀了好了，讲讲我现在对这题的理解既然N+A是B的倍数，N+B是A的倍数，那么我们就设N+A=K*B，那么N=K*B-A，把它带入到N+B中去，得到K*B-A+B也就是(K+1)*B-A是A的倍数，那么减去的A由于已经是A的倍数，就可以舍掉，就只用去研究(K+1)*B，既然这个是A的倍数，那么这个式子最小应该就是A与B的最小公倍数，而A与B的最小公倍数我们是可以求出来的， 然后拿最小公倍数除以B减...

这题属于整数划分，就是将m划分成最多n个数，问有多少种分法，我们选择使用动态规划去做dp[i][j]表示i个盘，j个苹果先初始化，如果苹果数量为0，那么就一定是只有一种，全空的情况然后进行递推，当苹果数量大于盘子的数量时，有两种，一种是所有盘子都用上，那么就是dp[i][j-i]，因为这种情况每个盘子至少需要一个，就等价于苹果数减去盘子数后的分法数量还有一种情况就是苹果数量少于盘子数量，那么多余的盘子就是摆设，没用，我们选择把多余的盘子去掉改为dp[j][j] import java.util.Scanner; public class Main { public static void ma...

根据费马小定理，a^(p-1)mod m =1;所以指数部分经过p-1次会重来，所以对于指数部分是对p-1取模对于整体就是对p取模P=1000000007；但是对于质数取模有一点需要特判，如果取完模后发现指数部分为0，那么需要看底数是否为0，如果底数为0，那么结果应当是0，而不是1，如果不特判就会输出1。那么该如何特判，其实只需要在求完指数以后，如果指数为0，我们就把它赋值为p-1，这样就不会因为指数而受影响 import java.util.Scanner; public class Main { public static void main(String[] args) { // TOD...

经典的分数取模，不能直接除，要使用模逆元改为相乘的形式，然后a乘b的模逆元后还要加上模数，因为a可能是负数，这是取余的一个性质，最后还要再取模 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int p=1000000007; int t=sc.nextInt(); whil...

这一题看题目很容易想到要使用前缀积，但是在求区间乘积的时候，会用到除法，这就不能单纯除，而是应该改成乘上模逆元，在Java中，求模拟元可以使用BigInteger自带的方法，modInverse(mod)，这样就可以省略很多代码最后输出结果就行 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(Sys...

这一题是快速幂的模板大概思路就是，如果指数是奇数，那么res=(res*a)%p;然后就a=(a*a)%p;b=b/2;一开始的res就要对p取模，这是为了防止p为1这种情况，当p为1时，任何数取模后都输出0；要注意这几个地方都要取模，不然答案就可能出错 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int t=sc.nextIn...

这个就是一个很典型的斐波那契数列，直接遍历就好了 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int k=sc.nextInt(); long f[]=new long[k+5]; f[1]=1; f[2]=1; for(int i=3;i<=k;i++) { f[i]=(f[i-1]+f[i-2])%(100000000...

这题说白了，直接数没有被右括号配对的左括号的最大值就行遍历这个字符串，如果遇到左括号，那么left++;如果遇到右括号，那么left--;同时判断是否超过max；最后输出max即可 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); String s=sc.next(); char c[]=s.toCharArray(); int le...

这题有点恶心的地方在于，n不是按顺序给出的，所以我们还是要去分析题目意思，来找出规律经过分析， f函数其实就是拿来求n中1的个数的，那么我们可以直接使用Long.bitcount()函数来直接求然后就是求出个数以后，我们需要知道第一次出现的n是多少其实就是2的a次方-1 import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new...

这一题并没有什么好说的，使用递归的思想，当a为个位数时，返回啊，否则就求每位数之和，返回调用函数后的结果 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int n=sc.nextInt(); System.out.println(f(n)); } public static int f(int a) { if(a>=0&am...

最大子段和，我们需要构造出一个dp数组，其中dp[i]表示以a[i]结尾的最大值，要么为dp[i-1]+a[i]，要么为a[i] import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextIn...

最长不降子序列其实就是把每一个值都考虑一下，如果该值比我列表中最大的都大，那么就直接装进来，如果不是，那么就需要遍历列表去找到第一个大于它的值，然后将这两个值进行替换注意：这里最后的list其实并不是严格意义上的最长不降子序列，我们也并不关心它是不是，我们只关心它的长度，因为它的长度一定是最长不降子序列的长度 import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method...