2021牛客寒假算法基礎集訓營1

• A. 串（線性DP）
• B. 括號（構造）
• E.三棱錐之刻（幾何）
• F. 對答案一時爽（簽到）
• I. 限制不互素對的排列（構造）
• J. 一群小青蛙呱蹦呱蹦呱

A. 串（線性DP）

$f[i][0]$ ：表示字符串前i個字符中既沒有’u’也沒有’s’；
$f[i][1]$ ：表示字符串前i個字符中有’u’沒有’s’；
$f[i][2]$ ：表示字符串前i個字符中含有’u’也有’s’；

初始化：
$f[1][0]$ = 25; // 第1項不是’u’，那么就有25種選擇
$f[1][1]$ = 1; // 第1項是’u’，那么就只能是1種選擇，就是’u’
$f[1][2]$ = 0; // 第1項是不可能同時存在u和s，所以 $f[1][2]=0$

狀態轉移方程：
如果前i項既不含’u’也不含’s’，那么前i-1項也不會含’u’和’s’；
$f[i][0]=（25\times f[i?1][0]）\%MOD$

如果前i項含有’u’不含’s’，那么有兩種情況
① 第i項是’u’，那么：$f[i?1][0]$
② 第i項不是’u’，且要保證第i項不是’s’，那么就有25個選擇：$25\times f[i?1][1]$
把這兩種情況加起來結果

如果前i項含有’u’也含有’s’，那么也有兩種情況
① 第i項是’s’，那么之前有’u’，轉移方程就是：$f[i?1][1]$
② 第i項不是’s’，第i項有26種選擇，$f[i?1][2]\times 26$

綜上：

f[i][0] = (25 * f[i - 1][0]) % MOD; f[i][1] = (25 * f[i - 1][1] + f[i - 1][0]) % MOD; f[i][2] = (f[i - 1][1] + f[i - 1][2] * 26) % MOD; #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1000010; const int MOD = 1e9 + 7; int n, ans; int f[N][4]; signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;f[1][0] = 25;f[1][1] = 1;f[1][2] = 0;for (int i = 2; i <= n; i++) {f[i][0] = (25 * f[i - 1][0]) % MOD;f[i][1] = (25 * f[i - 1][1] + f[i - 1][0]) % MOD;f[i][2] = (f[i - 1][1] + f[i - 1][2] * 26) % MOD;ans = (ans + f[i][2]) % MOD;}cout << ans << endl;return 0; }

B. 括號（構造）

題意：
本題是一個構造題，需要構造一個形如：
a × b + c的形式
如11
11 = 3 × 3 + 2
因為右邊要形成一個2，所以將 $a\times b+c$ 變換形式：變成 $a\times (b?1)+c+b$
這樣子就能滿足題意了：
舉幾個例子：
如果是 11 的時候： 3 × 3 + 2；
如果是 101 的時候：10 × 10 + 1；

① 求出一個 $a$，使得 $a^2$ 是盡可能接近 $k$ 的，$a$ = $\sqrt{k}$

② 此時的 $a^2$ == $k$ 不一定成立，而且如果將后面全部劃分給c的話，如果k == 1e9的話，會爆長度1e5

③ res：表示除去 $a^2$ 之后還有多少，$res=k?a^2$;

④ 從剩下的中再維護出一個 $?\frac{res}{a}?$，防止爆長度。
即：b = $?\frac{res}{a}?+a$

⑤ 此時還剩下 $res$ % $a$ 的即， $c$ = $res$ % $a$

綜上所述：
$a=\sqrt{k},res=k?a?a,b=?\frac{res}{a}?+a,c=res\%a$

#include<bits/stdc++.h> #define int long long using namespace std; signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int k;cin >> k;if (k == 0) {cout << ")(" << endl;return 0;} int a = sqrt(k), res = ceil(k - (a * a)), b = res / a + a, c = res % a; // cout << a << ' ' << res << ' ' << b << ' ' << c << endl;for (int i = 1; i <= a; i++) cout << '(';for (int i = 1; i <= b - 1; i++) cout << ')';for (int i = 1; i <= c; i++) cout << '(';cout << ')' << endl;return 0; }

