A
先打表, 然后两层暴力或者一层暴力 + lower_bound 水一水水过
B
哎这题水, LCA 板题啊, 美滋滋美滋滋
然后代码实现敲炸了
首先想多了, 特判了很多可以不用特判的, 两种情况一个写法的我又分别讨论, 无端增加码量不说, 还出了很多不知道为什么奇奇怪怪的错误, 最后就只拿了一个特判分
以及敲错了两边 (考试一遍订正一遍) 的一个很鬼的地方:
- scanf("%d%d",&x,&y);
- if(x == y){
- ......
- printf("%d\n", n - size[x11] - size[y11]);
- }
我写成了
- scanf("%d%d",&x,&y);
- if(x == y){
- ......
- printf("%d\n", size[lca] - size[x11] - size[y11]);
- }
考场上敲了一遍手工模拟了两组自己造的数据, 本来想对拍, 但是不太会写暴力(floyd 还写炸了), 写完暴力又不会造数据(树咋整啊)
考完认认真真学了一波对拍
- (实际上是改了半天错还是 WA70 后被过来巡视的老板逮住, 瑟瑟发抖的在老板的目光下学会了如何造一棵树 + 对拍的一些奇奇怪怪的错误修改技巧)
- C
有一说一, 码量还没 B 大, 先贪心一波:
显然尽可能选孤立点对 (两个点一条边) 出来, 设选出了 M 对孤立点对.
选够了 (\(M \times 2>= K\)) 就输出 \((K+1)/2\)
没有足够的点对的话剩下的点怎么连都是一个点一条边, 那么答案为 $M + (K - M \tims 2) $ == \(K - M\)
至于如何选最大孤立点对, 树形 dp 乱搞:
dp[i][0]表示以 i 为根的子树中能够两两配对的最大点数, 不包含节点 i.
dp[i][1]表示以 i 为根的子树中能够两两配对的最大点数, 包含节点 i.
显然 dp[i][1]>dp[i][0]
转移方程:
dp[u][0]=Σv 是 u 的儿子 dp[v][1];
- dp[u][1]=max(dp[u][1],dp[u][0]-dp[v][1]+dp[v][0]+2).
- M = dp[1][1]
总结一波
期望得分:\(100 + 100 + 0 = 200\)
实际得分:\(100 + 0 + 0 = 100\)
码力过于糟糕, 不予置评
来源: http://www.bubuko.com/infodetail-3224387.html