藍橋杯歷年真題及決議.
目錄
- 藍橋杯歷年真題及決議.
- A:平方十位數(難度:★).
- 分析:
- AC代碼:
- B:生命游戲(難度:★★★★).
- 分析:
- AC代碼:
- C:樹形顯示(難度:★).
- 分析:
- AC代碼:
- D:小計算器(難度:★★).
- 分析:
- AC代碼:
- E:填字母游戲(難度:★★★).
- 分析:
- AC代碼:
- F:區間移位(難度:★★★★★).
- 分析:
- AC代碼:
A:平方十位數(難度:★).
由0~9這10個數字不重復、不遺漏,可以組成很多10位數字,
這其中也有很多恰好是平方數(是某個數的平方),
比如:1026753849,就是其中最小的一個平方數,
請你找出其中最大的一個平方數是多少?
注意:你需要提交的是一個10位數字,不要填寫任何多余內容,
分析:
全排列列舉出所有排列情況,
對每一種情況進行Check即可
AC代碼:

public class Main {
public static long ans = 0;
public static int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
public static void tolong() {
long t = 0;
for (int i = 0; i < 10; i++) {
t *= 10;
t += arr[i];
}
long x = (long) Math.sqrt(t);
if (x * x == t)
ans = Math.max(ans, t);
}
public static void qpl(int k) {
if (k >= arr.length)
tolong();
else {
for (int i = k; i < arr.length; i++) {
int 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);
}
}
B:生命游戲(難度:★★★★).
康威生命游戲是英國數學家約翰·何頓·康威在1970年發明的細胞自動機,
這個游戲在一個無限大的2D網格上進行,
初始時,每個小方格中居住著一個活著或死了的細胞,
下一時刻每個細胞的狀態都由它周圍八個格子的細胞狀態決定,
具體來說:
- 當前細胞為存活狀態時,當周圍低于2個(不包含2個)存活細胞時, 該細胞變成死亡狀態,(模擬生命數量稀少)
- 當前細胞為存活狀態時,當周圍有2個或3個存活細胞時, 該細胞保持原樣,
- 當前細胞為存活狀態時,當周圍有3個以上的存活細胞時,該細胞變成死亡狀態,(模擬生命數量過多)
- 當前細胞為死亡狀態時,當周圍有3個存活細胞時,該細胞變成存活狀態, (模擬繁殖)
當前代所有細胞同時被以上規則處理后, 可以得到下一代細胞圖,按規則繼續處理這一代的細胞圖,可以得到再下一代的細胞圖,周而復始,


本題中我們要討論的是一個非常特殊的模式,被稱作"Gosper glider gun":

假設以上初始狀態是第0代,請問第1000000000(十億)代一共有多少活著的細胞?
注意:我們假定細胞機在無限的2D網格上推演,并非只有題目中畫出的那點空間,
當然,對于遙遠的位置,其初始狀態一概為死細胞,
注意:需要提交的是一個整數,不要填寫多余內容,
分析:
這個題比較復雜,需要有敏銳的觀察力,還有一些數論的基礎才可以搞,
首先我們將狀態迭代幾百次,然后觀察規律
然后就可以輕松的發現每30次迭代是一個周期(這TM誰能發現???)
然后將周期陣列儲存下來,按照十億次計算即可,
AC代碼:

//以下程式分兩段
//第一段求周期
//第二段求結果
import java.util.HashSet;
public class B生命游戲mod {
public static int maxn=1000;
public static char map[][]=new char [maxn][maxn];
public static char now[][]=new char [maxn][maxn];
public static char c[][]={
{'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',},
{'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','X','.','.','.','.','.','.','.','.','.','.','.','.',},
{'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','X','.','X','.','.','.','.','.','.','.','.','.','.','.','.',},
{'.','.','.','.','.','.','.','.','.','.','.','.','.','X','X','.','.','.','.','.','.','X','X','.','.','.','.','.','.','.','.','.','.','.','.','X','X','.',},
{'.','.','.','.','.','.','.','.','.','.','.','.','X','.','.','.','X','.','.','.','.','X','X','.','.','.','.','.','.','.','.','.','.','.','.','X','X','.',},
{'.','X','X','.','.','.','.','.','.','.','.','X','.','.','.','.','.','X','.','.','.','X','X','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',},
{'.','X','X','.','.','.','.','.','.','.','.','X','.','.','.','X','.','X','X','.','.','.','.','X','.','X','.','.','.','.','.','.','.','.','.','.','.','.',},
{'.','.','.','.','.','.','.','.','.','.','.','X','.','.','.','.','.','X','.','.','.','.','.','.','.','X','.','.','.','.','.','.','.','.','.','.','.','.',},
{'.','.','.','.','.','.','.','.','.','.','.','.','X','.','.','.','X','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',},
{'.','.','.','.','.','.','.','.','.','.','.','.','.','X','X','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',}
};
public static HashSet<String> set=new HashSet<String>();
public static String tos(){
StringBuilder sBuilder=new StringBuilder();
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
sBuilder.append(map[i][j]);
}
}
return sBuilder.toString();
}
public static void next(){
for(int i=1;i<maxn-1;i++){
for(int j=1;j<maxn-1;j++){
int cnt=0;
for(int x=-1;x<2;x++){
for(int y=-1;y<2;y++){
if(x==0&&y==0)continue;
if(map[i+x][j+y]=='X')cnt++;
}
}
if(map[i][j]=='X'){
if(cnt==2||cnt==3)now[i][j]='X';
else now[i][j]='.';
}else{
if(cnt==3)now[i][j]='X';
else now[i][j]='.';
}
}
}
for(int i=1;i<maxn-1;i++){
for(int j=1;j<maxn-1;j++){
map[i][j]=now[i][j];
}
}
}
public static int comput(){
int sum=0;
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
if(map[i][j]=='X')sum++;
}
}
return sum;
}
public static void main(String[] args) {
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
map[i][j]='.';
}
}
for(int i=0;i<c.length;i++){
for(int j=0;j<c[i].length;j++){
map[maxn/2+i][maxn/2+j]=c[i][j];
}
}
String string=tos();
int cnt=0,sum=0,cur=0;
while(!set.contains(string)){
set.add(string);
cnt++;
sum=comput();
next();
string=tos();
cur=comput();
System.out.print(cur-sum+",");
if(cnt%30==0){
System.out.println();
}
}
System.out.println(cnt+" "+set.size());
}
}
public class Main {
public static int mod[] = { 3, 4, 5, 3, -7, 7, -3, 13, -19, 6, 2, 4, 1, 1, -14, 2, 3, 6, 1, 0, 0, -5, 11, -17, 7,
-3, 0, 3, -2, -7 };
public static void main(String[] args) {
long ans = 36;
for (int i = 1; i < mod.length; i++)
mod[i] += mod[i - 1];
ans += (1000000000 / 30) * mod[mod.length - 1];
ans += mod[1000000000 % 30 - 1];
System.out.println(ans);
}
}
C:樹形顯示(難度:★).
對于分類結構可以用樹形來形象地表示,比如:檔案系統就是典型的例子,
樹中的結節具有父子關系,我們在顯示的時候,把子項向右縮進(用空格,不是tab),并添加必要的連接線,以使其層次關系更醒目,
下面的代碼就是為了這個目的的,請仔細閱讀原始碼,并填寫劃線部分缺少的代碼,
import java.util.*;
class MyTree
{
private Map<String, List<String>> map_ch = new HashMap<String, List<String>>();
private Map<String,String> map_pa = new HashMap<String,String>();
public void add(String parent, String child)
{
map_pa.put(child, parent);
List<String> lst = map_ch.get(parent);
if(lst==null){
lst = new ArrayList<String>();
map_ch.put(parent, lst);
}
lst.add(child);
}
public String get_parent(String me){
return map_pa.get(me);
}
public List<String> get_child(String me){
return map_ch.get(me);
}
private String space(int n)
{
String s = "";
for(int i=0; i<n; i++) s += ' ';
return s;
}
private boolean last_child(String x){
String pa = map_pa.get(x);
if(pa==null) return true;
List<String> lst = map_ch.get(pa);
return lst.get(lst.size()-1).equals(x);
}
public void show(String x){
String s = "+--" + x;
String pa = x;
while(true){
pa = map_pa.get(pa);
if(pa==null) break;
s = ___________________________________ ; // 填空
}
System.out.println(s);
}
public void dfs(String x){
show(x);
List<String> lst = map_ch.get(x);
if(lst==null) return;
for(String it: lst){
dfs(it);
}
}
}
public class TreeView
{
public static void main(String[] args)
{
MyTree tree = new MyTree();
tree.add("root", "dog");
tree.add("root", "cat");
tree.add("root", "duck");
tree.add("dog", "AAdog");
tree.add("dog", "BBdog");
tree.add("dog", "CCdog");
tree.add("AAdog", "AAdog01");
tree.add("AAdog", "AAdog02");
tree.add("cat", "XXcat");
tree.add("cat", "YYcat");
tree.add("XXcat","XXcat-oo");
tree.add("XXcat","XXcat-qq");
tree.add("XXcat-qq", "XXcat-qq-hahah");
tree.add("duck", "TTduck");
tree.add("TTduck", "TTduck-001");
tree.add("TTduck", "TTduck-002");
tree.add("TTduck", "TTduck-003");
tree.add("YYcat","YYcat.hello");
tree.add("YYcat","YYcat.yes");
tree.add("YYcat","YYcat.me");
tree.dfs("root");
}
}
對于題目中的測驗資料,輸出結果:

