人丑心更黑

分类

读书笔记(1) 题解(52)

/ 注册

全部文章（共53篇）

每日一题4月3日 Shortest Path 思维+dfs

算是一题有点思维难度的题。题意：有一颗n个节点的树，现在要把这棵树分成n/2部分，每部分都由2个节点构成，给出n-1条边的边权。当2个点构成一个部分的时候，假设是从u->v，认为经过的边的边权和为需要的花费。问最少的花费和是多少。思路：一开始的时候有点没有思绪。但是再纸上画一画可以发现一点...

2021-01-30

0 460

每日一题4月2日华华查月月的手机字符串枚举

一开始以为是kmp，结果发现是子序列，不要求连续。题意：给出一个字符串s，接着给m个询问，每次询问一个字符串p,问p是否是s的子序列。len(s)<=10^6,m<=10^6，∑p<=10^6. 思路：一开始想的是，预处理出s中的每个字母依次出现的位置，在询问的时候维护当前已经到...

2021-01-30

0 515

每日一题4月1日 Rinne Loves Edges 树形dp，dfs

每日一题居然放了一个简单题。题意：给一个无向图，n个点n-1条边，每条边上有边权，现在给定一个根s，求以s为根的图中，删掉一些边要让所有度为1的点不能连接到s。思路：根据题意，给出的图就是一颗树。那么就是问删一些边让叶子节点无法连通到根s。我们可以考虑某个点x，假设要让x子树的叶子节点无法连通s...

2021-01-28

0 462

NC15429 区间的连续段倍增

本题一开始想的是用f[i][j]表示从i开始长度为2^j的和，然后每次查询的时候利用倍增去快速找到某一段的最右边。结果超时了，后来想了下，万一卡一个n段的数据，就挂了。而且这样倍增还不如直接O（1）预处理每个点到下一段的距离来得快。题意: 给你一个长为n的序列a和一个常数k 有m次询问，每次查询一...

2021-01-28

0 699

每日一题3月31日城市网络树上倍增

好几天没有做每日一题了，因为周五有场比赛，然后周末出去浪了。其实是因为这题卡住了。T-T 题意：给一颗有n个点的树，每个点上有一个权值，记录1为根节点。现在有q次询问，每次询问（u,v,c）表示从u走到v，一路上遇到的点权如果比c大就选择购入珠宝，然后更新这个c，换句话说就是购入的时候的点权只能递增...

2021-01-26

0 527

牛客IOI周赛22-普及组题解

普及组的题目，感觉挺适合现在的我做的。。。。前两题可以无压力AC的，第三题想不出来了，第四题可惜没去试一试。 A 战争尾声题意：给一个200*200的矩形，放在平面直角坐标系中。给n个点，问能否找到一个点到所有n个点的距离相同。n的坐标要求是正整数。n<=200。思路：题目保证答案是正整数...

2021-01-25

0 447

每日一题3月30日滑动窗口单调队列

今天的题目比较简单~ 题意：有一个数字序列长度为N，现在有一个长度为K的窗口。每次窗口可以查看到序列中连续的K个数字，求窗口在不同位置时候查看的K个数字序列中的最大值和最小值。类型：单调队列思路：首先可能会考虑线段树，虽然存在频繁的查询，但是10^6的话nlogn应该还是可以碰一碰的，不过好像会...

2021-01-22

1 572

每日一题3月27日数学考试线性dp，线段树

这题乍一看还挺简单的，仔细一看，好像还有那么点意思。题意：从n个数中选出两个不相交的区间，且区间长度都为K，求这两个区间的和的最大值。(n<=200000) 题目类型：前缀和、动态规划、线段树思路：由于区间长度是固定的，很容易想到枚举区间的起点。如果分别枚举两个区间的起点的话，我们需要O(...

2021-01-21

1 621

每日一题3月26日合并回文子串区间dp

今天做的是合并回文子串虽说看到题目就知道是个dp，无奈写不出来。首先来看题意：给两个字符串A和B，现在将A和B进行合并，要求两个字符串中原有的相对位置不发生变化，问合并的可能中最长的回文子串长度？这里A和B的长度都不超过50. 题目类型：区间DP 题解已经讲的很好了，这里做个总结： 1.最长回文...

2021-01-20

5 806

每日一题3月25日tokitsukaze and Soldier 优先队列

看到牛客的每日一题挺有意思，决定刷一刷看看。本来想从后往前的，一看发现有点难，还是从头开始吧，应该前面简单点吧。先做第一期的第一题tokitsukaze and Soldier（3月25日）题目是这样的，从N个士兵中挑选一些组成一个团，每个士兵有一个战力v[i]和一个要求s[i]，这里的s[i]表...

2021-01-19

0 464