三道题，T1原本打了个错的DP，后来干脆改成了贪心，只花了30mins就解决了这题，获得了90pts的好成绩。T2想到了正解，写Code+对拍用了2h，最后因为数组开小获得了跟暴力一样的好成绩，苦酒入喉心作痛。T3 看都没看瞎jb打了个dp就交了，获得了0pts的好成绩。 事实证明： 数组开大一点会死吗？ 数组开大一点会死吗？ 数组开大一点会死吗？ 重要的事情说三遍，再忘记开大数组就回家种田吧。
这题的样例是有锅的，没有给数据组数T，导致很多人爆0，然而细心的忘了开大数组的我并没有掉进坑里。
不要小看这个特殊性质：数据保证随机生成。 记住是“水机”生成。 显然的贪心算法：选择 c i c_i ci最小的一个，把其他的都改成最小的这个，获得了 90 p t s 90pts 90pts的（nice）成绩，爆踩正解党。 然鹅这个数据就能把它卡掉： 5 4 4 1 4 4 这种情况的话肯定是把唯一的1改成4，但是贪心的做法就挂了。 （不过敢于贪心得到了出题人的极大鼓励）
题解是 O ( n 3 ) O(n^3) O(n3)的做法，还有 O ( n 2 ) O(n^2) O(n2)的算法，但我并没有理解。 我们首先枚举最终变成的颜色，然后就可以DP。 设 f i f_i fi表示把前 i i i个瓶子都改成最终颜色的代价， m i n i , j min_{i,j} mini,j表示区间 [ i , j ] [i,j] [i,j]的最小值， c o s t i , j cost_{i,j} costi,j表示把区间 [ i , j ] [i,j] [i,j]都改成 m i n i , j min_{i,j} mini,j的代价，最终颜色为 c o l o r color color，可以得到转移方程： f i = m i n ( f j + c o s t j + 1 , i ) i f m i n j + 1 , i = c o l o r f_i=min(f_j+cost_{j+1,i})\ \ if\ min_{j+1,i}=color fi=min(fj+costj+1,i) if minj+1,i=color f i = m i n ( f j + c o s t j + 1 , i + c o l o r ∗ ( i − j ) ∗ m i n j + 1 , i ) i f m i n j + 1 , i ≠ c o l o r f_i=min(f_j+cost_{j+1,i}+color*(i-j)*min_{j+1,i})\ \ if\ min_{j+1,i}≠color fi=min(fj+costj+1,i+color∗(i−j)∗minj+1,i) if minj+1,i̸=color 其中 0 ≤ j ≤ i − 1 0\le j \le i-1 0≤j≤i−1。 转移方程的由来其实就是选一段区间，先把这段区间改成区间内的最小值，然后再改成目标颜色。 但是这样DP可能会一次性把所有瓶子都改成非目标颜色，因此我们还需要倒着做一次DP，即设 g i g_i gi表示后 i i i个瓶子都改成最终颜色的代价。转移类似。 于是全部改成 c o l o r color color的最小花费就是 m i n ( f i − 1 + g i + 1 ∣ c i = c o l o r ) min(f_{i-1}+g_{i+1}|c_i=color) min(fi−1+gi+1∣ci=color)。
跑得很慢的Code：
#include <cstdio> #include <cstring> #include <cstdlib> typedef long long ll; const int N = 3e2 + 7, MAXC = 1e5 + 7; ll min(ll a, ll b) { return a < b ? a : b; } int T; int n, c[N], buc[MAXC]; ll ans = (1LL << 62), f[N], g[N], mi[N][N], sum[N], cost[N][N]; int main() { freopen("input", "r", stdin); //freopen("colour.in", "r", stdin); //freopen("colour.out", "w", stdout); scanf("%d", &T); while (T--) { memset(mi, 0, sizeof(mi)); memset(sum, 0, sizeof(sum)); memset(cost, 0, sizeof(cost)); memset(buc, 0, sizeof(buc)); ans = (1LL << 62); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", c + i); mi[i][i] = c[i], sum[i] = sum[i - 1] + c[i]; } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) mi[i][j] = min(mi[i][j - 1], c[j]); for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) { ll s = sum[j] - sum[i - 1]; for (int k = i; k <= j; k++) if (c[k] == mi[i][j]) s -= c[k]; cost[i][j] = mi[i][j] * s; } for (int i = 1; i <= n; i++) if (!buc[c[i]]) { memset(f, 0x3f, sizeof(f)); memset(g, 0x3f, sizeof(g)); f[0] = g[n + 1] = 0; for (int j = 1; j <= n; j++) for (int k = 0; k <= j - 1; k++) f[j] = min(f[j], f[k] + cost[k + 1][j] + (mi[k + 1][j] == c[i] ? 0 : 1ll * c[i] * (j - k) * mi[k + 1][j])); for (int j = n; j >= 1; j--) for (int k = n + 1; k >= j + 1; k--) g[j] = min(g[j], g[k] + cost[j][k - 1] + (mi[j][k - 1] == c[i] ? 0 : 1ll * c[i] * (k - j) * mi[j][k - 1])); ll ret = (1LL << 62); for (int j = 1; j <= n; j++) if (c[j] == c[i]) ret = min(ret, f[j - 1] + g[j + 1]); ans = min(ans, ret); buc[c[i]] = 1; } printf("%lld\n", ans); } fclose(stdin); fclose(stdout); return 0; }并不能启发人类智慧的Constraints。 这题虽然想到了正解，但是因为sb错误没有AC，以后一定要吸取教训。
都说从暴力想，跟着部分分的提示容易想出正解，但是我套路题做得比较多吧，这题就直接想出来了。
首先需要一个性质： 对于任意的 u , v u,v u,v， d ( u , v ) d(u,v) d(u,v)一定是图的最小生成树上的边的边权。
这个比较容易证明，因为要保证图联通首先需要一棵生成树，又为了使最大边最小，就用最小生成树上的边。
然后可以考虑用Kruskal构建最小生成树，新加的每一条边肯定连通了两个连通块。由于边权经过排序，这两个连通块中任意各选两点 u , v u,v u,v， d ( u , v ) d(u,v) d(u,v)一定等于新加这条边的边权，这个很容易想到吧。
Then，如果我们能快速得到两个连通块中满足条件的点对数，这个数*边权就是对答案的贡献。
暴力的思想是用桶维护两个连通块中每个点的 c i c_i ci，由于 c i c_i ci很大，我们可以考虑用权值线段树维护。依照启发式合并的思想，我们可以枚举较小连通块的每个点（这个用vector<int>记录一下，合并完clear()一下就行了），然后在较大连通块的权值线段树里查询答案。并查集，权值线段树，vector都用启发式合并，复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。 离散化之后可能常数小一点，我要实锤dh手动吸氧 。
Code：
#include <vector> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; typedef long long ll; const int N = 2e5 + 7, M = 5e5 + 7; inline int read() { int x = 0, f = 0; char c = getchar(); for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = 1; for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ '0'); return f ? -x : x; } int n, m, L, c[N], pl[N], rl[N]; int len, arr[N * 3]; struct edge { int from, to, len; } E[M]; ll ans; int fa[N], size[N]; int getfa(int x) { return fa[x] == x ? x : getfa(fa[x]); } vector<int> s[N]; int tot, root[N], sum[N * 50], lson[N * 50], rson[N * 50]; void merge(int x, int y) { sum[y] += sum[x]; if (lson[x] && lson[y]) merge(lson[x], lson[y]); else if (lson[x]) lson[y] = lson[x]; else if (lson[y]) lson[x] = lson[y]; if (rson[x] && rson[y]) merge(rson[x], rson[y]); else if (rson[x]) rson[y] = rson[x]; else if (rson[y]) rson[x] = rson[y]; } void insert(int &rt, int l, int r, int po) { if (!rt) rt = ++tot; sum[rt]++; if (l == r) return; int mid = l + r >> 1; if (po <= mid) insert(lson[rt], l, mid, po); else insert(rson[rt], mid + 1, r, po); } int qrysum(int rt, int l, int r, int ql, int qr) { if (ql > qr) return 0; if (!rt) return 0; if (ql <= l && r <= qr) return sum[rt]; int mid = l + r >> 1, ret = 0; if (ql <= mid) ret += qrysum(lson[rt], l, mid, ql, qr); if (mid + 1 <= qr) ret += qrysum(rson[rt], mid + 1, r, ql, qr); return ret; } int cmp(edge x, edge y) { return x.len < y.len; } void init() { n = read(), m = read(), L = read(); for (int i = 1; i <= n; i++) c[i] = read(), arr[++len] = c[i], arr[++len] = c[i] - L, arr[++len] = c[i] + L; sort(arr + 1, arr + len + 1); len = unique(arr + 1, arr + len + 1) - arr - 1; for (int i = 1; i <= n; i++) { pl[i] = lower_bound(arr + 1, arr + len + 1, c[i] + L) - arr; rl[i] = lower_bound(arr + 1, arr + len + 1, c[i] - L) - arr; c[i] = lower_bound(arr + 1, arr + len + 1, c[i]) - arr; } for (int i = 1; i <= m; i++) E[i].from = read(), E[i].to = read(), E[i].len = read(); for (int i = 1; i <= n; i++) fa[i] = i, size[i] = 1, insert(root[i], 1, len, c[i]), s[i].push_back(i); sort(E + 1, E + m + 1, cmp); } void solve() { for (int i = 1, cnt = 0; i <= m; i++) { int u = E[i].from, v = E[i].to; u = getfa(u), v = getfa(v); if (u == v) continue; if (size[u] > size[v]) swap(u, v); int siz = s[u].size(); for (int j = 0; j < siz; j++) { if (L == 0) ans += sum[root[v]] * 1ll * E[i].len; else ans += (qrysum(root[v], 1, len, 1, rl[s[u][j]]) + qrysum(root[v], 1, len, pl[s[u][j]], len)) * 1ll * E[i].len; s[v].push_back(s[u][j]); } s[u].clear(); fa[u] = v, size[v] += size[u], merge(root[u], root[v]); cnt++; if (cnt == n - 1) break; } printf("%lld\n", ans); } int main() { //freopen("input", "r", stdin); //freopen("output", "w", stdout); //freopen("graph.in", "r", stdin); //freopen("graph.out", "w", stdout); init(); solve(); fclose(stdin); fclose(stdout); return 0; }这么难不改了。
又是颓废的一天。。。
