凡尔赛卷卷

做题笔记

学习笔记(16)

/ 注册

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

杭电第二场补题 A String Distance dp

String Distance 题目链接题目大意给两个字符串a，b。 a的长度是1e5，b的长度是20. 有两种操作：选一个串在随便哪个位置插入随便哪个字符。随便删除一个字符。有q次询问，每次询问给出一个l，r 问a串的 l ~ r 区间与b字符串，经过多少次操作，能使他们相等？废...

2020-09-15

0 422

牛客多校第5场补题 B Graph 异或最小生成树

Graph 题目链接题目大意给出一颗树，有两种操作，添加一条边，删除一条边。每个时刻必须满足如果有环那么环的边权异或和必须是0，必须是联通的。题解也就是先求一下每个节点到根节点的异或和，然后用这些值的异或当边权求个最小生成树。问题就是知道一些点的点权，边权是两个点权异或，...

2020-09-15

0 472

杭电第三场 Tokitsukaze and Rescue 图

Tokitsukaze and Rescue 题目链接题目大意给一张完全图，每个边有边权。问删掉k条边让从1到n的最短路最长，问这个最长的距离是多少？边权随机，点的个数: 50 题解做的时候，感觉到了这个题很暴力，但是没想到这么暴力。。做的题少，主要不知道边权随机是干嘛用的。。...

2020-09-15

0 722

杭电第四场 Go Running 二分图

Go Running 题目链接题目大意一些人在跑步，从任意一个位置开始，向左或向右跑，速度都为1 m/s。现在已经知道在ti 时刻xi位置上出现了至少一个人，问最少有多少人在跑步题解先说一说比赛的时候的不足: 想到了往右跑的人在任意时刻 t - x 一定是相等的。想到了往左跑的...

2020-09-15

0 500

牛客第六场补题数位dp Harmony Pairs

Harmony Pairs 题目链接题目大意 S(A) 代表A的每位数之和。求0 <= A <= B <= n 并且 S(A) > S(B) 的（A，B）对的数量。题解看到这道题，首先想到数位dp，然后就不会了。。状态表示：dp[i][j][f1][f2]...

2020-09-15

0 485

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

杭电多校第五场 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