---

T1 洛谷 U490727 返鄉

思路

首先要意識到一個問題，就是如果所有人總分一定，那么是不會出現偏序的。

可以感性理解一下，就是對于 $i,j$， 若 $a_i\le a_j,b_i\le b_j$，那么一定會有 $c_i\ge c_j$。然后枚舉方案時，保證不會出現 $a_i==a_j\&b_i==b_j$ 這種情況就行。

然后就是看在總分為多少時，方案數最多。
考試的時候可以先寫一個暴力程序，先枚舉總分 $s\in [0,3n]$，然后枚舉前兩科分數 $i,j\in [0,n]$，若算下來第三科成績 $s?i?j$ 也小于等于 $n$，那就是一種合法情況，記錄下方案數，最后求最大值。
復雜度 $O(3n^3)$，代碼如下：

#include <bits/stdc++.h>#define mkpr make_pair
#define fir first
#define sec secondusing namespace std;typedef long long ll;const int maxn = 1e6 + 7;
const int inf  = 0x3f3f3f3f;int n, ansc, anss;
int ans[maxn][3];
int main() {scanf("%d", &n);for (int s = 0; s <= 3 * n; ++s) {int cnt = 0;for (int i = 0; i <= n; ++i)for (int j = 0; j <= n; ++j)if (i + j <= s && s - i - j <= n) ++cnt;if (cnt > ansc) {anss = s;  // 記錄下方案最多時的總分，找找規律ansc = cnt;cnt = 0;for (int i = 0; i <= n; ++i)for (int j = 0; j <= n; ++j)if (i + j <= s && s - i - j <= n) {++cnt,ans[cnt][0] = i;ans[cnt][1] = j;ans[cnt][2] = s - i - j;}}}printf("anss:%d, ansc:%d\n", anss, ansc);for (int i = 1; i <= ansc; ++i)printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);return 0;
}

$n\le 600$，由于有常數 $3$，所以過不去。

然后會有規律：$s=\frac{3n}{2}$ 時，方案數最多。（筆者有點不太會證，先鴿著。。。）

所以直接用如下代碼：

#include <bits/stdc++.h>#define mkpr make_pair
#define fir first
#define sec secondusing namespace std;typedef long long ll;const int maxn = 1e6 + 7;
const int inf  = 0x3f3f3f3f;int n, ansc;
int ans[maxn][3];
int main() {scanf("%d", &n);for (int i = 0; i <= n; ++i) {for (int j = 0; j <= n; ++j) {int k = n * 3 / 2 - i - j;if (k >= 0 && k <= n) {++ansc;ans[ansc][0] = i;ans[ansc][1] = j;ans[ansc][2] = k;}}}	printf("%d\n", ansc);for (int i = 1; i <= ansc; ++i)printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);return 0;
}

$O(n^2)$ 水過。

---

T2 洛谷 U490729 連接

相當溝槽好的一道題，讓我花了一天改。。。
還是要噴一下題解，高中肄業都寫不出那樣生理紊亂的表達。。。
還好有同機房的大佬給出的解法。

一、$15pts$ 思路（$n,l_i,p_i\le 10,O(({\sum }_{i=1}^n{l}_i{)}^2)$）

可以直接用數組把鋼管模擬出來，處理出質量與長度的前綴和數組后，直接 $({\sum }_{i=1}^n{l}_i{)}^2$ 暴力枚舉求密度。
代碼如下：

int sl, sm[107];
double ans;
void Main() {for (int i = 1; i <= n; ++i) {for (int j = sl + 1; j <= sl + len[i]; ++j)sm[j] = sm[j - 1] + p[i];sl += len[i];}for (int i = 1; i <= sl; ++i) {for (int j = i; j <= sl; ++j) {if (sm[j] - sm[i - 1] >= L && sm[j] - sm[i - 1] <= R)ans = max(ans, 1.0 * (sm[j] - sm[i - 1]) / (j - i + 1));}}printf("%.10lf\n", ans);
}

二、$50pts$ 思路（$n\le 5000,O(n^2)$）

$n^2$ 的做法要求我們以完整的塊為單位枚舉求解。

思考兩種截取方法，一種是截整塊（即若干個連續的塊完整地截下來），另一種是帶散塊（即兩端的鋼管不會被截完）。

對于前者，依舊用前綴和直接 $O(n^2)$ 求解。對于后者，要意識到兩件事：

1. 最多只會有一端是散塊，不會兩端都是散塊：因為在質量允許的范圍內，我們肯定更傾向于去兩端中密度更大的那一個，那樣可以使整體密度更大（這點根據生活經驗或者糖水不等式）；
2. 散塊的質量只會有 $L$ 或 $R$：因為如果散塊的密度大，我們肯定希望多取，那就直接取到 $R$，可以使整體密度最大化。如果密度小，那我們肯定希望少取，那就直接取到 $L$，防止其繼續拉低整體密度。

思路大概如此，實現時由于散塊可能是兩端中的任意一個，所以要給 $l_i,p_i$ 數組反轉后再求解一次。枚舉左端點 $i$，然后用雙指針或二分查找維護右端點取值范圍，再直接計算散塊密度。

代碼如下：

#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef double db;const int maxn = 3e5 + 7;int n, len[maxn], p[maxn];
ll L, R, sm[maxn], sl[maxn];
db ans;void solve() {for (int i = 1; i <= n; ++i)sl[i] = sl[i - 1] + len[i],sm[i] = sm[i - 1] + 1ll * len[i] * p[i];//	printf("sl: ");
//	for (int i = 1; i <= n; ++i) printf("%d ", sl[i]);
//	printf("\n");
//	
//	printf("sm: ");
//	for (int i = 1; i <= n; ++i) printf("%d ", sm[i]);
//	printf("\n");// 算一端是散塊的情況int l = 1, r = 0;for (int i = 1; i <= n; ++i) {// 必須滿足質量大于 Lwhile (l <= n && sm[l] - sm[i - 1] < L) ++l;// 這里 r 的判斷條件必須是 r <= n 而不是 r + 1 <= n// 因為后面要判斷質量能不能取到 Rwhile (r <= n && sm[r + 1] - sm[i - 1] < R) ++r;// 再怎么取都無法達到 Lif (l > n) break;// 分子是質量, 分母是長度db pl = 1.0 * L / (sl[l - 1] - sl[i - 1] + (L - (sm[l - 1] - sm[i - 1])) * 1.0 / p[l]);db pr = 1.0 * R / (sl[r - 1] - sl[i - 1] + (R - (sm[r - 1] - sm[i - 1])) * 1.0 / p[r]);// 如果質量取不到 R, 那就不能用 R 為質量來算密度if (r > n) pr = 0.0;ans = max(ans, max(pl, pr));}// 算選的都是整塊的情況for (int i = 1; i <= n; ++i) {for (int j = i; j <= n; ++j) {ll m = sm[j] - sm[i - 1];if (m >= L && m <= R) {ans = max(ans, 1.0 * m / (sl[j] - sl[i - 1]));
//				printf("%lf\n", 1.0 * m / (sl[j] - sl[i - 1]));}else if (m >= L && m > R && i == j)ans = max(ans, p[i] * 1.0);
//			printf("[%d, %d], ans:%lf\n", i, j, ans);}}
}
int main() {
//	freopen("connect2.in", "r", stdin);scanf("%d%lld%lld", &n, &L, &R);for (int i = 1; i <= n; ++i) scanf("%d", len + i);for (int i = 1; i <= n; ++i) scanf("%d", p + i);//	puts("|||||||||||||||||||||||||||||||||||||||||||||");solve();reverse(len + 1, len + n + 1);reverse(p + 1, p + n + 1);
//	puts("|||||||||||||||||||||||||||||||||||||||||||||");solve();printf("%.10lf\n", ans);return 0;
} 

三、正解（O(n×log(max{pi})O(n \times log(max\left \{p_i \right \})O(n×log(max{pi?})）

$O(n^2)$ 的做法在于整塊，所以優化這一部分。

機房大佬給出的解法是先二分密度 $mid$，然后再 $chk$。
$chk$ 函數依舊先枚舉左端點，然后二分查找或雙指針維護右端點取值范圍 $[l,r]$，然后再遍歷 $[l,r]$，看看其中是否存在一個 $j$ 滿足 $\frac{s{m}_j?s{m}_{i?1}}{s{l}_j?s{l}_{i?1}}\ge mid$。但是這樣本質上依舊是 $O(n^2)$ 暴力。

把判斷式子化簡一下，成這樣：$mid\times s{l}_{i?1}?s{m}_{i?1}\ge mid\times s{l}_j?s{m}_j$。發現我們判斷的是區間中的最小值是否小于 $mid\times s{l}_{i?1}?s{m}_{i?1}$，那就用單調隊列維護最小值就好了。

代碼如下：

#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef long double ld;
typedef double db;const int maxn = 3e5 + 7;int n, len[maxn], p[maxn];
ll L, R, sm[maxn], sl[maxn];
db ans;int q[maxn], h, t;
bool chk(ld x) {memset(q, 0, sizeof(q));h = 1, t = 0;for (int i = 1, r = 0; i <= n; ++i) {// 單調隊列擴展右區間while (r + 1 <= n && sm[r + 1] - sm[i - 1] <= R) {++r;while (h <= t && x * sl[q[t]] - sm[q[t]] > x * sl[r] - sm[r]) --t;q[++t] = r;}// 把不合法的左區間刪了while (h <= t && sm[q[h]] - sm[i - 1] < L) ++h;if (h > t) continue;// 滿足上述式子if (x * (ld)sl[i - 1] - (ld)sm[i - 1] >= x * (ld)sl[q[h]] - (ld)sm[q[h]])return true;}return false;
}
void solve() {for (int i = 1; i <= n; ++i)sl[i] = sl[i - 1] + len[i],sm[i] = sm[i - 1] + 1ll * len[i] * p[i];// 算一端是散塊的情況for (int i = 1, l = 1, r = 0; i <= n; ++i) {// 單個塊質量就超出 R 的話直接特判 if (sm[i] - sm[i - 1] >= R) {ans = max(ans, p[i] * 1.0);++l, ++r; continue;}while (l <= n && sm[l] - sm[i - 1] < L) ++l;while (r + 1 <= n && sm[r + 1] - sm[i - 1] <= R) ++r;if (l > n) break;db pl = 1.0 * L / (sl[l - 1] - sl[i - 1] + (L - (sm[l - 1] - sm[i - 1])) * 1.0 / p[l]);db pr = 1.0 * R / (sl[r] - sl[i - 1] + (R - (sm[r] - sm[i - 1])) * 1.0 / p[r + 1]);if (r > n) pr = 0.0;ans = max(ans, max(pl, pr));}// 算選的都是整塊的情況db l = 0.0, r = 0.0;for (int i = 1; i <= n; ++i) r = max(r, p[i] * 1.0);while (r - l >= 1e-7) {db mid = (l + r) / 2;if (chk(mid)) l = mid, ans = max(ans, mid);else r = mid;}
}
int main() {
//	freopen("connect2.in", "r", stdin);scanf("%d%lld%lld", &n, &L, &R);for (int i = 1; i <= n; ++i) scanf("%d", len + i);for (int i = 1; i <= n; ++i) scanf("%d", p + i);solve();reverse(len + 1, len + n + 1);reverse(p + 1, p + n + 1);solve();printf("%.10lf\n", ans);return 0;
} 

---

T3 洛谷 U490735 習慣孤獨

一道這輩子做的最溝施的樹形 $dp$，光改題改了我 $5h$，代碼 + 注釋 + 調試代碼一共 272 行，寫篇題解發泄一下，希望這題沒白改。

一、暴力思路

直接 $dfs$，枚舉第 $i$ 次刪一條邊，然后判斷刪去這條邊后形成的兩個連通塊是否符合要求，
如果符合就直接 $dfs$ 下去，不符合就不管。

理論復雜度是 $O(n^k)$，但是遠遠跑不滿，因為不合法的刪邊相當多。
考場上有一個人拿這得了 $70pts$，再次警醒寫暴力的重要性。但我懶得寫了

二、正解

樹上統計方案數一般就是樹形 $dp$，樹形 $dp$ 的精髓就在于分類討論。
首先轉化一下 $a_i$ 的含義，$a_i$ 表示第 $i$ 刀要砍下的子樹大小，即 $a_i=a_{i?1}?a_i$。

(一) 在以 $u$ 為根的子樹內切割

看見 $k\le 6$，所以可以用狀態壓縮表示切割狀態。
設 $f_{u,s}$ 表示以 $u$ 為根節點的子樹，切割狀態為 $s$ 時的方案數。
$f_{u,s}$ 一共有兩部分構成：一是 $u$ 的子節點，二是當它自己被劃分到一個連通塊時也有貢獻。

上述情況如下圖：

1. 子節點 $v$ 的貢獻（我們把這部分貢獻記為 $g_{u,s}$）：
   
2. $u$ 自己也在一個連通塊中：
   

對于第一種情況，$f_{u,s}$ 的答案就是若干個子樹的方案數的乘積，但是要注意，每個子樹的狀態 $S_v$ 并起來要等于 $s$，且全部 $\&$ 起來要為 $0$，因為不可能砍同一刀；
對于第二種情況，要先判斷 $u$ 所在的連通塊的大小是否符合某一個切割要求，即判斷以 $u$ 為根的子樹剩下的大小是否和某個 $a_i$ 相同。需要注意的是，$u$ 所在的連通塊必須比它子樹中的連通塊的切割時間要晚。下圖就是一個不合法的情況：

(二) 在以 $u$ 為根的子樹外切割

在 $u$ 子樹以外的部分的貢獻由三部分組成：

1. $u$ 的兄弟節點劃分成的連通塊：
   

2. 包含父親節點的連通塊（下面展示一種情況，當然 $fa$ 還可能被包含在"上面連著其他部分"的某個連通塊）：
   
   3.在【"上面連著其他部分"且不包含以 $fa$ 為根的子樹】的連通塊：
   

因此設 $h_{u,v}$ 表示在 $u$ 子樹以外的部分的方案數。

考慮這部分怎么求：
考慮換根 $dp$，那么這部分就可以用 $f_{fa}$ 減去 $f_u$ 的那一部分貢獻來求，但是這一部分貢獻并不好抽離出來（但是為什么我也不太清楚，同機房大佬說是因為這方案數計算的時候實際上是卷積的過程，我也完全不知道是啥），所以考慮正向求解。

1. 首先是兄弟節點，這部分何以用前后綴來求：$pr{e}_{i,s}$ 表示 $u$ 的前 $i$ 個兄弟節點的切割狀態并集為 $s$ 時的方案數，$su{f}_{i,s}$ 表示第 $i$ 個兄弟節點到最后一個兄弟節點的切割狀態并集為 $s$ 的方案數，那么這部分貢獻就是 $h_{u,s1|s2}=pr{e}_{i?1,s1}\times su{f}_{i+1,s2}$（$s1\&s2=0$，$u$ 就是第 $i$ 個兄弟節點）；
2. 其次是父親節點的貢獻：這部分求法和在【求 $f_u$ 中 $u$ 本身屬于一個連通塊的貢獻】的方法一樣；
3. 最后是 $fa$ 以外的貢獻：$fa$ 以外的貢獻實際上就是 $h_{fa}$，將它與 $h_u$ 合并就行。

最后答案是 ${\sum }_{i=1}^n{\sum }_{s=0}^{2^k?1}{g}_{i,s}\times h_{i,(2^k?1)\oplus s}$，但是還要除以 $a_k$，因為我們是欽定 $i$ 在最后一個連通塊中，會有 $a_k$ 個點記錄同一種情況。

代碼如下：

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 5e3 + 7;
const int maxs = (1 << 6) + 7;
const int mod  = 998244353;// 注: 下面所說的 "子節點的子樹" 指的是 "【以 u 的子節點】為根的子樹"int n, m, ms, a[10];
vector<int> e[maxn];int siz[maxn];ll f[maxn][maxs];  // f[u][s] 表示以 u 為根節點的子樹(且【包含 u 節點】)切的狀態為 s 時的方案數 
ll g[maxn][maxs];  // g[u][s] 表示以 u 為根節點的子樹(且【不包含 u 節點】)切的狀態為 s 時的方案數
ll tmp[maxs];void dfs1(int u, int fa) {// 沒切割也算一種方案 siz[u] = f[u][0] = 1;int fid = -1;  // 記錄父節點在 e[u] 中的下標// f[u] 由兩部分組成, 一個是其子節點子樹的貢獻(其實就是 g[u]), 一個是其本身被包含到一個連通塊的貢獻// 下面這部分求的是其 g[u] 的部分for (int i = 1; i <= e[u].size(); ++i) {int v = e[u][i - 1];if (v == fa) {fid = i - 1; continue;}dfs1(v, u), siz[u] += siz[v];// 記錄前 i - 1 棵子節點子樹【不同切割狀態下】的貢獻// 等會用于合并for (int s = 0; s <= ms; ++s)tmp[s] = f[u][s], f[u][s] = 0;// 枚舉前 i - 1 棵子節點子樹切割狀態的【并集】 // 并將其與第 i 棵合并for (int si = 0; si <= ms; ++si) {int sj = ms ^ si;  // 由于不可能砍同一刀, 所以 si & sk 必須等于 0 for (int sk = sj; ; sk = (sk - 1) & sj) {f[u][si | sk] = (f[u][si | sk] + tmp[si] * f[v][sk] % mod) % mod;if (!sk) break;}}}// 父邊沒用就刪了 if (fid != -1) e[u].erase(e[u].begin() + fid);// 記錄子節點的貢獻for (int s = 0; s <= ms; ++s)g[u][s] = f[u][s];// 現在計算 u 本身被包含到一個連通塊的貢獻for (int si = 0; si <= ms; ++si) {  // 枚舉其所有子節點子樹的切割狀態的【并集】 int cut = 0;  // 記錄子節點子樹中被砍去的大小for (int j = 1; j <= m; ++j)if ((si >> (j - 1)) & 1) cut += a[j]; int rest = siz[u] - cut;  // 剩下的節點數 // 枚舉 u 可能會被哪些連通塊包含// 這里必須倒序枚舉, 因為【包含 u 的連通塊】必須比【子節點子樹的連通塊】切得晚 for (int j = m; j; --j) {if ((si >> (j - 1)) & 1) break;  // 不能繼續枚舉比子節點子樹中【最晚的連通塊】更早的連通塊 if (rest == a[j]) f[u][si | (1 << (j - 1))] = (f[u][si | (1 << (j - 1))] + g[u][si]) % mod;}}
}ll pre[maxn][maxs];  // pre[i][s] 表示 u 的前 i 個子樹的切割狀態為 s 時的方案數
ll suf[maxn][maxs];  // suf[i][s] 表示 u 的第 i 個子節點到最后一個子節點的切割狀態為 s 時的方案數
ll h[maxn][maxs];  // h[u][s] 表示除【以 u 為根節點的子樹】以外其他部分的貢獻 
void dfs2(int u) {for (int i = 0; i <= e[u].size() + 1; ++i)for (int s = 0; s <= ms; ++s)pre[i][s] = suf[i][s] = 0;pre[0][0] = suf[e[u].size() + 1][0] = 1;for (int i = 1; i <= e[u].size(); ++i) {int v = e[u][i - 1];for (int si = 0; si <= ms; ++si) {  // 枚舉前 i - 1 個子節點子樹的切割狀態并集 int sj = si ^ ms;for (int sk = sj; ; sk = (sk - 1) & sj) {  // 枚舉第 i 個子節點子樹切割狀態 pre[i][si | sk] = (pre[i][si | sk] + pre[i - 1][si] * f[v][sk] % mod) % mod;if (!sk) break;}}}for (int i = e[u].size(); i; --i) {int v = e[u][i - 1];for (int si = 0; si <= ms; ++si) {int sj = si ^ ms;for (int sk = sj; ; sk = (sk - 1) & sj) {suf[i][si | sk] = (suf[i][si | sk] + suf[i + 1][si] * f[v][sk] % mod) % mod;if (!sk) break;}}}// h[v][s] 貢獻來自三部分for (int i = 1; i <= e[u].size(); ++i) {int v = e[u][i - 1];// 1. v 的兄弟節點for (int si = 0; si <= ms; ++si) {  // 枚舉前綴兄弟節點的切割狀態的【并集】 int sj = ms ^ si;for (int sk = sj; ; sk = (sk - 1) & sj) {  // 枚舉后綴兄弟節點的切割狀態的【并集】h[v][si | sk] = (h[v][si | sk] + pre[i - 1][si] * suf[i + 1][sk] % mod) % mod;if (!sk) break;}}// 2. v 的父親節點以外的for (int s = 0; s <= ms; ++s)tmp[s] = h[v][s], h[v][s] = 0;for (int si = 0; si <= ms; ++si) {  // 枚舉【除【以 u 為根節點的子樹】以外】的部分的切割狀態并集 int sj = si ^ ms;for (int sk = sj; ; sk = (sk - 1) & sj) {h[v][si | sk] = (h[v][si | sk] + h[u][si] * tmp[sk] % mod) % mod;if (!sk) break;}}// 3. v 的父親節點(就是把 (u, v) 斷開后, 產生的包含 u 的連通塊的貢獻) for (int s = 0; s <= ms; ++s) tmp[s] = h[v][s];// 這里枚舉的實際上是: 整棵樹中【除以 u 為根的子樹以外部分】和【v 的兄弟節點子樹】的切割狀態 for (int sj = 0; sj <= ms; ++sj) {int cut = 0;for (int j = 1; j <= m; ++j)if ((sj >> (j - 1)) & 1) cut += a[j];int rest = n - siz[v] - cut;for (int j = m; j; --j) {if ((sj >> (j - 1)) & 1) break;if (rest == a[j]) h[v][sj | (1 << (j - 1))] = (h[v][sj | (1 << (j - 1))] + tmp[sj]) % mod;}}}for (int v : e[u]) dfs2(v);
}
ll qpow(ll x, ll y) {ll res = 1;for (; y; y >>= 1, x = x * x % mod)if (y & 1) res = res * x % mod;return res;
}
int main() {scanf("%d", &n);for (int i = 1, u, v; i < n; ++i) {scanf("%d%d", &u, &v);e[u].push_back(v);e[v].push_back(u);}scanf("%d", &m), ms = (1 << m) - 1;for (int i = 1; i <= m; ++i) scanf("%d", a + i);a[0] = n;for (int i = m + 1; i; --i)a[i] = a[i - 1] - a[i];  // a[i] 表示第 i 次切割時需要切去的子樹大小// a[k] 還要保留下來, 等會統計答案時還要用dfs1(1, 0);h[1][0] = 1;dfs2(1);ll ans = 0;for (int i = 1; i <= n; ++i) {for (int s = 0; s <= ms; ++s) tmp[s] = 0;for (int si = 0; si <= ms; ++si) {int sj = ms ^ si;for (int sk = sj; ; sk = (sk - 1) & sj) {tmp[si | sk] = (tmp[si | sk] + g[i][si] * h[i][sk] % mod) % mod;if (!sk) break;}}ans = (ans + tmp[ms]) % mod;}// 由于在統計答案時, 我們欽定 i 留在最后一個塊中// 所以會有 a[k] 個點記錄的是同一個方案// 所以答案要除以 a[k]printf("%lld\n", ans * qpow(a[m + 1], mod - 2) % mod);return 0;
}

時間復雜度是 $O(n\times 2^{2k})$.

---

T4 車站

是最小樹形圖，不會先不改。