?????? 2013 ???????? ??? Java ??B? ????

ACSolo  发布于5年前 238 阅读 评论(0)

From ?http://blog.csdn.net/liuqiyao_01/article/details/8757800

?????????????????????????????ll???????????????????????????????????c?????????????????????????????????????3??????????????Java???????Java?????????????????

??????????????


???:?????

?????

??????????5??????5^2
????????????????1^2 + 2^2 + 3^2 + 4^2 + ...


????????

1^2 + 2^2 + 3^2 + 4^2 + ... + x^2 = y^2

???????x,y???????????x=y=1 ????????????????

?????????????????(?????1?)?

???????x???????
????????????

??????

24 ??10?

???

????????????

???

  1. public class test1 {  
  2.     public static void main(String[] args) {  
  3.   
  4.         int [] num = new int[110];  
  5.         num[0] = 0;  
  6.         int i, j;  
  7.         for (i = 1; i < 100; i++) {  
  8.             num[i] = num[i - 1] + i * i;  
  9.             for (j = i; j * j <= num[i]; j++) {  
  10.                 if (j * j == num[i])  
  11.                     System.out.println(i + " " + j);  
  12.             }  
  13.         }  
  14.   
  15.     }  
  16. }  


????????

?????

?50????????4????1??5??1??5??
??????20???????????
???2,34,6,8 ???????
? 2,33,15,0 ??????????????????

???????????????????????????????2???

??????????????????

??????

50 ??16?

???

(PS:?????dp??????????????????????????01????????????DP?????01?????????11?????????????????????????????)
???????????dp??????????????????????????????????????dp??????????OJ?????????TLE??
dp??????????
for (i = 0; i < 4; i++) 
        for (j = 1; j <= 50; j++) 
                for (k = 400; k >= coin[i]; k--) 
                        dp[j][k] += dp[j-1][k-coin[i]];
??????????dp[j][k] ???????j?????k?????????

???

  1. public class test2 {  
  2.   
  3.     public static void main(String[] args) {  
  4.   
  5.         int[] coin = { 121020 };  //?????????? 5????  
  6.         int[][] dp = new int[55][440]; // dp[j][k] ?? ?????j?????k????????  
  7.         dp[0][0] = 1;  
  8.   
  9.         int i, j, k;  
  10.         for (i = 0; i < 4; i++) {  
  11.             for (j = 1; j <= 50; j++) {  
  12.                 for (k = 400; k >= coin[i]; k--) {  
  13.                     dp[j][k] += dp[j-1][k-coin[i]];  
  14.                 }  
  15.             }  
  16.         }  
  17.         System.out.println(dp[50][400]);  
  18.     }  
  19.   
  20. }  


?????????

?????
???1???60??????100???????????????
??????????60????????????????
??????1?6??????????1,2,3,4,5,6??????60?

??????????1?n????????????

??????????????????n=100, ?????
69720375229712477164533808935312303556800

????????BigInteger?????????

????????????????????????

  1. import java.math.BigInteger;  
  2. public class My1  
  3. {  
  4.     // ????1~n ?????????  
  5.     public static BigInteger f(int n)  
  6.     {  
  7.         int[] x = new int[n+1];  
  8.           
  9.         for(int i=1; i<=n; i++) x[i] = i;  
  10.           
  11.         for(int i=2; i<n; i++)  
  12.         {  
  13.             for(int j=i+1; j<=n; j++)  
  14.             {  
  15.                 if(x[j] % x[i]==0) _______________;   // ????  
  16.             }  
  17.         }  
  18.           
  19.         BigInteger m = BigInteger.ONE;  
  20.         for(int i=2; i<=n; i++)  
  21.         {  
  22.             m = m.multiply(BigInteger.valueOf(x[i]));   
  23.         }  
  24.           
  25.         return m;  
  26.               
  27.     }  
  28.       
  29.     public static void main(String[] args)  
  30.     {  
  31.         System.out.println(f(30));    
  32.     }  
  33. }  

??????

x[j] /= x[i]    18?

???

??????????????????????????????

????????

?????

???????6???????


???????2??????1???
??????????????????

???????????
x?????
x?????
y?????
y?????
z?????
z?????

???????????????3??????????
x ???x?????????
y ???y?????????
z ???z?????????

??????????2,3,4???


xyz ???????x,y,z 3???

???????
??????????????????
??????????????????3??????
????x??y??z??

??????????????
???

?????????????
x
??????
???

?????????????
zyx
??????
???

?????

xy
xxyyy
xyzzzzyyyxxx
xyyzzz
xyxyzzxyxyzz

?????

???
???
???
???
???

???

5??????????*5  ??25

???

???????????????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????
????????????????????????????????

