2021年寒假每日一題，2017~2019年的省賽真題，
本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，
文章目錄
- 一、2017年藍橋杯軟體類 C語言大學A組
- 1. 迷宮
- 2. 跳蚱蜢
- 2.1 建模
- 2.2 判重
- 2.3 map判重
- 2.4 set判重
- 2.5 康托判重
- 2.6 擴展學習
- 附：2017年第八屆藍橋杯大賽個人賽省賽（軟體類） C/C++ 大學A組考生須知
OJ：可以到http://oj.ecustacm.cn/交題，從第3頁開始是歷年真題：http://oj.ecustacm.cn/problemset.php?page=3
后面的每日一題，每題發一個新博文，請大家看博客目錄：https://blog.csdn.net/weixin_43914593
一、2017年藍橋杯軟體類 C語言大學A組
共10題，題目總覽：
1、迷宮
2、跳蚱蜢
3、魔方狀態
4、方格分割
5、字母組串
6、最大公共子串
7、正則問題
8、包子湊數
9、分巧克力
10、油漆面積
第一天：2021.1.3日
1. 迷宮
題目鏈接： http://oj.ecustacm.cn/problem.php?id=1317
（1）投機取巧的搞法
??根據本文的“附考生須知”，第1題是填空題，只交答案就行了，如果不想編碼，直接用手一個個去數那100個點，幾分鐘就數完了，答案是31，比編碼還要快，
??在OJ上這樣交就能AC：
#include<iostream>
using namespace std;
int main(){
cout << 31 << endl;
return 0;
}
（2）還是用這題來練練DFS編碼吧
題解：
??一道搜索題，可以選擇暴力dfs，代碼簡短
??我寫的稍微長一點，但可以確保每個點只走到一次，稍微優化了那么一丟丟
??此題唯一的坑點是提交到OJ時，千萬不要寫輸入！！555
??直接輸出一個數字就好惹…
參考代碼：（羅老師注：倪文迪沒有用遞回寫DFS，參考這篇用遞回寫的DFS，更好懂：https://www.cnblogs.com/-citywall123/p/12316760.html）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;
int mp[20][20];
int vis[20][20];
bool tag[200];
int cnt[200];
int X[] = {0, 0, 0, -1, 1};
int Y[] = {0, -1, 1, 0, 0};
void solve(int x, int y, int id)
{
while(x >= 1 && x <= 10 && y >= 1 && y <= 10 && !vis[x][y]){
vis[x][y] = id;
cnt[id]++;
int now = mp[x][y];
x += X[now];
y += Y[now];
}
if(x < 1 || x > 10 || y < 1 || y > 10){
tag[id] = true;
return ;
}
if(vis[x][y]){
if(tag[vis[x][y]]) tag[id] = true;
}
return ;
}
int main(){
for(int i = 1 ; i <= 10 ; i++){
string s; cin >> s;
for(int j = 0 ; j < 10 ; j++){
if(s[j] == 'L') mp[i][j + 1] = 1;
else if(s[j] == 'R') mp[i][j + 1] = 2;
else if(s[j] == 'U') mp[i][j + 1] = 3;
else if(s[j] == 'D') mp[i][j + 1] = 4;
}
}
int id = 1;
for(int i = 1 ; i <= 10 ; i++){
for(int j = 1 ; j <= 10 ; j++){
if(!vis[i][j]){
solve(i, j, id);
id++;
}
}
}
/*for(int i = 1 ; i <= 10 ; i++){
for(int j = 1 ; j <= 10 ; j++){
printf("%3.d",vis[i][j]);
}
cout << endl;
}*/
int res = 0;
for(int i = 1 ; i < id ; i++){
if(tag[i]) res += cnt[i];
}
printf("%d\n", res);
return 0;
}
第二天：2021.1.4日
2. 跳蚱蜢
題目鏈接： http://oj.ecustacm.cn/problem.php?id=1318
??又是一道填空題，能用手數出答案嗎？
??提前告訴大家，答案是20，數字好像不大，可是，用手數出來好像不可能，還是老實編碼吧，
2.1 建模
??直接讓蚱蜢跳到空盤有點麻煩，因為有很多蚱蜢在跳，跳暈了，如果看成空盤跳到蚱蜢的位置就簡單多了，只有一個空盤在跳，
??題目給的是一個圓圈，不好處理，此時祭出一個建模大法：“化圓為線”！ 把空盤看成0，那么有9個數字{0,1,2,3,4,5,6,7,8}，一個圓圈上的9個數字，拉直成了一條線上的9個數字，
??等等，這不就是八數碼問題嗎？八數碼是經典的BFS問題，
??八數碼有9個數字{0,1,2,3,4,5,6,7,8}，它有9！=362880種排列，也不多，
??本題的初始狀態是“012345678”，終止狀態是“087654321”，
??從初始狀態跳一次，有4種情況：
2.2 判重
??這題要是寫個裸的BFS，不判重，能運行出來嗎？
??第1步到第2步，有4種跳法；第2步到第3步，有4*4種；…；第20步，有4^20=1萬億種！太多了！BFS的佇列也放不下呀，
??還是得判重，如果跳到一個曾經出現過的情況，就不用往下跳了，八數碼只有9！=362880種排列，好判，
??如何判重？比賽的時候緊張，當然得用STL，用map、set判重都行，效率都好，另外，有一種數字方法，叫康托判重，得自己寫，一般不用，
2.3 map判重
??把9個數字的排列定義為一種狀態，即字串s，例如初始狀態“012345678”是一個串，對應交換之后產生的s，我們可以使用map判重，將該字串以及它首次出現的時間作為一個單位推入佇列中，由于BFS的性質我們能看出，首次找到結果狀態的時間t即是最小的答案，
??倪文迪的代碼：
#include<bits/stdc++.h>
using namespace std;
struct node
{
node(){}
node(string ss, int tt){
s = ss, t = tt;
}
string s;
int t;
};
map<string, bool> mp;
queue<node> q;
void solve()
{
while(!q.empty()){
node now = q.front();
q.pop();
string s = now.s; int t = now.t;
if(s == "087654321"){
cout << t << endl;
break;
}
int i;
for(i = 0 ; i < 10 ; i++){
if(s[i] == '0') break;
}
for(int j = i - 2 ; j <= i + 2 ; j++){
int k = (j + 9) % 9;
if(k == i) continue;
char tmp;
tmp = s[i];s[i] = s[k];s[k] = tmp;
if(!mp[s]){
mp[s] = true;
q.push(node(s, t + 1));
}
tmp = s[i];s[i] = s[k];s[k] = tmp;
}
}
}
int main(){
string s = "012345678";
q.push(node(s, 0));
mp[s] = true;
solve();
return 0;
}
2.4 set判重
??代碼參考：https://blog.csdn.net/crazymooo/article/details/108816699
2.5 康托判重
??map和set的判重效率是很高的，另外有一種數學判重方法，叫做康托判重，運行起來比map和set快，下面介紹一下，
??在《演算法競賽入門到進階》（清華大學出版社，羅勇軍著）47頁詳解了八數碼的康托判重，這里附上截圖：
??以上是截圖，
??下面是書中的代碼，用“BFS + 康托(Cantor)”解決了八數碼問題，其中BFS用STL的queue實作，
#include<bits/stdc++.h>
const int LEN = 362888; //狀態共9!=362880種
using namespace std;
struct node{
int state[9]; //記錄一個八數碼的排列，即一個狀態
int dis; //記錄到起點的距離
};
int dir[4][2] = {{-1,0}, {0,-1},{1,0},{0,1}};
//左、上、右、下順時針方向，左上角坐標是(0,0)
int visited[LEN]={0}; //與每個狀態對應的記錄，Cantor函式對它置數，并判重
int start[9]; //開始狀態
int goal[9]; //目標狀態
long int factory[] = {1,1,2,6,24,120,720,5040,40320,362880};
//Cantor用到的常數
bool Cantor(int str[], int n) { //用康托展開判重
long result = 0;
for(int i = 0; i < n; i++) {
int counted = 0;
for(int j = i+1; j < n; j++) {
if(str[i] > str[j]) //當前未出現的元素中是排在第幾個
++counted;
}
result += counted*factory[n-i-1];
}
if(!visited[result]) { //沒有被訪問過
visited[result] = 1;
return 1;
}
else
return 0;
}
int bfs() {
node head;
memcpy(head.state, start, sizeof(head.state)); //復制起點的狀態
head.dis = 0;
queue <node> q; //佇列中放狀態
Cantor(head.state, 9); //用康托展開判重，目的是對起點的visited[]賦初值
q.push(head); //第一個進佇列的是起點狀態
while(!q.empty()) { //處理佇列
head = q.front();
q.pop(); //可在此處列印head.state，看彈出佇列的情況
int z;
for(z = 0; z < 9; z++) //找這個狀態中元素0的位置
if(head.state[z] == 0) //找到了
break;
//轉化為二維，左上角是原點(0, 0)，
int x = z%3; //橫坐標
int y = z/3; //縱坐標
for(int i = 0; i < 4; i++){ //上、下、左、右最多可能有4個新狀態
int newx = x+dir[i][0]; //元素0轉移后的新坐標
int newy = y+dir[i][1];
int nz = newx + 3*newy; //轉化為一維
if(newx>=0 && newx<3 && newy>=0 && newy<3) {//未越界
node newnode;
memcpy(&newnode,&head,sizeof(struct node));//復制這新的狀態
swap(newnode.state[z], newnode.state[nz]);//把0移動到新的位置
newnode.dis ++;
if(memcmp(newnode.state,goal,sizeof(goal)) == 0)
//與目標狀態對比
return newnode.dis; //到達目標狀態，回傳距離，結束
if(Cantor(newnode.state, 9)) //用康托展開判重
q.push(newnode); //把新的狀態放進佇列
}
}
}
return -1; //沒找到
}
int main(){
for(int i = 0; i < 9; i++) cin >> start[i]; //初始狀態
for(int i = 0; i < 9; i++) cin >> goal[i]; //目標狀態
int num = bfs();
if(num != -1) cout << num << endl;
else cout << "Impossible" << endl;
return 0;
}
2.6 擴展學習
??另外，可以用雙向BFS來進一步優化八數碼，參考這篇博文：https://blog.csdn.net/weixin_43914593/article/details/104761298
??
??
??
??
附：2017年第八屆藍橋杯大賽個人賽省賽（軟體類） C/C++ 大學A組考生須知
考生須知：
???考試開始后，選手首先下載題目，并使用考場現場公布的解壓密碼解壓試題，
???考試時間為4小時，時間截止后，提交答案無效，
???在考試強制結束前，選手可以主動結束考試（需要身份驗證），結束考試后將無法繼續提交或瀏覽答案，
???選手可瀏覽自己已經提交的答案，被瀏覽的答案允許拷貝，
???對同一題目，選手可多次提交答案，以最后一次提交的答案為準，
???選手切勿在提交的代碼中書寫“姓名”、“考號”，“院校名”等與身份有關的資訊或其它與競賽題目無關的內容，否則成績無效，
???選手必須通過瀏覽器方式提交自己的答案，選手在其它位置的作答或其它方式提交的答案無效，
???試題包含三種型別：“結果填空”、“代碼填空”與“程式設計”，
??結果填空題：要求選手根據題目描述直接填寫結果，求解方式不限，不要求源代碼，
??把結果填空的答案直接通過網頁提交即可，不要書寫多余的內容，
??代碼填空題：要求選手在弄清給定代碼作業原理的基礎上填寫缺失的部分，使得程式邏輯正確、完整，
??把代碼填空的答案（僅填空處的答案，不包括題面已存在的代碼或符號）直接通過網頁提交即可，不要書寫多余的內容，
??使用ANSI C/ANSI C++ 標準，不要依賴作業系統或編譯器提供的特殊函式，
??程式設計題目：要求選手設計的程式對于給定的輸入能給出正確的輸出結果，考生的程式只有能運行出正確結果才有機會得分，
??注意：在評卷時使用的輸入資料與試卷中給出的示例資料可能是不同的，選手的程式必須是通用的，不能只對試卷中給定的資料有效，
??對于編程題目，要求選手給出的解答完全符合ANSI C++標準，不能使用諸如繪圖、Win32API、中斷呼叫、硬體操作或與作業系統相關的API，
??代碼中允許使用STL類別庫，
??注意: main函式結束必須回傳0
??注意: 所有依賴的函式必須明確地在源檔案中 #include ， 不能通過工程設定而省略常用頭檔案，
??所有原始碼必須在同一檔案中，除錯通過后，拷貝提交，
??提交時，注意選擇所期望的編譯器型別，
1.結果填空 (滿分5分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，只要求提交結果，
??必須通過瀏覽器提交答案，
2.結果填空 (滿分11分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，只要求提交結果，
??必須通過瀏覽器提交答案，
3.結果填空 (滿分13分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，只要求提交結果，
??必須通過瀏覽器提交答案，
4.結果填空 (滿分17分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，只要求提交結果，
??必須通過瀏覽器提交答案，
5.代碼填空 (滿分7分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，
??只要求填寫缺失的代碼部分，千萬不要畫蛇添足，填寫多余的已有代碼或符號，
??必須通過瀏覽器提交答案，
6.代碼填空 (滿分9分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，
??只要求填寫缺失的代碼部分，千萬不要畫蛇添足，填寫多余的已有代碼或符號，
??必須通過瀏覽器提交答案，
7.程式設計（滿分19分）
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，必須通過編程的方式解決問題，
??注意：在評卷時使用的輸入資料與試卷中給出的示例資料可能是不同的，選手的程式必須是通用的，不能只對試卷中給定的資料有效，
??仔細閱讀程式的輸入、輸出要求，千萬不要輸出沒有要求的、多余的內容，例如：“請您輸入xx資料：”，
??建議仔細閱讀示例，不要想當然！
??程式處理完一個用例的資料后，立即退出（return 0），千萬不要回圈等待下一個用例的輸入，
??程式必須使用標準輸入、標準輸出，以便于機器評卷時重定向，
??對于編程題目，要求選手給出的解答完全符合ANSI C++標準，不能使用諸如繪圖、Win32API、中斷呼叫、硬體操作或與作業系統相關的API，
??代碼中允許使用STL類別庫，
??注意: main函式結尾需要return 0
??注意: 所有依賴的函式必須明確地在源檔案中 #include ， 不能通過工程設定而省略常用頭檔案，
??所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，
??提交時，注意選擇所期望的編譯器型別，
8.程式設計（滿分21分）
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，必須通過編程的方式解決問題，
??注意事項同上題
9.程式設計（滿分23分）
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，必須通過編程的方式解決問題，
??注意事項同上題
10.程式設計（滿分25分）
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，必須通過編程的方式解決問題，
??注意事項同上題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245332.html
標籤：其他