表示剛剛查了成績，省賽一等獎，有資格去北京了，然後寫一下總結，
先來寫一下我懂的題目，畢竟我也是菜鳥，聽說國賽比預賽難幾個等級。。。
第一題
報紙頁數
X星球日報和我們地球的城市早報是一樣的，
都是一些單獨的紙張疊在一起而已。每張紙印有4版。
比如，某張報紙包含的4頁是：5,6,11,12，
可以確定它應該是最上邊的第2張報紙。
我們在太空中撿到了一張X星球的報紙，4個頁碼分別是：
1125,1126,1727,1728
請你計算這份報紙一共多少頁（也就是最大頁碼,並不是用了幾張紙哦）？
請填寫表示總頁數的數字。
注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。
這道題我沒填，說實話，沒看懂，沒看過報紙的孩紙
不會。。
貼吧說的。。。
1125+1126+1727+1728=1+2+X，X等於5703，5703等於2851+2852
第二題
煤球數目
有一堆煤球，堆成三角稜錐形。具體：
第一層放1個，
第二層3個（排列成三角形），
第三層6個（排列成三角形），
第四層10個（排列成三角形），
….
如果一共有100層，共有多少個煤球？
請填表示煤球總數目的數字。
注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。
#include
#include
using namespace std;
int getInt(int n) {
int n1 = 1;
int sum = n1;
for (int i = 2; i <= n; i++) {
sum = i + n1;
n1 = sum;
}
return sum;
}
int main() {
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += getInt(i);
}
cout << sum << endl;
return 0;
}
我當時填的5050，計算的是第100層。。 題目要求的是100層總共多少。
答案171700
第三題
平方怪圈
如果把一個正整數的每一位都平方後再求和，得到一個新的正整數。
對新產生的正整數再做同樣的處理。
如此一來，你會發現，不管開始取的是什麼數字，
最終如果不是落入1，就是落入同一個循環圈。
請寫出這個循環圈中最大的那個數字。
請填寫該最大數字。
注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。
#include
#include
#include
using namespace std;
char s[100];
int getInt(char *s) {
int sum = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
sum += (s[i]-'0')*(s[i]-'0');
}
return sum;
}
int main() {
int num = 3;
int MAX = 0;
for (int i = 0; i < 100; i++) {
sprintf(s, "%d", num);
num = getInt(s);
MAX = max(MAX, num);
}
cout << MAX << endl;
return 0;
}
答案145 有一些是1，可以打印出來
第四題
打印方格
11分
小明想在控制台上輸出 m x n 個方格。
比如 10x4的，輸出的樣子是：
+—+—+—+—+—+—+—+—+—+—+
| | | | | | | | | | |
+—+—+—+—+—+—+—+—+—+—+
| | | | | | | | | | |
+—+—+—+—+—+—+—+—+—+—+
| | | | | | | | | | |
+—+—+—+—+—+—+—+—+—+—+
| | | | | | | | | | |
+—+—+—+—+—+—+—+—+—+—+
（如果顯示有問題，可以參見【圖1.jpg】）
以下是小明寫的程序，請你分析其流程，填寫劃線部分缺少的代碼。
#include
//打印m列，n行的方格
void f(int m, int n)
{
int row;
int col;
for(row=0; row
注意：僅僅填寫劃線部分缺少的內容，不要添加任何已有內容或說明性文字。
for循環即可，反正我是這樣寫的
for(col=0; col
第五題
13分
快速排序
排序在各種場合經常被用到。
快速排序是十分常用的高效率的算法。
其思想是：先選一個“標尺”，
用它把整個隊列過一遍篩子，
以保證：其左邊的元素都不大於它，其右邊的元素都不小於它。
這樣，排序問題就被分割為兩個子區間。
再分別對子區間排序就可以了。
下面的代碼是一種實現，請分析並填寫劃線部分缺少的代碼。
#include
void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];
while(1){
while(ix);
if(i>=j) break;
swap(a,i,j);
}
______________________;
return j;
}
void quicksort(int a[], int p, int r)
{
if(p
答案是swap(a,p,j)
第六題
6.
15分
湊算式
B DEF
A + — + ——- = 10
C GHI
（如果顯示有問題，可以參見【圖1.jpg】）
這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。
比如：
6+8/3+952/714 就是一種解法，
5+3/1+972/486 是另一種解法。
這個算式一共有多少種解法？
注意：你提交應該是個整數，不要填寫任何多余的內容或說明性文字。
![這裡寫圖片描述](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012110121576.png "\")
記住要通分，不要fabs(…) < 1E10 這樣來進行約等於
dfs思路
#include
#include
#include
using namespace std;
int a1[9], book[9], COUNT = 0;
bool getSum(int *a) {
int A = a[0], B = a[1], C = a[2];
int DEF = a[3]*100+a[4]*10+a[5], GHI = a[6]*100+a[7]*10+a[8];
if ((B*GHI+DEF*C)%(C*GHI) != 0) return false;
if (A+(B*GHI+DEF*C)/(C*GHI) == 10) return true;
return false;
}
void dfs(int step) {
if (step == 9) {
if (getSum(a1)) COUNT++;
return;
}
for (int i = 0; i < 9; i++) {
if (book[i] == 0) {
book[i] = 1;
a1[step] = i+1;
dfs(step+1);
book[i] = 0;
}
}
}
int main() {
dfs(0);
cout << COUNT << endl;
return 0;
}
答案29
第七題
19分
寒假作業
現在小學的數學題目也不是那麼好玩的。
看看這個寒假作業：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果顯示不出來，可以參見【圖1.jpg】)
每個方塊代表1~13中的某一個數字，但不能重復。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
就算兩種解法。（加法，乘法交換律後算不同的方案）
你一共找到了多少種方案？
還是dfs思路
#include
#include
#include
using namespace std;
int a1[13], book[13], COUNT = 0;
bool getSum(int *a) {
if (a[9]%a[10] != 0) return false;
return (
a[0]+a[1] == a[2] &&
a[3]-a[4] == a[5] &&
a[6]*a[7] == a[8] &&
a[9]/a[10] == a[11]
);
}
void dfs(int step) {
if (step == 13) {
if (getSum(a1)) COUNT++;
return;
}
for (int i = 0; i < 13; i++) {
if (book[i] == 0) {
book[i] = 1;
a1[step] = i+1;
dfs(step+1);
book[i] = 0;
}
}
}
int main() {
dfs(0);
cout << COUNT << endl;
return 0;
}
大概運行了5分鐘。。
答案64
如果有好的解法，請告訴我，本人水平有限。嘿嘿
第八題
21分
冰雹數
任意給定一個正整數N，
如果是偶數，執行： N / 2
如果是奇數，執行： N * 3 + 1
生成的新的數字再執行同樣的動作，循環往復。
通過觀察發現，這個數字會一會兒上升到很高，
一會兒又降落下來。
就這樣起起落落的，但最終必會落到“1”
這有點像小冰雹粒子在冰雹雲中翻滾增長的樣子。
比如N=9
9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
可以看到，N=9的時候，這個“小冰雹”最高沖到了52這個高度。
輸入格式：
一個正整數N（N<1000000）
輸出格式：
一個正整數，表示不大於N的數字，經過冰雹數變換過程中，最高沖到了多少。
例如，輸入：
10
程序應該輸出：
52
再例如，輸入：
100
程序應該輸出：
9232
相信很多童鞋被這道題給坑了。。。 哈哈哈，請看清題意
一個正整數，表示不大於N的數字
好吧，是後面往前面推，在考場我不到五分鐘寫好代碼。。。 然後跪了。。
錯誤代碼
#include
#include
using namespace std;
int getInt(int N) {
if (N%2 == 0) return N/2;
return N*3+1;
}
int main() {
int N;
scanf("%d", &N);
int MAX = N;
while(N != 1) {
N = getInt(N);
MAX = max(MAX, N);
}
cout << MAX << endl;
return 0;
}
寫完之後，感覺麼麼哒。。。
然後一測數據，感覺不對勁，是不是題目測試數據給錯了，到了快交卷，我還是以為是測試數據錯了。。
其實是我理解題意錯了。
正確代碼
#include
#include
using namespace std;
int getInt(int N) {
if (N%2 == 0) return N/2;
return N*3+1;
}
int main() {
int N, MAX, M;
scanf("%d", &N);
MAX = N;
for (int i = N; i >= 1; i--) {
M = i;
while(M != 1) {
M = getInt(M);
MAX = max(MAX, M);
}
}
cout << MAX << endl;
return 0;
}
如果輸入的數大於122222就會超時。。
水一部分數據吧。
第九題
25
卡片換位
你玩過華容道的游戲嗎？
這是個類似的，但更簡單的游戲。
看下面 3 x 2 的格子
+—+—+—+
| A | * | * |
+—+—+—+
| B | | * |
+—+—+—+
在其中放5張牌，其中A代表關羽，B代表張飛，* 代表士兵。
還有一個格子是空著的。
你可以把一張牌移動到相鄰的空格中去(對角不算相鄰)。
游戲的目標是：關羽和張飛交換位置，其它的牌隨便在哪裡都可以。
輸入格式：
輸入兩行6個字符表示當前的局面
輸出格式：
一個整數，表示最少多少步，才能把AB換位（其它牌位置隨意）
![這裡寫圖片描述](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012110121509.png "\")
資源約定：
峰值內存消耗 < 256M
CPU消耗 < 1000ms
記憶化搜索
不會。。
第十道
密碼脫落
X星球的考古學家發現了一批古代留下來的密碼。
這些密碼是由A、B、C、D 四種植物的種子串成的序列。
仔細分析發現，這些密碼串當初應該是前後對稱的（也就是我們說的鏡像串）。
由於年代久遠，其中許多種子脫落了，因而可能會失去鏡像的特征。
你的任務是：
給定一個現在看到的密碼串，計算一下從當初的狀態，它要至少脫落多少個種子，才可能會變成現在的樣子。
輸入一行，表示現在看到的密碼串（長度不大於1000）
要求輸出一個正整數，表示至少脫落了多少個種子。
例如，輸入：
ABCBA
則程序應該輸出：
0
再例如，輸入：
ABECDCBABC
則程序應該輸出：
3
資源約定：
峰值內存消耗 < 256M
CPU消耗 < 3000ms
請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內容。
所有代碼放在同一個源文件中，調試通過後，拷貝提交該源碼。
注意: main函數需要返回0
注意: 只使用ANSI C/ANSI C++ 標准，不要調用依賴於編譯環境或操作系統的特殊函數。
注意: 所有依賴的函數必須明確地在源文件中 #include ， 不能通過工程設置而省略常用頭文件。
提交時，注意選擇所期望的編譯器類型。
聽大神說動態規劃
不會。。。
