题解
T1 小K与赞助
题目分析:
一张图里两棵树,每个人选择一个点集,两个人选的点集不想交,求最大权值
8~21pts
直接暴力枚举 两个节点不想交
47~65pts
只考虑两棵树完全一样的情况:
树形DP(背包)
dp[i][j][j][k]表示以i为跟的子树,在第一棵树上选j个,第二棵树上选k个点的最大利润。
时间复杂度:O(n3)
100pts
**方法:费用流 **
两个人的两棵树分别建出来 每棵树父亲向儿子连一条有向边,
流量:当前点所对应的子树最多选的点数
每个点都可以接受1的流量(被选择)
最后跑一遍最大费用最大流
时间复杂度:O(n2logn)
T2 小K与重建计划
题意分析:
有解当前仅当:所有点的点权和大于等于所有边的边权和
证明:
∑u,v(a[u]+a[v]−wa,w)>=0
∑u,v(a[u]+a[v])−∑wa,w>=0
7pts
枚举全排列
15pts
状压DP
38pts
枚举所有边,找到一条满足的边,缩边,时间复杂度O(n2)优先缩两端点权
45pts
找边权和最小的树(即最小生成树),其余同38分做法。
70pts
每次找到两个点之间有一条边,合并后点权会改变
100pts
从下往上贪心
每次缩一个子树,满足: 子树点权和(a)-边权和(b)-连到根节点的边+根节点的权值>=0
每次操作后变的只有根节点的权值。
可以按子树点权和-边权和从大到小排序,但其实没必要排序,先做a-b大于0部分,这样的话有解情况下根节点的权值一定会增加,再做a-b小于0部分
T3 小K与作品
**写在前面:**对于一个完全平方数: 每一个质因子的次幂都是偶数
100pts:
设 g(x) 为 x 向左找到的最近的数,即与 f(x) 意义类似,方向相反的函数。
实际上f(x)与 g(x) 互为反函数。
证明:假设从 f(x) 向左找到的第一个位置为 y>x ,则我们把两次找到的序列取对称差(即异或),则得到的新序列也是完全平方数,发现由于 f(x) 在两个序列里都出现了,且 x 只出现了一次,所以可以找到一个左端点为 x ,右端点 <f(x) 的序列,与 f(x) 是向右找到最近的数矛盾。
也就是说,每个合数都有且仅有一个互不相同的解,且答案为 g(x) 。
考虑从 x往前扫,每次加入一个 l ,看是否线性无关~~(直接百度)~~即可。
时间复杂度:O(64ln2nn3) 真的不知道怎么搞出来的
发现超过$ \sqrt n$ 的质数只会有一个,在线性基上特判一下即可。(然而我不知道怎么特判)
不超过 1000的质数只有 168 个,复杂度 O(1281682×nn) ,但实际上答案不会超过 2n,所以可过。
以上思路是理解了,代码还是不会写Orz
今日总结
本来以为第一题能得部分分(两棵树一样的情况),感觉思路还蛮清晰的,没想到居然爆零TOT,第三题打了前n<=20的表然鹅并没有什么用,只有质数的特判得了分。心态有点崩orz
感觉自己见的题型太少了,有些题有些想法但完全没有正解的思路。不过每天都还是在进步吧。QAQ