???

  1. import java.util.Scanner;  
  2.   
  3. public class test4 {  
  4.   
  5.     public static void main(String[] args) {  
  6.   
  7.         int[] number = new int[24];  
  8.         int[] num = new int[24];  
  9.         int[] newnum = new int[24];  
  10.         int[] flag = { 1819 };  
  11.   
  12.         number[0] = number[1] = number[2] = number[3] = 1// x?? ??  
  13.         number[4] = number[5] = number[6] = number[7] = 2// x?? ??  
  14.         number[8] = number[9] = number[10] = number[11] = 3// y?? ??  
  15.         number[12] = number[13] = number[14] = number[15] = 4// y?? ??  
  16.         number[16] = number[17] = number[18] = number[19] = 5// z?? ??  
  17.         number[20] = number[21] = number[22] = number[23] = 6// z?? ??  
  18.   
  19.         // newnum = num;  
  20.         // for (int i = 0; i < 24; i++)  
  21.         // System.out.print(newnum[i] + " ");  
  22.   
  23.         String str;  
  24.         char[] ch = new char[1000];  
  25.         Scanner cin = new Scanner(System.in);  
  26.         while (cin.hasNext()) {  
  27.             str = cin.nextLine();  
  28.   
  29.             for (int i = 0; i < 24; i++)  
  30.                 num[i] = number[i];  
  31.             ch = str.toCharArray();  
  32.             int len = ch.length;  
  33.   
  34.             for (int i = 0; i < len; i++) {  
  35.                 for (int j = 0; j < 24; j++)  
  36.                     newnum[j] = num[j];  
  37.                 if (ch[i] == 'x') {  
  38.                     newnum[20] = num[10];  
  39.                     newnum[21] = num[8];  
  40.                     newnum[10] = num[19];  
  41.                     newnum[8] = num[18];  
  42.                     newnum[19] = num[13];  
  43.                     newnum[18] = num[15];  
  44.                     newnum[13] = num[20];  
  45.                     newnum[15] = num[21];  
  46.                     newnum[0] = num[2];  
  47.                     newnum[1] = num[0];  
  48.                     newnum[3] = num[1];  
  49.                     newnum[2] = num[3];  
  50.                 } else if (ch[i] == 'y') {  
  51.                     newnum[17] = num[1];  
  52.                     newnum[19] = num[3];  
  53.                     newnum[1] = num[21];  
  54.                     newnum[3] = num[23];  
  55.                     newnum[21] = num[5];  
  56.                     newnum[23] = num[7];  
  57.                     newnum[5] = num[17];  
  58.                     newnum[7] = num[19];  
  59.                     newnum[8] = num[10];  
  60.                     newnum[9] = num[8];  
  61.                     newnum[11] = num[9];  
  62.                     newnum[10] = num[11];  
  63.                 } else if (ch[i] == 'z') {  
  64.                     newnum[0] = num[8];  
  65.                     newnum[1] = num[9];  
  66.                     newnum[8] = num[7];  
  67.                     newnum[9] = num[6];  
  68.                     newnum[7] = num[12];  
  69.                     newnum[6] = num[13];  
  70.                     newnum[12] = num[0];  
  71.                     newnum[13] = num[1];  
  72.                     newnum[16] = num[18];  
  73.                     newnum[17] = num[16];  
  74.                     newnum[19] = num[17];  
  75.                     newnum[18] = num[19];  
  76.                 }  
  77.                 for (int j = 0; j < 24; j++)  
  78.                     num[j] = newnum[j];  
  79.             }  
  80.   
  81.             for (int i = 0; i < 3; i++) {  
  82.                 // System.out.println(num[flag[i]]);  
  83.                 if (num[flag[i]] == 1) {  
  84.                     System.out.print("?");  
  85.                 } else if (num[flag[i]] == 2) {  
  86.                     System.out.print("?");  
  87.                 } else if (num[flag[i]] == 3) {  
  88.                     System.out.print("?");  
  89.                 } else if (num[flag[i]] == 4) {  
  90.                     System.out.print("?");  
  91.                 } else if (num[flag[i]] == 5) {  
  92.                     System.out.print("?");  
  93.                 } else if (num[flag[i]] == 6) {  
  94.                     System.out.print("?");  
  95.                 }  
  96.             }  
  97.             System.out.println();  
  98.         }  
  99.   
  100.     }  
  101. }  

???????

?????

  ?4???????????????9?, 7?, 4?, 2?
  
  ?????? [9,0,0,0]?????????????????????

  ???????????????????????????????????????????????????????1????
  ???????????????????????????????????????
  ?????????????????????
  ?????????????
  ???????????????????-1?

???
???
9,0,0,0
?????
0

???
6,0,0,3
?????
-1

???
7,2,0,0
?????
2

?????

2 4 1 2
3 1 3 2
2 6 1 0

?????

6
9
7

???

