大数的加减乘除
高精度加法
public class 高精度加法 { public static void add(ArrayList<Integer> a,ArrayList<Integer> b){ int tmp = 0; ArrayList C = new ArrayList(); for (int i=0;i<a.size()||i<b.size();i++){ if(i<a.size()) tmp += a.get(i); if(i<b.size()) tmp += b.get(i); C.add(tmp%10); tmp = tmp/10; } if(tmp!=0){C.add(1);} for(int i=C.size()-1;i>=0;i--){ System.out.print(C.get(i)); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.next(); String B = sc.next(); ArrayList<Integer> a = new ArrayList(); ArrayList<Integer> b = new ArrayList(); for(int i=A.length()-1;i>=0;i--){ a.add(A.charAt(i)-'0'); } for (int j=B.length()-1;j>=0;j--){ b.add(B.charAt(j)-'0'); } add(a,b); } }
高精度减法
public class 高精度减法 { public static boolean cmp(ArrayList<Integer> a,ArrayList<Integer> b){ if(a.size()!=b.size()) return a.size()>b.size(); for(int i=0;i<a.size();i++){ if(a.get(i)!=b.get(i)) return a.get(i)>b.get(i); } return true; } public static ArrayList<Integer> jianfa(ArrayList<Integer> a, ArrayList<Integer> b){ ArrayList<Integer> C = new ArrayList<>(); for(int i=0,t=0;i<a.size();i++){ t = a.get(i)-t; if(i<b.size()) t -= b.get(i); C.add((t+10)%10); if(t<0) t=1; else t=0; } while (C.size()>0&&C.get(C.size()-1)==0) C.remove(C.size()-1); return C; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.next(); String B = sc.next(); ArrayList<Integer> a = new ArrayList(); ArrayList<Integer> b = new ArrayList(); for(int i=A.length()-1;i>=0;i--){ a.add(A.charAt(i)-'0'); } for (int j=B.length()-1;j>=0;j--){ b.add(B.charAt(j)-'0'); } ArrayList<Integer> C = new ArrayList<>(); if(cmp(a,b)){ C = jianfa(a,b); for (int i=C.size()-1;i>=0;i--){ System.out.print(C.get(i)); } }else{ System.out.print("-"); C = jianfa(b,a); for (int i=C.size()-1;i>=0;i--){ System.out.print(C.get(i)); } } } }
高精度乘法
public class 高精度乘法 { public static void mul(ArrayList<Integer> a,int b){ int t = 0; ArrayList<Integer> C = new ArrayList<>(); for(int i=0;i<a.size()||(t!=0);i++){ if(i<a.size())t += a.get(i)*b; C.add(t%10); t /=10; } for(int i=C.size()-1;i>=0;i--){ System.out.print(C.get(i)); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.nextLine(); ArrayList<Integer> a = new ArrayList(); int b; for(int i=A.length()-1;i>=0;i--){ a.add(A.charAt(i)-'0'); } b = sc.nextInt(); mul(a,b); } }
高精度除法
public class 高精度除法 { public static void chu(ArrayList<Integer> a,int b){ ArrayList<Integer> C = new ArrayList<>(); String t = "0"; for(int i=0;i<a.size();i++){ int tmp = (Integer.parseInt(t)*10)+a.get(i); C.add(tmp/b); t = (tmp%b)+""; } while (C.size()>0&&C.get(0)==0) C.remove(0); for (int i=0;i<C.size();i++){ System.out.print(C.get(i)); } System.out.println(); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.nextLine(); ArrayList<Integer> a = new ArrayList(); int b; for(int i=0;i<A.length();i++){ a.add(A.charAt(i)-'0'); } b = sc.nextInt(); chu(a,b); } }
前缀和
一维前缀和
public class 前缀和 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[] str1 = new int[N+1]; int[] str2 = new int[N+1]; for(int i=1;i<=N;i++){ str1[i]=sc.nextInt(); } for(int i=1;i<=N;i++){ str2[i] = str2[i-1]+str1[i]; } for(int i=0;i<M;i++){ int l = sc.nextInt(); int r = sc.nextInt(); System.out.println(str2[r]-str2[l-1]); } } }
二位前缀和
public class 二维前缀和 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int q = sc.nextInt(); int[][] str1 = new int[n+1][m+1]; int[][] str2 = new int[n+1][m+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ str1[i][j]=sc.nextInt(); } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ str2[i][j]=str2[i-1][j]+str2[i][j-1]-str2[i-1][j-1]+str1[i][j]; } } for(int i=0;i<q;i++){ int x1 = sc.nextInt(); int y1 = sc.nextInt(); int x2 = sc.nextInt(); int y2 = sc.nextInt(); System.out.println(str2[x2][y2]-str2[x1-1][y2]-str2[x2][y1-1]+str2[x1-1][y1-1]); } } }
差分
一维差分
public class 差分 { public static void insert(int l,int r,int c,int[] b){ b[l] += c; b[r+1] -=c; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[] a = new int[N+2]; int[] b = new int[N+2]; for(int i=1;i<=N;i++){ a[i]=sc.nextInt(); } for(int i=1;i<=N;i++){ insert(i,i,a[i],b);} for(int i=0;i<M;i++){ int l,r,c; l = sc.nextInt(); r = sc.nextInt(); c = sc.nextInt(); insert(l,r,c,b); } for(int i=1;i<=N;i++){ b[i] += b[i-1]; } for(int i=1;i<=N;i++){ System.out.print(b[i]+" "); } } }
二维差分
public class 差分矩阵 { public static void insert(int x1,int y1,int x2,int y2,int c,int[][] b){ b[x1][y1]+=c; b[x1][y2+1]-=c; b[x2+1][y1]-=c; b[x2+1][y2+1]+=c; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int q = sc.nextInt(); int[][] a = new int[n+2][m+2]; int[][] b = new int[n+2][m+2]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j] = sc.nextInt(); } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ insert(i,j,i,j,a[i][j],b); } } for(int i=0;i<q;i++){ int x1 = sc.nextInt(); int y1 = sc.nextInt(); int x2 = sc.nextInt(); int y2 = sc.nextInt(); int c = sc.nextInt(); insert(x1,y1,x2,y2,c,b); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ System.out.print(b[i][j]+" "); } System.out.println(); } } }
