凡尔赛卷卷

分类

做题笔记(85) 学习笔记(16)

/ 注册

全部文章（共101篇）

牛客第六场补题 Josephus Transform 置换、快速幂

Josephus Transform 题目链接题目大意一个长度为n的排列，初始为1……n。有m次操作：每次操作是进行y次 k-约瑟夫变换。这个变换就是：先把1……n写成一个环，然后从1开始找到第k个，把这个数加到b里，把这个数在环里删去，从这个位置下一个继续找第k个，直到数字被删...

2020-09-15

0 586

牛客多校第五场 A Portal 图 dp

Portal 题目链接题目大意刚刚给一个无向图，边权是距离，有k个任务，每个任务是要去两个点，必须先去ai点，后去bi点。任务必须从前往后做，也就是说不能做完1任务就做3任务。现在有两个传送门可以放置，放置传送门的时候必须走到那个点放置，撤掉传送门的时候可以不在那个点。一个传送门可以直接...

2020-09-15

0 415

牛客多校第七场 A National Pandemic 树刨

A National Pandemic 题目链接题目意思给一颗树有三种操作： 1 x y 给每个点点权都加上y - dis[x][y] （dis[x][y]是x->y路径上的边数） 2 x 如果x点的点权大于0，就把他变为0. 3 x 查询x的点权。题解先看第一种操作： y...

2020-09-15

0 371

找矩阵第k大的数、力扣 1508. 子数组和排序后的区间和

如何在有序矩阵中找第k大的数？ 378. 有序矩阵中第K小的元素题目链接一个矩阵从左到右递增、从上到下递增怎么找第k大的数？ 1、把矩阵变成一维然后排个序 2、合并有序数组那样合并 3、二分主要说二分怎么求。二分一个第k大是多少。 check的时候，也就是判断有没有k个数大于等于mi...

2020-09-15

0 817

杭电多校第五场 Tree 树形dp

Tree 题目链接题目大意给一棵树，让选择一个联通的子图满足: 度数大于k的点的数量不超过1个（小于等于1）图是联通的。边权和最大。问能选出来的最大边权和是多少。题解树形dp dp[x][0] 表示x的子树里的点的度数都小于等于k的边权和最大值。 dp[x][1] 表示x的...

2020-09-15

0 412

牛客第七场补题 Valuable Forests prufer序列

Valuable Forests 题目链接题目大意定义一个树的权值为它的所有顶点度数的平方和。森林的权值为所有树的权值和。求有n个点，带编号点的，所有的森林的权值和。带编号意思是1-2-3 不等于 1-3-2 题解 prufer序列学习博客大佬题解博客看的这两篇博客学会的这道...

2020-09-15

0 406

牛客第九场补题 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