Cwyy

题解

学习笔记(3) 比赛(1)

/ 注册

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

题解 P4211 【[LNOI2014]LCA】

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

线段树树链剖分 lca 转化

2020-03-03

1 821

题解 CF722E 【Research Rover】

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

期望贪心动态规划转化

2020-02-26

1 832

题解 P3523 【[POI2011]DYN-Dynamite】

题解- P3523 DYN-Dynamite 题目意思就是在一颗树中选个点使得这个点到关键点的距离最大值最小。双倍经验总算看懂题解来重新理解一遍，加深记忆。。回归正题，因为题目要我们求最大值最小显然会想到二分。首先我们设几个变量：表示以为子树最近选择节点的距...

二分贪心动态规划

2020-02-25

1 792

题解 P2569 【[SCOI2010]股票交易】

题解- P2569 股票交易题目意思由于题面过长，不再描述。戳这里这道题目想清楚后还是不难的，是一道不错的单调队列练习题。首先我们要明确状态：表式到第天拥有个股票的最大收益。这个状态还是挺显然的，不像某些题目卡状态。对于转移，要分成多种情况来考虑： ...

单调队列动态规划

2020-02-16

1 713

题解 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

题解 P4134 【[BJOI2012]连连看】

题解- P4134 连连看题目大意就是在区间中找出尽量多的数对,若两种情况下数对数相同使得若干对数对和尽量大。这道题目难点在于如何转换到熟悉的模型——最小费用最大流。但是题目要我们求数对和尽量大，所以我们只要把边权取反相当于求最小费用，最后答案再去一遍反即可。因为这样我们就可以用简单...

网络流

2020-01-20

1 673

题解 CF650D 【Zip-line】

题解- CF650D Zip-line 题目意思就是给你个序列以及多次操作，每次把换做求一遍（操作之间互不影响）显然每次修改暴力做是不可行的复杂度至少为。于是我们要思考每次修改会对答案形成怎样的影响。先对原序列每个点做一遍以他为结束的记为，以他作为起始的记为。易得原序列的就为。每次对...

树状数组 lis

2020-01-20

1 702