Codeforces Round #700 (Div. 2)A~D2解題報告

A Yet Another String Game

原題鏈接

http://codeforces.com/contest/1480/problem/A

解題思路

• Alice想讓更小，先手
• Bob想讓其更大，后手
• 解決方案當然是貪心，從第一個排到最后一個
• 如果不是選擇當前未更改的第一個，那么被別人修改，那么就會往反方向走了

AC代碼

#include <bits/stdc++.h> using namespace std;const int N = 110; char s[N];int main() {int t; cin >> t;while (t -- ){scanf("%s", s);for (int i = 0; s[i]; i ++ ){if (i & 1) // bigger{if (s[i] != 'z')putchar('z');elseputchar('y');}else // smaller{if (s[i] != 'a')putchar('a');elseputchar('b');}}puts("");}return 0; }

---

B The Great Hero

原題鏈接

http://codeforces.com/contest/1480/problem/B

解題思路

就是一個英雄和一群小怪獸打，機制和洛克王國一樣，問自己安排小怪獸出廠順序，是否可以打死所有小怪獸（包括同歸于盡）。
我們一直英雄的傷害為$A$,血量為$B$,$n$個小怪獸的傷害為$a_i$,血量為$b_i$,可以計算出他可以承受的傷害為$c_i=?b_i/A?$
英雄可以打過的充要條件是:
$A>c_1?a_1+...+c_i?a_i+...+((c_n?1)?a_n)$ 注意這里是大于，因為保證最后一下可以打出去就行
$?$
$A+a_n>c_1?a_1+...+c_i?a_i+...+(c_n?a_n)$
右邊是常數(shù)，左面越大越好，也就是攻擊力最大的放在最后即可
$O(N)$

