A. Ilya and Diplomas
思路：水題了， 隨隨便便枚舉一下，分情況討論一下就OK了。
code：
#include#include #include #include #include #include #include #define inf 1000000 #define clr(x, y) memset(x, y, sizeof x) using namespace std; int rmina,rmaxa; int rminb,rmaxb; int rminc,rmaxc; int n; int main() { scanf(%d, &n); scanf(%d%d%d%d%d%d, &rmina, &rmaxa, &rminb, &rmaxb, &rminc, &rmaxc); int d = n - rminb - rminc; if (d > rmaxa) { d = n - rmaxa - rminc; if (d > rmaxb) { d = n - rmaxa - rmaxb; printf(%d %d %d , rmaxa, rmaxb, d); } else printf(%d %d %d , rmaxa, d, rminc); } else printf(%d %d %d , d, rminb, rminc); return 0; }
B. Pasha and Tea
題意：一共有w升水，有n個男生和n個女生。每個人都有一個有容量限制a[i]的杯子，每個男生分到的水容量相等，每個女生分到的水容量相等，且每個男生分到的水是女生的二倍，問所有人能分到水的容量的最大值是多少。
思路：設x為在總終狀態下每個女生分到的水的量，a代表女生的最小容量，b代表男生的最小容量，則有x = min(a,b/2,w/3*n)，則 ans = x * 3* n
code :
#include#include #include #include #include #include #define clr(x, y) memset(x, y, sizeof x) #define inf 1000000000 using namespace std; const int maxn = 300005; int a[maxn]; int n, w; int main() { scanf(%d%d, &n, &w); for (int i = 0; i < 2*n; i++) scanf(%d, &a[i]); sort(a, a + 2*n); double x0 = (double)w / (3*n); double x1 = (double)a[0]; double x2 = (double)a[n] / 2; x0 = min(x0, x1); x0 = min(x0, x2); x0 = x0 * 3 * n; printf(%f , x0); return 0; }
C. Arthur and Table
題意：給一個有n個腿的桌子，每個腿有其長度li，同時移除某個腿需要消費di的能量，當長度為最大值的腿的個數大於桌腿的總數的時候，桌子處於平穩狀態，輸入給出n，li，di問將桌子變成平穩狀態所需要的耗費的能量的最小值。
思路：第一眼看上去肯定是要去枚舉最大長度的桌腿了，但是怎麼樣快速的計算確定桌腿後達到平穩狀態所需要花費的能量呢？ 這個能量包括兩部分，一部分是將長度大於當前正在枚舉的桌腿的桌腿全部刪掉所需要的能量，一部分是刪掉使被枚舉的長度的桌腿個數大於一半所要消耗的能量。 一開始我把所有的注意力全部都放在了單個的桌腿上，然後在計算復雜度的時候怎麼算都感覺會超時， 後來才注意到題目的key ------- di 的大小只有200， 可以按照di對桌腳進行分類， 然後從小到大來枚舉di，問題就迎刃而解了～～
code：
#include#include #include #include #include #include #define clr(x, y) memset(x, y, sizeof x) #define inf 1000000000 using namespace std; const int maxn = 100005; int n; int L[maxn]; int D[maxn]; int sum[maxn]; int cnt[maxn]; int cnt_d[maxn]; struct pp { int li, di; pp(int a = 0, int b = 0) : li(a), di(b) {} } P[maxn]; bool cmp(pp A, pp B) { return A.li > B.li; } int main() { scanf(%d, &n); for (int i = 0; i < n; i++) scanf(%d, &L[i]); for (int i = 0; i < n; i++) scanf(%d, &D[i]); for (int i = 0; i < n; i++) P[i] = pp(L[i],D[i]); clr(sum, 0); clr(cnt, 0); clr(cnt_d, 0); for (int i = 0; i < n; i++) { sum[L[i]] += D[i]; cnt[L[i]] ++; cnt_d[D[i]] ++; } sort(P, P + n, cmp); int coa, ss, cnta, ans; coa = 0; cnta = 0; ans = inf; for (int i = 0; i < n; i++) { ss = coa; int v = P[i].li; int j; for (j = i; j < n; j++) { if (P[j].li != v) break; cnt_d[P[j].di]--; } i = j-1; int nn = n - cnta; int cha; if (cnt[v] == 1) cha = nn - 1; else cha = nn - (cnt[v] - 1) * 2 - 1; for (int i = 1; i <= 200; i++) { if (cha > cnt_d[i]) { ss += cnt_d[i] * i; cha -= cnt_d[i]; } else { if (cha >= 0) ss += i * cha; break; } } ans = min(ans, ss); cnta += cnt[v]; coa += sum[v]; } printf(%d , ans); return 0; }
D. Vitaly and Cycle
題意：給出一個無向圖（圖可能不聯通），問最少加入多少條邊可以使圖具有一個奇環，並計算有多少種加邊的方法。
思路： 題目其實不是很難，但是自己做的時候也是磨了好久才把題目給磨出來， 做法是這樣的：首先有一個大家都懂的事實：要構成奇環加入邊的個數不會超過3條，然後再分情況討論加入0,1,2,3條邊的情況。
首先對圖進行黑白染色，在染色的同時統計每個聯通塊中黑色節點的個數， 還有白色節點的個數，然後討論
Case 0： 如果存在一個聯通塊黑白染色不成功，則肯定存在一個奇環，此時所需要加入的邊數就為0，其方案數固定為1。（如果有一條邊的兩端顏色是一樣的則染色不成功）
Case 1： 對於一個聯通塊，如果用一條邊將兩個黑色點或者白色點連起來，就能形成一個奇環，所以就可以通過一開始所統計的每個聯通塊中黑白節點的個數快速的計算出來。
Case 2： 如果每個聯通塊都是1個頂點或者兩個頂點，則用2條邊就能形成環，這種就統計一下一個點的連通塊和兩個點的連通塊各有多少個再用組合數學搞一搞就行了。
Case 3: 全部是獨立點的情況， 從中隨意取三個點就可以了～～～
ps: 黑白染色其實直接跑一遍dfs（or bfs） 就行了， 我太年輕的先跑了一個生成樹，然後則染色，其實沒有必要～。
code:
#include#include #include #include #include #include #define clr(x, y) memset(x, y, sizeof x) #define inf 1000000000 using namespace std; const int maxn = 200005; vector G[maxn]; struct edge { int st,ed; bool flag; } E[maxn]; int n, m; int par[maxn]; int col[maxn]; int white[maxn]; int black[maxn]; int ta; void init(int n_) { for(int i = 0; i <= n_; i++) par[i] = i; } int Find(int x) { if (x == par[x]) return x; return par[x] = Find(par[x]); } void unit(int x, int y) { x = Find(x); y = Find(y); if (x == y) return ; par[y] = x; } bool same(int x, int y) { return Find(x) == Find(y); } void dfs(int u, int &wh, int &bl) { for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (col[v] != -1) continue; col[v] = col[u]^1; col[v] == 0? wh++ : bl++; dfs(v, wh, bl); } } int main() { scanf(%d%d, &n, &m); int st, ed; for (int i = 0; i < m; i++) { scanf(%d%d, &E[i].st, &E[i].ed); E[i].flag = false; } init(n); for (int i = 0; i < m; i++) { if (!same(E[i].st, E[i].ed)) { unit(E[i].st, E[i].ed); G[E[i].st].push_back(E[i].ed); G[E[i].ed].push_back(E[i].st); E[i].flag = true; } } clr(col, -1); clr(white, 0); clr(black, 0); ta = 0; for (int i = 1; i <= n; i++) { if (col[i] == -1) { int wh = 1; int bl = 0; col[i] = 0; dfs(i, wh, bl); white[ta] = wh; black[ta++] = bl; } } for (int i = 0; i < m; i++) { if (E[i].flag == true) continue; if (col[E[i].st] == col[E[i].ed]) { printf(0 1 ); return 0; } } long long w = 0; for (int i = 0; i < ta; i++) { if (white[i] > 1) w += (long long)white[i]*(white[i]-1)/2; if (black[i] > 1) w += (long long)black[i]*(black[i]-1)/2; } if (w > 0) { printf(1 %lld , w); return 0; } int cnt = 0; int tmp = n; for (int i = 0; i < ta; i++) { if (white[i]+black[i] > 1) cnt++; } for (int i = 0; i < ta; i++) { if (white[i]+black[i] > 1) { cnt--; tmp -= 2; w += tmp; w += 2*cnt; } else { tmp --; w += cnt; } } if (w > 0) { printf(2 %lld , w); return 0; } w += (long long)n*(n-1)*(n-2)/6; printf(3 %lld , w); return 0; }
E. Ann and Half-Palindrome
題意： 首先題目定義了一個半回文串：一個串是半回文串，當且僅當，這個中間軸左邊的奇數位置上的字符與其對稱位置上的字符相同，題目給出一個串s，和整數k讓你求出s的所有半回文子串中字典序第k大的串，s的長度是5000。
思路：這道題目做起來也可謂是波折滿滿啊， 一開始聽劉神說是暴力，就自己敲了一個最最暴力的做法，尼瑪啊O（n^3）的方法你怕不怕，然後一算肯定超時啊，就在想怎麼來優化，感覺枚舉子串的地方沒有什麼可優化的了， 就在想判回文的地方有沒有什麼可以更快的方法，沒想出來（還是太弱了），然後劉神告訴我說用區間dp的思想隨便預處理一下就行了，頓時恍然大悟，馬上又去改了一發，發現超內存 ->___->,然後劉神有告訴我說用動態字典樹啊，然後我就去改了字典樹，發現T了~~~~， 一看劉神的姿勢才發現字典樹的插入是O（n）的，但是他沒插入一個就相當於插入了所有的以插入串開頭的前綴子串，所以在枚舉子串的時候只有枚舉頭就行了~~~，又改了一發最後才過...
其中字典樹的每個節點都多維護一個域用來存，其子樹中有多少個半回文串，之後找第K大的串就用類似平衡樹上dfs查找某個節點的思想不斷的查找左右子樹就行了，其中還有一些小的細節需要注意~~~
code：
