#2473. 「九省联考 2018」秘密袭击
链接 https://loj.ac/problem/2473
分析:
首先枚举一个权值 W, 计算这个多少个连通块中, 第 k 大的数是这个权值.
$f[i][j]$ 表示到第 i 个节点, 有 j 个大于 W 数的连通块的个数. 然后背包转移.
复杂度是 $O(n^2k)$, 时限 5s, 然后卡卡常就过了.
代码:
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<iostream>
- #include<cmath>
- #include<cctype>
- #include<set>
- #include<queue>
- #include<vector>
- #include<map>
- using namespace std;
- typedef unsigned int ui;
- inline int read() {
- int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
- for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
- }
- const int N = 2005, mod = 64123;
- struct Edge{ int to, nxt; } e[N <<1];
- int head[N], id[N], fa[N], st[N], ed[N], a[N];
- ui f[N][N];
- int n, k, w, Now, En;
- inline bool cmp(int x,int y) { return a[x] == a[y] ? x <= y : a[x] < a[y]; }
- inline void add_edge(int u,int v) {
- ++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En;
- ++En; e[En].to = u, e[En].nxt = head[v]; head[v] = En;
- }
- void dfs(int u) {
- for (int i = st[u]; i <= ed[u]; ++i) f[u][i] = 0;
- if (cmp(Now, u)) st[u] = ed[u] = 1;
- else st[u] = ed[u] = 0;
- f[u][st[u]] = 1;
- for (int i = head[u]; i; i = e[i].nxt) {
- int v = e[i].to;
- if (v == fa[u]) continue;
- fa[v] = u;
- dfs(v);
- for (int j = ed[u]; j>= st[u]; --j)
- for (int k = ed[v]; k>= st[v]; --k)
- f[u][j + k] = (f[u][j + k] + f[u][j] * f[v][k]) % mod;
- ed[u] += ed[v];
- }
- for (int i = st[u]; i <= ed[u]; ++i) f[0][i] = (f[0][i] + f[u][i]) % mod;
- }
- int main() {
- n = read(), k = read(), w = read();
- for (int i = 1; i <= n; ++i) a[i] = read();
- for (int i = 1; i < n; ++i) {
- int u = read(), v = read();
- add_edge(u, v);
- }
- for (int i = 1; i <= n; ++i) id[i] = i;
- sort(id + 1, id + n + 1, cmp);
- ui ans = 0;
- for (int i = 1; i <= n; ++i) {
- memset(f[0], 0, sizeof(f[0]));
- Now = id[i];
- dfs(1);
- for (int j = k; j <= n; ++j)
- ans = (ans + f[0][j] * (a[id[i]] - a[id[i - 1]])) % mod;
- }
- cout << ans % mod;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2949643.html