注：只為拿分 部分優化思路沒有更新

1 幸運數

題目描述：

小藍認為如果一個數含有偶數個數位，并且前面一半的數位之和等于后面一半的數位之和，則這個數是他的幸運數字。例如 2314 是一個幸運數字, 因為它有 44 個數位, 并且 2+3=1+4 。現在請你幫他計算從 1 至 100000000 之間共有多少個不同的幸運數字。

比較簡單，直接附上我的暴力題解：

答案：4430091

代碼：

#include <bits/stdc++.h>
using namespace std;
string to_str(int x) {string res;while(x) {res = res + (char)(x % 10 + '0');
//        cout<<res<<endl;x /= 10;}reverse(res.begin(), res.end());return res;
}
int main() {int ans = 0;for(int i = 10; i <= 100000000; i++) {string str = to_str(i);
//        cout<<str;int len = str.size();bool flag = true;int left = 0, right = 0;if(len % 2 == 0) {for(int j = 0; j < len / 2; j++) {left += (int)str[j];right +=(int)str[len-j-1];}if(left==right) ans++;}}cout << ans;return 0;
}

2 有獎問答

題目描述：

小藍正在參與一個現場問答的節目。活動中一共有 30 道題目, 每題只有答對和答錯兩種情況, 每答對一題得 10 分，答錯一題分數歸零。

小藍可以在任意時刻結束答題并獲得目前分數對應的獎項，之后不能再答任何題目。最高獎項需要100 分, 所以到達 100 分時小藍會直接停止答題。請注意小藍也可能在不到 100 分時停止答題。

已知小藍最終實際獲得了 70 分對應的獎項, 請問小藍所有可能的答題情況有多少種?

重點：

答錯一題，分數全部歸零，一開始看錯題了，直接用的組合數+循環。。。

答案：8335366

代碼：

附上dfs暴力求解：

#include <bits/stdc++.h>
using namespace std;
int ans = 0;
void dfs(int score, int n) {//答題情況+1 if(score == 70) ans += 1;//答完所有的題或達到100分 停止遞歸 if(n == 30 || score == 100) return;dfs(score + 10, n + 1);//答錯score歸零 dfs(0, n + 1);
}int main(){dfs(0,0);cout<<ans;return 0;
}

3 平方差

題目描述：

$$輸入兩個整數，輸出A^2?B^2的值$$

貌似真題不是這個，為什么官網給的上面這道題。。。
$$給定L,R，問L\le x\le R中有多少個數x滿足存在整數y,z使得x^2=y^2?z^2$$
我們按下面這道題來

思路：數學+找規律

發現x只要滿足是奇數或者4的倍數就是一種答案，因為x的組合形式只能是奇×奇 或者 偶×偶 兩個偶數相乘，結果一定是4的倍數。

• x/2上取整可以獲得[1,x]奇數個數: ?9 / 2? = 5（1，3，5，7，9為[1,x]的奇數）
• x/4下取整可以獲得[1,x]4的倍數的個數?5 / 4? = 1（只有4一個為4的倍數）
• 再加一個前綴和思想求區間內滿足的個數

代碼：

#include <bits/stdc++.h>
using namespace std;
int calc(int x) {return (x + 1) / 2 + x / 4;
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int L, R;cin >> L >> R;cout << calc(R) - calc(L - 1) << endl;return 0;
}

不是我說，這誰能在考場上做出這么大的假設并證明。。。

4 更小的數

題目描述：

0更小的數 - 藍橋云課 (lanqiao.cn)

小藍想要將選出的子串進行反轉后再放入原位置處得到的新的數字 numnew 滿足條件 numnew<num，請你幫他計算下一共有多少種不同的子串選擇方案，只要兩個子串在 num 中的位置不完全相同我們就視作是不同的方案。

就是一個雙指針，不斷判斷區間左端點和右端點的數字大小即可，附上我的題解：

代碼：

#include <iostream>  
#include <vector>  
#include <string>  
using namespace std;  
using ll = long long;  bool is_smaller(int l, int r, const vector<char>& num) {  while (l < r && num[l] == num[r]) {  l++;  r--;  }  return num[l] > num[r]; 
}  int main() {  string input;  getline(cin, input);     vector<char> num;  for (char c : input) {  if (c != ' ') {    num.push_back(c);  }  }  ll ans = 0;  for (int i = 0; i < num.size(); i++) {  for (int j = i; j < num.size(); j++) {  if (is_smaller(i, j, num)) {  ans++;  }  }  }  cout << ans;  return 0;  
}

5 顏色平衡樹

題目描述：

1.顏色平衡樹 - 藍橋云課 (lanqiao.cn)

給定一棵樹，結點由 1 至 n 編號，其中結點 1 是樹根。樹的每個點有一個顏色 Ci。

如果一棵樹中存在的每種顏色的結點個數都相同，則我們稱它是一棵顏色平衡樹。求出這棵樹中有多少個子樹是顏色平衡樹。

思路：啟發式合并

顏色數量最小=顏色數量最大，說明是顏色平衡樹

代碼：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 8;
//vector<pair<int,int>> g[N];
//int col[200000];
map<int, int>col[N], num[N];
vector<int> g[N];
int ans;void dfs(int x, int fa) {//遞歸處理其所有子節點yfor(auto & y : g[x]) {dfs(y, x);//比較x和y的col大小，總是將小的合并到大的中if(col[x].size() < col[y].size()) {swap(col[x], col[y]);swap(num[x], num[y]);}//遍歷子節點y的顏色統計for(auto it : col[y]) {int y_col = it.first, y_num = it.second;//如果顏色在x中已存在：合并數量，并更新num統計if(col[x].count(y_col)) {int x_num = col[x][y_col];num[x][x_num]--;if(num[x][x_num] == 0) num[x].erase(x_num);num[x][x_num + y_num]++;} //如果顏色在x中不存在：直接添加else num[x][y_num]++;col[x][y_col] += y_num;}//清空子節點y的統計信息（釋放內存）map<int, int>tmp1, tmp2;col[y].swap(tmp1);num[y].swap(tmp2);}//x的子樹中所有顏色出現的次數都相同if(num[x].size() == 1) ans++;}int main() {int n;cin >> n;for(int i = 1; i <= n; i++) {int c, fa;cin >> c >> fa;//1號節點沒有father 即fa=0g[fa].push_back(i);col[i][c]++;//i節點 顏色為c的數量num[i][1]++; //i點有顏色數量為1的一個顏色}dfs(1, 0);cout<<ans;return 0;
}

大佬啊，我不會反正

6 買瓜

題目描述：

1.買瓜 - 藍橋云課 (lanqiao.cn)

小藍正在一個瓜攤上買瓜。瓜攤上共有 n 個瓜，每個瓜的重量為 Ai。小藍刀功了得，他可以把任何瓜劈成完全等重的兩份，不過每個瓜只能劈一刀。小藍希望買到的瓜的重量的和恰好為 m。

請問小藍至少要劈多少個瓜才能買到重量恰好為 m 的瓜。如果無論怎樣小藍都無法得到總重恰好為 m 的瓜，請輸出 ?1。

思路：dfs+剪枝（只能通過45%）

每個瓜只可能存在三種情況：

1. 選擇整一個瓜
2. 被切后選擇一半
3. 不選擇該瓜

dfs暴力求解之后剪枝優化：

1. 當前方案切的刀數大于等于之前已知方案的最優解
2. 如果該路徑上包括未選擇的瓜的重量總和不夠m
3. 當前已有的重量超過m，則當前方案非法
4. 貪心trick：按瓜的重量從大到小排序

從上面的思路得出我們的數據結構：

• 后綴和數組 s[i]
• 傳參：當前判斷第u個瓜，目前已有的重量w，切的刀數cnt

代碼：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 33;
int a[N], s[N];
int ans=INF;
int m, n;
void dfs(int u, double w, int cnt) {//當前方案有效if(w == m) {ans = min(ans, cnt);return;}//已經遍歷完成if(u > n) return;//當前方案不優if(cnt > ans) return;if(w + s[u] < m) return;//選擇列表dfs(u + 1, w + a[u], cnt);//選整個瓜dfs(u + 1, w + a[u] / 2.0, cnt + 1);//切且選半個瓜dfs(u + 1, w, cnt);//不選該瓜
}
bool cmp(int x, int y) {return x > y;
}
int main() {cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + n + 1, cmp);//記錄后綴和for(int i = n; i >= 1; i--) s[i] = s[i + 1] + a[i];dfs(1, 0.0, 0);cout << (ans==INF? -1 : ans);return 0;
}

標答給的動態規劃。。。

7 異或和之和

題目描述：

0異或和之和 - 藍橋云課 (lanqiao.cn)

給定一個數組 Ai ，分別求其每個子段的異或和，并求出它們的和。或者說，對于每組滿足 1 ≤ L ≤ R ≤ n 的 L , R ，求出數組中第 L 至第 R 個元素的異或和。然后輸出每組 L, R 得到的結果加起來的值。

代碼：

沒有位運算優化，直接附上我的暴力代碼，可以過90%

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
using ll = long long;
ll a[N];
int main() {int n;cin >> n;ll ans=0;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) {ll sum=0;for(int j = i; j <= n; j++) {sum^=a[j];ans+=sum;}}cout<<ans;return 0;
}

