Cwyy

题解

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

/ 注册

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

题解 CF1082D Maximum Diameter Graph

题解-CF1082D Maximum Diameter Graph 题目大意就是让你构造一连通的无向图,使得每个点的度数并且要使得直径足够长。贪心：要让直径最长我们就要构造链，对于的点把他们加到链上去。然后把那些度为的点粘到链上去。最后一点也是最值得注意的是：我们还可以让链变得更加长...

构造贪心树的直径

2019-11-13

1 571

题解 P3658 [USACO17FEB]【cdq模板题】

题解- P3658 Why Did the Cow Cross the Road III P 题目大意很小清新。就是给你两个排列使得两个排列中相同的数字两边相连。最后问你存在多少对数对满足有交叉且我们可以将题目转化的更加小清新。因为要有交显然满足以及为该元素在排列中的位置这样我们就可...

树状数组 cdq

2019-11-03

1 772

题解 P2824 [TJOI2016]排序

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

线段树二分转化

2019-10-28

2 758

题解-CF121E Lucky Array

题目大意就是有两种操作：把区间里面的数加上询问区间里有多少幸运数字由于最大值很小，直接预处理即可然后用树状数组维护区间这种数的个数。对于查询操作我们直接输出即可。对于修改操作我们可以暴力扫一遍对于原来是幸运数的数先再如果原数加上后为幸运数。时间复杂度： #include &l...

树状数组数论

2019-10-24

1 583

W round 1 题解

W round 1 题解比赛链接 https://www.luogu.org/contest/18397 .好题题目意思给一个巨大的杨辉三角，采用类似入门题(数字三角形)的方式求从顶点到指定点的最小累加和。输出样例，和样例中的第二组数据一样呀应该比较好写吧组合数问...

2019-10-16

2 706

题解 [USACO2004OPEN]洞穴里的牛之三

这道题目难度不是很大的，主要就是分类讨论。题目意思题目意思很简单，就是让你找出一对点对使得两点之间曼哈顿距离最大。暴力大法这道题目显然暴力不能过。正解这道题目难就难在分类讨论：我们已经知道原式为：我们先来考虑几种情况：当以及的时候，此时原式将会转换为：。然后移项可得：，要让这个柿子...

数论

2019-10-15

1 670

题解 P4427 【[BJOI2018]求和】

这道题目难度不是很大，大概也就的难度。下面我们来讲一下我的心路历程理解题目意思：这道题目就是给我们求树上的两个点，给你一个权值，让你计算在之间的总和，这道题目的总和是这样算的:那么我们先来理解一下样例：样例中，所以对于第一组数据它的答案就是算法思想这道题目看到点与点之间的距离、深度，很...

lca

2019-10-15

1 1531

题解 CF1131D 【Gourmet choice】

题解-CF1131D Gourmet choice 题目意思就是给你很多个约束条件,让你求出合法的序列满足条件且最大值最小的方案。对于一开始的那些条件我们先让以及放入同一个连通块里。第二次再做一遍，如果两个处于同一个联通块的点又有的关系显然就只要输出即可。然后第...

topu 贪心 tarjan

2019-10-15

1 766

题解 P1156 【垃圾陷阱】

这是一道很好的题目对于这道题目，我们首先明确的状态：表示当扔下第个垃圾时，高度为此时的还可以存活多久对于转移，我们要分两种情况：当不选用这个垃圾来当垫子时：当选用这个垃圾来当垫子时表示垃圾可以垫高的高度表示吃垃圾可以维持的生命多少对于爬不出的情况：初始化： #include...

贪心动态规划

2019-10-15

1 768

题解 P3225 【[HNOI2012]矿场搭建】

这道题目真是挺难的：主要的算法就是,以及点双连通以及最后对答案的处理用到的组合数学。题目传送门：P3225 [HNOI2012]矿场搭建题目大概意思：就是有很多个点，在某个时候一个点将会塌陷，你要建造一些点，使他们在那个点塌陷时成功逃脱！此时我们要分类讨论三种情况：情况一：在一个强连通中没有...

数论 tarjan

2019-10-15

1 985