2016年第七屆藍橋杯java B組省賽試題
- 1-3仙蚜、結(jié)果填空
- 4-5匙姜、代碼填空
- 6-7、結(jié)果填空
- 8-10番宁、程序設計
1.煤球數(shù)目 (結(jié)果填空)
有一堆煤球元莫,堆成三角棱錐形。具體:
第一層放1個贝淤,
第二層3個(排列成三角形)柒竞,
第三層6個(排列成三角形)政供,
第四層10個(排列成三角形)播聪,
....
如果一共有100層,共有多少個煤球布隔?
請?zhí)畋硎久呵蚩倲?shù)目的數(shù)字离陶。
注意:你提交的應該是一個整數(shù),不要填寫任何多余的內(nèi)容或說明性文字衅檀。
示例代碼:
public class Main1 {
public static void main(String[] args) {
int a[] = new int[101];
for (int i = 1; i <= 100; i++) {
a[i] = i * (i + 1) / 2;
}
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum = sum + a[i];
}
System.out.println(sum);
}
}
答案:
171700
2招刨、生日蠟燭 (結(jié)果填空)
某君從某年開始每年都舉辦一次生日party,并且每次都要吹熄與年齡相同根數(shù)的蠟燭哀军。
現(xiàn)在算起來沉眶,他一共吹熄了236根蠟燭。
請問杉适,他從多少歲開始過生日party的谎倔?請?zhí)顚懰_始過生日party的年齡數(shù)。
注意:你提交的應該是一個整數(shù)猿推,不要填寫任何多余的內(nèi)容或說明性文字片习。
答案:
26
參考代碼:
public class Main1 {
public static void main(String[] args) {
//i代表舉辦了i個生日party
for (int startAge = 1; startAge < 1000; startAge++) {
int sum = 0;
for (int i = 0; i < 100; i++) {
sum += startAge + i;
if (sum == 236) {
System.out.println("startAge = " + startAge);
}
}
}
}
}
設:x為開始過生日的年齡數(shù),一共過了n個生日
優(yōu)化代碼,此時復雜度為n;
public class Main {
public static void main(String[] args) {
for (int i = 1; i < 20; i++) {
int isDivisible = (472+i-i*i) % (2*i);
if (isDivisible==0){
System.out.printf("年齡:"+(472+i-i*i) / (2*i));
System.out.printf(",過了%d個生日\n", i);
}
}
}
}
3蹬叭、湊算式 (結(jié)果填空)
這個算式中A-I代表1-9的數(shù)字藕咏,不同的字母代表不同的數(shù)字。
比如:
6+8/3+952/714 就是一種解法秽五,
5+3/1+972/486 是另一種解法孽查。
這個算式一共有多少種解法?
注意:你提交應該是個整數(shù)坦喘,不要填寫任何多余的內(nèi)容或說明性文字卦碾。
import java.util.Stack;
/**
* Created by harry on 2016/10/16.
*/
public class Main {
public static int count = 0;
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
for (int a = 1; a < 10; a++) {
stack.push(a);
fun(stack);
stack.pop();
}
System.out.println(count);
}
private static void fun(Stack<Integer> stack) {
for (int j = 1; j < 10; j++) {
if (stack.size() == 9) {
int a = stack.get(0);
int b = stack.get(1);
int c = stack.get(2);
int d = stack.get(3);
int e = stack.get(4);
int f = stack.get(5);
int g = stack.get(6);
int h = stack.get(7);
int i = stack.get(8);
int DEF = d * 100 + e * 10 + f;
int GHI = g * 100 + h * 10 + i;
int left = a * c * GHI + b * GHI + DEF * c;
int right = 10 * c * GHI;
if (left == right ) {
count++;
}
return;
}
if (!stack.contains(j)) {
stack.push(j);
fun(stack);
stack.pop();
}
}
}
}
答案
29
4铺坞、 分小組 (代碼填空)
9名運動員參加比賽,需要分3組進行預賽洲胖。
有哪些分組的方案呢济榨?
我們標記運動員為 A,B,C,... I
下面的程序列出了所有的分組方法。
該程序的正常輸出為:
ABC DEF GHI
ABC DEG FHI
ABC DEH FGI
ABC DEI FGH
ABC DFG EHI
ABC DFH EGI
ABC DFI EGH
ABC DGH EFI
ABC DGI EFH
ABC DHI EFG
ABC EFG DHI
ABC EFH DGI
ABC EFI DGH
ABC EGH DFI
ABC EGI DFH
ABC EHI DFG
ABC FGH DEI
ABC FGI DEH
ABC FHI DEG
ABC GHI DEF
ABD CEF GHI
ABD CEG FHI
ABD CEH FGI
ABD CEI FGH
ABD CFG EHI
ABD CFH EGI
ABD CFI EGH
ABD CGH EFI
ABD CGI EFH
ABD CHI EFG
ABD EFG CHI
..... (以下省略绿映,總共560行)擒滑。
參考示例:
public class A
{
public static String remain(int[] a)
{
String s = "";
for(int i=0; i<a.length; i++){
if(a[i] == 0) s += (char)(i+'A');
}
return s;
}
public static void f(String s, int[] a)
{
for(int i=0; i<a.length; i++){
if(a[i]==1) continue;
a[i] = 1;
for(int j=i+1; j<a.length; j++){
if(a[j]==1) continue;
a[j]=1;
for(int k=j+1; k<a.length; k++){
if(a[k]==1) continue;
a[k]=1;
//此處應填 s+" "+(char)(i+'A')+(char)(j+'A')+(char)(k+'A')+" "+remain(a)
System.out.println(__________________________________); //填空位置
a[k]=0;
}
a[j]=0;
}
a[i] = 0;
}
}
public static void main(String[] args)
{
int[] a = new int[9];
a[0] = 1;
for(int b=1; b<a.length; b++){
a[b] = 1;
for(int c=b+1; c<a.length; c++){
a[c] = 1;
String s = "A" + (char)(b+'A') + (char)(c+'A');
f(s,a);
a[c] = 0;
}
a[b] = 0;
}
}
}
5、抽簽 (代碼填空)
X星球要派出一個5人組成的觀察團前往W星叉弦。
其中:
A國最多可以派出4人丐一。
B國最多可以派出2人。
C國最多可以派出2人淹冰。
....
那么最終派往W星的觀察團會有多少種國別的不同組合呢库车?
下面的程序解決了這個問題。
數(shù)組a[] 中既是每個國家可以派出的最多的名額樱拴。
程序執(zhí)行結(jié)果為:
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
....
(以下省略柠衍,總共101行)
public class A {
public static void f(int[] a, int k, int n, String s) {
if (k == a.length) {
if (n == 0) System.out.println(s);
return;
}
String s2 = s;
for (int i = 0; i <= a[k]; i++) {
_________; //填空位置
//應該填f(a,k+1,5-s2.length(),s2);
s2 += (char) (k + 'A');
}
}
public static void main(String[] args) {
int[] a = {4, 2, 2, 1, 1, 3};
f(a, 0, 5, "");
}
}
6、方格填數(shù)(結(jié)果填空)
如下的10個格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+(如果顯示有問題晶乔,也可以參看【圖1.jpg】)
填入0~9的數(shù)字珍坊。要求:連續(xù)的兩個數(shù)字不能相鄰。
(左右正罢、上下阵漏、對角都算相鄰)一共有多少種可能的填數(shù)方案?
請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)翻具。
注意:你提交的應該是一個整數(shù)履怯,不要填寫任何多余的內(nèi)容或說明性文字。
package seven.six;
import java.util.Stack;
/**
* A[2]reated on 2016/10/26 17:57
*
* @author harry
* @version 1.0
*/
public class Test {
public static int count = 0;
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
Stack<Integer> stack = new Stack<>();
fun(stack);
long endTime = System.currentTimeMillis();
System.out.println("時間: " + (endTime - startTime));
System.out.println("count=" + count);
}
private static void fun(Stack<Integer> stack) {
if (stack.size() == 10) {
int A[] = new int[10];
A[0] = stack.get(0);
A[1] = stack.get(1);
A[2] = stack.get(2);
A[3] = stack.get(3);
A[4] = stack.get(4);
A[5] = stack.get(5);
A[6] = stack.get(6);
A[7] = stack.get(7);
A[8] = stack.get(8);
A[9] = stack.get(9);
boolean one = isNeibor(A[0], A[1], A[5], A[4], A[3]) && isNeibor(A[1], A[0], A[2], A[6], A[5], A[4]) && isNeibor(A[2], A[1], A[5], A[6]);
boolean two = isNeibor(A[3], A[0], A[4], A[8], A[7]) && isNeibor(A[4], A[0], A[8], A[5], A[9], A[8], A[7], A[3])
&& isNeibor(A[5], A[0], A[1], A[2], A[6], A[9], A[8], A[4]) && isNeibor(A[6], A[2], A[1], A[5], A[9]);
boolean three = isNeibor(A[7], A[8]) && isNeibor(A[8], A[9]);
if (one && two && three) {
System.out.printf("%d,%d,%d, %d,%d,%d,%d, %d,%d,%d\n", A[0], A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8], A[9]);
count++;
}
return;
}
for (int j = 0; j < 10; j++) {
if (!stack.contains(j)) {
stack.push(j);
fun(stack);
stack.pop();
}
}
}
public static boolean isNeibor(int ...args){
int first = args[0];
for (int i = 1; i < args.length; i++) {
if (Math.abs(first - args[i]) == 1) {
return false;
}
}
return true;
}
}
答案
1580
7裆泳、剪郵票 (結(jié)果填空)
如【圖1.jpg】, 有12張連在一起的12生肖的郵票叹洲。
現(xiàn)在你要從中剪下5張來,要求必須是連著的晾虑。
(僅僅連接一個角不算相連)
比如疹味,【圖2.jpg】,【圖3.jpg】中帜篇,粉紅色所示部分就是合格的剪取糙捺。
請你計算,一共有多少種不同的剪取方法笙隙。
請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)洪灯。
注意:你提交的應該是一個整數(shù),不要填寫任何多余的內(nèi)容或說明性文字竟痰。
$$
圖1
$$
$$
圖2
$$
$$
圖3
$$
116
參考程序:
public class Main {
private static int mp[] = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14};
private static int aa[] = new int[5];
private static int vis[] = new int[5];
private static int sum = 0;
private static int b[] = {-1, 1, -5, +5};
public static void main(String[] args) {
for (int a = 0; a < 12; a++)
for (int b = a + 1; b < 12; b++)
for (int c = b + 1; c < 12; c++)
for (int d = c + 1; d < 12; d++)
for (int e = d + 1; e < 12; e++) {
aa[0] = mp[a];
aa[1] = mp[b];
aa[2] = mp[c];
aa[3] = mp[d];
aa[4] = mp[e];
for (int i = 0; i < 5; i++) {
vis[i] = 0;
}
vis[0] = 1;
dfs(0);
int flag = 1;
for (int i = 0; i < 5; i++) {
if (vis[i] != 1) {
flag = 0;
break;
}
}
if (flag == 0) continue;
else{
sum++;
}
}
System.out.println(sum);
}
public static void dfs(int n) {
for (int i = 0; i < 4; i++) {
int t = aa[n] + b[i];
if (t < 1 || t > 14 || t == 5 || t == 10) continue;
for (int j = 0; j < 5; j++)
if (!(vis[j] == 1) && aa[j] == t) {
vis[j] = 1;
dfs(j);
}
}
}
}
8签钩、四平方和 (程序設計)
四平方和定理掏呼,又稱為拉格朗日定理:
每個正整數(shù)都可以表示為至多4個正整數(shù)的平方和。
如果把0包括進去铅檩,就正好可以表示為4個數(shù)的平方和憎夷。比如:
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
(^符號表示乘方的意思)對于一個給定的正整數(shù),可能存在多種平方和的表示法昧旨。
要求你對4個數(shù)排序:
0 <= a <= b <= c <= d
并對所有的可能表示法按 a,b,c,d 為聯(lián)合主鍵升序排列拾给,最后輸出第一個表示法程序輸入為一個正整數(shù)N (N<5000000)
要求輸出4個非負整數(shù),按從小到大排序兔沃,中間用空格分開例如蒋得,輸入:
5
則程序應該輸出:
0 0 1 2再例如,輸入:
12
則程序應該輸出:
0 2 2 2再例如乒疏,輸入:
773535
則程序應該輸出:
1 1 267 838資源約定:
峰值內(nèi)存消耗(含虛擬機) < 256M
CPU消耗 < 3000ms請嚴格按要求輸出额衙,不要畫蛇添足地打印類似:“請您輸入...” 的多余內(nèi)容。
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int Number = in.nextInt();
int maxSubNumber = (int) Math.sqrt(Number);
Loop:
for (int a = 0; a <= maxSubNumber; a++) {
for (int b = a; b < maxSubNumber; b++) {
for (int c = b; c <= maxSubNumber; c++) {
for (int d = c; d <= maxSubNumber; d++) {
int S = a * a + b * b + c * c + d * d;
if (S == Number) {
System.out.print(a);
System.out.print(" " + b);
System.out.print(" " + c);
System.out.print(" " + d);
break Loop;
}
}
}
}
}
}
}
9怕吴、取球博弈 (程序設計)
兩個人玩取球的游戲窍侧。
一共有N個球,每人輪流取球械哟,每次可取集合{n1,n2,n3}中的任何一個數(shù)目疏之。
如果無法繼續(xù)取球殿雪,則游戲結(jié)束暇咆。
此時,持有奇數(shù)個球的一方獲勝丙曙。
如果兩人都是奇數(shù)爸业,則為平局。
假設雙方都采用最聰明的取法亏镰,
第一個取球的人一定能贏嗎扯旷?
試編程解決這個問題。
輸入格式:
第一行3個正整數(shù)n1 n2 n3索抓,空格分開钧忽,表示每次可取的數(shù)目 (0<n1,n2,n3<100)
第二行5個正整數(shù)x1 x2 ... x5,空格分開逼肯,表示5局的初始球數(shù)(0<xi<1000)
輸出格式:
一行5個字符耸黑,空格分開。分別表示每局先取球的人能否獲勝篮幢。
能獲勝則輸出+大刊,
次之,如有辦法逼平對手三椿,輸出0缺菌,
無論如何都會輸葫辐,則輸出-
例如,輸入:
1 2 3
1 2 3 4 5
程序應該輸出:
+ 0 + 0 -
再例如伴郁,輸入:
1 4 5
10 11 12 13 15
程序應該輸出:
0 - 0 + +
再例如耿战,輸入:
2 3 5
7 8 9 10 11
程序應該輸出:
+ 0 0 0 0
資源約定:
峰值內(nèi)存消耗(含虛擬機) < 256M
CPU消耗 < 3000ms
這一題比較難下手,我們先來道題作為引子
今盒子里有n個小球焊傅,A昆箕、B兩人輪流從盒中取球,每個人都可以看到另一個人取了多少個租冠,也可以看到盒中還剩下多少個鹏倘,并且兩人都很聰明,不會做出錯誤的判斷顽爹。
我們約定:
每個人從盒子中取出的球的數(shù)目必須是:1纤泵,3,7或者8個镜粤。
輪到某一方取球時不能棄權(quán)捏题!
A先取球,然后雙方交替取球肉渴,直到取完公荧。
被迫拿到最后一個球的一方為負方(輸方)
請編程確定出在雙方都不判斷失誤的情況下,對于特定的初始球數(shù)同规,A是否能贏循狰?
輸入
先是一個整數(shù)n(n<100),表示接下來有n個整數(shù)券勺。然后是n個整數(shù)绪钥,每個占一行(整數(shù)<10000),表示初始球數(shù)关炼。
輸出
程序則輸出n行程腹,表示A的輸贏情況(輸為0,贏為1)儒拂。
樣例輸入
4
1
2
10
18
樣例輸出
0
1
1
0
參考代碼:
import java.util.Scanner;
public class Test1 {//簡單博弈寸潦,找出必敗點必勝點
static int b[] = {1, 3, 7, 8};
static boolean a[] = new boolean[10010];
public static void main(String[] args) {
Init();
Scanner input = new Scanner(System.in);
int N = input.nextInt();
while (N-- > 0) {
int n = input.nextInt();
System.out.println(a[n] ? 1 : 0);
}
}
private static void Init() {
for (int i = 1; i < 10000; i++) {//從1開始
if (!a[i]) {
for (int j = 0; j < 4; j++)
a[i + b[j]] = true;
}
}
}
}
本題較難,本人暫時無法找到解決方案社痛!
10见转、壓縮變換(程序設計)
小明最近在研究壓縮算法。
他知道褥影,壓縮的時候如果能夠使得數(shù)值很小池户,就能通過熵編碼得到較高的壓縮比。
然而,要使數(shù)值很小是一個挑戰(zhàn)校焦。最近赊抖,小明需要壓縮一些正整數(shù)的序列,這些序列的特點是寨典,后面出現(xiàn)的數(shù)字很大可能是剛出現(xiàn)過不久的數(shù)字氛雪。對于這種特殊的序列,小明準備對序列做一個變換來減小數(shù)字的值耸成。
變換的過程如下:
從左到右枚舉序列报亩,每枚舉到一個數(shù)字,如果這個數(shù)字沒有出現(xiàn)過井氢,剛將數(shù)字變換成它的相反數(shù)弦追,如果數(shù)字出現(xiàn)過,則看它在原序列中最后的一次出現(xiàn)后面(且在當前數(shù)前面)出現(xiàn)了幾種數(shù)字花竞,用這個種類數(shù)替換原來的數(shù)字劲件。比如,序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在變換過程為:
a1: 1未出現(xiàn)過约急,所以a1變?yōu)?1零远;
a2: 2未出現(xiàn)過,所以a2變?yōu)?2厌蔽;
a3: 2出現(xiàn)過牵辣,最后一次為原序列的a2,在a2后奴饮、a3前有0種數(shù)字纬向,所以a3變?yōu)?;
a4: 1出現(xiàn)過拐云,最后一次為原序列的a1罢猪,在a1后近她、a4前有1種數(shù)字叉瘩,所以a4變?yōu)?;
a5: 2出現(xiàn)過粘捎,最后一次為原序列的a3薇缅,在a3后、a5前有1種數(shù)字攒磨,所以a5變?yōu)?泳桦。
現(xiàn)在,給出原序列娩缰,請問灸撰,按這種變換規(guī)則變換后的序列是什么。輸入格式:
輸入第一行包含一個整數(shù)n,表示序列的長度浮毯。
第二行包含n個正整數(shù)完疫,表示輸入序列。輸出格式:
輸出一行债蓝,包含n個數(shù)壳鹤,表示變換后的序列。例如饰迹,輸入:
5
1 2 2 1 2程序應該輸出:
-1 -2 0 1 1再例如芳誓,輸入:
12
1 1 2 3 2 3 1 2 2 2 3 1程序應該輸出:
-1 0 -2 -3 1 1 2 2 0 0 2 2數(shù)據(jù)規(guī)模與約定
對于30%的數(shù)據(jù),n<=1000啊鸭;
對于50%的數(shù)據(jù)锹淌,n<=30000;
對于100%的數(shù)據(jù)赠制,1 <=n<=100000葛圃,1<=ai<=10^9資源約定:
峰值內(nèi)存消耗(含虛擬機) < 256M
CPU消耗 < 3000ms
public class Test {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int length = scanner.nextInt();
int[] a = new int[length];
for (int i = 0; i < length; i++) {
a[i] = scanner.nextInt();
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < length; i++) {
if (!map.keySet().contains(a[i])) {
map.put(a[i], i);
System.out.print(-a[i] + " ");
} else {
Integer position = map.get(a[i]);
map.put(a[i], i);
List<Integer> tmpList = new ArrayList<>();
for (int j = position + 1; j < i; j++) {
if (!tmpList.contains(a[j])) {
tmpList.add(a[j]);
}
}
System.out.print(tmpList.size() + " ");
}
}
}
}