A. PizzaForces

題意

有三種披薩制作方案：15分鐘制作6片、20分鐘制作8片和25分鐘制作10片。

問制作出至少$n$片披薩要多少分鐘

分析

三種方案的效率都一樣，都是每分鐘制作0.4個披薩，也就是一片披薩要做2.5分鐘，所以讓溢出的時間盡可能少就可以了。

由于我們有$6,8,10$這三個數，我們可以通過不同的方案湊出$12,14,16,...$，所有大于等于6的偶數。

所以如果小于6，輸出15，否則如果是偶數就輸出$2.5n$，是奇數輸出$2.5(n+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;signed main() {// DDLC_ESCAPE_PLAN_FAILED;int t;cin >> t;while(t--){int n;scanf("%lld", &n);if(n <= 6) printf("15\n");else if(n & 1){printf("%lld\n", (int)((n + 1) * 2.5));}else printf("%lld\n",(int)( n * 2.5));}return 0; }

B. Two Tables

題意

一個大矩形區域內有一張桌子，你要平移這張桌子（任意方向），使得能放下另一個$w\times h$的桌子。求最小移動距離

分析

看這張桌子的正上方。正上方的區域，長度肯定是滿足，可以放下的。所以我們只需要將其垂直向下平移就可以得到一種方案。那么，對于其他3個方向也一樣。所以沿著坐標軸平移肯定優于斜著來，因為長和寬里面總是有一個是不需要額外移動來滿足的，而斜平移相對于垂直平移在另外一個方向上做了無用的移動。

代碼

#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 W, H;int x1, x2, y1, y2, w, h;cin >> W >> H;cin >> x1 >> y1 >> x2 >> y2;cin >> w >> h;int ans = inf;int r = abs(w - x1);if(x1 >= w) r = 0;if(x2 + r <= W) ans = min(ans, r);int l = abs(x2 - W + w);if(x2 <= W - w) l = 0;if(x1 - l >= 0) ans = min(ans, l);int u = abs(y2 - H + h);if(y2 <= H - h) u = 0;if(y1 - u >= 0) ans = min(ans, u);int d = abs(y1 - h);if(y1 >= h) d = 0;if(y2 + d <= H) ans = min(ans, d);cout << (ans == inf ? -1 : ans) << endl;}return 0; }

C. Coin Rows

題意

有一個兩行$m$列的矩陣，每個格子上有金幣。$Alice$和$Bob$可以在矩陣中向下或者向右移動，但不能向其他方向移動。

$Alice$從$(1,1)$出發，走到$(2,m)$，并取走所有停留過的格子里的金幣。

$Bob$同樣從$(1,1)$出發，走到$(2,m)$，并取走所有停留過的格子里的金幣（$Alice$已經取走的$Bob$取不到了）

$Alice$要讓$Bob$得到的金幣盡可能少，$Bob$會讓自己得的盡可能多。

問最終$Bob$會得到多少金幣？

分析

由于$Alice$要走到$(2,m)$，有且僅有一次向下移動。觀察$m$在$1e5$的規模，枚舉她向下移動發生的位置。然后，她拿走金幣后，留下的金幣只會分布在右上和左下兩個地方，且$Bob$只能選擇其中一個地方的金幣全部拿走，而不能同時拿2個地方的金幣。所以對2個地方剩余的金幣取$max$就是答案。剩余金幣的數量可以用前綴和處理。

時間復雜度$O(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 = 1e5 + 10; int a[3][maxn]; int pre[maxn], lst[maxn]; // 第一行從前往后的和，第二行從后往前的和 int sum1, sum2; signed main() {DDLC_ESCAPE_PLAN_FAILED;int t;cin >> t;while(t--){sum1 = sum2 = 0;int m;cin >> m;fors(i, 1, 2){fors(j, 1, m){cin >> a[i][j];if(i == 1) sum1 += a[i][j];else sum2 += a[i][j];}}pre[0] = lst[m + 1] = 0;fors(i, 1, m) pre[i] = pre[i - 1] + a[1][i];for(int i = m; i; --i) lst[i] = lst[i + 1] + a[2][i];int ans = inf;fors(i, 1, m){ans = min(ans, max(sum2 - lst[i], sum1 - pre[i]));}cout << ans << endl;}return 0; }

D. Say No to Palindromes

題意

定義一個字符串是$beautiful$的，當且僅當：任選一個長度大于1的子串，其不是回文串。

現在給出一個只含有字母a,b,c的字符串$s$，然后給出$m$個詢問，對每個詢問，你需要回答下標$l$到$r$的子串如果要稱為$beautiful$串，至少需要修改幾次（只能用a,b,c修改）。

分析

考慮下面的情況：
對字符串$baa$：

$b$替換$a$，$bba$,$bab$都含有回文子串，都不行

$c$替換$a$,$bac,bca$都符合要求.

其他情況很顯然不行

進一步總結規律，我們發現，一個字符串如果要變成非回文，其只能是形如$abcabcabcabc...$或者$bacbacbac...$，其他的情況都會發生兩個字符相鄰一樣，或者隔一個一樣，因此都是會導致回文子串產生的。

因此我們只需要看當前子串轉變為以上兩種串任意一種的子串就可以了，然后取$min$。

這樣暴力的復雜度就是$O(n^2)$了，但還不夠，需要繼續優化。

優化很簡單，任意區間修改成對應串的最小次數顯然可以用前綴和維護，復雜度降到$O(n+m)$.

當然你也可以用莫隊分塊$O(m\sqrt{n})$或者線段樹$O(mlogn)$，但顯然做復雜了（我屬于是最近學了莫隊就想用莫隊，就當是練習了，差點超時，被很多Hacker盯上了QAQ，幸好沒人叉掉）

代碼（莫隊）

#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) 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 + 5; string abc; string bca; string cab; string cba; string acb; string bac; struct query{int l, r;int ans, idx, blc; }q[maxn]; string s; bool cmp1(const query& x, const query& y){if(x.blc != y.blc) return x.blc < y.blc;return x.r < y.r; } bool rearr(const query& x, const query& y){return x.idx < y.idx; } signed main() {for(int i = 0; i < maxn; ++i){abc += i % 3 + 'a';bca += (i + 1) % 3 + 'a';cab += (i + 2) % 3 + 'a';if(i % 3 == 0){acb += 'a';cba += 'c';bac += 'b';}else if(i % 3 == 1){acb += 'c';cba += 'b';bac += 'a';}else {acb += 'b';cba += 'a';bac += 'c';}}DDLC_ESCAPE_PLAN_FAILED;int t;t = 1;while(t--){int n, m;cin >> n >> m;cin >> s;fors(i, 1, m){cin >> q[i].l >> q[i].r;q[i].l--, q[i].r--;q[i].idx = i;q[i].blc = (q[i].l - 1) / (int)sqrt(n) + 1;}sort(q + 1, q + 1 + m, cmp1);int l = 0, r = -1;int ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0, ans5 = 0, ans6 = 0;fors(i, 1, m){while(l > q[i].l){l--;if(s[l] != abc[l]) ans1++;if(s[l] != bca[l]) ans2++;if(s[l] != cab[l]) ans3++;if(s[l] != acb[l]) ans4++;if(s[l] != cba[l]) ans5++;if(s[l] != bac[l]) ans6++;}while(r < q[i].r){r++;if(s[r] != abc[r]) ans1++;if(s[r] != bca[r]) ans2++;if(s[r] != cab[r]) ans3++;if(s[r] != acb[r]) ans4++;if(s[r] != cba[r]) ans5++;if(s[r] != bac[r]) ans6++;}while(l < q[i].l){if(s[l] != abc[l]) ans1--;if(s[l] != bca[l]) ans2--;if(s[l] != cab[l]) ans3--;if(s[l] != acb[l]) ans4--;if(s[l] != cba[l]) ans5--;if(s[l] != bac[l]) ans6--;l++;}while(r > q[i].r){if(s[r] != abc[r]) ans1--;if(s[r] != bca[r]) ans2--;if(s[r] != cab[r]) ans3--;if(s[r] != acb[r]) ans4--;if(s[r] != cba[r]) ans5--;if(s[r] != bac[r]) ans6--;r--;}q[i].ans = min(min(ans1, min(ans2, ans3)), min(ans4, min(ans5, ans6)));}sort(q + 1, q + 1 + m, rearr);fors(i, 1, m) cout << q[i].ans << endl;}return 0; }

代碼（前綴和）

#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; const int inf = 1e9 + 7; int n, m; int pre[6][maxn] = {0}; string s; char check[6][4] = {"abc", "bca", "cab", "acb", "cba", "bac"}; int main() {ios::sync_with_stdio(false), cin.tie(0);cin >> n >> m;cin >> s;for(int i = 0; i < 6; ++i){if(s[0] != check[i][0]) pre[i][0] = 1;for(int j = 1; j < s.size(); ++j){if(s[j] != check[i][j % 3]) pre[i][j] = pre[i][j - 1] + 1;else pre[i][j] = pre[i][j - 1];}}for(int i = 0; i < m; ++i){int l, r; cin >> l >> r;l--, r--;int ans = inf;for(int j = 0; j < 6; ++j){if(l != 0) ans = min(ans, pre[j][r] - pre[j][l - 1]);else ans = min(ans, pre[j][r]);}cout << ans << endl;}return 0; }

顯然前綴和好寫多了，效率也快多了

總結

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

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