- 結果填空題
- 試題 A: 遞增序列（5分）
- 試題 B: 平方拆分（5分）
- 試題 C: 切割（10分）
- 試題 D: 最優旅行（10分）
- 試題 E: 序列求和（15分）
- 程式設計題
- 試題 F: 最長子序列（15分）
- 試題 G: 數正方形（20分）
- 試題 H: 大胖子走迷宮（20分）
- 試題 I: 估計人數
- 試題 J: 分考場
結果填空題
試題 A: 遞增序列（5分）
【問題描述】
對于一個字母矩陣，我們稱矩陣中的一個遞增序列是指在矩陣中找到兩個字母，它們在同一行，同一列，或者在同一 45 度的斜線上，這兩個字母從左向右看、或者從上向下看是遞增的，
例如，如下矩陣中
LANN
QIAO
有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等 13 個遞增序列，注意當兩個字母是從左下到右上排列時，從左向右看和從上向下看是不同的順序，
對于下面的 30 行 50 列的矩陣，請問總共有多少個遞增序列？（如果你把
以下文字復制到文本檔案中，請務必檢查復制的內容是否與檔案中的一致，在試題目錄下有一個檔案 inc.txt，內容與下面的文本相同）
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案決議
答案是：52800
這道題主要是題目比較難懂，要求在同一行，同一列，或者在同一 45 度的斜線上，也就是八個方向，然后沒有說相鄰的行或者列，說明兩個數可以不相鄰，這兩個字母從左向右看、或者從上向下看是遞增的，這點也比較容易誤解，只需要判斷兩個字母的行或者列順序即可，
import java.util.Scanner;
public class Main {
static int[] dix = { 1, 1, 1, -1, -1, -1, 0, 0 };
static int[] diy = { -1, 1, 0, -1, 0, 1, -1, 1 };
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
char[][] ch = new char[35][55];
for (int i = 1; i <= 30; i++) {
String str = sc.next();
for (int j = 0; j < 50; j++) {
ch[i][j + 1] = str.charAt(j);
}
}
int ans = 0;
for (int i = 1; i <= 30; i++) {
for (int j = 1; j <= 50; j++) {
char temp = ch[i][j];
for (int t = 0; t < 8; t++) {
//并沒有相鄰行或者相鄰列，所以要回圈所有可能的情況，只要在范圍內即可
for (int x = i + dix[t], y = j + diy[t]; x >= 1 && x <= 30 && y >= 1
&& y <= 50; x += dix[t], y += diy[t]) {
//從左向右看、從上向下看遞增
if (ch[x][y]>temp && (x>i || y>j))
ans++;
}
}
}
}
System.out.println(ans);
}
}
試題 B: 平方拆分（5分）
【問題描述】
將 2019 拆分為若干個兩兩不同的完全平方數之和，一共有多少種不同的方法？
注意交換順序視為同一種方法，例如 132 + 252 + 352 = 2019 與 132 + 352 +252 = 2019 視為同一種方法，
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案決議
答案是：52574
2019的平方根范圍是 [0~45) ，直接深搜，只要保證平方根遞增就不會有重復的情況出現，這里有個坑，0是完全平方數，所以要從0開始深搜，
public class Main {
static int ans = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
dfs(0,45,2019);
System.out.println(ans);
}
static void dfs(int minn, int maxx, int num) {
if (num<0) return;
if (num==0) {
ans++;
return;
}
for (int i=minn;i<maxx;i++) {
dfs(i+1,maxx,num-i*i);
}
}
}
試題 C: 切割（10分）
【問題描述】
在 4 × 4 的方格矩陣中畫一條直線，則直線穿過的方格集合有多少種不同的可能？
這個里直線穿過一個方格當且僅當直線將該方格分割成面積都大于 0 的兩
部分，
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案決議
不會！
試題 D: 最優旅行（10分）
【問題描述】
中國的高鐵四通八達，乘坐方便，小明經常乘坐高鐵在城市間旅游，
現在，小明又有了一個長假，他打算繼續乘坐高鐵旅游，這次，他打算到下面的城市旅游，
上海、廣州、長沙、西安、杭州、濟南、成都、南京、昆明、鄭州、天津、太原、武漢、重慶、南昌、長春、沈陽、貴陽、福州，
小明打算從北京出發，游覽以上每個城市正好一次，最侄訓到北京，在每個城市（除北京外），小明都至少停留 24 小時，而當小明決定從一個城市去往另一個城市時，他只會選擇有直接高鐵連接的城市，不會在中途換乘轉車，
在試題目錄下有一個檔案 trip.txt 保存了小明可以選擇的車次，小明不會
選擇其他車次，
小明出發的時間是第 1 天的中午 12:00，請問，小明游覽完以上城市正好一次，最侄訓到北京，最快需要多少分鐘（請注意單位為分鐘，請注意除北京外的城市需要至少停留 24 小時，即最少停留 1440 分鐘），
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案決議
試題 E: 序列求和（15分）
【問題描述】
學習了約數后，小明對于約數很好奇，他發現，給定一個正整數 t，總是可以找到含有 t 個約數的整數，小明對于含有 t 個約數的最小數非常感興趣，并把它定義為 S t，
例如 S 1 = 1, S 2 = 2, S 3 = 4, S 4 = 6，· · · ，
現在小明想知道，前 60 個 S i 的和是多少？即 S 1 + S 2 + · · · + S 60 是多少？
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案決議
這道題有點歧義呀！“給定一個正整數 t，總是可以找到含有 t 個約數的整數，”，這句話是要我們找到只含 t 個約數的最小整數，還是說找到含大于等于 t 個約數的整數，如果是后者的話，就很簡單了，感覺這樣又比前面兩道容易很多，不太合理，這里貼出后者的做法，
//答案是101449，不確保是否是正確答案，
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
int ans = 0;
for (int i = 1;i<=60; i++) {
for (int j=1;;j++) {
int cnt = 0;
for (int k = 1; k <= j; k++) {
if (j % k == 0)
cnt++;
if (cnt == i) {
ans += j;
break;
}
}
if (cnt == i) {
break;
}
}
}
System.out.println(ans);
}
}
程式設計題
試題 F: 最長子序列（15分）
【問題描述】
我們稱一個字串 S 包含字串 T 是指 T 是 S 的一個子序列，即可以從字串 S 中抽出若干個字符，它們按原來的順序組合成一個新的字串與 T 完全一樣，
給定兩個字串 S 和 T，請問 T 中從第一個字符開始最長連續多少個字符被 S 包含？
【輸入格式】
輸入兩行，每行一個字串，第一行的字串為 S，第二行的字串為 T，
兩個字串均非空而且只包含大寫英文字母，
【輸出格式】
輸出一個整數，表示答案，
【樣例輸入】
ABCDEABCD
AABZ
【樣例輸出】
3
【評測用例規模與約定】
對于 20% 的評測用例，1 ≤ |T| ≤ |S | ≤ 20；
對于 40% 的評測用例，1 ≤ |T| ≤ |S | ≤ 100；
對于所有評測用例，1 ≤ |T| ≤ |S | ≤ 1000，
答案決議
這道題一開始看題目，以為是最長公共子序列，仔細一看，才發現很簡單，就是要從S字串中找出一個子序列使得其盡量與T字串相同，從T第一個字符開始，
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sn=new Scanner(System.in);
String S=sn.next();
String T=sn.next();
char[] s=S.toCharArray();
char[] t=T.toCharArray();
int k=0;//統計個數
for(int j=0;j<s.length;j++) {
if(t[k]==s[j])k++;
}
System.out.println(k);
}
}
試題 G: 數正方形（20分）
【問題描述】
在一個 N × N 的點陣上，取其中 4 個點恰好組成一個正方形的 4 個頂點，一共有多少種不同的取法？
由于結果可能非常大，你只需要輸出模 109 + 7 的余數，
如上圖所示的正方形都是合法的，
【輸入格式】
輸入包含一個整數 N，
【輸出格式】
輸出一個整數代表答案，
【樣例輸入】
4
【樣例輸出】
20
【資料規模與約定】
對于所有評測用例，2 ≤ N ≤ 1000000，
答案決議
試題 H: 大胖子走迷宮（20分）
【問題描述】
小明是個大胖子，或者說是個大大胖子，如果說正常人占用 1 × 1 的面積，小明要占用 5 × 5 的面積，
由于小明太胖了，所以他行動起來很不方便，當玩一些游戲時，小明相比小伙伴就吃虧很多，
小明的朋友們制定了一個計劃，幫助小明減肥，計劃的主要內容是帶小明玩一些游戲，讓小明在游戲中運動消耗脂肪，走迷宮是計劃中的重要環節，
朋友們設計了一個迷宮，迷宮可以看成是一個由 n × n 個方陣組成的方陣，正常人每次占用方陣中 1 × 1 的區域，而小明要占用 5 × 5 的區域，小明的位置定義為小明最正中的一個方格，迷宮四周都有障礙物，
為了方便小明，朋友們把迷宮的起點設定在了第 3 行第 3 列，終點設定在了第 n ? 2 行第 n ? 2 列，
小明在時刻 0 出發，每單位時間可以向當前位置的上、下、左、右移動單位 1 的距離，也可以停留在原地不動，小明走迷宮走得很辛苦，如果他在迷宮里面待的時間很長，則由于消耗了很多脂肪，他會在時刻 k 變成一個胖子，只占用 3 × 3 的區域，如果待的時間更長，他會在時刻 2k 變成一個正常人，只占用 1 × 1 的區域，注意，當小明變瘦時迷宮的起點和終點不變，
請問，小明最少多長時間能走到迷宮的終點，注意，小明走到終點時可能變瘦了也可能沒有變瘦，
【輸入格式】
輸入的第一行包含兩個整數 n, k，
接下來 n 行，每行一個由 n 個字符組成的字串，字符為 + 表示為空地，字符為 * 表示為阻礙物，
答案決議
這道題是經典BFS題目，要處理的就是胖子的厚度，其他就是常規的條件判斷，
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static class Node {
int x, y, time;
public Node(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
}
static int n, k, ans;
static int[] dix = { 0, 0, 1, -1 };
static int[] diy = { 1, -1, 0, 0 };
static char[][] maps;
static boolean[][] vis;
static int culcate(int time) {
if (time / k == 1)
return 1;
else if (time / k == 0)
return 2;
else
return 0;
}
static void bfs() {
ArrayList<Node> queue = new ArrayList<Node>();
queue.add(new Node(3, 3, 0));
while (!queue.isEmpty()) {
Node node = queue.get(0);
queue.remove(0);
if (node.x == n - 2 && node.y == n - 2) {
System.out.println(node.time);
return;
}
queue.add(new Node(node.x, node.y, node.time + 1));
for (int i = 0; i < 4; i++) {
int xx = node.x + dix[i];
int yy = node.y + diy[i];
int fat = culcate(node.time);
if (xx - fat < 1 || xx + fat > n || yy - fat < 1 || yy + fat > n)
continue;
if (vis[xx][yy])
continue;
boolean flag = true;
if (fat != 0) {
for (int x = xx - fat; x <= xx + fat; x++) {
for (int y = yy - fat; y <= yy + fat; y++) {
if (maps[x][y] == '*')
flag = false;
}
}
} else {
if (maps[xx][yy] == '*')
flag = false;
}
if (!flag)
continue;
vis[xx][yy] = true;
queue.add(new Node(xx, yy, node.time + 1));
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
maps = new char[n + 1][n + 1];
vis = new boolean[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
String str = sc.next();
for (int j = 1; j <= n; j++) {
maps[i][j] = str.charAt(j - 1);
vis[i][j] = false;
}
}
vis[3][3] = true;
bfs();
}
}
試題 I: 估計人數
【問題描述】
給定一個 N × M 的方格矩陣，矩陣中每個方格標記 0 或者 1 代表這個方格是不是有人踩過，
已知一個人可能從任意方格開始，之后每一步只能向右或者向下走一格，走了若干步之后，這個人可以離開矩陣，這個人經過的方格都會被標記為 1，包括開始和結束的方格，注意開始和結束的方格不需要一定在矩陣邊緣，
請你計算至少有多少人在矩陣上走過，
【輸入格式】
輸入第一行包含兩個整數 N、M，
以下 N 行每行包含 M 個整數 (0/1)，代表方格矩陣，
【輸出格式】
輸出一個整數代表答案，
【樣例輸入】
5 5
00100
11111
00100
11111
00100
【樣例輸出】
3
【資料規模與約定】
對于所有評測用例，1 ≤ N, M ≤ 20，標記為 1 的方格不超過 200 個，
試題 J: 分考場
【問題背景】
古語有云：春風得意馬蹄疾，一日看盡長安花，
當然在一場考試中所有人都春風得意馬蹄疾是不可能的，尤其是碰到一些毒瘤出題人的時候，
【問題描述】
又到了每月一次的月考，又是 xf 老師出題，
上一次 xf 老師出的題太毒瘤了，平均分只有 40 多，同學們都非常不滿意，畢竟別的科的平均分都是 80 多，
這次 xf 為了不被同學們寄刀片，想了一個辦法：只公布所有考場的平均分的平均分，這樣他就可以通過調整考場的分配方式，使得平均分顯得高，（每個考場都可以容納無限人）
每次考試也不是所有同學都參加的，只有學號在 [l,r] 這個區間中的同學會參加，
他想知道對于每次考試，他調整過考場后，所有考場的平均分的平均分的最大值，
當然，同學們也可能會努力學習或整日頹廢使成績發生改變，
【輸入格式】
輸入的第一行包含一個整數 n，
第二行包含 n 個整數，第 i 個數 vi，表示開始時每個同學的成績，
第三行包含一個整數 q，表示有 q 次操作，
之后 q 行，每行描述一個操作，第一個數表示操作型別，
如果操作為 1 p x，表示學號為 p 的同學分數變為 x，
如果操作為 2 l r k, 表示把學號在 [l,r] 中的同學分成 k 個考場，求這 k 個考場的平均分的平均分的最大值，
【輸出格式】
對于每個 2 操作輸出一行，四舍五入保留正好 3 位小數，
【樣例輸入】
5
5 3 4 2 1
5
2 1 4 3
1 4 8
2 3 5 3
1 2 2
2 1 3 2
【樣例輸出】
3.833
4.333
4.000
【樣例說明】
第一個操作詢問學號在 [1, 4] 之間的同學分成 3 個考場的平均分的平均分的最大值，最優策略是：{1}, {2, 4}, {3}，平均分是
第二個操作把學號為 4 的同學的分數變為 8，
第三個操作詢問學號在 [3, 5] 之間的同學分成 3 個考場的平均分的平均分的最大值，最優策略是：{3}, {4}, {5}，
第四個操作把學號為 2 的同學分數變為 2，
第五個操作詢問學號在 [1, 3] 之間的同學分成 2 個考場的平均分的平均分的最大值，最優策略是：{1}, {2 3}，
【評測用例規模與約定】
對于全部評測用列，n ≤ 200000, q ≤ 200000, 任意時刻同學的分數 vi ≤ 109，k ≤ r ? l + 1，
評測時將使用 10 個評測用例測驗你的程式，每個評測用例的限制如下：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/215507.html
標籤：java