THUPC2018 城市地铁规划
2024-09-23 22:39:55
$n$ 个点,你可以随意连成一棵树,一个点的贡献为 $F(度数) \space mod \space 59393$ ,$F$ 为给定多项式函数,不超过 $10$ 次
求这 $n$ 个点的最大贡献,和最后连出来的那棵树
$n \leq 3000$
sol:
看到这种跟树度数有关的题大概是要上 prufer 序列?
对 prufer 序列进行 dp,每个点大概相当于一个物品,由于 prufer 序列可以任意放,大概还是个完全背包
于是可以写出一个朴素的转移式:
$f_{(i,j)}$ 表示 prufer 序列的前 $i$ 项,目前出现的最后一个数出现了 $j$ 次的最大贡献
每次可以转移到 $f_{(i+1,j+1)}$ (填一个一样的)或者 $f_{(i+1,1)}$ (填一个新的)
或者优秀一点(平时刷题啥都敢写系列),直接对于 prufer 序列上每一个位置,分配它连了多少个叶子,这样空间是一维的,也少了很多分类讨论
后面把 prufer 序列变成一棵树就...用个 set 模拟一下就完事了
#include<bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for(register LL i = (s), i##end = (t); i <= i ## end; ++i)
#define dwn(i, s, t) for(register LL i = (s), i##end = (t); i >= i ## end; --i)
using namespace std;
inline int read() {
int x = , fv = ; char ch = getchar();
for(;!isdigit(ch);ch=getchar())if(ch == '-') fv=-fv;
for(;isdigit(ch);ch=getchar())x = * x + ch - '';
return x * fv;
}
const int maxn = , mod = ;
inline int inc(int x, int y) { x += y; if(x >= mod) x -= mod; return x; }
inline int dec(int x, int y) { x -= y; if(x < ) x += mod; return x; }
inline int mul(int x, int y) { return 1LL * x * y % mod; }
inline int power(int a, int b) {
int res = ;
for (; b; b >>= , a = mul(a, a))
if (b & ) res = mul(res, a);
return res;
}
int n, k, a[], fv[maxn], p[maxn];
LL f[maxn];
inline int getval(int x) {
int res = ;
for (int i = , j = ; i <= k; j = mul(j, x), i++) res = inc(res, mul(j, a[i]));
return res;
}
multiset<int> S, leaves;
int main() {
n = read(); k = read();
rep(i, , k) a[i] = read();
rep(i, , n) fv[i] = getval(i);
if (n == ) {
cout << << " " << a[] << endl;
return ;
}
if (n == ) {
cout << << " " << inc(fv[], fv[]) << endl << << " " << << endl;
return ;
}
rep(i, , n-) rep(j, , i)
if (f[i - j] + 1LL * fv[] * (j - ) + fv[j + ] > f[i])
f[i] = f[i - j] + 1LL * (j - ) * fv[] + fv[j + ], p[i] = i - j; printf("%d %lld\n", n-, f[n-] + fv[] + fv[]);
for (int i = n - , j = i, cnt = ; i; ++cnt, j = i = p[i])
while (j > p[i]) S.insert(cnt), --j;
rep(i, , n) if (!S.count(i)) leaves.insert(i);
rep(i, , n-) {
int u = *leaves.begin(); leaves.erase(u);
int v = *S.begin(); S.erase(S.find(v));
printf("%d %d\n", u, v);
if (!S.count(v)) leaves.insert(v);
}
printf("%d %d\n", *leaves.begin(), *leaves.rbegin());
}
最新文章
- css3部分选择器整理
- 对象关联(associated objects)
- Dev ChartControl鼠标移动显示坐标点
- Python爬虫入门案例:获取百词斩已学单词列表
- href脱离iframe显示
- 时间戳转换成Date
- Oracle安装后,服务中没有监听器怎么处理?
- ZOJ1260/POJ1364国王(King)
- jdbc操作mysql
- bzoj1426
- xmanager远程登录
- java构造函数也可以用private开头
- Permutations 解答
- 一个loader加载多个swf
- lab4 Cache Geometries 深入理解计算机系统——高速缓存
- 18 个最新实用的 jQuery 插件
- 九度OJ题目1076:N的阶乘 (java)运用BigInteger的例子。
- MNIST手写识别
- MySQL 8.0 新增SQL语法对窗口函数和CTE的支持
- android彻底关闭应用程序方法