回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共29篇）

Sum of Paths CodeForces - 1467D 来自专栏

Sum of Paths CodeForces - 1467DTagscombinatorics dp math *2200 题意：定义一条好的路径，当且仅当从任意点出发之后恰好经过了 k 次移动，定义这条路径的权值为经过点权值的总和(可重)，进行 q 次修改，每次将ak 改为 x ,询问此时所有...

*** dp

2021-03-01

0 875

Three Bags CodeForces - 1467C 来自专栏

题意：三堆石子，你可以取两堆石子各一个石头a,b。然后消掉a，使得b=b-a再放入b的那一堆。这样操作直到只剩下一个石子，求该石子价值最大。题解：构造题可以构造出两者情况：其中两堆都是正的，一堆都是负的一个背包都是正的，另两个背包的最小值是负的，其他都是正的为什么是这样构造出来的呢？参考...

*** 思维

2021-03-01

0 912

Codeforces Round #696 来自专栏

Codeforces Round #696@[toc] CF1474A Puzzle From the Future 题意：在2022年，Mike发现了两个长度为n的二进制整数a和b(它们都只由前导有0的数字(和1)表示)。为了不忘记它们，他想用以下方式构造整数d: 他将a和b按位加和而不进行进位...

比赛 ***

2021-03-01

0 816

CF613D Kingdom and its Cities

CF613D Kingdom and its Cities 题目：给定一棵有n 个节点的树，树上有一些关键点(key)。接下来有q组询问，每次给出ki 个key，要求删去一些点，使得这些key不相连。要求删去的最少的点数。 1<=n<=100000 1<=q<=100000...

虚树树形dp ***

2021-02-23

0 652

P2607 [ZJOI2008]骑士

P2607 [ZJOI2008]骑士题意： n个点n个边，每个点都有权值，相邻的点不能同时选择，问如何选择能使得权值最大题解：这个题很有P1352 没有上司的舞会这个题的感觉，唯一的区别是那个题保证是树，而本题肯定不是树，而是基环树也就是本题中，每一个连通块有且只有一个环，所以我们找到这个环并...

基环树树形dp ***

2021-02-22

0 613

P5049 [NOIP2018 提高组] 旅行

P5049 [NOIP2018 提高组] 旅行题意：一棵树(可能是基环树)，从1出发，每到达一个新的点就记录下编号。求一种走法使得记录下来的编号字典序最小。 1≤n≤500000 m=n−1 或 m=n 题解：如果不是基环树，那直接每次走字典序小的点即可对于基环树：第一个方法：暴力删边将基环...

基环树 ***

2021-02-22

0 517

P3992 [BJOI2017]开车

P3992 [BJOI2017]开车题意：题解：我们要先将问题转换圈是车，x是加油站。红色部分为车移动的路线数组a是车数量的前缀和数组b是加油站的前缀和而a[i]与b[i]的差的绝对值就是对应的红色路被走的次数现在车发生位置移动，b数组没有影响，a数组i到j这段整体减一现在我们要做的就是维护...

*** 分块

2021-02-22

0 560

CF1183H Subsequences (hard version) 来自专栏

题意：长度为n的字符串S，现在要找出k个不同的子序列，使得这些序列的总价值最低一个序列的价值等于删去的字符长度（空串也算子序列）1≤n≤100,1≤k≤10^12^ 题解：一看就是dp，我们先想想串a可以有多少不同的子序列dp[i][j]表示前i个字符构造出来的长度为j的子序列数量转移方程不难得...

*** dp

2021-02-20

0 723

P5829 【模板】失配树

P5829 【模板】失配树题目：题解：参考题解我们先想一个问题：如何求出一个字符串的所有border？如果一个字符串既是 S的前缀又是 S 的后缀，那么我们把 SS 自己平移一下就可以前后重合，然后我们就可以继续匹。。。。。这不就是KMP吗求两个前缀的最长公共border，先对原串进行KMP...

失配树 ***

2021-02-18

0 641

P3265 [JLOI2015]装备购买

题目描述：给N个整数向量，每个向量带权值，求权值和最小的线性基题解：按权值v从小->大排序，依次插入线性基。整数线性基的思想类似，只是此时“消去”不能直接xor完成，需要类似高斯消元一样for一遍代码： #include<bits/stdc++.h> #define eps...

线性基 *** 高斯消元

2021-02-18

0 632