中秋節(jié)快樂！

A. Regular Bracket Sequences

題意

輸出$n$個不同的長度為$2n$的合法括號序列.

分析

先輸出一個"()()()…"序列.

然后依次輸出"(())()", “()(())”,…，也就是每次把第$i$個和第$i+1$個交換，其中$i$從下標2到n-2，這樣恰好$n?1$個，加上最開始的共$n$個。

代碼

#include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll; //const ll linf = 9223372036854775807LL; // const ll linf = 1e18; using namespace std;signed main() {DDLC_ESCAPE_PLAN_FAILED;int t;cin >> t;while(t--){int n;cin >> n;string s;for(int i = 0; i < n; ++i){s += '(';s += ')';}cout << s << endl;for(int i = 1; i + 1 < s.size(); i += 2){s[i] = '(';s[i + 1] = ')';cout << s << endl;s[i] = ')';s[i + 1] = '(';}}return 0; }

B. Combinatorics Homework

題意

你需要判斷是否存在一個字符串：

恰好a個’A’，b個’B’，c個‘C’

沒有其他字符

恰好m對相鄰且相同的字符對（如"AA"）

分析

目標是尋找可以滿足要求的$m$取值范圍。

將三種字符的數(shù)量排序，找到其個數(shù)最多的，假設(shè)為’A’，記’B’和’C’的數(shù)量和為$s$。

$m$最大取值顯然是$a+b+c?3$.

找$m$的最小值。把$s$個字符排開，其有$s+1$個位置可以插入’A’。若’A’的數(shù)量不超過$s+1$，那么肯定可以達到最小狀態(tài)，即不存在相鄰且相同的字符對。可能會想到’A’沒有填滿所有空缺時有可能’B’或者’C’會出現(xiàn)連續(xù)的情況，但其實這種情況發(fā)生的話’A’肯定就不是個數(shù)最多的了。反之，若’A’的數(shù)量超過了$s+1$，那么至少出現(xiàn)的相同字符對就是$s+1?a$對。

代碼

#include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll; //const ll linf = 9223372036854775807LL; // const ll linf = 1e18; using namespace std;signed main() {DDLC_ESCAPE_PLAN_FAILED;int t;cin >> t;while(t--){int a, b, c, m;cin >> a >> b >> c >> m;int mx = a + b + c - 3;int p[3] = {a, b, c};sort(p, p + 3);int r2 = p[0] + p[1] + 1, r1 = p[2];int mn = max(0LL, r1 - r2);if(mx >= m && mn <= m){cout << "YES" << endl;}else cout << "NO" << endl;}return 0;

C. Slay the Dragon

題意

有$m$條龍和$n$個勇士，每個勇士的力量是$a_i$，每個龍的防御力為$x_i$，攻擊力為$y_i$。對每條龍$i$，你需要派遣一個勇士，要求力量大于等于$x_i$，如果不足$x_i$，需要支付等量的金幣補足差值；同時要求剩余的勇士力量總和大于等于$y_i$，不足用金幣補足。問擊殺每條龍需要支付的金幣至少是多少（每條龍之間分別計算，相互獨立）

分析

貪心，對勇士力量升序排序。對每條龍，lower_bound(a+1,a+1+n, x[i])查找出一個勇士$s$，如果要派遣一個大于等于$x_i$的勇士去，那么必定是派$s$去。

但又有可能這個$s$超過$x_i$很多而其他的總和不足$y_i$，這個時候$s?1$也可能是答案。

所以答案要么是派$s$去，要么是派$s?1$去。

代碼