之后再更新完善吧，孩子沒時間了。。。

8 網絡穩定性

題目描述：

0網絡穩定性 - 藍橋云課 (lanqiao.cn)

有一個局域網，由 n 個設備和 m 條物理連接組成，第 i 條連接的穩定性為w i 。對于從設備 A 到設備 B 的一條經過了若干個物理連接的路徑，我們記這條路徑的穩定性為其經過所有連接中穩定性最低的那個。

我們記設備 A 到設備 B 之間通信的穩定性為 A 至 B 的所有可行路徑的穩定性中最高的那一條。
給定局域網中的設備的物理連接情況，求出若干組設備 x i 和 y i 之間的通信穩定性。如果兩臺設備之間不存在任何路徑，請輸出 ?1 。

孩子先不想看了，這種圖論的題太吃基礎了。。。可以直接看題解

9 像素放置

小藍最近迷上了一款名為《像素放置》的游戲，游戲在一個 n × m 的網格棋盤上進行，棋盤含有 n 行，每行包含 m 個方格。

玩家的任務就是需要對這n × m 個方格進行像素填充，填充顏色只有黑色或白色兩種。有些方格中會出現一個整數數字 x(0 ≤ x ≤ 9)，這表示當前方格加上周圍八個方向上相鄰的方格（分別是上方、下方、左方、右方、左上方、右上方、左下方、右下方）共九個方格內有且僅有 x 個方格需要用黑色填充。
玩家需要在滿足所有數字約束下對網格進行像素填充，請你幫助小藍來完成。題目保證所有數據都有解并且解是唯一的。