3?????   ????*10.333   ??31

???

????????bfs??????????????????num??????????????????????????????????????????????????????????????????????????

???

  1. package test;  
  2.   
  3. import java.util.LinkedList;  
  4. import java.util.Queue;  
  5. import java.util.Scanner;  
  6.   
  7. class state {  
  8.     int a, b, c, d, step;  
  9.   
  10.     state() {  
  11.         step = 0;  
  12.     }  
  13.   
  14.     state(int x, int y, int z, int q, int p) {  
  15.         a = x;  
  16.         b = y;  
  17.         c = z;  
  18.         d = q;  
  19.         step = p;  
  20.     }  
  21. }  
  22.   
  23. public class test5 {  
  24.   
  25.     static int inf = 0x3f3f3f3f;  
  26.     static int[] full = { 9742 };  
  27.     static int[][][][] num = new int[10][8][5][3];  
  28.     static Queue<state> queue = new LinkedList<state>();  
  29.   
  30.     public static void judge(int a, int b, int c, int d, int step) {  
  31.   
  32.         if (num[a][b][c][d] > step + 1) { // ????????  
  33.             num[a][b][c][d] = step + 1;  
  34.             state tmp = new state(a, b, c, d, step + 1);  
  35.             queue.add(tmp); // ????????  
  36.         }  
  37.     }  
  38.   
  39.     public static void main(String[] args) {  
  40.   
  41.         queue.clear();  
  42.   
  43.         int i, j, k, q;  
  44.         for (i = 0; i < 10; i++)  
  45.             for (j = 0; j < 8; j++)  
  46.                 for (k = 0; k < 5; k++)  
  47.                     for (q = 0; q < 3; q++)  
  48.                         num[i][j][k][q] = inf;  
  49.         num[9][0][0][0] = 0;  
  50.         state sta = new state(90000);  
  51.         queue.add(sta);  
  52.   
  53.         while (queue.size() > 0) { // bfs  
  54.             sta = queue.poll();  
  55.             int[] tmpnum = { sta.a, sta.b, sta.c, sta.d, sta.step };  
  56. //          System.out.println(tmpnum[0] + " " + tmpnum[1] + " " + tmpnum[2]  
  57. //                  + " " + tmpnum[3] + " " + tmpnum[4]);  
  58.             for (i = 0; i < 4; i++) {  
  59.   
  60.                 int tmpi = tmpnum[i]; // ???i?  
  61. /////----------------------------------?i??------------------------------------------//////  
  62.                 int cha = full[i] - tmpnum[i];  
  63.                 tmpnum[i] = full[i];  
  64.                 judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// ????????  
  65.                 tmpnum[i] = tmpi; // ???i??  
  66.   
  67.                 if (tmpnum[i] == 0)  
  68.                     continue;  
  69.                   
  70. /////-----------------------------------?i??-----------------------------------------//////  
  71.                 tmpnum[i] = 0// ??i???0  
  72.                 judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// ????????  
  73.                 tmpnum[i] = tmpi; // ???i??  
  74.                   
  75. /////---------------------------------?i??j-------------------------------------------//////  
  76.                 for (j = 0; j < 4; j++) { // ????i??????j???  
  77.                     if (j == i || tmpnum[j] == full[j])  
  78.                         continue// ???j??????continue  
  79.                     int tmpj = tmpnum[j];  
  80.                     cha = full[j] - tmpnum[j]; // ?j???????????  
  81.                     if (tmpnum[i] >= cha) { // ??tmpnum[i]???????????  
  82.                         tmpnum[i] -= cha;  
  83.                         tmpnum[j] += cha;  
  84.                     } else { // ??????  
  85.                         tmpnum[j] += tmpnum[i];  
  86.                         tmpnum[i] = 0;  
  87.                     }  
  88.                     judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// ????????  
  89.                     tmpnum[i] = tmpi; // ???i??  
  90.                     tmpnum[j] = tmpj;// ???j??  
  91.   
  92.                 }  
  93.             }  
  94.         }  
  95.   
  96.         Scanner cin = new Scanner(System.in);  
  97.         while (cin.hasNext()) {  
  98.             int a, b, c, d;  
  99.             a = cin.nextInt();  
  100.             b = cin.nextInt();  
  101.             c = cin.nextInt();  
  102.             d = cin.nextInt();  
  103.   
  104.             if (a > full[0] || b > full[1] || c > full[2] || d > full[3]  
  105.                     || num[a][b][c][d] == inf) {  
  106.                 System.out.println("-1");  
  107.                 continue;  
  108.             }  
  109.             System.out.println(num[a][b][c][d]);  
  110.         }  
  111.   
  112.     }  
  113. }  

 
 
 
 
Vote: I like it 0 Vote: I do not like it

Reply: Reply it before Login