成績與復(fù)盤

估分：0 + 0 + 10 + 10 + 2 + 15 + 10 + 8 + 10 + 0 = 65
成績：全國二等獎中上

筆者估自己的分一直很準(zhǔn)，至于這次比賽：

1. 估分不會偏高，因為編程題基本上經(jīng)過賽場上的對拍
2. 估分不會偏低，不會裝弱

經(jīng)歷與經(jīng)驗

筆者是一名退役的ACM同學(xué)，總共參加了三場藍橋杯國賽，成績依次是十一屆CB國二、十二屆CA國三、十三屆CA國二。由于欠缺一點實力和運氣，在ACM賽事上沒取得什么成績，但是自認為有些比賽經(jīng)歷和經(jīng)驗。藍橋杯有很多地方確實做的不好，該罵還得罵，然后不可否認的是，它給很多比上不足（ACM區(qū)域賽）、或者壓根沒有參加算法競賽（ACM省賽）的同學(xué)提供了一個更大眾、更適合的比賽平臺。對于藍橋杯，要想取得滿意的成績，我認為最重要的是細心。雖然這個詞看似是一個在哪都通吃的話術(shù)，但是對于藍橋杯尤為重要：

• 認真對待。這是筆者吃過很多虧才明白的道理，當(dāng)你想做好一件事的時候，或者說，當(dāng)這件事做不好你會留有遺憾的時候，那就應(yīng)該用謙卑的態(tài)度去做好這件事。比如藍橋杯，我記得C/C++組必須要return 0，這在參賽手冊上寫得很清楚，但仍然每年都有很多同學(xué)犯這種低級錯誤。還有今年是在新的平臺比賽，編程題提交框中，Ctrl+A不是快捷鍵，有不少同學(xué)修改代碼沒有覆蓋之前提交的代碼（這更多是平臺的問題），這種問題其實也可以通過花一兩分鐘簡單地檢查一遍避免。

• 相比于其他比賽，細心在藍橋杯上也體現(xiàn)得更為重要。比如ACM比賽、力扣周賽，錯誤提交會有罰時，在參加ACM比賽的時候，筆者和隊友也都保持謹慎的態(tài)度，有時候?qū)懲炅舜a必須反復(fù)測試才敢提交，生怕返回錯誤。但是ACM比賽錯誤了還能繼續(xù)提交，只是花費時間更多而已（當(dāng)然，并不是說時間不重要，很多時候解題數(shù)一樣，需要依靠花費時間更少來獲獎），而藍橋杯，一旦犯了低級錯誤（筆者在這次省賽中，青蛙那題因為寫錯一句代碼，導(dǎo)致整題都掛了），導(dǎo)致的結(jié)果很可能是整道題差不多直接掛了。一種推薦的解決辦法：程序?qū)ε?#xff0c;不了解對拍的同學(xué)可以參考以上文章或者自行上網(wǎng)搜索，不再贅述。也正是省賽的低級錯誤，讓我堅定了國賽寫對拍的決心，因此國賽雖然寫出來的題目也不多，但是基本上都能保證正確。

• 比賽策略。一、題目難度不保證梯度上升。也就是說后面的題可能比前面的簡單，那遇到卡題的情況，果斷地選擇跳過，換其他題目可能是制勝的關(guān)鍵。二、有部分得分。比如這次國賽的H題替換字符，暴力解法就有8分，這不比前面的RMQ、最短路什么的簡單多了？一道題的數(shù)據(jù)范圍直接決定了解題方法和題目難度。所以在最后一小時，一定要保證把所有題的小數(shù)據(jù)分拿到，它們真的很簡單。

真誠地希望能夠幫助到后來人

——2022.07.08

---

試題 A: 小藍與鑰匙

C(28,14)*錯排

錯排可以容斥或者遞推

1286583532342313400

代碼如下：

#include <bits/stdc++.h>
using namespace std;const int N = 16;
long long dp[N];
int main() {long long ans = 1;int ct = 2;for (int i = 15; i <= 28; i++) {ans = ans * i;while (ans % ct == 0 && ct <= 14)ans /= ct, ct++;}dp[2] = 1, dp[3] = 2;for (int i = 3; i <= 14; i++)dp[i] = 1ll * (i - 1) * (dp[i - 1] + dp[i - 2]);cout << ans * dp[14] << endl;return 0;
}

試題 B: 排列距離

康托展開，注意是循環(huán)排列。

試題 C: 內(nèi)存空間

預(yù)計得分：100%

模擬即可

