A. Inscribed Figures

分類討論打表即可。

PS：這道題翻譯有歧義。

這樣稍微翻轉一下，就可以是\(7\)個交點呀...（大概是我沒看英文題干導致的慘案）

#include <cstdio> #include <iostream> using namespace std; const int N = 110; int n, a[N], ans = 0; int d[3][3]{{-1, 3, 4},{3, -1, -1},{4, -1, -1} }; int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", a + i);for(int i = 2; i <= n; i++){int res = d[a[i - 1] - 1][a[i] - 1];if(i > 1 && i + 1 <= n && a[i + 1] == 2 && a[i] == 1 && a[i - 1] == 3) res = 3;if(res == -1){puts("Infinite");return 0;}else{ans += res;}}printf("Finite\n%d\n", ans);return 0; }

B. Ugly Pairs

將奇數字母\((char - 'a') \& 1\)與偶數字母分別分開來升序排序，設為\(A\)、\(B\)。

嘗試\(AB\)或者\(BA\)，若都不行則無解（注意，題有坑，\(za\)是可以的，而\(az\)不行）

---

證明：

\(A\)與\(B\)都滿足\(str[i] <= str[i + 1] (1 <= i < len)\)

若\(A.end()\)不滿足\(B.begin()\)，反過來匹配也不行。則說明無論怎么拼，它們都是不嚴謹遞增的。

則它們的開頭與結尾是相鄰的，它們相當于一個并行的狀態，必須有一方是不嚴謹遞增的重復字母且一方鄰向。（否則不可能不嚴謹遞增）

#include <cstdio> #include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int N = 110; char s[N]; int n, vis[N]; vector<char> A, B; char inline pre(char c){return 'a' + ((c - 'a' + 25) % 26); } char inline nxt(char c){if(c == 'z') return '?';return 'a' + ((c - 'a' + 1) % 26); } int main(){int T; scanf("%d", &T);while(T--){A.clear(); B.clear();scanf("%s", s + 1);n = strlen(s + 1);for(int i = 1; i <= n; i++){if((s[i] - 'a') & 1) A.push_back(s[i]);else B.push_back(s[i]);}sort(A.begin(), A.end());sort(B.begin(), B.end());if(A.empty() || B.empty()){for(int i = 0; i < A.size(); i++)putchar(A[i]);for(int i = 0; i < B.size(); i++)putchar(B[i]);printf("\n");}else if(pre(A.back()) != B[0] && nxt(A.back()) != B[0]){for(int i = 0; i < A.size(); i++)putchar(A[i]);for(int i = 0; i < B.size(); i++)putchar(B[i]);printf("\n");}else if(pre(B.back()) != A[0] && nxt(B.back()) != A[0]){for(int i = 0; i < B.size(); i++)putchar(B[i]);for(int i = 0; i < A.size(); i++)putchar(A[i]);printf("\n");}else puts("No answer");}return 0; }

C. Match Points

發現答案具有單調性，既然有\(3\)個，那么一定有\(2\)對，可以二分答案。

\(check()\)函數的檢查是一個貪心的過程，使\(x_i\)匹配\(x_{(n / 2) + i}\)這樣是很明顯最優的方案。

---

證明：

存在\(x_a <= x_b <= x_c <= x_d\)

若\((a, b),(c, d)\) 可匹配成功，那么\((a, c),(b, d)\)必定能匹配成功，反命題則不然。

那么\(x_b - x_a >= z\)，也就是\(x_c >= x_b >= z + x_a\)，換過來就是\(x_c - x_a >= z\)

\((b, d)\)的證明同理，所以一一匹配一定是最優的。

PS：寫完了程序才發現可以直接\(O(n)\)求解，看了題解才知道自己太弱了...

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int N = 200010; int n, z, x[N]; bool check(int m){for(int i = 1; i <= m; i++)if(x[n - m + i] - x[i] < z) return false;return true; } int main(){scanf("%d%d", &n, &z);for(int i = 1; i <= n; i++)scanf("%d", x + i);sort(x + 1, x + 1 + n);int l = 0, r = n / 2;while(l < r){int mid = (l + r + 1) >> 1;if(check(mid)) l = mid;else r = mid - 1;}printf("%d\n", l);return 0; }

D. 0-1-Tree

自閉，想不到什么好方法，\(dp\)死活想不出來...

計數問題，可以利用加法原理分開處理。

符合條件的點對\((u, v)\)有三種情況：

全部是\(0\)邊

全部是\(1\)邊

先經過一些\(0\)邊，然后經過\(1\)邊

對于情況\(1\)，我們可以考慮讓圖僅存在\(0\)邊，然后對于每個連通塊，它的點對數量為：

\(size * (size - 1)\)?？梢岳斫鉃槊恳粋€點可以找另外連通塊的所有點，交換下來仍然成立。

對于情況\(2\)，同理情況\(2\)。

對于情況\(3\)，可以考慮找到一個截點\(x\)，路徑考慮為\(s -> x -> t\)，\(s - > x\)上的路徑全部為\(0\)，\(x -> t\)的路徑全部為\(1\)。這種情況，方案數為\((size_{x屬于的0邊連通塊} - 1) * (size_{x屬于的1邊連通塊} - 1)\)，理解為在\(x\)屬于的\(0\)邊連通塊中找一個點\(s(s != x)\) ，在\(1\)邊同理。

對于上述所有操作，僅僅是集合之間的合并，可以用并查集維護。

#include <iostream> #include <cstdio> using namespace std; typedef long long LL; const int N = 200010, M = N << 1; int n, f[N][2], size[N][2]; LL ans = 0; int inline find(int x, int c){return f[x][c] == x ? x : f[x][c] = find(f[x][c], c); } void merge(int a, int b, int c){a = find(a, c), b = find(b, c);if(a != b) f[a][c] = b, size[b][c] += size[a][c]; } int main(){scanf("%d", &n);for(int i = 1; i <= n; i++){f[i][0] = f[i][1] = i;size[i][0] = size[i][1] = 1;}for(int i = 1, u, v, w; i < n; i++){scanf("%d%d%d", &u, &v, &w);merge(u, v, w);}for(int i = 1; i <= n; i++){if(f[i][0] == i)ans += (LL)size[i][0] * (size[i][0] - 1);if(f[i][1] == i)ans += (LL)size[i][1] * (size[i][1] - 1);int p = find(i, 0), q = find(i, 1);ans += (LL)(size[p][0] - 1) * (size[q][1] - 1);}printf("%lld\n", ans);return 0; }

轉載于:https://www.cnblogs.com/dmoransky/p/11310347.html

總結

以上是生活随笔為你收集整理的Codeforces Edu Round 64 A-D的全部內容，希望文章能夠幫你解決所遇到的問題。

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