思路：dfs+判斷合法

代碼：

#include <iostream>
using namespace std;
int n, m;
char d[12][12];//原始數組 
int f[12][12];//填充后的數組 //檢查是否合法 
bool check(int x, int y) {if(d[x][y] == '_') return true;int cnt = 0;for(int i = -1; i <= 1; i++) {for(int j = -1; j <= 1; j++) cnt += f[x + i][y + j];}// 如果周圍1(黑棋)數量等于 d[x][y] 對應的數字，返回true，否則返回falseif(cnt == d[x][y] - '0') return true;return false;
}
//深搜試探，從左往右，從上往下
void dfs(int x, int y) {//檢查是否符合最后一行if(x == n + 1) {for(int j = 1; j <= m; j++) {if(!check(n, j)) return;}//找到答案，直接輸出，結束for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {cout << f[i][j];}cout << endl;}return;}//到該行的最后一列 準備換行if(y == m) {//嘗試0 f[x][y] = 0;if(x == 1 || (y == 1 && check(x - 1, y)) || (check(x - 1, y - 1) && check(x - 1, y))) {dfs(x + 1, 1);}//嘗試1 f[x][y] = 1;if(x == 1 || (y == 1 && check(x - 1, y)) || (check(x - 1, y - 1) && check(x - 1, y))) {dfs(x + 1, 1); //換行}}//沒到換行，遍歷該行下一列else {f[x][y] = 0;if(x == 1 || y == 1 || (check(x - 1, y - 1)))dfs(x, y + 1);f[x][y] = 1;if(x == 1 || y == 1 || check(x - 1, y - 1))dfs(x, y + 1);}
}int main() {cin >> n >> m;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {cin >> d[i][j];}}dfs(1, 1);return 0;
}

10 翻轉硬幣

0翻轉硬幣 - 藍橋云課 (lanqiao.cn)

這個的難度也是不想再吐槽了。。。直接借鑒的別人的50%的暴力：

思路：

轉一個i位置不會影響到小于i的位置，所以暴力得從小到大，確保前面每個位置都已經被修改，那么久根據題意從2開始，遇到一個i位置是0，就開始把i的倍數的位置翻轉即可。用一個tot記錄需要翻轉的位置數，根據翻轉的情況來更改tot，如果某次執行后tot為0那么久代表已經全部為1，統計翻轉次數即可。

代碼：

#include <bits/stdc++.h>
using namespace std;
bitset<200000001>t;
int main() {int n;cin >> n;int ans = 1;t[1] = 1;int tot = n - 1;for(int i = 2; i <= n; i++) {if(t[i]) continue;int j = i;ans++;while(j <= n) {t[j] = !t[j];if(t[j]) tot--;else tot++;j += i;}if(!tot) break;}cout << ans;return 0;
}

自己模擬根本沒時間看這道題。。。