【藍橋杯】十五屆省賽B組c++

前言

握手問題

分析

排列組合寫法

枚舉

小球反彈

分析

代碼

好數

分析

代碼

R 格式

分析

代碼

寶石組合

分析

代碼

數字接龍

分析

代碼

拔河

分析

代碼

總結

前言

主播這兩天做了一套藍橋杯的省賽題目（切實感受到了自己有多菜）。

握手問題

分析

填空題的第一道，很簡單，不過主播第一次錯了（原因是把方案數的+想成了*，被自己蠢笑了）。

這道題如果有一些排列組合的基礎的話應該很容易想到答案就是從7加到49。

但這不代表沒有排列組合的基礎就不會，依然可以寫對這道題。（枚舉）

排列組合寫法

#include<iostream>
using namespace std;
int l;
?
int main()
{for(int i = 7; i <= 49; i++)l += i;cout << l;
}

枚舉

#include<iostream>
using namespace std;
int l;
int main()
{for(int i = 1; i <= 50; i++)for(int j = i + 1; j <= 50; j++){if(i <= 7 && j <= 7) continue; //選定七個人不握手l++;}cout << l;
}

小球反彈

分析

這道題主播依舊沒有寫出來（）

物理題，首先將速度分解到x和y兩個方向，隨后整個運動過程就可以看作在x軸上來回運動的同時在y軸上來回運動。

假設在x軸上經過a個來回，在y軸上經過b個來回后回到原點，可得：
$2ax/dx = 2by/dy$

移項：
$a/b = dx * y/ dy * x$

隨后我們對a / b進行約分，即： $a / gcd(a, b), b / gcd(a, b)$

隨后再根據路程和速度即可得出：。

最后通過t * v求出路程。

代碼

#include<iostream>
#include<cmath>
using namespace std;
int x = 343720, y = 233333;
int dx = 15, dy = 17;
?
int gcd(int a, int b)
{if(b == 0) return a;return gcd(b, a % b);
}
int main()
{int a = y * dx, b = x * dy;a /= gcd(a, b); //約分double t = 2.0 * a * x / dx; //時間
?printf("%.2lf", t * sqrt(dx * dx + dy * dy));
?return 0;
}

好數

分析

觀察數據量——1e7枚舉每一位的話最大是7 * 1e7，小于1e8所以直接暴力枚舉計數即可。（這個主播最開始也是沒有想到，去寫模擬了）

代碼

#include<iostream>
using namespace std;
int l, n;
?
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){int j = 1, k = i;l++;while(k){if((j & 1) != (k & 1)){l--;break;}j++;k /= 10;}}printf("%d", l);return 0;
}

R 格式

分析

發現n很大d也很大，所以考慮高精度。

這道題主要考察了對浮點數的高精度寫法，可以在最開始忽略掉小數點，隨后進行累乘（高精度 * 低精度），再最后手動進位（高精度 + 低精度）。

主播最開始還去寫了高精度*高精度QAQ，最后發現根本沒必要，真是蠢到家了。

代碼

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
int n;
string l;
vector<int> A, B;
?
vector<int> cur(vector<int>& A, int b)
{int x = 0;vector<int> C;for(int i = 0; i < A.size(); i++){x += A[i] * b;C.push_back(x % 10);x /= 10;}while(x){C.push_back(x % 10);x /= 10;}return C;
}
?
vector<int> add(vector<int>& A, vector<int> B)
{int x = 0;vector<int> C;for(int i = 0; i < A.size() || i < B.size(); i++){if(i < A.size()) x += A[i];if(i < B.size()) x += B[i];C.push_back(x % 10);x /= 10;}if(x) C.push_back(1);return C;
}
?
int main()
{cin >> n >> l;for(int i = l.size() - 1; i >= 0; i--){if(l[i] == '.') continue;A.push_back(l[i] - '0'); //先不考慮小數點}for(int i = 1; i <= n; i++)A = cur(A, 2); //乘法計算.// 四舍五入int i = 0;for(; i < l.size(); i++)if(l[i] == '.') break; //找到小數點位置
?int x = 0;int d = l.size() - 1 - i; //小數部分reverse(A.rbegin(), A.rend()); //反轉for(int k = 0; k < l.size() - 1 - i; k++){x = A.back();A.pop_back();} //消除小數部分reverse(A.rbegin(), A.rend()); //反轉if(x >= 5)A = add(A, {1}); //進位for(int i = A.size() - 1; i >= 0; i--)printf("%d", A[i]);return 0;
}

寶石組合

分析

題意很簡單，這道題的主要難點就在于公式的推導。
$S = H_aH_bH_c * LCM(H_a, H_b, H_c) / (LCM(H_a, H_b)*LCM(H_a, H_c)*LCM(H_b,H_c))$

公式的推導有兩種方法，因為主播目前只熟悉一種所以就按照這個思路來講了。

公式推導基于算數基本定理：

我們將每一項進行質因數分解可得到
$H_a = p_1^{c_1} * p_2^{c_2} * ... p_n^{c_n}$

同理將Hb于Hc分解質因數可得
$H_a = p_1^{e_1} * p_2^{e_2} * ... p_n^{e_n}$
$H_a = p_1^{d_1} * p_2^{d_2} * ... p_n^{d_n}$

我們按照質數進行因式分解，取出其中的一項可得：
$p_1^{c_1} * p_1^{d_1} * p_1^{e_1} * p_1^{max(c_1, d_1, e_1)} / (p_1^{max(c_1, d_1)} * p_1^{max(c_1, e_1)} * p_1^{max(d_1, e_1)})$

隨后我們消掉max和min函數，設c1 > d1 > e1，可得：
$p^{e_1}$

又
$e_1 = min(c_1, d_1, e_1)$

滿足最大公因數的條件，我們最后將公式整合可得：
$S = gcd(H_a, H_b, H_c)$

至此我們完成了本道題的第一步

隨后我們來查找max(gcd(Ha, Hb, Hc))。

顯然對于本道題直接枚舉的話會超時，如何來做呢？

可以發現H很小且gcd < H，所以我們可以直接枚舉約數。

代碼

#include<iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){int x; scanf("%d", &x);a[x]++; //存儲出現次數}for(int i = N - 1; i; i--) ? ? ? ? ? {int l = 0;for(int j = i; j < N; j += i)l += a[j];if(l >= 3){l = 0;for(int j = i; j < N && l < 3; j += i)for(int k = 0; k < a[j] && l < 3; k++, l++)printf("%d ", j);break;}}return 0;
}

