2019暑假正睿集训8.5day2题解及总结

题解

T1 小K与赞助

题目分析:

一张图里两棵树,每个人选择一个点集,两个人选的点集不想交,求最大权值

8~21pts

直接暴力枚举 两个节点不想交

47~65pts

只考虑两棵树完全一样的情况:

树形DP(背包)

dp[i][j][j][k]dp[i][j][j][k]dp[i][j][j][k]表示以i为跟的子树,在第一棵树上选j个,第二棵树上选k个点的最大利润。

时间复杂度:O(n3)O(n^3)O(n3)

100pts

**方法:费用流 **

两个人的两棵树分别建出来 每棵树父亲向儿子连一条有向边,

流量:当前点所对应的子树最多选的点数

每个点都可以接受1的流量(被选择)

最后跑一遍最大费用最大流

时间复杂度:O(n2logn)O(n^2logn)O(n2logn)

T2 小K与重建计划

题意分析:

有解当前仅当:所有点的点权和大于等于所有边的边权和

证明:

u,v(a[u]+a[v]wa,w)>=0\sum_{u,v}(a[u]+a[v]-w_{a,w})>=0∑u,v​(a[u]+a[v]−wa,w​)>=0

u,v(a[u]+a[v]wa,w>=0\sum_{u,v}(a[u]+a[v])-\sum w_{a,w}>=0∑u,v​(a[u]+a[v])−∑wa,w​>=0

7pts

枚举全排列

15pts

状压DP

38pts

枚举所有边,找到一条满足的边,缩边,O(n2)时间复杂度O(n^2)时间复杂度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(n364ln2n)O(\frac{n^3}{64\ln ^2n})O(64ln2nn3​) 真的不知道怎么搞出来的

发现超过$ \sqrt n$ 的质数只会有一个,在线性基上特判一下即可。(然而我不知道怎么特判)

不超过 1000的质数只有 168 个,复杂度 O(1682×n128n)O(\frac{168^2\times n}{128}n)O(1281682×n​n) ,但实际上答案不会超过 n2\frac n22n​,所以可过。

以上思路是理解了,代码还是不会写Orz

今日总结

本来以为第一题能得部分分(两棵树一样的情况),感觉思路还蛮清晰的,没想到居然爆零TOT,第三题打了前n<=20的表然鹅并没有什么用,只有质数的特判得了分。心态有点崩orz

感觉自己见的题型太少了,有些题有些想法但完全没有正解的思路。不过每天都还是在进步吧。QAQ

上一篇:SpringBoot集成 mybatis


下一篇:java基础复习四