我可爱的珂朵莉树 珂朵莉树又名 在数据随机的情况下极其优秀，会有些意想不到的结果 思维简单暴力，操作简单粗暴 实现原理 就是现对于原数组相同颜色段推平然后一起处理。必然如果数据部随机一种颜色一格一定会有非常美妙的效果。 实现方式 初始化 我们可以用一个三元组分别表示被推平后用来维护即可的左右端点以及区间值。 代码如下： vector<pair<int,int> >g; struct nood { int l,r; mutable int v; inline bool friend operator < (const noo...

题解- P3658 Why Did the Cow Cross the Road III P 题目大意 很小清新。就是给你两个排列使得两个排列中相同的数字两边相连。最后问你存在多少对数对满足有交叉且 我们可以将题目转化的更加小清新。因为要有交显然满足以及为该元素在排列中的位置 这样我们就可以设一个三元组满足 于是这样就转换为一个三维偏序的简单问题，三维偏序见戳这里 然后我们考虑单次计算的贡献显然为这段区间里的答案，简单容斥即可 #include <bits/stdc++.h> #define For(i,a,b) for ( int i=(a);i<...

题解-P2824[HEOI2016/TJOI2016]排序 题目意思 就是给你一个排列，接下来有次操作每次将区间里的数降序或者升序排列，最后询问。 这道题目主要是思想的转化，其他并无难点。对于这种思想的转化可以看戳这里。 考虑离线。 我们可以二分答案，对于每次二分的答案如果大于那么将变为否则变为。 然后对于修改为递增序列我们可以先统计出区间中的个数，然后将区间里的数变为并且将里的数变为,如果是递减序列也是相近类似的操作。这些都是可以用线段树进行维护的。 对于最后我们只要判断是不是为即可。 #include <bits/stdc++.h> using namespac...

题目大意 就是有两种操作： 把区间里面的数加上 询问区间里有多少幸运数字 由于最大值很小，直接预处理即可 然后用树状数组维护区间这种数的个数。对于查询操作我们直接输出即可。 对于修改操作我们可以暴力扫一遍对于原来是幸运数的数先再如果原数加上后为幸运数。 时间复杂度： #include <bits/stdc++.h> #define lowbit(x) x&(-x) using namespace std; const int maxn=200005; int n,m,c[maxn],a[maxn],is[maxn],ans,ma; inline void i...

#1024#&nbsp;cout<<"Happy&nbsp;1024!";

rp++

W&nbsp;round&nbsp;1&nbsp;题解&nbsp;比赛链接&nbsp;https://www.luogu.org/contest/18397&nbsp;.好题&nbsp;题目意思&nbsp;给一个巨大的杨辉三角，采用类似入门题(数字三角形)的方式求从顶点到指定点的最小累加和。&nbsp;输出样例，和样例中的第二组数据一样呀&nbsp;应该比较好写吧&nbsp;组合数问题&nbsp;顶点到指定点的最小累加和，一定是走边上。因为边上的数值最小。从顶点到指定点的最小累加和，是先走步竖直向下的，每步取最小值，然后再斜向下走一直到.累加和为。另外，我们可以发现，当时，先斜向下走到，再竖直向下走到，路径上的数值累加和是最小的。但是这道题目直接运用求组合数是会超时的，要加不少预处理才...

这道题目难度不是很大的，主要就是分类讨论。&nbsp;题目意思&nbsp;题目意思很简单，就是让你找出一对点对使得两点之间曼哈顿距离最大。&nbsp;暴力大法&nbsp;这道题目显然暴力不能过。&nbsp;正解&nbsp;这道题目难就难在分类讨论：&nbsp;我们已经知道原式为：&nbsp;我们先来考虑几种情况：&nbsp;当以及的时候，此时原式将会转换为：。然后移项可得：，要让这个柿子的结果尽量大，我们就要让大，尽量小，这个很好理解：更大的减去更小的才能更大。&nbsp;当以及的时候，此时原式转换为：此时我们像情况一样，让尽量小，尽量大。&nbsp;最后只要比较这两种情况谁大谁小就可以了：，这样我们就将复杂度缩小到。&nbsp;代码实现&nbsp;#include&nbsp;&lt;bits/stdc++.h&gt;&nbsp;using...

这道题目难度不是很大，大概也就的难度。&nbsp;下面我们来讲一下我的心路历程&nbsp;理解题目意思：这道题目就是给我们求树上的两个点，给你一个权值，让你计算在之间的总和，这道题目的总和是这样算的:那么我们先来理解一下样例：&nbsp;样例中，所以对于第一组数据它的答案就是&nbsp;算法思想这道题目看到点与点之间的距离、深度，很容易想到用,如果你不会右拐☞这样我们这道题目剩下的就是如何统计答案，我们记录一个数组表示以为节点，为题目给定的权值，在这棵数中的前缀和。&nbsp;对于样例的第二组数据：表示从到根节点的答案。那么我们计算与之间的总和是不是就是&nbsp;于是我们对于任何树上的两点，的公共祖先为两点之间的总和就是，其中的就是求时候的变量...

题解-CF1131D&nbsp;Gourmet&nbsp;choice&nbsp;题目意思&nbsp;就是给你很多个约束条件,让你求出合法的序列满足条件且最大值最小的方案。&nbsp;对于一开始的那些条件我们先让以及放入同一个连通块里。&nbsp;第二次再做一遍，如果两个处于同一个联通块的点又有的关系显然就只要输出即可。&nbsp;然后第二次做关于大于小于关系的点的时候：&nbsp;若为则：从并且统计的度加加&nbsp;若为则：从并且统计的度加加&nbsp;这样做完一遍我们就形成了一个。于是只要在这张图上跑一下拓扑就可以了，在途中用表示答案，因为题目要求求最大值最小，所以&nbsp;#include&nbsp;&lt;bits/stdc++.h&gt;&nbsp;using&nbsp;nam...

这是一道很好的题目&nbsp;对于这道题目，我们首先明确的状态：&nbsp;表示当扔下第个垃圾时，高度为此时的还可以存活多久&nbsp;对于转移，我们要分两种情况：&nbsp;当不选用这个垃圾来当垫子时：&nbsp;当选用这个垃圾来当垫子时&nbsp;表示垃圾可以垫高的高度&nbsp;表示吃垃圾可以维持的生命多少&nbsp;对于爬不出的情况：&nbsp;初始化：&nbsp;#include&nbsp;&lt;bits/stdc++.h&gt;&nbsp;using&nbsp;namespace&nbsp;std;&nbsp;const&nbsp;int&nbsp;N=1e2+5,Inf=1e12;&nbsp;struct&nbsp;rubbish&nbsp;{&nbsp;int&nbsp;t,f,h;&nbsp;}&nbsp;num[N];&nbsp;inline&nbsp;bool&nbsp;cmp(rubbish&nbsp;x,rubbish&nbsp;y)...

这道题目真是挺难的：主要的算法就是,以及点双连通以及最后对答案的处理用到的组合数学。&nbsp;题目传送门：P3225&nbsp;[HNOI2012]矿场搭建&nbsp;题目大概意思：就是有很多个点，在某个时候一个点将会塌陷，你要建造一些点，使他们在那个点塌陷时成功逃脱！&nbsp;此时我们要分类讨论三种情况：&nbsp;情况一：在一个强连通中没有一个割点（见下图）&nbsp;那么此时至少要建立两个点，使得在点坍塌时能顺利逃脱，那么此时要建立的点的个数就是(就是强连通的个数)，而方案数则是&nbsp;情况二：在一个强连通中有一个割点（见下图）&nbsp;绿色的点即为割点，此时在一个强连通分量中只要建立个即可，那么总共需要建立个（意义同上）；&nbsp;情况三：在一个强连通中有两...