代碼如下：

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 5;
const long long mod = 1e9 + 7;
string str;void solve()
{int n;scanf("%d", &n);getchar();long long ans = 0;for (int i = 1; i <= n; i++){getline(cin, str);string TP = "";int m = str.size();bool f = 0;for (int i = 0; i < m; i++){if (!f){TP += str[i];if (TP == "int" || TP == "long" || TP == "String")f = 1;continue;}if (TP == "String"){bool flag = 0;for (int j = i; j < m; j++){if (!flag){if (str[j] == '\"')flag = 1;continue;}if (str[j] == '\"'){flag = 0;continue;}ans++;}break;}if (str[i] == '['){bool flag = 0;long long res;for (int j = i + 2; j < m; j++){if (!flag){if (str[j] == '[')flag = 1, res = 0;continue;}if (str[j] == ']'){flag = 0;ans += res * (TP == "int" ? 4 : 8);continue;}res = res * 10 + str[j] - '0';}break;}for (int j = i; j < m; j++){if (str[j] == ',' || str[j] == ';')ans += (TP == "int" ? 4 : 8);}break;}}long long B = ans % 1024;long long KB = ans / 1024 % 1024;long long MB = ans / 1024 / 1024 % 1024;long long GB = ans / 1024 / 1024 / 1024 % 1024;if (GB)printf("%lldGB", GB);if (MB)printf("%lldMB", MB);if (KB)printf("%lldKB", KB);if (B)printf("%lldB\n", B);
}
int main()
{solve();return 0;
}
/*
1
long[] nums=new long[131072];4
int a=0,b=0;
long x=0,y=0;
String s1=?? hello??,s2=??world??;
long[] arr1=new long[100000],arr2=new long[100000];
*/

試題 D: 最大公約數(shù)

預(yù)計得分：100%

如果數(shù)組中已經(jīng)有$1$，那么直接用$1$平鋪即可。

否則找出最小區(qū)間滿足區(qū)間$GCD=1$，用這個$1$進行平鋪。

尋找方法可以使用二分+RMQ。

代碼如下：

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 5;
const long long mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f;
int a[N];struct node
{int l, r, g;
} tr[N << 2];void pushup(int k)
{tr[k].g = __gcd(tr[k * 2].g, tr[k * 2 + 1].g);
}void build(int k, int l, int r)
{tr[k].l = l, tr[k].r = r;if (l == r){tr[k].g = a[l];return;}int mid = l + r >> 1;build(k * 2, l, mid);build(k * 2 + 1, mid + 1, r);pushup(k);
}int query(int k, int L, int R)
{if (tr[k].l == L && tr[k].r == R){return tr[k].g;}int mid = (tr[k].l + tr[k].r) >> 1;if (R <= mid)return query(k * 2, L, R);else if (L > mid)return query(k * 2 + 1, L, R);elsereturn __gcd(query(k * 2, L, mid), query(k * 2 + 1, mid + 1, R));
}void solve()
{int n;scanf("%d", &n);int ct = 0;for (int i = 1; i <= n; i++){scanf("%d", &a[i]);ct += a[i] == 1;}if (ct) //有1直接平鋪{printf("%d\n", n - ct);return;}build(1, 1, n);if (query(1, 1, n) != 1) //肯定不行{puts("-1");return;}int min_step = INF;for (int i = 1; i <= n; i++){int l = i + 1, r = n, res = INF;while (l <= r){int mid = l + r >> 1;if (query(1, i, mid) == 1){res = mid - i;r = mid - 1;}elsel = mid + 1;}min_step = min(min_step, res);}printf("%d\n", min_step + n - 1);
}
int main()
{solve();return 0;
}
/*
3
4 6 95
6 4 6 10 5
*/

試題 E: owo

預(yù)計得分：10%

應(yīng)該是個DP，剛開始沒什么思路，后面也沒時間想了，交了暴力。

