HNOI 模拟赛
HNOI2021 模拟赛记录。
2020.12.26-27
2021.01.02 ~ 2021.01.03
2021.01.09 ~ 2021.01.10
2021.01.16 ~ 2021.01.17
2021.01.29
2021.02.06 ~ 2021.02.07
2021.02.17
2021.02.18
2021.02.20
2021.02.22
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Cauphenuny's Blog！
相关推荐
2020-12-01
noip2020 模拟赛
记录考试总结 2020.09.05 比赛入口 比赛时一开始把T1做了，用了个错算法，但是我当时不知道。随后想了一会儿做了T2。最后半个小时一对拍就发现T1用了个错的dp方法，于是赶紧写了个60pts暴力交上去。 然而，T2由于把题目理解错了，只计算了 ∑i=1npi\sum_{i=1}^{n}p_i∑i=1npi ，导致100pts$\to$20pts。 最终得分：80 Solution： 无线网路发射器选址 经典的求最大矩形问题：悬线法。 记 hi,jh_{i, j}hi,j 为以 (i,j)(i,j)(i,j) 为起点，向上的最长空线段（即悬线）长度。 li,jl_{i,j}li,j 为 (i,j)(i,j)(i,j) 向左最多拓展到的点 ri,jr_{i,j}ri,j 为 (i,j)(i,j)(i,j) 向右最多拓展到的点 si,js_{i,j}si,j 为悬线最多向左移动到的列编号 ti,jt_{i,j}ti,j 为悬线最多向右移动到的列编号 则有 ans=max(hi,j×(ti,j−si,j+1))(1≤i≤n,1≤j≤m)ans=max...
2020-12-03
CF708C Centroids 总结
CF708C Centroids 题意简述： 给定一棵 nnn 个点的树，你可以删除一条边并增加一条边，形成一棵新树。 问每个点在进行这样的操作后，是否可能成为新树的重心。 1≤n≤4⋅1051 \le n \le 4\cdot 10^51≤n≤4⋅105 发现没有是一个无根树，很难处理。考虑把树的重心 rt 找出来，然后想象把这颗树从 rt 处提起来 于是对于子树内的每个点 v ，大于 ⌊n2⌋\left\lfloor\dfrac{n}{2}\right\rfloor⌊2n⌋ 的部分只可能出现在 v 的父亲 u 所在联通块上。 即红色区域。那么我们需要把红色区域拆分成两个大小不大于 ⌊n2⌋\left\lfloor\dfrac{n}{2}\right\rfloor⌊2n⌋ 的部分，分别接到 v 上。 拆分有几个选择，拆掉 u 的父亲所在子树（即上图 1 部分），或者把与 v 同级的子树拆掉，（即上图 2,3,4 ）。 设分出来不大于 ⌊n2⌋\left\lfloor\dfrac{n}{2}\right\rfloor⌊2n⌋ 的部分的最大大小为...
2020-10-19
P2596 [ZJOI2006]书架 总结
link 构造一颗中序遍历是序列的Treap，发现可以很容易地求出序列上第 xxx 位的值，即为 getval(root, x) ，但是不好求一个数 kkk 在序列上的位置。这时我们就可以维护一个值 idx(k)idx(k)idx(k) ，表示值为 kkk 的节点编号，这时只需要设计出一个函数来求节点 uuu 的排名了，而这个函数也很容易实现，对于一个节点 uuu ，每次将它向树根跳，如果它是右儿子，那么就将它父亲的左子树的值以及父亲的大小计入结果。 12345678910int getpos(int id) { int f, cnt = 0; while ((f = p[id].f) != 0) { if (id == p[f].rs) { cnt += p[p[f].ls].siz + 1; } id = f; } return cnt;} 既然要存储一个节点的父亲，那么 pushup...
2020-10-03
可持久化平衡树
link fhq 改几个函数就可以了 12345int refresh(int id) { tot++; p[tot] = p[id]; return tot;} 123456789101112131415void split_by_val(int rt, int &a, int &b, int val) { if (rt == 0) { a = b = 0; return; } if (p[rt].val <= val) { a = refresh(rt);// split_by_val(p[rt].rs, p[a].rs, b, val); pushup(a);//记得是pushup(a)，不是pushup(rt)！！！ } else { b = refresh(rt);// split_by_val(p[rt].ls, a,...
2021-02-06
P5851 (USACO19DEC) Greedy Pie Eaters P
区间 dp ，注意枚举端点 i，j，k 的顺序，模拟一下就好了，如果使用了未更新的状态，就是错的 sorry for that i don’t have a chinese input method Functions: g(x, l, r) means we have the largest cow which can eat pos(x) , and it can only affect pies in [l, r] f(x, l, r) means the weight summary that we can get from a sequence of cows, and it only affect pies in [l, r] So we have the things below: 12345678910111213foreach cow_i foreach x in range[l_i, r_i] g(x, l_i, r_i) = w_i;foreach k in [1 -> n] foreach i in [k -> 1], j in [k...
评论