柚子快報邀請碼778899分享：十二屆/十四屆藍(lán)橋杯學(xué)習(xí)筆記
柚子快報邀請碼778899分享：十二屆/十四屆藍(lán)橋杯學(xué)習(xí)筆記
十二
1.卡片
挺好寫的，其實手寫用筆搓也能搓出來。
#include
using namespace std;
int sum = 1;
int t;
int h;
int main() {
?? ?for (int i=1; sum <= 2021; i++) {
?? ??? ?for (t = i; t != 0; t = t / 10) { //測定一個數(shù)有幾個1
?? ??? ??? ?if (t%10 == 1)
?? ??? ??? ??? ?sum++;
?? ??? ?}
?? ??? ?h = i; //記錄一下數(shù)字
?? ?}
?? ?cout << h;
?? ?return 0;
}
2.直線
思路：主要是通過set容器去除重復(fù)值，再就是四重循環(huán)來去到兩個點的坐標(biāo)。為了避免重復(fù)，在第二個點處去x值加一為起始點。注意最后加的20為斜率不存在的情況。
代碼：
#include
#include
using namespace std;
int main()
{
? ? set
? ? double k, b;
? ? for (int x1 = 0; x1 < 20; x1++) {
? ? ? ? for (int y1 = 0; y1 < 21; y1++) {
? ? ? ? ? ? for (int x2 = x1 + 1; x2 < 20; x2++) { ? ? //給x加
? ? ? ? ? ? ? ? for (int y2 = 0; y2 < 21; y2++) {
? ? ? ? ? ? ? ? ? ? k = (double)(y1 - y2) / (x1 - x2);
? ? ? ? ? ? ? ? ? ? b = (double)(x1 * y2 - x2 * y1) / (x1 - x2); ?//將公式通分，不然會有精度損失
? ? ? ? ? ? ? ? ? ? line.insert({ k,b });
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? cout << line.size() + 20; ?//斜率不存在的情況加20
? ? return 0;
}
3.貨物擺放
求因子計算方案
#include
using namespace std;
#include
#include
int main() {
? ? //其實為什么我們那樣去想，因為那樣去想最簡單，最不費腦子。但是我們發(fā)現(xiàn)那種方法很多組都是無效的，也就是出現(xiàn)不是num因子的數(shù)字出現(xiàn)
? ? //因此這樣的計算毫無意義反而給我們的CPU增加負(fù)擔(dān)；
? ? //好，簡化的目的擺明了，找num的因子唄~
? ? //但是我們事先不知道num到底有多少因子，因此這里可以設(shè)置一個vector容器，產(chǎn)生一個就壓進(jìn)vector容器里
? ? //因為因子也可能是num本身，所以咱們的因子容器設(shè)置為long long類型的
? ? //我們開始找因子，只需要找到num的平方根即可，因為如果再往后找的話，就找到之前小于num平方根的i除得的num中對應(yīng)于i的較大的因子；
? ? //這里對于較大的因子我們可以通過循環(huán)里的j得到
?? ?long long n= 2021041820210418;
?? ?vector
?? ?int sum = 0;
?? ?for (long long i = 1; i<=sqrt(n); i++) {
?? ??? ?if (n % i == 0) {
?? ??? ??? ?S.push_back(i);
?? ??? ??? ?long long j = n / i;
?? ??? ??? ?S.push_back(j);
?? ??? ?}
?? ??? ??? ?
?? ?}
?? ?for (int i = 0; i < S.size(); i++) {
?? ?//?? ?cout << S[i] << endl;
?? ??? ?for (int j = 0; j < S.size(); j++) {
?? ??? ??? ?for (int k = 0; k < S.size(); k++) {
?? ??? ??? ??? ?if (S[i] * S[j] * S[k] == n)
?? ??? ??? ??? ??? ?sum++;
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?cout << sum << endl;
}
4.路徑
自己寫，寫麻煩了。。。。。。。。
題解他們用動態(tài)規(guī)劃寫了，我用迪杰維斯特。。麻了
迪杰韋斯特：
#include
using namespace std;
const int N = 2021,n=2021;
long long dist[N]; ?//起點到第N點的距離
long long g[N][N]; ? //構(gòu)建鄰接矩陣
int vis[N]; ?//判斷第N個節(jié)點是否被訪問過
int gcd(int c, int d) { ?//輾轉(zhuǎn)相除法求的最大公約數(shù)
?? ?if (c % d == 0)
?? ??? ?return d;
?? ?else
?? ??? ?return gcd(d, c % d);
}
int func_Q(int a, int b) { ? //再求得最小公倍數(shù)
?? ?return a * b / gcd(a, b);
}
void Store() { ?//存圖
?? ?memset(g, 0x3f3f3f3f, sizeof(g));
?? ?for (int i = 1; i <= 2021; i++) {
?? ??? ?for (int j = 1; j <= 2021; j++) {
?? ??? ??? ?if (i == j)
?? ??? ??? ??? ?g[i][j] = g[j][i] = 0;
?? ??? ??? ?if ((i - j) <= 21 && (i - j) >0)
?? ??? ??? ??? ?g[i][j] =g[j][i] = func_Q(i, j);
?? ??? ??? ?/*if((j - i) <= 21 && (j - i) > 0)
?? ??? ??? ??? ?g[i][j] = func_Q(j, i);?? ?*/
?? ??? ?}
?? ?}
}
int dijkstra() {
?? ?memset(dist, 0x3f3f3f3f, sizeof(dist)); ?//初始化最短距離數(shù)組
?? ?for (int i = 1; i <= n; i++) { ?//初始化距離數(shù)組第一次和記錄訪問數(shù)組
?? ??? ?dist[i] = g[1][i];
?? ??? ?vis[i] = 0;
?? ?}
?? ?dist[1] = 0; ?//第一個點到第一個點的距離為0
?? ?for (int i = 0; i < n; i++) { ?
?? ??? ?int t = -1;
?? ??? ?for (int j = 1; j <= n; j++) {
?? ??? ??? ?if (!vis[j] && (t == -1 || dist[j] < dist[t])) {//選取未訪問的且距離起點最近的點
?? ??? ??? ??? ?t=j;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?vis[t] = 1; ?//標(biāo)記該點已訪問
?? ??? ?for (int j = 1; j <=n; j++) { //更新未訪問點的最短距離
?? ??? ??? ?if (vis[j] == 0)?
?? ??? ??? ??? ?dist[j]= min(dist[j],dist[t]+g[t][j]);?? ??? ??? ?
?? ??? ?}
?? ?}
?? ?return dist[n];
}
int main() {
?? ?Store();
?? ?cout << dijkstra()< ?? ?return 0; } 動態(tài)規(guī)劃，第二種辦法： 注意：#include #include using namespace std; int gcd(int x, int y) { ? ? return !y ? x : gcd(y, x % y); ? //輾轉(zhuǎn)相除法，背過背過 } int main() { ? ? int f[2022]; ? ?//儲存最短路徑 ? ? memset(f, 0, sizeof f); ? ?//初始化為0 ? ? for (int i = 1; i <= 2021; i++) { ? ?//一個一個節(jié)點過 ? ? ? ? for (int j = i + 1; j <= i + 21; j++) { ? //賦權(quán)以及計算 ? ? ? ? ? ? if (j > 2021) ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? if (f[j] == 0) ? //f[j]=0則代表第一次計算這個點，到這個點的距離為到i的加上i到j(luò)的權(quán) ? ? ? ? ? ? ? ? f[j] = f[i] + j * i / gcd(i, j); ? ? ? ? ? ? else ? //不是第一來的話就比較比較 ? ? ? ? ? ? ? ? f[j] = min(f[j], f[i] + j * i / gcd(i, j)); ? ? ? ? } ? ? } ? ? cout << f[2021] << endl; } 5.時間顯示 簡單 #include using namespace std; int main() { ?? ?long long n; ?? ?cin >> n; ?? ?n = n % 86400000; ?? ?int hour=n; ?? ?hour = hour / 3600000; ?? ?/*while (hour >= 24) { ?? ??? ?hour=hour% ?? ?}*/ ?? ?int min = (n - hour * 3600000) / 60000; ?? ?int miao = (n - hour * 3600000 - min * 60000) / 1000; ?? ?printf("%02d:%02d:%02d", hour, min, miao); } 6.砝碼稱重 思路在注釋里面了 #include using namespace std; long long N; long long sum = 0; long long ans = 0; long long a[101]; int dp[101][100001]; //dp[i][j]表示前i個砝碼能得到j(luò)的重量 int main() { cin >> N; for (int i = 1; i <= N; i++) { cin >> a[i]; sum += a[i]; } for (int i = 1; i <= N; i++) { for (long long j = 1; j <= sum; j++) { dp[i][j] = dp[i - 1][j]; //先繼承前i-1個的狀態(tài) if (dp[i][j] == 0) { //如果前i-1個算不出j的重量，那么就使用第i個砝碼試試 //使用第i個砝碼有三種情況 if (j == a[i]) dp[i][j] = 1; //第一種情況，直接用第i個砝碼 if (dp[i - 1][abs(j - a[i])] == 1) dp[i][j] = 1; //第二種情況，前i-1個能稱出j-a[i]的重量，那直接加就行 if (dp[i - 1][j + a[i]] == 1) dp[i][j] = 1; //第三種情況，減第i個砝碼； } } } for (long long j = 1; j <= sum; j++) { if (dp[N][j] == 1) ans++; } cout < return 0; } 7.異或數(shù)列 題解的大佬，真牛 #include #include using namespace std; int main() { int t; cin >> t; while (t--) { int n = 0; cin >> n; int res = 0; vector int x; for (int i = 0; i < n; ++i) { cin >> x; res ^= x; for (int j = 0; (j < 32) && x; ++j) { if (x & 1) { v[j]++; } x >>= 1; } } /* * 最優(yōu)策略： * 為了讓自己的數(shù)更大，優(yōu)先選擇將高位的1異或到自己的數(shù)上 * 如果自己高位已是1，對方對應(yīng)高位也是1，則優(yōu)先將1異或到對方身上，使其為0 */ // 特殊情況：所有數(shù)異或起來是0，說明每個比特位上的1都有偶數(shù)個 // 此時采取最優(yōu)策略，最終Alice和Bob得到的數(shù)是相同的，因此平局 if (res == 0) { cout << 0 << endl; } else { // 一般情況:從高位開始選數(shù)進(jìn)行異或 for (int i = 31; i >= 0; --i) { if (v[i] > 0) { if (v[i] % 2 == 0) // 如果是偶數(shù)個，則無法通過這一位決出勝負(fù) { continue; } else // 如果是奇數(shù)個，分類討論 { if (v[i] == 1) // 由于Alice先拿，此時必贏 { cout << 1 << endl; } // 如果數(shù)列大小n是偶數(shù)，那么由于該bit位1是奇數(shù)個，故0也是奇數(shù)個 else if (n % 2 == 0) { /* * 若Alice先拿1，那么Bob必然拿0，而Alice也因此只能拿0 * 最終Bob拿最后1個0, 此時由于1有偶數(shù)個，Alice只能用1給Bob異或，此時Bob該位是1 * Bob再給A異或使其為0，A再給自己異或使其為1，最終，Bob拿最后一個1給Alice異或使其為0 * * 若Alice先拿0，那么Bob也拿0，最后1個0由Alice拿，此時Bob拿第一個1給自己異或 * 然后Alice也拿1給自己異或，然后Bob拿1給Alice異或，Alice拿1給自己異或... * 最終，Bob拿最后一個1給Alice異或，此時Alice為0，Bob為1 * * 因此這種情況，Bob必贏 */ cout << -1 << endl; } // 如果數(shù)列大小n是奇數(shù)，那么由于該bit位1是奇數(shù)，故0是偶數(shù) else { /* * 偶數(shù)個0不會對結(jié)果造成影響 * 因此Alice先拿1給自己，Bob也拿1給自己，Alice再拿1給Bob，Bob拿1給自己... * 最終，Alice把最后一個1給Bob使其為0，而自己依然是1 * 因此，這種情況Alice必贏 */ cout << 1 << endl; } break; } } } } } return 0; } 8.雙向排序 原題是得用線段樹寫的，不會，整個騙分的，能過60%也可以了 #include using namespace std; #include bool up(int a, int b) { return a < b; } bool down(int a, int b) { return a > b; } int main() { int n, m; cin >> n >> m; int a[100000]; for (int i = 0; i < n; i++) { a[i] = i + 1; } for (int i = 0; i < m; i++) { int p, q; cin >> p >> q; if (p) sort(a + q-1, a + n, up); //sort自定義排序順序時以這種方式 else sort(a, a + q, down); } for (int i = 0; i < n; i++) { cout << a[i]<<" "; } return 0; } 十四 1.工作時長 excel直接做 參考博客：藍(lán)橋杯2023年第十四屆省賽真題-工作時長-CSDN博客 注意設(shè)置單元格格式，排序，第二行減第一行。。。然后求和就完事了。 2.與或異或 暴力法： #include using namespace std; #include //暴力法 int main() { int a[5][5]; a[0][0] = a[0][2] = a[0][4] = 1; a[0][1] = a[0][3] = 0; //輸入初始條件 int max = (int)pow(3, 10); //定義循環(huán)次數(shù) 3的10次方次 int t = 0,op=0,ans=0; for (int k = 0; k < max; k++) { t = k; for (int i = 1; i < 5; i++) { for (int j = 0; j < 5 - i; j++) { //循環(huán)到每一個數(shù) op = t % 3; //確定該哪一個操作了 t /= 3; //每一個操作完 除3 到下一對數(shù)字 switch (op) { case 0:a[i][j] = a[i-1][j] & a[i-1][j + 1]; break; case 1:a[i][j] = a[i-1][j] | a[i-1][j + 1]; break; case 2:a[i][j] = a[i-1][j] ^ a[i-1][j + 1]; } } } if (a[4][0] == 1) ans++; } cout << ans; return 0; } 3.翻轉(zhuǎn) #include #include using namespace std; string S,T; int n; //組數(shù) int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> T; cin >> S; int count=0; //記錄變更數(shù)據(jù) int l = S.size(); for (int j = 0; j < l; j++) { if (S[j] == T[j]) continue; else { if (S[0] != T[0]) { //第一個不對直接不行 count = -1; break; } if (S[j] != S[j - 1] && S[j] != S[j + 1]) { //變更 S[j] = S[j - 1]; count++; //計數(shù) } else { //兩個數(shù)不對又不能改變肯定不行 count = -1; break; } } } cout << count << endl; } return 0; } 4.階乘的和 嘗試使用暴力法，但是一個也通不過 看了題解，發(fā)現(xiàn)對于階乘的特性 因數(shù)其實就是最小的階乘，畢竟每一個小的階乘都是大的階乘的因數(shù)（一堆階乘的和也還是最小階乘的倍數(shù)嘛），所以其實就是求最小階乘的問題。但是有一種情況就是可以階乘合并，比如3個2！就是3！ 這個直接轉(zhuǎn)化就行? num的個數(shù)cnt滿足? ?cnt%（num+1)==0的話? cnt*num！=cnt/（num+1） *（num+1）*num！=cnt/（num+1）*(num+1)!? ?這樣操作之后，輸出最小階乘就行了。 這里寫代碼用了map，可以自動的排序保存一下，調(diào)用遍歷的時候用迭代器就行。 #include using namespace std; #include typedef long long ll; map int main() { int n; cin >> n; int num; for (int i = 0; i < n; i++) { cin >> num; mp[num]++; //統(tǒng)計各個數(shù)出現(xiàn)幾次 } map for (it = mp.begin(); it != mp.end(); it++) { //遍歷 mp會自己排序 int num = it->first; int cnt = it->second; if (cnt % (num + 1) == 0) //如果滿足cnt整除num+1的話 cnt*num!=cnt/(num+1)*(num+1)! mp[num + 1] += cnt / (num + 1); else { //不能升階的話直接就是最小的了，升不動也就不行了 cout << num << endl; break; } } return 0; } 5.公因數(shù)匹配 暴力法：44.4% #include using namespace std; const int MAX = 1e5; int GCD(int a, int b) { //輾轉(zhuǎn)相除法 if (a % b == 0) return b; else return GCD(b, a % b); } int main() { int n; cin >> n; long long A[MAX]; for (int i = 0; i < n; i++) { cin >> A[i]; } bool found = false; for (int i = 0; i < n && !found; i++) { //找到后把標(biāo)志設(shè)置為找到了，可以直接退出兩層循環(huán) for (int j = i + 1; j < n; j++) { if (GCD(A[i], A[j]) > 1) { cout << i+1 << " " << j+1 << endl; //要輸出的是第幾個數(shù)，下標(biāo)從0開始，所以要加1 found = true; break; } } } return 0; } 分解質(zhì)因數(shù)存儲的辦法：參考藍(lán)橋杯真題講解：公因數(shù)匹配（數(shù)論：分解質(zhì)因數(shù)）-CSDN博客 存儲和分解參考，后面遍歷的時候自己弄 #include using namespace std; #include #include map void prim(int x, int pos) { //將所有的質(zhì)數(shù)對應(yīng)的數(shù)組坐標(biāo)歸到map里 就是一個質(zhì)數(shù)對應(yīng)一個數(shù)組，數(shù)組中存放的是數(shù)的下標(biāo) for (int i = 2; i*i <= x; i++) { if (x % i == 0){ mp[i].push_back(pos); while (x % i == 0) { //一步一步把所有的2.3..除掉 x /= i; } } } if (x > 1) //將除剩下的也加入 mp[x].push_back(pos); } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { int x; cin >> x; prim(x, i + 1); } int x=0x3f3f3f3f, y=0x3f3f3f3f; int m = size(mp); for (int i = 2;i<1e6; i++) { //循環(huán)所有的質(zhì)數(shù)，找質(zhì)數(shù)對應(yīng)map存儲的數(shù)組中的數(shù) if (size(mp[i]) >= 2) { if (mp[i][0] < x|| (mp[i][0] == x && mp[i][1] < y)) { x = mp[i][0]; //存的時候從小到大存的，數(shù)組第一個和第二個就是需要的 y = mp[i][1]; } } } cout << x << " " << y << endl; return 0; } 6.子樹的大小 都在注釋里面了，注意把數(shù)據(jù)類型都設(shè)置為long long #include using namespace std; #include //主要思路是不斷計算k節(jié)點在每一層的左節(jié)點和右節(jié)點 //左節(jié)點的左節(jié)點是最左節(jié)點，右節(jié)點的右節(jié)點是最右節(jié)點，右節(jié)點減左節(jié)點再加和 //左節(jié)點公式： 第k個節(jié)點 前面有(k-1)個節(jié)點 則 左節(jié)點前有(k-1)*m+2個節(jié)點 2是根節(jié)點和第k個節(jié)點 //右節(jié)點公式： k*m+1 1是根節(jié)點 long long n, m, k; long long solve() { long long l = k, r = k; long long sum = 1; //計算結(jié)點數(shù)，初始值為1是算上k節(jié)點 bool pos=true; while (pos) { l = (l - 1) * m + 2; r = r * m + 1; if (r >= n) { //處理最后一個節(jié)點，最后一個節(jié)點在左右子節(jié)點中間 結(jié)束條件 r = n; pos = false; } if (l<=n) { //如果l>n 則表明節(jié)點已經(jīng)在這個子樹之前結(jié)束，不進(jìn)行求和 sum += r - l + 1; //r-n的話多減了一個同一級的節(jié)點 } } return sum; } int main() { int T; cin >> T; for (int i = 0; i < T; i++) { cin >> n >> m >> k; cout << solve() << endl; } return 0; } 7.反異或01串 使用馬拉車算法：Manacher (馬拉車算法)-CSDN博客 思路都在注釋里面。 #include using namespace std; #include #include typedef long long ll; //進(jìn)行反異或操作后得到的一定是一個 回文串 //進(jìn)行一次反異或操作最多可以節(jié)省 l/2 個1。 //思路：找到給定T的含1最多的回文串，使得這一部分是由反異或操作得到的， 剩下的1是一次一次添加得到的 //查找含一最多的回文串 由manacher算法查找 ll manacher(string s) { string temp = "#"; ll l = s.size(); for (ll i = 0; i < l; i++) { //改造字符串； (temp += s[i]) += '#'; } ll newL = temp.size(); //新字符串長度 vector vector //int r[MAX] = {0}; //存儲半徑長度 ll c = 0; //存儲要進(jìn)行馬拉車字符串的 中心位置 //int pre[MAX] = { 0 }; //存儲1的前綴和 ll ans=0; //存儲1的數(shù)量 for (ll i = 1; i < newL; i++) { //第一個和最后一個字符都是#，直接從1開始 pre[i] = pre[i - 1]; if (temp[i] == '1') //記錄1的數(shù)量 // pre[i]++; } for (ll i = 1; i < newL; i++) { //第一個和最后一個字符都是#，直接從1開始 if (c + r[c] > i) //i小于回文字符串的范圍 可以對稱 r[i] = min(r[2 * c - i], c + r[c] - i); //2*c-i是直接對稱 //c+r[c]-i是 如果對稱點的回文串太長,不超過大的回文串范圍 while (i - r[i] >= 0 && i + r[i] < newL && temp[i - r[i]] == temp[i + r[i]]) r[i]++; //暴力求 --r[i]; //相當(dāng)于減掉自身，因為循環(huán)必然會最開始的時候進(jìn)入一次，比如 i=0，r[i]=0,r會加一次 if (i + r[i] > c + r[c]) //更新c的位置 c = i; ans = max(ans, pre[i + r[i]]- pre[i - r[i]-1]); } return pre[newL-1]-ans/2; } int main() { string T; cin >> T; cout< return 0; } 柚子快報邀請碼778899分享：十二屆/十四屆藍(lán)橋杯學(xué)習(xí)筆記 參考文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Megaknihy書海閣
