这次笔试给我的教训是很多题目不要想当然，也不要想太多。像第一题、第三题，想太多就是问题；像最后一题，如果不是想太多也不会浪费太多时间。然后就是很多细节，比如并查集的细节就没有太了解，导致花费了很多不必要的功夫。
第一题：
我发现我每次笔试的问题就是想太多……实际上这个题最简单的方法就可以做出来。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] array = new int[n][2];
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
array[i][0] = x;
array[i][1] = y;
}
sc.close();
int res = maxCoin(m, array);
System.out.print(res);
}
private static int maxCoin(int m, int[][] array) {
if (m == 0 || array.length == 0)
return 0;
int total_cost = 0;
int total_coin = 0;
for (int i = 0; i < array.length; i++) {
if (array[i][0] / m > array[i][1]) {//只要打这个怪是赚的就打
total_cost += array[i][0];
total_coin += array[i][1];
}
}
if (total_cost % m == 0) {
total_coin -= (total_cost / m);
} else {
total_coin -= (total_cost / m + 1);
}
return total_coin;
}
第二题：
纯数学题，算就算了好久，不知道做的对不对。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
sc.close();
double res = compute(A, B, C);
System.out.println(res);
}
private static double compute(int a, int b, int c) {
if (a == 0 || a <= 2 * b * c)
return 0;
double v = 2 * Math.sqrt(a * a - 2 * a * b);
double y1 = (2 * a + v) / (2 * b * b * 1.0);
double y2 = (2 * a - v) / (2 * b * b * 1.0);
double size = Math.abs(helper(y1, a, b, c) - helper(y2, a, b, c));
return size;
}
private static double helper(double y, int a, int b, int c) {
return (y * y / (2 * b)) - (c * y / b) - (y * y * y / (6 * a));
}
第三题：
多想了公式算错了可还行……
private static final int mod = 100003;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();//2
int n = sc.nextInt();//3
sc.close();
int res = chongtu(m, n);
System.out.println(res);
}
private static int chongtu(int m, int n) {
if (m == 0 || n == 0)
return 0;
int res = binaryPow(m, n) - m % mod * binaryPow(m - 1, n - 1);//所有方法减去完全不冲突的方法
return res;
}
private static int binaryPow(int m, int n) {
int ans = 1;
while (n > 0) {
if ((n & 1) != 0) {
ans = ans * m % mod;//快速幂所有部分都要%mod，避免溢出
}
m = m * m % mod;
n = n >> 1;
}
return ans;
}
第四题：
第五题：
最后一秒写出来没来得及粘上去啊啊啊！！！！
哭唧唧……
private static ArrayList<Integer> count;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
int[][] array = new int[n][2];
Set<Integer> set = new HashSet<>();
for (int j = 0; j < n; j++) {
int x = sc.nextInt();
int y = sc.nextInt();
set.add(x);
set.add(y);
array[j][0] = x;
array[j][1] = y;
}
int res = pengyou(set.size(), array);
System.out.print(res);
}
sc.close();
}
private static int pengyou(int n, int[][] array) {
if (n < 2)
return n;
boolean[][] quan = new boolean[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(quan[i], false);
quan[i][i] = true;
}
for (int[] ints : array) {
int x = ints[0] - 1;
int y = ints[1] - 1;
quan[x][y] = true;
quan[y][x] = true;
}
boolean[] hasVisit = new boolean[n];
Arrays.fill(hasVisit, false);
count = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (!hasVisit[i]) {//DFS
hasVisit[i] = true;
dfs(quan, i, hasVisit, 1);
}
}
int max = 1;
for (int i = 0; i < count.size(); i++) {
max = Math.max(max, count.get(i));
}
return max;
}
private static void dfs(boolean[][] quan, int x, boolean[] hasVisit, int sum) {
boolean flag = true;
for (int i = 0; i < quan.length; i++) {
if (quan[i][x] && !hasVisit[i]) {
flag = false;
hasVisit[i] = true;
sum++;
dfs(quan, i, hasVisit, sum);
}
}
if (flag)
count.add(sum);
}