题目： 给你一棵个结点的树。给个标记结点，距离。问树上有几个结点到所有标记结点的距离均。 做法： 考虑做一个树，表示结点到所有标记结点的最大距离。求出之后，一遍看有多少就出结果了。这个树怎么做呢？先一遍求出以结点为根的子树下的标记到的最大距离，放到（若子树下无标记则为）。然后第二遍换根转移，每次用不经过儿子的，到子树下标记的最大距离更新。新开一个表示结点不经过第个儿子，到子树下标记的最大距离。则同时还要更新下结点的数组。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(...

题目： 游戏界面是一个长为，高为的二维平面，其中有个管道（忽略管道的宽度）。 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。 小鸟每个单位时间沿横坐标方向右移的距离为1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度Y。小鸟位于横坐标方向不同位置时，上升的高度X和下降的高度Y可能互不相同。 小鸟高度等于0或者小鸟碰到管道时，游戏失败。小鸟高度为m时，无法再上升。现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少...

题目： 给一棵以为根，带点权的二叉树。让你找出一棵最大的子树是对称二叉树。对称二叉树就是将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。 做法： 所谓对称二叉树我们转换一下概念就是子树的中根遍历序列是一个回文，当然要保证树的形态一致，我们在对树进行中序遍历时，进入一个结点就加一个，退出一个结点就加一个。然后我们对中序遍历序列正反都做一个哈希，在反序列中和进行互换。然后我们就能在时间复杂度判断一段区间是否是回文序列了。此时，我们枚举每棵子树对应的区间序列，判断一下就行。 代码： #include <bits/stdc++.h> #define IOS i...

题目： 给你一个，让你将其拆成最少的若干个十进制数的和，这些十进制数只由和构成。要求输出方案。 做法： 这些特殊的十进制数其实与二进制数一一对应，以内只有个（对应于位以内二进制数和）。我们考虑先将以内的数先求出来。然后这就变成了一个完全背包问题，要求输出方案。方案用一个辅助记录当前最后一个选的数即可。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << ...

题目： 个点的无向图，货车要连续天将货物从结点运到结点，货车走过一条边的代价=边的长度。其中会给一些限制，即结点在天内无法使用。货车每换一次运输路线需要花费的代价。问货车天将货物从结点运到结点的最小代价。 做法： 由于和的规模比较小。我们要打破固有的图论思维做这道题。设为货车前天运送货物的最小代价。我们可以枚举上一次更换运输路线的时间点来转移。因为当确定了天运输路线不变时，此路线就是这些天里用能用的点跑出来的到的最短路。也就是。因为和又很小，所以枚举每个都跑一遍最短路转移即可。 代码： #include <bits/stdc++.h> #define IOS ios::sync...

题目： 给你一棵个结点的树，结点带权值。让你删去2条树边使其变成3棵点权和相等的非空树。输出任意方案。 做法： 我们求出个点的点权和。如果肯定无解。任一合法方案，删除2条边后，必定形成如下图形状的联通块，其中的点权和相同： 和必定是某棵完整的子树。所以我们从根一遍，一旦找到某棵子树和为，说明找到了，记录这棵子树的根，把子树删掉，接着处理。最后如果纪录了棵子树，说明有解。注意不能用判断，因为点权有负值，可能找到茫茫多子树。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0...

题目： 给定一个长度为的数组，刚开始每一项的值均为0。个操作：1 l r：数组A中区间的数+1。2 l r：区间的操作重做一遍。（数据保证小于当前操作编号） 次操作后，输出数组。1e9+7输出。 做法： 由于2操作不会直接作用在数组上。所以我们的关注点在于个操作中所有1操作对应的次数。如果我们知道每个1操作做了几次，设为第个操作的次数，那么差分一下就能得到数组了，具体就是1到m一遍，对所有1操作,然后做一次前缀和。题目告诉我们2操作只会影响前面操作的次数。所以我们从后往前处理，同样用一次差分就能得到数组，具体就是m到1一遍，对所有的2操作，,因为差分要用到,所以做差分的同时做的后缀和。所以总...

题目： 数轴上n个点。k个炸弹，每个炸弹可以将一个长2R+1的区间覆盖。问覆盖n个点的，R的最小值。n≤50000，k≤10 做法： 很明显可以二分R的值。然后O(n)check。具体就是贪心地用区间的左端点覆盖当前最左边的点，这样每个区间都发挥最大的作用。然后看覆盖n个点需要用几个区间，设为cnt，若cnt>k，说明R小了，l = mid+1，否则r = mid-1。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout...

题目： 给一个长为的，落在上的区间序列，问最短的子序列，相邻区间有交集，连续覆盖上所有点。。 做法： 线段树上每个叶子表示上的一个点，维护当前延伸到需要的最短区间序列长度。一开始设结点1为0，其他点为。每次读入一个区间，左端点，即用已有的区间延伸到所需的最短区间序列长度，设为。然后用，线段树上区间的值。最后终点的值即为答案。 代码： #include <cstdio> #include <algorithm> #define lson rt<<1 #define rson rt<<1|1 #define IOS ios::sync_with_...

题目： n个用户上网，有m条网线。每条网线规定只[L,R]区间中的用户能上，且最多同时上v人。问最多能同时几人在线。组数不超过10n，m(1<=n，m<=10000) 做法： 看这个题面，第一时间想到最大流。当然看到数据范围发现有点勉强。（但跑得还挺快）考虑朴素的建图：1、源点s和每个用户建边，流量1；2、每个用户和能连上的网线建边，流量1；3、每条网线和汇点t建边，流量v。但是这样边数就太多了。想想，每条网线都要连R-L+1条边其实是没必要，考虑可以用线段树维护整段区间建边，这样可以减少很多的边。然后用sap跑最大流。 代码： #include <bits/stdc++...

题目： 小a有N个数a1, a2, ..., aN，给出q个询问，每次询问给出区间[L, R]，现在请你找到一个数X，使得1、 2、最大，表示异或操作。 做法： 由于异或位于位之间是不影响的，所以我们可以分别考虑X每个位选0还是选1。若[L,R]区间的数中第i位，0的数量＞1的数量，则X的第i位选1比0优。反之，选0比选1优。所以通过前缀和处理，快速得到[L,R]区间中的数每个位的1的数量，然后每个位贪心选0或1，问题解决。 代码： #include <bits/stdc++.h> #define debug(a) cout << #a ": " << ...

题目： 珂朵莉给了你一个序列，有个子区间，求出她们各自的逆序对个数，然后加起来输出。对于100%的数据，n <=1000000 ,0 <= 序列中每个数 <= 1000000000 做法： 换个角度，题目要我们求的是每个逆序对在多少个子区间内。那么对于一个逆序对，它的贡献就是理解为，任选一个位置，任选一个位置，区间是一个包含逆序对的子区间。序列中第个位置作为第二个数的逆序对，就是在中找多少个比大的数。现在假如我们知道在中比大的数的位置和。那么第个位置作为第二个数的所有逆序对的子区间贡献就等于。这个我们离散化之后用线段树维护。问题就解决了。具体怎么维护的请看代码。PS：这题数...

题目： 小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。输出一个最简分数a/b，表示小A不亏本的概率。若概率为1，则输出1/1，概率为0，则输出0/1。0≤n≤30 做法： n这么小。直接枚举所有情况。定义状态(i,j,k,l)表示金额分别为1、2、3、4元的彩票分别有i、j、k、l张。直接3重循环枚举状态。然后看一下亏不亏本。不亏则加上这种状态的出现次数：。然后所有情况数。答案就是约过的。 ...

题目： n天，第i天有a[i]个教室可以借出。m个订单，第i个订单需要[li,ri]区间内借xi个教室。问到第几个订单无法满足。对于100%的数据，有1≤n, m≤106, 0≤ri, dj≤109, 1≤sj≤tj≤ n。 做法： 每个订单我们都分2步走：1、确定能不能满足；2、完成订单，把教室借出去。第一步我们需要知道当前[li,ri]区间是不是所有数≥xi。我们只需知道[li,ri]区间的最小值即可。第二步把教室借出去，则[li,ri]区间可借出的教室数量都减xi。区间更新操作。所以很明显我们可以用线段树维护区间更新和区间最小值查询来解决这个问题。 代码： #include <...