AC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 100010; int n; LL A, B; class Node { public:int a, b; }q[N];int main() {int t; cin >> t;while (t -- ){scanf("%lld%lld", &A, &B);scanf("%d", &n);int tmp;int max_a = 0;for (int i = 1; i <= n; i ++ ){scanf("%d", &q[i].a);max_a = max(max_a, q[i].a);}LL sum = 0;for (int i = 1; i <= n; i ++ ){scanf("%d", &tmp);q[i].b = tmp / A + (tmp % A != 0); // 可以幾回合sum = sum + LL(q[i].a) * q[i].b;}if (B + max_a > sum)puts("YES");elseputs("NO");}return 0; }

---

C Searching Local Minimum

原題鏈接

http://codeforces.com/contest/1480/problem/C

解題思路

二分題目
這個題目二分特性很難一眼看出，平時的二分基本是左側為滿足（不滿足），右側是不滿足（滿足），然后進行二分，有意思的地方就是在于滿足的是什么特性!!
本題這個特性和平時遇到的特性不同， 特性是：區(qū)間[l,r]中至少含有一個local_min，至少含有一個是精髓！ 因為對于本體而言局部最小值可能有很多，而且還很分散，我們需要找任意一個局部最小值，直接按照這個性質(zhì)來找就可以二分。
需要注意的一點是，被我們舍棄的另一部分不是說不含有l(wèi)ocal_min，而是在我們未詢問的前提下可能不含有l(wèi)ocal_min，而選中的那個區(qū)間一定含有。

AC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 100010, INF = 0x3f3f3f3f; int a[N];void query(int idx) {if (a[idx] != -1) // 之前已經(jīng)是有數(shù)字了return;printf("? %d\n", idx);cout.flush();scanf("%d", &a[idx]); } int n;int main() {cin >> n;memset(a, -1, sizeof a);a[0] = INF, a[n + 1] = INF;int l = 1, r = n, mid;while (l < r){mid = (l + r) / 2;query(mid);query(mid + 1);if (a[mid] < a[mid + 1]){r = mid;}else{l = mid + 1;}}printf("! %d\n", l);return 0; }

---

D1 Painting the Array I

原題鏈接

http://codeforces.com/contest/1480/problem/D1

解題思路

題目大概描述為，將原本的數(shù)組$a_1,a_2,...,a_n$通過染色分成兩個子數(shù)組$a_1^{(0)},a_2^{(0)},...,a_{n1}^{(0)}$和$a_1^{(1)},a_2^{(1)},...,a_{n1}^{(1)}$使得合并數(shù)組毗鄰相同的元素后，兩個數(shù)組的長度和盡可能的大。
下面我們對原數(shù)組變形，形成以下形式
$\underset{n_0}{a_0,???,a_0},\underset{n_1}{a_1,???,a_1},???\underset{n_i}{a_i,???,a_i},???,\underset{n_{ed}}{a_{ed},???,a_{ed}}$。\quad其中$?i,a_i=a_{i+1}$
假設我們當前正要處理$\underset{n_i}{a_i,???,a_i},$部分時，分配的兩個數(shù)組當前為$b_1,b_2,???,b_{cur1}$和$c_1,c_2,???,c_{cur2}$
下面我們對當前處理的情況進行討論，

• $n_i=1$
  $b_{cur1}和c_{cur2}至少存在一個不等于a_i$，那么直接放在不等于的后面，$res+=1$
• $n_i\ge 2$
  $b_{cur1}和c_{cur2}存在一個等于a_i，另一個不等于a_i$，那么直接放在不等于的后面(兩邊都放也行)，$res+=1$
  $b_{cur1}和c_{cur2}都不等于a_i$，那么兩邊都放至少一個，$res+=2$
  那么為什么這樣做是對的？

補證明:

AC代碼

#include <bits/stdc++.h> using namespace std;const int N = 100010; const int INF = 0x3f3f3f3f; int a[N]; int n; int main() {cin >> n;for (int i = 1; i <= n; i ++ )scanf("%d", &a[i]);int pre = 1, ed = 0, cnt;a[0] = a[n + 1] = a[n + 2] = a[n + 3] = INF;int res = 0;int surp1 = -INF, surp2 = -INF;int tmp1;for (int i = 1; i <= n + 1; i ++ ){if (a[i] == a[i - 1]){ed = i;}else{cnt = ed - pre + 1;if (cnt == 0){pre = ed = i;continue;}if (surp1 == a[i - 1] || surp2 == a[i - 1]){surp1 = surp2 = a[i - 1];res += 1;}else if (cnt >= 2){res += 2;surp1 = surp2 = a[i - 1];}else if (cnt == 1) // 幫忙遮掩{tmp1 = a[i];if (surp1 == a[i])surp1 = a[i - 1];else if (surp2 == a[i])surp2 = a[i - 1];elsesurp1 = a[i - 1];res += 1;}pre = ed = i;}}cout << res << endl;return 0;}

---

D2 Painting the Array II

原題鏈接 待補

http://codeforces.com/contest/1480/problem/D2

解題思路

該題目也是貪心，
首先，原數(shù)組$\underset{n_0}{a_0,???,a_0},\underset{n_1}{a_1,???,a_1},???\underset{n_i}{a_i,???,a_i},???,\underset{n_{ed}}{a_{ed},???,a_{ed}}$。\quad其中$?i,a_i=a_{i+1}$。因為是要求最小，我們將數(shù)組改造為$a_0,a_1,???,a_i,???,a_{ed}$
假設我們當前構造的兩行$line1,line2$是正確的，現(xiàn)在查看$a[i]$應該放在哪個隊列之后。

• $line1\_back()=line2\_back()$，那么我們將$a[i]$放在那里都是可以的。
• $line1\_back()=line2\_back()$時候，進行下列分析
  倘若$line1\_back()=a[i]$，那么直接放在$line1$即可，因為可以直接抵消掉
  同理，倘若$line2\_back()=a[i]$，那么直接放在$line2$即可。
  最后 一種情況，$line1\_back()=a[i]而且line2\_back()=a[i]$，那么我們考慮$line1$和$line2$的末尾誰可以最近的匹配，放入較遠的一方即可。（因為最近匹配優(yōu)先，不可被中斷）。

AC代碼

#include <bits/stdc++.h> using namespace std;const int N = 100010, INF = 0x3f3f3f3f; int a[N], b[N]; int n; vector<int> pos[N]; int cur[N];int nxt(int x) {if (x == INF || cur[x] == pos[x].size()) // 已經(jīng)到達了最后一個return INF;elsereturn pos[x][cur[x]]; }int main() {cin >> n;for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);int n2 = 1;b[1] = a[1];for (int i = 2; i <= n; i ++ )if (a[i] != a[i - 1])b[++ n2] = a[i];n = n2;memset(cur, 0, sizeof cur);for (int i = 1; i <= n; i ++ ){// printf("%d ", b[i]);pos[b[i]].push_back(i);}// puts("");int res = n;vector<int> v[2];int tar = INF, cur_tar, tar_line = 1;v[0].push_back(INF), v[1].push_back(INF);for (int i = 1; i <= n; i ++ ){cur[b[i]] ++;if (v[0].back() == v[1].back()) // 情況一，line1 == line2{if (v[0].back() == b[i])res --;v[0].push_back(b[i]);}else if (v[0].back() == b[i]){res --;v[0].push_back(b[i]);}else if (v[1].back() == b[i]){res --;v[1].push_back(b[i]);}else{static int nxt0, nxt1;nxt0 = nxt(v[0].back());nxt1 = nxt(v[1].back());if (nxt0 >= nxt1){v[0].push_back(b[i]);}else{v[1].push_back(b[i]);}}}cout << res << endl;return 0; } /* 15 1 1 1 2 2 1 3 2 1 1 1 2 3 3 1 */

---

總結

以上是生活随笔為你收集整理的Codeforces Round #700 (Div. 2)A~D2解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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