注意,只填寫劃線部分缺少的代碼,不要抄寫已有的代碼或符號,
分析:
觀察題目發現我們只需要做一個字串拼接的作業,
而且我們觀察圖發現,
當本節點是父結點的最后一個節點時,不需要有|,其他情況有|
所以我們推測拼接方式為s=(last_child(pa)?" “:”|")+space(4)+s;
AC代碼:
不能交題,但是運行結果是正確的
package JAVA2017;
import java.util.*;
public class C樹形顯示 {
public static void main(String[] args) {
MyTree tree = new MyTree();
tree.add("root", "dog");
tree.add("root", "cat");
tree.add("root", "duck");
tree.add("dog", "AAdog");
tree.add("dog", "BBdog");
tree.add("dog", "CCdog");
tree.add("AAdog", "AAdog01");
tree.add("AAdog", "AAdog02");
tree.add("cat", "XXcat");
tree.add("cat", "YYcat");
tree.add("XXcat", "XXcat-oo");
tree.add("XXcat", "XXcat-qq");
tree.add("XXcat-qq", "XXcat-qq-hahah");
tree.add("duck", "TTduck");
tree.add("TTduck", "TTduck-001");
tree.add("TTduck", "TTduck-002");
tree.add("TTduck", "TTduck-003");
tree.add("YYcat", "YYcat.hello");
tree.add("YYcat", "YYcat.yes");
tree.add("YYcat", "YYcat.me");
tree.dfs("root");
}
}
class MyTree {
private Map<String, List<String>> map_ch = new HashMap<String, List<String>>();
private Map<String, String> map_pa = new HashMap<String, String>();
public void add(String parent, String child) {
map_pa.put(child, parent);
List<String> lst = map_ch.get(parent);
if (lst == null) {
lst = new ArrayList<String>();
map_ch.put(parent, lst);
}
lst.add(child);
}
public String get_parent(String me) {
return map_pa.get(me);
}
public List<String> get_child(String me) {
return map_ch.get(me);
}
private String space(int n) {
String s = "";
for (int i = 0; i < n; i++)
s += ' ';
return s;
}
private boolean last_child(String x) {
String pa = map_pa.get(x);
if (pa == null)
return true;
List<String> lst = map_ch.get(pa);
return lst.get(lst.size() - 1).equals(x);
}
public void show(String x) {
String s = "+--" + x;
String pa = x;
while (true) {
pa = map_pa.get(pa);
if (pa == null)
break;
//也對
// s=(map_pa.get(pa)==null||get_child(map_pa.get(pa)).indexOf(pa)==get_child(map_pa.get(pa)).size()-1?" ":"| ")+s;
s=(last_child(pa)?" ":"|")+space(4)+s;
// s = ___________________________________ ; // 填空
}
System.out.println(s);
}
public void dfs(String x) {
show(x);
List<String> lst = map_ch.get(x);
if (lst == null)
return;
for (String it : lst) {
dfs(it);
}
}
}
D:小計算器(難度:★★).
模擬程式型計算器,依次輸入指令,可能包含的指令有
- 數字:‘NUM X’,X為一個只包含大寫字母和數字的字串,表示一個當前進制的數
- 運算指令:‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’,分別表示加減乘,除法取商,除法取余
- 進制轉換指令:‘CHANGE K’,將當前進制轉換為K進制(2≤K≤36)
- 輸出指令:‘EQUAL’,以當前進制輸出結果
- 重置指令:‘CLEAR’,清除當前數字
指令按照以下規則給出:
數字,運算指令不會連續給出,進制轉換指令,輸出指令,重置指令有可能連續給出
運算指令后出現的第一個數字,表示參與運算的數字,且在該運算指令和該數字中間不會出現運算指令和輸出指令
重置指令后出現的第一個數字,表示基礎值,且在重置指令和第一個數字中間不會出現運算指令和輸出指令
進制轉換指令可能出現在任何地方
運算程序中中間變數均為非負整數,且小于2^63,
以大寫的’A’'Z’表示1035
[輸入格式]
第1行:1個n,表示指令數量
第2…n+1行:每行給出一條指令,指令序列一定以’CLEAR’作為開始,并且滿足指令規則
[輸出格式]
依次給出每一次’EQUAL’得到的結果
[樣例輸入]
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
[樣例輸出]
2040
補充說明:
- n 值范圍: 1<= n < 50000
- 初始默認的進制是十進制
分析:
簡單的計算器處理問題,
對于資料的存盤,我們只采用十進制存盤即可
如果需要輸出,再把十進制轉成對應的R進制
然后我們定義兩個變數nums[2]用來存放資料即可
對于每次不同的操作采取不同的措施+ - * / % 運算
不過要注意的是,輸出的多進制要采用大寫輸出,否則結果不正確,
如abc應該寫成ABC
AC代碼:

