三、负数幂

image.png
负数的计算：(a + b i)(c + d i) = (ac - bd) + (bc + ad) i
然后计算就行了，不适用Cxx的形式，直接一次次乘就可以实现
其中使用大数，long无法储存

  1. import java.io.*;
  2. import java.math.BigInteger;
  4. public class Main {
  6.     public static void main(String[] args) throws FileNotFoundException {
  7.         PrintStream ps=new PrintStream(new FileOutputStream("work.txt"));  
  8.             System.setOut(ps);  //文件输出
  9.         int n=123456;
  10.         BigInteger a=new BigInteger("2");
  11.         BigInteger b=new BigInteger("3");
  12.         BigInteger a1=new BigInteger("2");
  13.         BigInteger b1=new BigInteger("3");
  14.         for(int i=1;i<n;i++) {
  15.             BigInteger ta=a;
  16.             a=a.multiply(a1).subtract(b.multiply(b1));//a=a*a1-b*b1;
  17.             b=ta.multiply(b1).add(b.multiply(a1));//b=a*b1+b*a1
  18.         }
  19.         System.out.println(a+(b.compareTo(BigInteger.ZERO)>0?"+":"-")+b+"i");
  20.     }
  21. }

四、测试次数

类比于摔鸡蛋。
此处先写摔鸡蛋的例题问题。
https://blog.csdn.net/wolinxuebin/article/details/47057707
注意，此处是和二分查找不一样的。由于鸡蛋碎了就没了，所以不能二分
问题是100层楼2个鸡蛋
因此，我们先假设egg在x层要进行一个摔
如果没碎，就在 x+（x-1）层摔
如果碎了，在1到 x-1层中间遍历摔
（以上的情况是为了保证，对于任意的一个x，能保证一个大致的平衡（即左右都为需要有x-1个测试的）
最后得出一个公式 x + x-1 + x-2 + … + 1，当这个式子大于所要求的楼层总数时，才能解出。
所以求出x = 14（是进一法求）
第二个问题就是100层楼多个鸡蛋
设n个鸡蛋吧，那么用动态规划
理由同上。dp[鸡蛋个数+1][楼层数+1]
dp[m][n] = 1+ max(dp[m][n-k] , dp[m-1][n-1]) 其中k属于1到n-1，迭代遍历
前者是如果在n层没摔碎的话，就继续测试 n + n-1。我们前面为了保证平衡，左右次数其实是相同的，因此取1到 n-k,k次遍历
后者是如果摔碎了，就直接用n-1个鸡蛋的第n-1层楼的数据+1，（+1是因为已经摔碎了
（这里直接看代码更清楚

  1. public class Eggs{
  2.     public int countMinSetp(int egg,int num){
  3.         if(egg < 1 || num < 1) return 0;
  4.         int[][] f = new int[egg+1][num+1];//代表egg个鸡蛋，从num楼层冷下来所需的最小的次数
  5.         for(int i=1;i<=egg; i++){
  6.             for(int j=1; j<=num; j++)
  7.                 f[i][j] = j;//初始化，最坏的步数
  8.         }
  10.         for(int n=2; n<=egg; n++){
  11.             for(int m=1; m<=num; m++){
  12.                 for(int k=1; k<m; k++){
  13.                     //这里的DP的递推公式为f[n][m] = 1+max(f[n-1][k-1],f[n][m-k]) k属于[1,m-1]
  14.                     //从1-m层中随机抽出来一层k
  15.                     //如果第一个鸡蛋在k层碎了，那么我们将测试1~k-1层，就可以找出来，也即1+f[1][k-1]
  16.                     //如果第一个鸡蛋在k层没有碎，那么我们将测试k+1~m也即m-k层，
  17.                     //      这里也是重点！！！！ 
  18.                     //      现在我们手里有2个鸡蛋，要测试m-k层，那么我想问，
  19.                     //此时和你手里有2个鸡蛋要测试1~m-k层有什么区别？
  20.                     //      没有区别！是的在已知k层不碎的情况下，测试k+1~m层的方法和测试1~m-k没区别，
  21.                     //所以可以写成 1+f[n][m-k] 其中1表示为 在k层的那一次测试
  22.                     f[n][m] = Math.min(f[n][m],1+Math.max(f[n-1][k-1],f[n][m-k]));
  23.                     //这里前面是min的理由是要将结果最优
  24.                     //max是要保证一定能测出来
  25.                 }
  26.             }
  27.         }
  28.         return f[egg][num];
  29.     }
  30.     public static void main(String[] args) {
  31.         Eggs e = new Eggs();
  32.         System.out.println(e.countMinSetp(2,100));
  33.     }
  34. }