#include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll; //const ll linf = 9223372036854775807LL; // const ll linf = 1e18; using namespace std; const int maxn = 2e5 + 10; int a[maxn]; int x[maxn], y[maxn]; int pre[maxn]; signed main() {DDLC_ESCAPE_PLAN_FAILED;int t;t = 1;a[0] = 0;while(t--){int n;cin >> n;fors(i, 1, n) cin >> a[i];int m;cin >> m;fors(i, 1 , m) cin >> x[i] >> y[i];sort(a + 1, a + 1 + n);pre[0] = 0;fors(i, 1, n) pre[i] = pre[i - 1] + a[i];fors(i, 1, m){int now = lower_bound(a + 1, a + 1 + n, x[i]) - a;int ans = 0;if(now == n + 1){ans += x[i] - a[n];ans += (pre[n - 1] >= y[i] ? 0 : y[i] - pre[n - 1]);cout << ans << endl;}else{// 要么選now，要么選now-1.ans = (pre[n] - a[now] >= y[i] ? 0 : y[i] - (pre[n] - a[now]));if(now == 1){cout << ans << endl;continue;}int res = 0;now--;res += x[i] - a[now];res += (pre[n] - a[now] >= y[i] ? 0 : y[i] - (pre[n] - a[now]));ans = min(ans, res);cout << ans << endl;}}}return 0; }

D. The Strongest Build

題意

有$n(n\le 10)$個單調(diào)不下降數(shù)組，每個數(shù)組長$c_i$，第$i$個數(shù)組的第$j$個元素表示為$a_{ij}$，保證$\sum c_i\le 2?10^5$，你需要從每個數(shù)組中選一個元素，但約定有$m(m\le 10^5)$個選擇方案是不允許的。求一個方案使得所有選擇的元素和最大，輸出方案。

分析

暴力枚舉。首先考慮所有數(shù)組都選最后一個元素（最大的），如果這個方案不行，那就枚舉所有被禁止的方案。例如，假如某個方案{a,b,c}是禁止的，那么就看{a-1,b,c},{a,b-1,c},{a,b,c-1}有沒有禁止，沒有就更新答案，這樣枚舉出來的一定是最優(yōu)解。

貪心思路：

若$\{a_{c_1},a_{c_2},...\}$這個在沒有限制條件下的方案被限制了的話，可能的最優(yōu)解就從$\{a_{c_1?1},a_{c_2},...\},\{a_{c_1},a_{c_2?1},...\}$里面產(chǎn)生。如果這些方案中也有被限制的，那么就再從這些中枚舉每個位置分別將其減一再更新答案。這樣可以保證每次都是“退而求其次”，但一定是可選擇的里面最優(yōu)的。畢竟$m\le 10^5$，故最多需要枚舉$mn$次。加上二分查找，時間復雜度為$O(mn\log m)$

代碼

#include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll; //const ll linf = 9223372036854775807LL; // const ll linf = 1e18; using namespace std; const int maxn = 2e5 + 10; int a[12][maxn]; int n; set<vector<int> > v; signed main() {DDLC_ESCAPE_PLAN_FAILED;cin >> n;fors(i, 1, n){cin >> a[i][0];fors(j, 1, a[i][0]) cin >> a[i][j];}int m, p;cin >> m;vector<int> tmp;fors(I, 1, m){fors(j, 1, n){cin >> p;tmp.pb(p);}v.insert(tmp);tmp.clear();}vector<int> ideal; fors(i, 1, n) ideal.pb(a[i][0]);// bool flag = 0;if(v.find(ideal) == v.end()){for(auto x : ideal) cout << x << ' ';cout << endl; return 0;}else{int ans = 0;vector<int> f;for(auto x : v){tmp = x;int sum = 0;for(int i = 0; i < x.size(); ++i){sum += a[i + 1][x[i]];}for(int j = 0; j < x.size(); ++j){if(x[j] - 1 == 0) continue;sum -= a[j + 1][x[j]];sum += a[j + 1][x[j] - 1];x[j]--;if(v.find(x) == v.end() && sum > ans) ans = sum, f = x;x[j]++;sum += a[j + 1][x[j]];sum -= a[j + 1][x[j] - 1];}}for(auto x : f) cout << x << ' ';cout << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 114 (Rated for Div. 2) 个人题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。