題目大意：給出誤差函數?，現在給出 z 和 n，要求求出 x 和 y ，使得函數 F 的取值最小

題目分析：首先數據范圍是冪次級別的，1e5 的 10 次方，也就是 1e50 次方，需要用到大數，我用的是 java 的大數類

因為 x 和 y 的取值是 x < y < z，考慮枚舉 x 或 y ，然后二分去逼近另一個，這里我枚舉的是 y ，將絕對值去掉后，得到?，當 y 和 z 確定后，顯然這個函數具有單調性，將整個式子向 0 逼近即可，即求出??的最大的可行 x1，然后嘗試去更新答案，又因為絕對值是一個對稱函數，不能只考慮整體小于等于 0 的最大值，還需要考慮整體大于等于 0 的最小值才行，因為 x1 是整體小于等于 0 的最大值了，所以 x1 + 1 一定是大于等于 0 的最小值，不太會證明，感性理解一下吧，所以用 x1 和 x1 + 1 各自嘗試更新一下答案就好了

需要注意的點：

需要預處理出冪次 pow[ x ][ y ] = x^y，如果每次都調用 pow() 函數的話會 TLE

只能進行一次二分，進行兩次二分的話帶著一個常數，會 TLE

只能寫二分而不能寫三分，據說三分會 TLE

代碼：
?

import java.math.BigInteger; import java.util.Scanner;public class Main {static Scanner cin = new Scanner(System.in);static public BigInteger[][] pow=new BigInteger[100005][15];static public int n,z,xx,yy;static public BigInteger ans;public static BigInteger cal(int x,int y){return pow[x][n].add(pow[y][n]).subtract(pow[z][n]);}public static void solve(int y){int l=1,r=y-1,mark=-1;while(l<=r){int mid=l+r>>1;if(cal(mid,y).compareTo(BigInteger.ZERO)<=0){mark=mid;l=mid+1;}elser=mid-1;}if(mark!=-1){if(ans.compareTo(cal(mark,y).abs())>0){ans=cal(mark,y).abs();xx=mark;yy=y;}if(mark<y-1){if(ans.compareTo(cal(mark+1,y).abs())>0){ans=cal(mark+1,y).abs();xx=mark+1;yy=y;}}}}public static void main(String []args){for(int i=1;i<=100000;i++){pow[i][0]=BigInteger.ONE;for(int j=1;j<=10;j++)pow[i][j]=pow[i][j-1].multiply(BigInteger.valueOf(i));}BigInteger inf=BigInteger.ONE;for(int i=1;i<=6;i++)inf=inf.multiply(pow[10][10]);int kase=cin.nextInt();while(kase-->0){n=cin.nextInt();z=cin.nextInt();ans=inf;for(int y=2;y<z;y++)solve(y);System.out.printf("%d %d ",xx,yy);System.out.println(ans);}} }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - Fermat‘s Optimization Problem(Java高精度运算+二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。