E.三棱錐之刻（幾何）

P為正三棱錐內部的中心，PA，PD為正三棱錐外接球半徑，OP為正三棱錐內切球半徑

結論：已知正三棱錐的棱長為a，那么正三棱錐外接球半徑為：$\frac{\sqrt{6}}{4}a$ ，正三棱錐內切球半徑為：$\frac{\sqrt{6}}{12}a$

//minn為正三棱錐內切球半徑，maxx為正三棱錐外接球半徑 double minn = sqrt(6.0) * a / 12, maxx = sqrt(6.0) * a / 4; double area;

本題分三種情況：

當染色半徑 $r\le \frac{\sqrt{6}}{12}a$時， 即染色球還未觸及正三棱錐內壁，那么就無法染色

if (r <= minn) area = 0;//無法染色，染色面積自然為0

當染色半徑 $r\ge \frac{\sqrt{6}}{4}a$時， 即染色球已經包含整個正三棱錐，那么整個正三棱柱的內部都會染色

else if (r >= maxx) area = sqrt(3.0) / 4 * f(a);//正三棱錐一個側面三角形的面積

當染色半徑 $\frac{\sqrt{6}}{12}a\le r\le \frac{\sqrt{6}}{4}a$ 時，分為兩個小情況：
(1) 當橫截面積 ≤ 是三角形的內切圓 即 橫截圓的半徑 ≤ $\frac{\sqrt{3}}{6}a$

此時OG為底面三角形ABC的內切圓，OG為內切圓的半徑為：$d=\frac{\sqrt{3}}{6}a$ ，染色圓的半徑為：r

那么染色球與其中一個底面三角形ABC形成的橫截圓的半徑為：$r_1=\sqrt{(r?\frac{\sqrt{6}}{12}a{)}^2?d^2}$

所以：此時底面三角形ABC染色面積為：$\pi r_1^2$ ，有4個面就是 $4\pi r_1^2$

(2) 當 正三角形的內切圓 ＜ 橫截圓 ＜ 正三角形的外接圓 即 染色的面積如藍色陰影部分：

這個面積分為兩個部分：等腰三角形+扇形

此時的 $r_1,d,2d$ 如圖所示

3個等腰三角形面積 = $\sqrt{r_1^2?d^2}\times d\times 3$

扇形的弧度：$\alpha =(2\pi ?acos(\frac{d}{r_1})\times 2\times 3)÷3$

3個扇形面積 = $\frac{\alpha }{2\pi }\times \pi \times r_1^2\times 3$