數字接龍

分析

發現數據量很小所以直接搜索就好。

對于本道題的一個細節是如何判斷交叉。

主播的建議是存儲一個這樣的值：read[x + dx][y + dy]

數組內的兩個參數是起始坐標和終止坐標。

這樣寫為什么是正確的呢？

因為只有斜著走的時候才有可能出現交叉的情況，所以每個方向的步長都是1。

很容易發現兩個方向是一個奇數和一個偶數，和一定是一個奇數，而若將一個奇數分解為兩個相差為1的數字只有兩種情況（交換位置）。對于本道題來說正合適。所以寫一個這樣的數組就可以避免交叉。

代碼

#include <iostream>
#include <cstring>
#include <vector>
#define s second
#define f first
using namespace std;
typedef pair<int, int> PII;
const int N = 15;
int n, p;
int map[N][N];
vector<int> to[N][N]; //存儲能夠到達哪個點，顯著降低時間復雜度的小小小優化。
bool read[N][N];
bool cun[2 * N][2 * N]; //防止交叉
vector<int> vtr;
PII s[] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; //八個方向
?
bool dfs(int x, int y, int k)
{if(x == n && y == n && vtr.size() == n * n - 1){for(int i = 0; i < vtr.size(); i++)printf("%d", vtr[i]);return true;}if(x == n && y == n) return false;for(int i : to[x][y]){int dx = x + s[i].f, dy = y + s[i].s;if(read[dx][dy] == false) //第一層篩選{if(i & 1 == 0 || cun[x + dx][y + dy] == false) //無交叉{read[dx][dy] = true;if(i & 1) cun[x + dx][y + dy] = true;vtr.push_back(i);if(dfs(dx, dy, (k + 1) % p))return true;vtr.pop_back();if(i & 1) cun[x + dx][y + dy] = false;read[dx][dy] = false;}}}return false;
}
?
int main()
{memset(map, 0x3f, sizeof map);scanf("%d%d", &n, &p);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%d", &map[i][j]);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)for(int k = 0; k < 8; k++){int dx = i + s[k].f, dy = j + s[k].s;if(map[dx][dy] == (map[i][j] + 1) % p)to[i][j].push_back(k); }read[1][1] = true;if(!dfs(1, 1, 1))printf("-1");return 0;
}

拔河

分析

最開始以為是dp但是后來發現我想多了。

題目要求兩個不相交的區間的差值最小，可以發現無論兩個區間又無相交情況差值都是不變的，所以問題就轉化成了差值最小的區間問題。

套用模板——首先求出所有區間的和，隨后sort之后差值最小的必然會在相鄰的兩個區間上產生。當然對于本題需要考慮結果是否合法，即：一個區間不可以完全包含另一個區間。（使用區間取交集模板即可）

代碼

#include<iostream>
#include<vector>
#include<algorithm>
#define s second
#define f first
using namespace std;
typedef long long LL;
?
typedef pair<LL, pair<int, int>> PIII;
using namespace std;
const int N = 2010;
int n;
LL s[N];
vector<PIII> vtr; 
?
bool cmp(pair<int, int> A, pair<int, int> B)
{int x = max(A.f, B.f);int y = min(A.s, B.s); //查看有沒有交集return x == A.f && y == A.s || x == B.f && y == B.s;
}
?
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%lld", s + i);s[i] += s[i - 1];}LL cnt = 0x3f3f3f3f3f3f3f3f;for(int i = 1; i <= n; i++)for(int j = i; j <= n; j++)vtr.push_back({s[j] - ?s[i - 1], {i, j}});sort(vtr.begin(), vtr.end());for(int i = 1; i < vtr.size(); i++)if(!cmp(vtr[i].s, vtr[i - 1].s))cnt = min(cnt, vtr[i].f - vtr[i - 1].f);printf("%lld", cnt);return 0;
}