import java.util.Scanner;
//大小寫敏感
public class Main {
public static long nums[]=new long[2];
public static int p=0,r=10;
public static String op;
public static void comput(){
if(op.equals("ADD")){
nums[0]+=nums[1];
}else if(op.equals("SUB")){
nums[0]-=nums[1];
}else if(op.equals("MUL")){
nums[0]*=nums[1];
}else if(op.equals("DIV")){
nums[0]/=nums[1];
}else if(op.equals("MOD")){
nums[0]%=nums[1];
}
nums[1]=0;
p=0;
}
public static void oper(String s[]){
if(s[0].equals("NUM")){
nums[p]=Long.parseLong(s[1], r);
if(p==1) comput();
}else if(s[0].equals("CHANGE")){
r=Integer.parseInt(s[1]);
}else if(s[0].equals("EQUAL")){
System.out.println(Long.toString(nums[0], r).toUpperCase());
}else if(s[0].equals("CLEAR")){
nums[p]=0;
}else{
p=(p+1)%2;
op=s[0];
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();sc.nextLine();
String s[];
while(n-->0){
s=sc.nextLine().split(" ");
oper(s);
}
}
}
E:填字母游戲(難度:★★★).
小明經常玩 LOL 游戲上癮,一次他想挑戰K大師,不料K大師說:
“我們先來玩個空格填字母的游戲,要是你不能贏我,就再別玩LOL了”,
K大師在紙上畫了一行n個格子,要小明和他交替往其中填入字母,
并且:
- 輪到某人填的時候,只能在某個空格中填入L或O
- 誰先讓字母組成了“LOL”的字樣,誰獲勝,
- 如果所有格子都填滿了,仍無法組成LOL,則平局,
小明試驗了幾次都輸了,他很慚愧,希望你能用計算機幫他解開這個謎,
本題的輸入格式為:
第一行,數字n(n<10),表示下面有n個初始局面,
接下來,n行,每行一個串,表示開始的局面,
比如:

要求輸出n個數字,表示對每個局面,如果小明先填,當K大師總是用最強著法的時候,小明的最好結果,
1 表示能贏
-1 表示必輸
0 表示可以逼平
例如,

分析:
我們定義一個Map,用來存盤狀態和結果,
對于每一個沒解決的問題,我們針對每個位置可以采取兩個方案,
方案1,放置L
方案2,放置O
然后順次迭代下去,
理論上分析時間復雜度極高,不過卻通過了全部資料,,,
AC代碼:

import java.util.*;
public class Main {
static Map<String, Integer> map = new HashMap<String, Integer>();
// -1: 必輸,0: 平局, 1: 必贏
static int f(char[] x) {
String s = new String(x);
if (map.get(s) != null)
return map.get(s);
if (s.contains("LOL")) {
map.put(s, -1);
return -1;
}
if (s.contains("*") == false) {
map.put(s, 0);
return 0;
}
boolean ping = false;
for (int i = 0; i < x.length; i++) {
if (x[i] == '*') {
try {
x[i] = 'L';
int t = f(x);
if (t < 0) {
map.put(s, 1);
return 1;
}
if (t == 0)
ping = true;
x[i] = 'O';
t = f(x);
if (t < 0) {
map.put(s, 1);
return 1;
}
if (t == 0)
ping = true;
} finally {
x[i] = '*';
}
}
}
if (ping) {
map.put(s, 0);
return 0;
}
map.put(s, -1);
return -1;
}
static int game(String s) {
map.clear();
return f(s.toCharArray());
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(scan.nextLine().trim());
for (int i = 0; i < n; i++) {
System.out.println(game(scan.nextLine().trim()));
}
}
}
F:區間移位(難度:★★★★★).
數軸上有n個閉區間:D1,…,Dn,
其中區間Di用一對整數[ai, bi]來描述,滿足ai < bi,
已知這些區間的長度之和至少有10000,
所以,通過適當的移動這些區間,你總可以使得他們的“并”覆寫[0, 10000]——也就是說[0, 10000]這個區間內的每一個點都落于至少一個區間內,
你希望找一個移動方法,使得位移差最大的那個區間的位移量最小,
具體來說,假設你將Di移動到[ai+ci, bi+ci]這個位置,你希望使得maxi{|ci|} 最小,
【輸入格式】
輸入的第一行包含一個整數n,表示區間的數量,
接下來有n行,每行2個整數ai, bi,以一個空格分開,表示區間[ai, bi],
保證區間的長度之和至少是10000,
【輸出格式】
輸出一個數字,表示答案,如果答案是整數,只輸出整數部分,如果答案不是整數,輸出時四舍五入保留一位小數,
【樣例輸入】
2
10 5010
4980 9980
【樣例輸出】
20
【樣例說明】
第一個區間往左移動10;第二個區間往右移動20,
【樣例輸入】
4
0 4000
3000 5000
5001 8000
7000 10000
【樣例輸出】
0.5
【樣例說明】
第2個區間往右移0.5;第3個區間往左移0.5即可,
【資料規模與約定】
對于30%的評測用例,1 <= n <= 10;
對于100%的評測用例,1 <= n <= 10000,0 <= ai < bi <= 10000,
分析:
區間壓縮演算法,待更新
以后忘了記得催我,,,,
AC代碼:

轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/206305.html
標籤:其他
