藍橋杯歷年真題及決議.
目錄
- 藍橋杯歷年真題及決議.
- A：三角形面積（難度：★）.
- 分析：
- AC代碼：
- B：最大乘積（難度：★★）.
- 分析：
- AC代碼：
- C：全排列（難度：★）.
- 分析：
- AC代碼：
- D：整理玩具（難度：★★★）.
- 分析：
- AC代碼：
- E：版本分支（難度：★★★★）.
- 分析：
- AC代碼：
- F：防御力（難度：★★★★★）.
- 分析：
- AC代碼：
A：三角形面積（難度：★）.
已知三角形三個頂點在直角坐標系下的坐標分別為：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)
求該三角形的面積，
注意，要提交的是一個小數形式表示的浮點數，
要求精確到小數后3位，如不足3位，需要補零，
分析：
直接帶入海倫公式即可，
p=(a+b+c)/2;
ans=sqrt(p(p-a)(p-b)(p-c));
AC代碼：
public class Main {
public static void main(String[] args) {
double a=Math.sqrt((6.4-2.3)*(6.4-2.3)+(3.1-2.5)*(3.1-2.5));
double b=Math.sqrt((6.4-5.1)*(6.4-5.1)+(3.1-7.2)*(3.1-7.2));
double c=Math.sqrt((5.1-2.3)*(5.1-2.3)+(7.2-2.5)*(7.2-2.5));
double p=(a+b+c)/2;
System.out.println(String.format("%.3f", Math.sqrt(p*(p-a)*(p-b)*(p-c))));
}
}
B：最大乘積（難度：★★）.
把 1~9 這9個數字分成兩組，中間插入乘號，
有的時候，它們的乘積也只包含1~9這9個數字，而且每個數字只出現1次，
比如：
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
…
符合這種規律的算式還有很多，請你計算在所有這些算式中，乘積最大是多少？
注意，需要提交的是一個整數，表示那個最大的積，不要填寫任何多余的內容，
（只提交乘積，不要提交整個算式）
分析：
全排列出九個數字的所有排列順序
對每一種排列進行列舉分割成兩部分
對兩部分的乘積取結果
檢查乘積結果是否符合條件
如果符合條件即更新全域變數ans
AC代碼：
import java.util.HashSet;
//求最大值，不是求符合條件的種數
public class Main{
public static long arr[]={1,2,3,4,5,6,7,8,9};
public static long ans=0;
public static long tolong(int begin,int end){
long cur=0;
for(int i=begin;i<=end;i++){
cur*=10;
cur+=arr[i];
}
return cur;
}
public static void check(){
for(int i=0;i<8;i++){
long x=tolong(0,i);
long y=tolong(i+1,8);
long cur=x*y;
if(cur<123456789)continue;
HashSet<Integer> set=new HashSet<Integer>();
while(cur>0){
set.add((int) (cur%10));
cur/=10;
}
if(set.size()==9&&!set.contains(0)){
ans=Math.max(ans, x*y);
}
}
}
public static void qpl(int k){
if(k>=arr.length){
check();
}else{
for(int i=k;i<arr.length;i++){
long t=arr[i];arr[i]=arr[k];arr[k]=t;
qpl(k+1);
t=arr[i];arr[i]=arr[k];arr[k]=t;
}
}
}
public static void main(String[] args) {
qpl(0);
System.out.println(ans);
}
}
C：全排列（難度：★）.
對于某個串，比如：“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");
}
}
請注意：只需要填寫劃線部分缺少的內容，不要抄寫已有的代碼或符號，
分析：
觀察題目發現是個全排列問題，
填空部分是全排列的回溯部分
只需要根據函式體內上半部分交換的原則重新進行回溯回去即可，
AC代碼：
不能交題，但是運行結果是正確的
public class Main {
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");
}
}
D：整理玩具（難度：★★★）.
小明有一套玩具，一共包含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，否則按無效代碼處理，
分析：
由題目可以確定數字相同的玩具放在了一起，
所以我們可以定義一個陣列用來存放當前資料的資訊，
我們采用二維陣列，
每一行代表當前編號玩具的資訊
第一串列示當前編號玩具的占地面積
第二串列示當前編號玩具的占地右下角的橫坐標
第三串列示當前編號玩具的占地右下角的縱坐標
第四串列示當前編號玩具的占地左上角的橫坐標
第五串列示當前編號玩具的占地左上角的縱坐標
所以應該有
-> buf[i][0]!=0&&buf[i][0]!=(buf[i][1]-buf[i][3]+1)*(buf[i][2]-buf[i][4]+1)
恒成立，
AC代碼：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int t=scanner.nextInt();
while(t-->0){
int n=scanner.nextInt(),m=scanner.nextInt();
char c[][]=new char[n][m];
int buf[][]=new int[10][5];
for(int i=0;i<10;i++){
buf[i][0]=0;
buf[i][1]=-1;
buf[i][2]=-1;
buf[i][3]=999;
buf[i][4]=999;
}
for(int i=0;i<n;i++){
c[i]=scanner.next().toCharArray();
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
buf[c[i][j]-'0'][0]++;
buf[c[i][j]-'0'][1]=Math.max(buf[c[i][j]-'0'][1], i);
buf[c[i][j]-'0'][2]=Math.max(buf[c[i][j]-'0'][2], j);
buf[c[i][j]-'0'][3]=Math.min(buf[c[i][j]-'0'][3], i);
buf[c[i][j]-'0'][4]=Math.min(buf[c[i][j]-'0'][4], j);
}
}
boolean ok=true;
for(int i=0;i<10;i++){
if(buf[i][0]!=0&&buf[i][0]!=(buf[i][1]-buf[i][3]+1)*(buf[i][2]-buf[i][4]+1)){
ok=false;
}
}
System.out.println(ok?"YES":"NO");
}
}
}
E：版本分支（難度：★★★★）.
小明負責維護公司一個奇怪的專案，這個專案的代碼一直在不斷分支(branch)但是從未發生過合并(merge)，
現在這個專案的代碼一共有N個版本，編號1~N，其中1號版本是最初的版本，
除了1號版本之外，其他版本的代碼都恰好有一個直接的父版本；即這N個版本形成了一棵以1為根的樹形結構，
如下圖就是一個可能的版本樹：
現在小明需要經常檢查版本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，否則按無效代碼處理，
分析：
我才用并查集的思路，
用一個陣列儲存該節點的父節點，
當詢問祖先關系是，向上查找父節點，
時間復雜度較高
通過資料50%
AC代碼：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),q=sc.nextInt(),u,v;
int pa[]=new int[n+1];
for(int i=1;i<n;i++){
u=sc.nextInt();
v=sc.nextInt();
pa[v]=u;
}
for(int i=0;i<q;i++){
u=sc.nextInt();
v=sc.nextInt();
boolean is=false;
while(v!=0){
if(v==u){
is=true;
break;
}
v=pa[v];
}
System.out.println(is?"YES":"NO");
}
}
}
F：防御力（難度：★★★★★）.
小明最近在玩一款游戲，對游戲中的防御力很感興趣，
我們認為直接影響防御的引數為“防御性能”，記作d，而面板上有兩個防御值A和B，與d成對數關系，A=2^d， B=3^d（注意任何時候上式都成立），
在游戲程序中，可能有一些道具把防御值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，否則按無效代碼處理，
分析：
題目要求防御性能最好，
而且AB的先后順序已經固定，
我們只需要排好A和B兩序列內部的排列順序即可
對于A序列，對2取log，如果要使最終防御性能最好，
那么就要先使用增益效果最差的道具，把增益效果好的道具放到后邊以獲得最大漲幅
對于B序列，對3取log，如果要使最終防御性能最好
那么就要先使用增益效果最好的道具，以便在初期能獲得最大漲幅，
AC代碼：
import java.util.Scanner;
public class Main{
public static int n1, n2;
public static double arr1[];
public static double arr2[];
public static int buf1[];
public static int buf2[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n1 = sc.nextInt();
n2 = sc.nextInt();
arr1 = new double[n1]; // arr儲存資料，buf做標記
arr2 = new double[n2];
buf1 = new int[n1];
buf2 = new int[n2];
sc.nextLine();
int x;
for (int i = 0; i < arr1.length; i++) {
x = sc.nextInt();
arr1[i] = Math.log(x) / Math.log(2); // 儲存資料對2取log
}
sc.nextLine();
for (int i = 0; i < arr2.length; i++) {
x = sc.nextInt();
arr2[i] = Math.log(x) / Math.log(3); // 儲存資料對3取log
}
sc.nextLine();
String str = sc.nextLine();
check(str); // 對資料處理
}
public static void check(String s) // 每遞回一次處理完字串開頭的所有相同字符
{
if (s.length() != 0) // 字串長度不為零
{
int x = sub(s); // 處理開頭的所有相同字符
s = s.substring(x); // 將沒有被處理的字符截取下來
check(s); // 遞回
} else {
System.out.println("E"); // 字串長度為零，輸出E
}
}
public static int sub(String s) {
int i = 0;
if (s.charAt(0) == '0') // 如果第一個字符為0
{
while (s.length() > i && s.charAt(i) == '0') // i++，直到遇見不相同字符跳出
i++;
int ans[] = new int[i]; // 建立小的答案陣列，儲存前i個答案
for (int j = 0; j < i; j++) // ans指的是答案的下標
{
ans[j] = getmin(); // 回圈i次，獲取i個答案
}
int ii = i; // 定義ii控制回圈次數
while (ii > 0) {
ii--;
double min = Integer.MAX_VALUE; // 定義最小值
int p = -1; // 定義指標，指向ans中最小的值
for (int j = 0; j < ans.length; j++) // 回圈ans找min
{
if (arr1[ans[j]] < min) // 找最小值取代min，p指向新值
{
min = arr1[ans[j]];
p = ans[j];
}
}
arr1[p] = Integer.MAX_VALUE; // 將找過的值處理掉
p += 1; // p指的下標，p+1指的第幾個數
System.out.println("A" + p); // 輸出一個答案
}
} else { // 跟上邊一樣，只是物件變成了第一個字符為1，求最大值
while (s.length() > i && s.charAt(i) == '1')
i++;
int ans[] = new int[i];
for (int j = 0; j < i; j++) {
ans[j] = getmax();
}
int ii = i;
while (ii > 0) {
ii--;
double max = -1;
int p = -1;
for (int j = 0; j < ans.length; j++) {
if (arr2[ans[j]] > max) {
max = arr2[ans[j]];
p = ans[j];
}
}
arr2[p] = -1;
p += 1;
System.out.println("B" + p);
}
}
return i; // i是處理過的長度，提供給check函式，對字串剪切
}
public static int getmin() {
double x = Integer.MAX_VALUE;
int p = -1;
for (int i = 0; i < arr1.length; i++) {
if (buf1[i] == 0) {
if (x > arr1[i]) {
x = arr1[i];
p = i;
}
}
}
buf1[p] = 1;
return p;
}
public static int getmax() {
double x = -1;
int p = -1;
for (int i = 0; i < arr2.length; i++) {
if (buf2[i] == 0) {
if (x < arr2[i]) {
x = arr2[i];
p = i;
}
}
}
buf2[p] = 1;
return p;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/200045.html
標籤：其他