代碼如下：

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 5;int ans = 0;
string s[N];int ct = 0;
int func()
{int r = 0;for (int i = 1; i <= 1e3; i++){random_shuffle(s + 1, s + 1 + ct);string tmp;for (int i = 1; i <= ct; i++)tmp += s[i];int n = tmp.size();int res = 0;for (int i = 2; i < n; i++)res += tmp[i - 2] == 'o' && tmp[i - 1] == 'w' && tmp[i] == 'o';r = max(r, res);}return r;
}
void solve()
{srand(time(NULL));int n;cin >> n;for (int i = 1; i <= n; i++){string str;cin >> str;if (str[0] != 'o' && str[0] != 'w' && str[(int)str.size() - 1] != 'o' && str[(int)str.size() - 1] != 'w') //剪枝{printf("%d\n", ans);continue;}else{s[++ct] = str;ans = func();printf("%d\n", ans);}}
}
int main()
{solve();return 0;
}

試題 F: 環(huán)境治理

預(yù)計得分：100%

比較簡單的一個題，二分+FLOYD求最短路。時間復(fù)雜度$n^{3}logm$，其中m為把所有路徑清理到下限的所需天數(shù)（開個都行）。

代碼如下：

#include<bits/stdc++.h>
using namespace std;const int N = 105;
const long long mod = 1e9+7;
const int INF= 0x3f3f3f3f;int w[N][N];
int ww[N][N];
int minn[N][N];
int n , q;
int check(int day)
{int ans =0 ;for(int i =0; i<n; i++)for(int j =0; j<n; j++)ww[i][j]=w[i][j];for(int i =0; i<n; i++){int val = day/n+(day%n>=i+1?1:0);for(int j =0 ; j<n; j++)ww[i][j]-=val,ww[j][i]-=val;}for(int i =0; i<n; i++)for(int j =0 ; j<n; j++)ww[i][j]=max(minn[i][j],ww[i][j]);for(int k =0 ; k<n; k++)for(int i =0 ; i<n; i++)for(int j =0 ; j<n; j++)ww[i][j]=min(ww[i][j],ww[i][k]+ww[k][j]);for(int i =0; i<n; i++)for(int j =0; j<n; j++)ans+=ww[i][j];return ans ;
}void solve()
{scanf("%d %d",&n,&q);for(int i =0; i<n; i++)for(int j =0 ; j<n; j++)scanf("%d",&w[i][j]);for(int i =0; i<n; i++)for(int j =0 ; j<n; j++)scanf("%d",&minn[i][j]);int  l =0,r= 100000*n,ans =-1;while(l<=r){int mid = l+r>>1;if(check(mid)<=q){r= mid -1;ans = mid;}elsel=mid+1;}cout<<ans<<endl;
}
int main()
{solve();return 0;
}

試題 G: 選素數(shù)

預(yù)計得分：30%

數(shù)學(xué)廢物，沒思路，交了暴力。

代碼如下：

#include <bits/stdc++.h>
using namespace std;const int N = 5005;
const long long mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;bool f[N];
int prime[N];
int ct;void init()
{f[0] = f[1] = 1;for (int i = 2; i < N; i++)if (!f[i]){prime[++ct] = i;for (int j = i + i; j < N; j += i)f[j] = 1;}
}
void solve()
{init();int n;cin >> n;for (int x = 2; x <= n; x++){for (int p1 = 1; p1 <= ct && prime[p1] < x; p1++){int xx = x;int a = prime[p1];if (x % a)xx = (xx / a + 1) * a;if (xx > n) //剪枝continue;for (int p2 = 1; p2 <= ct && prime[p2] < xx; p2++){a = prime[p2];int xxx = xx;if (xx % a)xxx = (xx / a + 1) * a;if (xxx == n){cout << x << endl;return;}}}}puts("-1");
}
int main()
{solve();return 0;
}

試題 H: 替換字符

預(yù)計得分：40%

感覺需要神奇的數(shù)據(jù)結(jié)構(gòu)來維護，并不會，交了暴力。

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 5;
const long long mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f;
char s[N];
int l, r;
char a[3], b[3];void solve()
{scanf("%s", s + 1);int n = strlen(s + 1);int m;scanf("%d", &m);while (m--){scanf("%d %d %s %s", &l, &r, a, b);for (int i = l; i <= r; i++)if (s[i] == a[0])s[i] = b[0];}printf("%s", s + 1);
}
int main()
{solve();return 0;
}

試題 I: 三角序列

預(yù)計得分：40%

單獨維護每個三角形， 類似于分塊的思想，邊界單獨維護一下。

時間復(fù)雜度：$nmlognlogn$

代碼如下：

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 5;
const long long mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f;struct tri
{int typ, len, l, r;
} a[N];
long long pre[N]; //前綴列數(shù)量之和
int n, m;
long long cal2(int len, int h) //計算邊長為len的三角形 高度<=h的貢獻
{long long sum = 1ll * len * (len + 1) / 2;long long len2 = max(0, len - h);long long res = 1ll * len2 * (len2 + 1) / 2;return sum - res;
}
long long cal(int col, int idx, int h) //計算 第idx個三角形，從第col列開始， 高度<=h的貢獻
{if (col > a[idx].r)return 0;if (a[idx].typ == 0){long long s1 = cal2(a[idx].len, h);long long len2 = col - a[idx].l;long long s2 = cal2(len2, h);return s1 - s2;}else{long long len2 = a[idx].r - col + 1;return cal2(len2, h);}
}
int check(int l, int r, int h)
{int left_idx = lower_bound(pre + 1, pre + 1 + n, l) - pre;int right_idx = lower_bound(pre + 1, pre + 1 + n, r) - pre;if (left_idx == right_idx) //只有一個三角形return cal(l, left_idx, h) - cal(r + 1, left_idx, h);else{long long ans = 0;ans += cal(l, left_idx, h);ans += cal(a[right_idx].l, right_idx, h) - cal(r + 1, right_idx, h);for (int i = left_idx + 1; i < right_idx; i++) //計算中間的三角形貢獻ans += cal(a[i].l, i, h);return ans;}
}void solve()
{scanf("%d %d", &n, &m);int max_h = 0;for (int i = 1; i <= n; i++){scanf("%d %d", &a[i].len, &a[i].typ);pre[i] = pre[i - 1] + a[i].len;a[i].l = pre[i - 1] + 1;a[i].r = pre[i];max_h = max(max_h, a[i].len);}for (int i = 1; i <= m; i++){int L, R, v;scanf("%d %d %d", &L, &R, &v);int l = 1, r = max_h, h = -1;while (l <= r){int mid = l + r >> 1;if (check(L, R, mid) >= v){h = mid;r = mid - 1;}elsel = mid + 1;}printf("%d\n", h);}
}
int main()
{solve();return 0;
}

試題 J: 括號序列樹

樹的最大匹配的定義？