else {if (r1 <= d) {area = PI * r1 * r1;} else {double area1 = sqrt(f(r1) - f(d)) * d * 3;//3個等腰三角形的面積//cos() 是已知一個角的弧度值 x，求該角的余弦值 y;而 acos() 是已知一個角的余弦值 y，求該角的弧度值 x。//扇形面積 = ((2 * PI - 三個等腰三角形的角度) * 3 / 3) / (PI * 2) * PI * f(r1);double area2 = ((((PI * 2) - (acos(d / r1) * 2) * 3) / 3) / (PI * 2)) * PI * f(r1);area = area1 + area2; }}

完整的AC代碼：

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #define ll long long #define int ll #define PI acos(-1) #define MOD 1000000007 using namespace std; int read() {int w = 1, s = 0;char ch = getchar();while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0';ch = getchar(); }return s * w; } //x的平方 double f(double x) {return x * x; } signed main() {double a;//題目給的正三棱錐的棱長double r;//題目給的染色的半徑scanf("%lf%lf", &a, &r);// sqrt(6) * a / 12;是正三棱柱內切球的半徑// sqrt(6) * a / 4; 是正三棱柱外接球的半徑double minn = sqrt(6.0) * a / 12, maxx = sqrt(6.0) * a / 4;/*本題分三種情況：Ⅰ. 當染色半徑 r <= sqrt(6) * a / 12; 那么就無法染色Ⅱ. 當染色半徑 r >= sqrt(6) * a / 4; 那么整個正三棱柱的內部都會染色Ⅲ. 當染色半徑 sqrt(6) * a / 12 < r < sqrt(6) * a / 4 時分為兩個小情況：(1) 當橫截面積 恰好是三角形的內切圓(2) 當橫截面積 大于正三角形的內切圓 小于正三角形的外接圓*/double r1 = sqrt(f(r) - f(sqrt(6.0) * a / 12));//在正三棱錐的一個側面被染色截面圓的半徑double d = sqrt(3.0) / 6 * a;//正三角形的內切圓的半徑double area;if (r <= minn) area = 0;else if (r >= maxx) area = sqrt(3.0) / 4 * f(a);//正三棱錐一個側面三角形的面積else {if (r1 <= d) {area = PI * r1 * r1;} else {double area1 = sqrt(f(r1) - f(d)) * d * 3;//3個等腰三角形的面積//cos() 是已知一個角的弧度值 x，求該角的余弦值 y;而 acos() 是已知一個角的余弦值 y，求該角的弧度值 x。double area2 = 3 * ((((PI * 2) - (acos(d / r1) * 2) * 3) / 3) / (PI * 2)) * PI * f(r1);//扇形面積 = ((2 * PI - 三個等腰三角形的角度) * 3 / 3) / PI * 2 * PI * f(r1);area = area1 + area2;}}printf("%.6lf\n", area * 4);return 0; }

F. 對答案一時爽（簽到）

#include<bits/stdc++.h> #define int long long using namespace std; const int N = 200010; char a[N], b[N]; signed main() {ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) cin >> b[i];int same = 0, usame = 0;for (int i = 1; i <= n; i++) {if(a[i] == b[i] && a[i] != ' ') same++;}printf("%lld 0\n", same + n);return 0; }

I. 限制不互素對的排列（構造）

題意：給定n，k，長度為n的序列，使得其中正好有 k 對相鄰的數gcd（最大公約數）大于 1

題解：
一般簡單的構造題，都會有一個萬能的解法，邊界需要特殊判斷。
這道題需要多次嘗試，得出結論
① 在n == 4 && k == 1時，輸出：1 4 2 3 或者 1 2 4 3
② 在n == 5 && k == 1時，輸出：1 4 2 3 5 或者 1 2 4 3 5
③ 在n >= 6時，就有一個萬能公式：
這個萬能公式，其實題目有提示：$0\le k\le \frac{n}{2}$
最多只有 $\frac{n}{2}$ 對 不互素對。

以 示例2 為例子：
那么3 6首先是一對，后面的話 6和2，2和4
所以，結果也可以是：3 6 2 4 1 5
那么觀察這個例子：
長度為6，我們先構造了一對 3 6 ，而后枚舉偶數即可，偶數與偶數之間一定存在一個公約數2，枚舉偶數只需要枚舉k-1個就行了，枚舉一個就用 st[ ] 數組標記一個，最后把剩下長度的順序輸出即可。
這里看個例子就懂了：

其余的情況就輸出 -1

#include<bits/stdc++.h> #define int long long using namespace std; const int N = 100010; bool st[N]; signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;if (k == 0) {for (int i = 1; i <= n; i++) cout << i << ' ';cout << endl;return 0;}if (n == 4 && k == 1) {cout << "1 4 2 3" << endl;} else if (n == 5 && k == 1) {cout << "1 4 2 3 5" << endl;} else if (n >= 6) {cout << "3 6 ";st[3] = st[6] = 1;for (int i = 1; i <= k - 1; i++) {if (i == 3) {k++;continue;}cout << 2 * i << ' ';st[2 * i] = 1;}for (int i = 1; i <= n; i++) {if (!st[i]) {cout << i << ' ';if (i == 2) {cout << 5 << ' ';st[i] = 5;}}}cout << endl;} else {cout << "-1" << endl;}return 0; }

J. 一群小青蛙呱蹦呱蹦呱

題意：要我們算出除了$(2^k)(3^k)\dots (4^k)$ 的所有數字的最小公倍數lcm。

總結

以上是生活随笔為你收集整理的2021牛客寒假算法基础集训营1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。