Kur1su

题解

paper(8) 机器学习(2) 生活记录(6) 读书笔记(1)

/ 注册

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

牛客小白月赛34 题解（ABCDEFGH）

A. dd爱科学1.0 Solution 要求最少花费，只需要找到最长不降子序列，该子序列不做修改，将剩下的修改至符合条件即可。令最长不降子序列长度为，答案为 Code https://ac.nowcoder.com/acm/contest/view-submission?submission...

2021-05-29

3 1133

ABC202 E. Count Descendants(dsu on tree)

链接 Description 给定一棵树，个查询，每次查询给出，查询子树里深度为的节点个数。 Solution 题目特征：1.可离线。2.无修改。显然思路：把查询离线，思考能否把问题转化成找在树上遍历找每个节点下面所有深度的点并统计。显然可以用树上启发式合并实现以上任务，那么只要看我...

2021-05-23

3 804

牛客挑战赛50 C.k-palindrome（双模数哈希+Manacher）来自专栏

Description 简单的说就是定义一个回文串为阶回文需要满足把他切成两半（, ，奇数长度中间的字符不用管）然后这两半都是阶的，定义回文串都可以是阶。 Solution 不会双模数哈希，抄的题解，单模数一直被卡。按照定义，显然是可以类似于的思想去做的，定义所有朴素的回文串都为 ...

2021-05-21

2 820

2021天梯赛L3-1，L3-2个人题解

L3-1 森森旅游 Solution 对1到的所有点建图正向跑关于的最短路反向建图，对到 1的所有点跑关于的最短路令正向最短路为 , 反向最短路为在过程中最短路大小是不会变的，不难推出每个点的贡献是 (向上取整)用一个维护最小值即可，每次进行查找和删除操作注意并不是所有点都能在...

2021-04-28

5 1026

【每日一题】Max Flow（LCA，树上差分）来自专栏

Description FJ给他的牛棚的(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。 FJ有(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间运输到隔间。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你...

2021-04-14

2 929

牛客IOI周赛24-普及组 B 数字串

Descripiton SOlution 不难发现的长度最多为。对于一段不包含的串，需要满足条件至少长度为需要满足条件至多长度为即长度为的串都可能为答案的贡献，对此我们可以暴力找出到底这一段有多长，因为这一段的长度不超过。至于前导零，我们可以记录当前位置的前导零...

2021-04-03

4 658

【每日一题】[HAOI2015]树上染色（树形dp）来自专栏

Description 有一棵点数为的树，树边有边权。给你一个在之内的正整数，你要在这棵树中选择个点，将其染成黑色，并将其他的个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。 Solution , 考虑二维树形令表示以...

2021-03-24

9 939

【每日一题】Tower of Hay 题解(单调队列优化dp) 来自专栏

Description 一堆数字，必须从左到右且全部取出，从下往上放，满足下层上层, 求所能得到的最高层。如下图为两层：样例解释： 3 1 2 3第一层(最下面)放1 2，第二层放3，答案为2 Solution 瞎贪心肯定是不可取的，但是需要知道一个事实：在构造的过程中，在相同高度下，最底层的数...

2021-03-16

3 728

【每日一题】[HAOI2012]容易题(EASY) (组合数学) 来自专栏

Description 给出个数字，每个数字范围是的自然数，有个限制注意: Solution 从数据范围得知要从入手若没有限制条件，则每一个位置都能放答案为可见每一个位置的地位都是相同的，限制条件只是改变某一个位置的值但是实际上最多只能改变个位置，剩下的个位置直接用快速...

2021-03-15

2 712

牛客IOI周赛23-普及组 D.小L的数列(dp)

Description 一句话题意：给出一个数字序列，找出最长的序列满足： Solution 这里给出一个的做法,由于 , 可以通过本题。对于先排序，这样可以满足的要求。随后从小到大做质因数分解，不妨令为当前质因子所能构造的最长序列，那么当遍历到每个数字时...

2021-03-06

2 671