凡尔赛卷卷

做题笔记

学习笔记(16)

/ 注册

全部文章 / 做题笔记（共85篇）

牛客第九场补题 B Groundhog and Apple Tree 贪心

Groundhog and Apple Tree 题目链接题目大意给一棵树，有边权，点权。走过这条边的需要的hp是边权。只有hp大于等于边权的时候才能走这条边。第一次走到这个点可以获得 ai 的hp。也可以呆在原地不动休息，每秒hp增加1。刚开始在1号节点，问要走完所有的点，并且回...

2020-09-15

0 551

牛客多校第十场补题 Decrement on the Tree 树、妙啊妙啊

Decrement on the Tree 题目链接题目大意一棵树，每次选一条路径让这条路径上的边权都减一，问最少操作多少次可以让这棵树的边权变成0？还有m次修改，每次给出x，y把第x条边边权变为y。每次修改完输出答案是多少。题解一直以为是什么数据结构维护之类的。。是我太年轻了...

2020-09-15

0 503

杭电多校第八场 Kidnapper‘s Matching Problem 线性基 kmp

Kidnapper’s Matching Problem 题目链接题目大意给一个长度为n的数组a，长度为m的数组b，长度为k的数组s。从a数组中选一个长度为m的连续子序列跟b数组两两匹配。配对只能是这样配：(a[l], b[1]), (a[l + 1], b[2]), (a[l + 2...

2020-09-15

0 360

杭电多校第三场 Tokitsukaze and Colorful Tree 树

Tokitsukaze and Colorful Tree 题目链接题目大意给一颗树，每个点有颜色、权值。求的值。这个式子就是颜色相同的，并且u不是v的祖先，并且v不是u的祖先的权值异或完的和。两种操作： 1 x v 把x点的权值变成v 2 x c 把x点的颜色变成c 每次操作完输...

2020-09-15

0 514

Codeforces Global Round 10 E Omkar and Duck

Omkar and Duck 题目链接题目大意这是一个交互题，你先给出一个矩阵，然后输入权值，这个权值是矩阵中(1,1)点到(n,n)点的路径上的权值和。让你输出这个路径。所以要保证每种走法的路径权值和都不一样。题解做的时候想到了，可能的权值是0~x （x是走法的数量）。但是...

2020-09-15

0 512

洛谷 P2633 Count on a tree 主席树、lca、前缀

P2633 Count on a tree 题目链接题目大意给一棵树，有点权，每次询问，x到y路径上点点权的第k小是多少？强制在线，题解第k小，肯定会想到主席树。但是怎么处理呢？数组中求区间第k小的方法是把数组的每个前缀建个权值线段树，然后要查询 l~r 区间的值，就用r的...

2020-09-15

0 417

杭电第九场补题 Game 平衡树维护

Game 题目链接题目大意初始有n列木块，第 i 列有 a[i] 个。有两种操作： 1 x y ：向左推第x列的从下到上第y个，（如上图所示） 2 x ：查询第x列有多少个木块题解用平衡树维护，我用的是fhq treap （因为我只会这个，我好菜hhhh）操作二就是找第x个...

2020-09-15

0 405

杭电第十场 Permutation Counting dp

Permutation Counting 题目链接题目大意给一个只包含0、1，长度维n - 1的数组b， b[i] = 1 表示a[i] > a[i + 1] b[i] = 0 表示a[i] < a[i + 1] a数组是1~n的一个排列，问有多少种a数组。题解 lg过的...

2020-09-15

0 482

杭电第十场 Mine Sweeper 构造

Mine Sweeper 题目链接题目大意扫雷，一个数字代表周围一圈里有多少个雷。给出一个数N，代表所有数字的和。让构造一个所有数字和是N的棋盘。（雷的地方没有数字）要求大小行、列都小于等于25 题解艹，没有看数据范围是1000，还在想怎么能装下最多的，最多装多少。。 x代表...

2020-09-15

0 431

杭电第十场 Coin Game

Coin Game 题目链接题目大意有n台机器可以产生硬币，每一台机器按第一次产生a[i] 个硬币，按第二次产生b[i] 个硬币，按第三次又产生a[i] 个硬币，之后再按就不会产生硬币了。设按x次可以得到的最多的硬币数量是 f(x) ，问f(1) ^ f(2) ^ f(3) ^ …… ...

2020-09-15

0 421