Cwyy

分类

学习笔记(3) 比赛(1) 题解(24)

/ 注册

全部文章（共7篇）

题解 P4211 【[LNOI2014]LCA】

题解- 窝，调了个上午发现被***错误困扰，总算调出来了。题目意思题面很小清新：就是求前置知识：树链剖分+差分考虑离线。我们首先可以把题目意思转换为：每次把询问区间里的点到根节点路径上的点权值（包括自己）加一，最后询问到根节点的权值和。我们可以画张图来理解这个转换...

线段树树链剖分 lca 转化

2020-03-03

1 821

题解 CF722E 【Research Rover】

题解- CF722E 题目意思题目就是让你从走到的道路中有个特殊点，没经过一个特殊点会使分数变为原来一半，问从到的期望得分（对取模）我们首先把也看成特殊点，但是分数不用除二，然后为了保证每次是向下或向右先对排序即可，接下来就是啦。这道题目如果把状态设为表示到点经过个特殊点的方...

期望贪心动态规划转化

2020-02-26

1 832

题解 CF1296E2 【String Coloring (hard version)】

题解- CF1296E2 题目意思就是要给每个位置分配一种颜色，使得不同的颜色相邻的字符可以完成交换位置。求一种合理的方案。思维题。其实发现几个显然的性质就很容易啦。对于一段相同或者递增的串只要使得他们相同即可，因为不需要进行交换，可以随意填色。但是值得注意的是，如果一个串长成...

构造转化

2020-02-12

2 1180

题解 CF264C 【Choosing Balls】

题解- CF246C Choosing Balls 题目意思说人话就是你可以选若干个物品，若这次选择的物品与上次选的相同那么这个的贡献就是否则是。要使得利益最大化。一开始我以为是什么贪心。后来想想认为还是一个。就是要利用其特殊的一个性质单调性我们设表示到现在选择的最后一个元素...

动态规划转化

2020-02-06

1 711

题解 P6040 课后期末考试滑溜滑溜补习班

题解-P6040 「ACOI2020」课后期末考试滑溜滑溜补习班题目意思题目较长，不便于描述这道题目就是考察了一道基础的单调队列优化，以及化柿子的方法。，暴力设表示到的最小花费精力，转移即可 if(n<=1000) { memset(f,127/3,si...

单调队列动态规划转化

2020-02-01

1 674

题解 P6005 Time is Mooney G

题解-P6005 Time is Mooney G 题目意思就是给你一个有向图，你在上面走，没经过一个点可以获得，最后你要减去(走过的边数) 考虑,我们设表示第天到达城市的最大收益。转移很简单对于的处理我们只需要反向建有向边即可，答案就是但是这样的枚举范围无法确定，但是我们发现即可，因...

最短路动态规划转化

2020-01-26

1 1078

题解 P2824 [TJOI2016]排序

题解-P2824[HEOI2016/TJOI2016]排序题目意思就是给你一个排列，接下来有次操作每次将区间里的数降序或者升序排列，最后询问。这道题目主要是思想的转化，其他并无难点。对于这种思想的转化可以看戳这里。考虑离线。我们可以二分答案，对于每次二分的答案如果大于那么将变为否...

线段树二分转化

2019-10-28

2 758