題目1：三角形面積
已知三角形三個頂點在直角坐標系下的坐標分別為：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)
求該三角形的面積，
注意，要提交的是一個小數形式表示的浮點數，
要求精確到小數后3位，如不足3位，需要補零，
思路：
把這個三個點構造成一個矩形，入下圖，通過觀察不難發現，只需用矩形面積減去四周的三角形面積就可得出所求三角形面積，
public static void main(String[] args) {
double c = 6.4 - 2.3;
double h = 7.2 - 2.5;
double s = c * h - c * (3.1 - 2.5) / 2 - (7.2 - 3.1) * (6.4 - 5.1) / 2 - h * (5.1 - 2.3) / 2;
System.out.println(s); // 8.795000000000002
}
題目2：最大乘積
把 1~9 這9個數字分成兩組，中間插入乘號，
有的時候，它們的乘積也只包含1~9這9個數字，而且每個數字只出現1次，
比如：
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
…
符合這種規律的算式還有很多，請你計算在所有這些算式中，乘積最大是多少？
注意，需要提交的是一個整數，表示那個最大的積，不要填寫任何多余的內容，
（只提交乘積，不要提交整個算式）
思路：全排列
這題只要簡單的全排列一下，然后檢測就可得出結果，
public class Main {
static int[] a = new int[]{1,2,3,4,5,6,7,8,9};
static int ans = 0;
public static void main(String[] args) {
f(a, 0);
System.out.println(ans); // 876943125
}
private static void f(int[] a, int k) {
if(k == 9) {
check();
return;
}
for(int i = k; i < 9; i++) {
int t = a[i];
a[i] = a[k];
a[k] = t;
f(a, k + 1);
t = a[i];
a[i] = a[k];
a[k] = t;
}
}
private static void check() {
int[] b = new int[9];
b[8] = 9;
int bz = 10;
for(int i = 7; i >= 0; i--) {
b[i] = b[i + 1] + a[i] * bz;
bz *= 10;
}
int q = 0;
for(int i = 0; i < 8; i++) {
q = q * 10 + a[i];
int z = q * b[i + 1];
check1(z);
}
}
private static void check1(int z) {
boolean[] is = new boolean[10];
int c = z;
while(z > 0) {
int cur = z % 10;
if(!is[cur] && cur >= 1 && cur <= 9) is[cur] = true;
else return;
z /= 10;
}
ans = Math.max(ans, c);
}
}
題目3：全排列
對于某個串，比如：“1234”，求它的所有全排列，
并且要求這些全排列一定要按照字母的升序排列，
對于“1234”，應該輸出(一共4!=24行)：
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
下面是實作程式，請仔細分析程式邏輯，并填寫劃線部分缺少的代碼，
// 輪換前k個，再遞回處理
import java.util.*;
public class A
{
static void permu(char[] data, int cur){
if(cur==data.length-1){
System.out.println(new String(data));
return;
}
? for(int i=cur; i<data.length; i++){
? char tmp = data[i];
? for(int j=i-1; j>=cur; j–) data[j+1] = data[j];
? data[cur] = tmp;
? permu(data, cur+1);
? tmp = data[cur];
? __________________________________________ ;
? data[i] = tmp;
? }
}
static void permu(String x){
permu(x.toCharArray(),0);
}
public static void main(String[] args){
permu(“1234”);
}
}
請注意：只需要填寫劃線部分缺少的內容，不要抄寫已有的代碼或符號，
代碼：
public class A
{
static void permu(char[] data, int cur){
if(cur==data.length-1){
System.out.println(new String(data));
return;
}
for(int i=cur; i<data.length; i++){
char tmp = data[i];
for(int j=i-1; j>=cur; j--) data[j+1] = data[j];
data[cur] = tmp;
permu(data, cur+1);
tmp = data[cur];
for(int j = cur-1; j >= i; j--) data[j + 1] = data[j];
// __________________________________________ ;
data[i] = tmp;
}
}
static void permu(String x){
permu(x.toCharArray(),0);
}
public static void main(String[] args){
permu("1234");
}
}
題目4：整理玩具
小明有一套玩具，一共包含NxM個部件，這些部件擺放在一個包含NxM個小格子的玩具盒中，每個小格子中恰好擺放一個部件，
每一個部件上標記有一個0~9的整數，有可能有多個部件標記相同的整數，
小明對玩具的擺放有特殊的要求：標記相同整數的部件必須擺在一起，組成一個矩形形狀，
如以下擺放是滿足要求的：
00022
00033
44444
12244
12244
12233
01234
56789
以下擺放不滿足要求：
11122
11122
33311
111111
122221
122221
111111
11122
11113
33333
給出一種擺放方式，請你判斷是否符合小明的要求，
輸入
輸入包含多組資料，
第一行包含一個整數T，代表資料組數， (1 <= T <= 10)
以下包含T組資料，
每組資料第一行包含兩個整數N和M， (1 <= N, M <= 10)
以下包含N行M列的矩陣，代表擺放方式，
輸出
對于每組資料，輸出YES或者NO代表是否符合小明的要求，
【樣例輸入】
3
3 5
00022
00033
44444
3 5
11122
11122
33311
2 5
01234
56789
【樣例輸出】
YES
NO
YES
資源約定：
峰值記憶體消耗（含虛擬機） < 256M
CPU消耗 < 1000ms
請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多余內容，
所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，
不要使用package陳述句，不要使用jdk1.7及以上版本的特性，
主類的名字必須是：Main，否則按無效代碼處理，
思路：
遍歷整個矩陣，每遇到一個數，就檢查一遍是否符合要求，然后將這個數標記為已檢查（其它地方不能在出現這個數），
演算法：
- 找到與這個數相同的最大的長寬
- 在這個矩陣里檢查是否存在其它數字，如果存在則回傳false
- 當這個矩陣都檢查完之后還沒有回傳false，則回傳true
- 在檢查的時候將所有檢查了的點都打上記號
public class Main {
private static int n;
private static int m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i = 0; i < t; i++) {
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine();
char[][] a = new char[n][m];
for(int j = 0; j < n; j++) {
a[j] = sc.nextLine().toCharArray();
}
System.out.println(check(a));
}
}
private static boolean check(char[][] a) {
boolean[][] is = new boolean[n][m];
boolean[] isc = new boolean[10];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!is[i][j]) {
if(isc[a[i][j] - '0']) return false;
isc[a[i][j] - '0'] = true;
if(check(is, a, i, j)) return false;
}
}
}
return true;
}
public static boolean check(boolean[][] is, char[][] a, int x, int y) {
char t = a[x][y];
int c = y;
while(c < m && a[x][c] == t) c++;
int h = x;
while(h < n && a[h][y] == t) h++;
for(int i = x; i < h; i++) {
for(int j = y; j < c; j++) {
is[i][j] = true;
if(a[i][j] != t) return true;
}
}
return false;
}
}
題目5：版本分支
小明負責維護公司一個奇怪的專案，這個專案的代碼一直在不斷分支(branch)但是從未發生過合并(merge)，
現在這個專案的代碼一共有N個版本，編號1~N，其中1號版本是最初的版本，
除了1號版本之外，其他版本的代碼都恰好有一個直接的父版本；即這N個版本形成了一棵以1為根的樹形結構，
如下圖就是一個可能的版本樹：
1
/
2 3
| /
5 4 6
現在小明需要經常檢查版本x是不是版本y的祖先版本，你能幫助小明嗎？
輸入
第一行包含兩個整數N和Q，代表版本總數和查詢總數，
以下N-1行，每行包含2個整數u和v，代表版本u是版本v的直接父版本，
再之后Q行，每行包含2個整數x和y，代表詢問版本x是不是版本y的祖先版本，
對于30%的資料，1 <= N <= 1000 1 <= Q <= 1000
對于100%的資料，1 <= N <= 100000 1 <= Q <= 100000
輸出
對于每個詢問，輸出YES或NO代表x是否是y的祖先，
【樣例輸入】
6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4
【樣例輸出】
YES
YES
NO
NO
NO
資源約定：
峰值記憶體消耗（含虛擬機） < 256M
CPU消耗 < 1000ms
請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多余內容，
所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，
不要使用package陳述句，不要使用jdk1.7及以上版本的特性，
主類的名字必須是：Main，否則按無效代碼處理，
思路：時間上會超
通過輸入的資料生成一棵樹，每個子節點都指向它的父節點，執行查找操作的時候就通過子節點往上找，看是否找得到父節點，
但當整棵樹形成一條鏈時（當這棵樹的高度過高時），會超時
我也在網上查了一些題解，大多數在空間上回超，
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] tree = new int[n + 1];
tree[1] = 1;
int q = sc.nextInt();
int x, y, t;
for(int i = 1; i < n; i++) {
x = sc.nextInt();
y = sc.nextInt();
tree[y] = x;
}
for(int i = 0; i < q; i++) {
x = sc.nextInt();
y = sc.nextInt();
if(x == 1) System.out.println("YES");
else {
while(y != 1) {
if(y == x){
System.out.println("YES");
break;
}
y = tree[y];
}
if(y == 1) System.out.println("NO");
}
}
}
}
題目6：防御力
小明最近在玩一款游戲，對游戲中的防御力很感興趣，
我們認為直接影響防御的引數為“防御性能”，記作d，而面板上有兩個防御值A和B，與d成對數關系，A=2d，B=3d（注意任何時候上式都成立），
在游戲程序中，可能有一些道具把防御值A增加一個值，有另一些道具把防御值B增加一個值，
現在小明身上有n1個道具增加A的值和n2個道具增加B的值，增加量已知，
現在已知第i次使用的道具是增加A還是增加B的值，但具體使用那個道具是不確定的，請找到一個字典序最小的使用道具的方式，使得最終的防御性能最大，
初始時防御性能為0，即d=0，所以A=B=1，
【輸入格式】
輸入的第一行包含兩個數n1,n2，空格分隔，
第二行n1個數，表示增加A值的那些道具的增加量，
第三行n2個數，表示增加B值的那些道具的增加量，
第四行一個長度為n1+n2的字串，由0和1組成，表示道具的使用順序，0表示使用增加A值的道具，1表示使用增加B值的道具，輸入資料保證恰好有n1個0，n2個1，
【輸出格式】
對于每組資料，輸出n1+n2+1行，前n1+n2行按順序輸出道具的使用情況，若使用增加A值的道具，輸出Ax，x為道具在該類道具中的編號（從1開始），若使用增加B值的道具則輸出Bx，最后一行輸出一個大寫字母E，
【樣例輸入1】
1 2
4
2 8
101
【樣例輸出1】
B2
A1
B1
E
【樣例輸入2】
3 0
7 11 13
000
【樣例輸出2】
A1
A2
A3
E
【樣例說明】
對于第一組測驗資料，操作程序如下：
操作 d A B
初始 0 1 1
B2 2 4 9
A1 3 8 27
B1 log3(29) 2^(log3(29)) 29
可以證明，這個值是最大的，
對于第二組測驗資料，可見無論用什么順序，A最后總為32，即d總為5，B總為243，
【資料規模】
對于20%的資料，字串長度<=10000；
對于70%的資料，字串長度<=200000；
對于100%的資料，字串長度<=2000000，輸入的每個增加值不超過2^30，
資源約定：
峰值記憶體消耗（含虛擬機） < 256M
CPU消耗 < 1000ms
請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多余內容，
所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，
不要使用package陳述句，不要使用jdk1.7及以上版本的特性，
主類的名字必須是：Main，否則按無效代碼處理，
思路：貪心
貪心的證明并不是那么好證明，簡單寫了一下，把B從大到小排，把A從小到達大排就是答案了，
public class Main {
public static void main(String[] args) {
long start = System.currentTimeMillis();
Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt();
int n2 = sc.nextInt();
int[][] a = new int[n1][2];
int[][] b = new int[n2][2];
for(int i = 0; i < n1; i++) {
a[i][0] = sc.nextInt();
a[i][1] = i + 1;
}
sc.nextLine();
for(int i = 0; i < n2; i++) {
b[i][0] = sc.nextInt();
b[i][1] = i + 1;
}
sc.nextLine();
String s = sc.nextLine();
Arrays.sort(a, (o1, o2) -> {
double o11 = Math.log(o1[0] + 1) / Math.log(2);
double o22 = Math.log(o2[0] + 1) / Math.log(2);
if(o11 == o22) return 0;
else if(o11 > o22) return 1;
else return -1;
});
Arrays.sort(b, (o1, o2) -> {
double o11 = Math.log(o1[0] + 1) / Math.log(3);
double o22 = Math.log(o2[0] + 1) / Math.log(3);
if(o11 == o22) return 0;
else if(o11 > o22) return -1;
else return 1;
});
int n = n1 + n2;
StringBuilder[] ans = new StringBuilder[n];
int i1 = 0;
int i2 = 0;
for(int i = 0; i < n; i++) {
ans[i] = new StringBuilder();
if(s.charAt(i) == '0') {
ans[i].append("A").append(a[i1++][1]);
}else {
ans[i].append("B").append(b[i2++][1]);
}
}
for (StringBuilder x :
ans) {
System.out.println(x);
}
System.out.println("E");
System.out.println(System.currentTimeMillis() - start);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/215237.html
標籤：其他
上一篇：求凸包面積