其中，Math.max(f[n-1][k-1],f[n][m-k])，max的原因是就是有可能破碎也有可能不碎，为了保证能够测出来，必须要取最大的。

那么现在再看手机问题，其实本质是一样的，其中只要设置n = 3 ，层数 = 1000即可

六、递增三元组

image.png
算法思路：先把三个数组都排序（可以调用库函数），然后只遍历b数组，由于b数组最特殊。
b数组最为特别，因为一个数组要比它小，C数组要比它大
那么总和就是每个b中的元素在a数组中小于这个元素的*在c数组中大于b数组这个元素的个数

  2. import java.util.Arrays;
  3. import java.util.Comparator;
  4. import java.util.Scanner;
  6. public class T6 {
  7.     public static void main(String[] args) {
  8.         //首先是输入
  9.         Scanner sc = new Scanner(System.in);
  10.         int n = sc.nextInt();
  11.         int[] a = new int[n];
  12.         Integer[] b = new Integer[n];
  13.         Integer[] c = new Integer[n];
  15.         for (int i = 0; i < n; i++) {
  16.             a[i] = sc.nextInt();
  17.         }
  18.         for (int i = 0; i < n; i++) {
  19.             b[i] = sc.nextInt();
  20.         }
  21.         for (int i = 0; i < n; i++) {
  22.             c[i] = sc.nextInt();
  23.         }
  25.         //对b进行遍历
  27.         Arrays.sort(a);//默认从小到大
  28.         Arrays.sort(b, new cmp());
  29.         Arrays.sort(c, new cmp());
  31.         int ans = 0;
  33.         //要求是a<b<c
  34.         for (int i = 0; i < n; i++) {
  35.             //如果a>b,就不比较了，直接跳出，此时j的数就是符合的数。
  36.             int j = 0;
  37.             for (j = 0; j < n; j++) {
  38.                 if (a[j] >= b[i]) {
  39.                     break;
  40.                 }
  41.             }
  42.             int k = 0;
  43.             for (k = 0; k < n; k++) {
  44.                 if (c[k] <= b[i]) {
  45.                     break;
  46.                 }
  47.             }
  48.             ans += j * k;
  49.         }
  50.         System.out.println(ans);
  51.     }
  52. }
  54. class cmp implements Comparator<Integer> {
  55.     @Override
  56.     public int compare(Integer o1, Integer o2) {
  57.         return o2 - o1;
  58.     }
  59. }

七、螺旋折线

image.png
image.png
两种解法：
第一种：https://blog.csdn.net/qq799028706/article/details/84312062
巧算
第二种自己算的：

  1. public class T7 {
  2.     public static void main(String[] args) {
  3.         Scanner sc = new Scanner(System.in);
  4.         int x = sc.nextInt();
  5.         int y = sc.nextInt();
  6.         int n = Math.max(Math.abs(x), Math.abs(y));//最大值
  8.         //直接算就行了
  9.         int ans = (2 * n - 1) * (2 * n - 2);
  10.         //就是是x轴较大
  11.         if (n == Math.abs(x)) {
  12.             //右边的竖线
  13.             if (x > 0) {
  14.                 ans = ans + 2 * (2 * n - 1) + 2 * n + n - y;
  15.             }else
  16.                 //左边的竖线
  17.             ans = ans+ 2 * n - 1 + y+(n-1);
  18.         }else {
  19.             //是y轴比较大，算横坐标
  20.             //上面横线
  21.             if (y >0){
  22.                 ans = ans + 2 * (2 * n - 1) + x+n;
  23.             }else
  24.                 //下面横线
  25.             ans = ans + n-x;
  26.         }
  27.         System.out.println(ans);
  28.     }
  29. }