题外话: 这题开始并没有什么思路,第二天参考并学习了雨神的思路和写法。感谢雨神大大和清楚姐^-^           题意: 给出n个点和m条边的无向图,有一些边被‘0’或者‘1’染色了. 问你:给没有染色的边染色,使得一个环的异或值为0.求这样满足条件的环有多少种染色方案。         &n...

本弱由于把题目看错，k和m看反了，导致样例一直推不出，还有怀疑题目错误的**行为。 先说下题目意思，给出一个A数组，问所有区间长度大于等于k中，取第k大的数，然后放进B数组中，最后在B数组中在求第m大的数。 分析: 首先暴力去做，1e5的数据量那是妥妥的T了，我们可以先对答案进行二分，然后反向去满足题目的要求。 假设，我们二分出来一个答案为x，那么我们用取尺的思想去得出，我们可以这么想，我们已知了x，我们要从A数组中得到第k大数大于等于x的区间个数，如果区间个数大于了m，说明大于x数太多了，二分出来的x偏小，往后走，否则就往前走。 如何找第k大数大于等于x的区间个数呢，首先从1开始到n，如果...

首先感谢 PDSU----18计一-----周宁 ，我是看了这位大佬的解题，然后获取了一些思路。 题目意思： 第i个糖糖会有bi的能力值，然后他父亲能够在第i秒把1-i位置的b能力值都加1. 第i个糖糖在第i秒能干掉前面比他能力值小的人,并且是不用小组的，同一小组是不能干的。 小组最多就2组。 思路：首先我们需要先预处理父亲在每个时间点，对整体答案的影响。先计算算出来！ 样例给出的是 bi:3 2 3 1 经过4秒钟之后的结果是 6 4 5 2 然后我们就发现，很显然，3号能攻击2号，因为5>4 并且2号和3号不在同一组 这样的话，我们从后往前就很好处理了 复杂度也降为O（n） ...

题意: 给出若干个木棍长度，你可以对每个木棍进行切割。 比如 有5个木棍，长度分别是4 4 4 5 3 你可以一次切长度为2的，那么4能切2刀，5能切2刀，3只能切一刀。总数加起来ans=2+2+2+2+1=9 题目问的就是一次切w刀，能使的ans>K.(K由题目给出),算出max(w) 数据范围： n=2e5 木棍最大长度1e9 很显然这是一道二分的题目，二分一次切W刀，其实我们可以发现，最大切的次数应该是最大木棍长度，因为大于最大木棍长度没法切了嘛。 所以我们最大二分的区间是[1-1e9] 由于题目要最大值，我们只需要当ans>K的时候，记录最大值即可，注意二分的右边界...

题意:给出一个长度为n的“01”串，问:统计所有01串的逆序对总数 分析： 首先对于逆序对，满足 设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。 只有当出现 1 0 这种样子串，才会对结果造成影响，所以先从n个中选出2个。 剩下n-2个数就有2^(n-2)种情况，也就是这几种情况会有贡献。 所以ans=C(n,2)*2^(n-2) 细节的话就是取mod，不要漏取mod，很容易炸 下面给出2中写法，一种是常规求组合数，用逆元+费小马定理。因为题目比较特殊，上面的ans可以化简成ans=（n-1）n2^(n-3) 所以第二种没必要用逆元 第一种： ...

题意:树中长度路径为偶数的路径数，不能重复 分析： 首先 树中点x到点y的距离 =dep[x]+dep[y]-2*dep[LCA(x,y)] 首先可以发现，2*dep[LCA(x,y)]对奇偶性无影响那么就剩下dep[x]和dep[y] 所以我们只需要求出深度为奇数的个数和偶数的个数 然后奇偶性相同的两两组合就是一种情况 深度为奇数个数：a深度为偶数个数：b 答案=a(a-1)/2+b(b-1)/2 code #include <iostream> #include <algorithm> #include <cstdio> #include <c...

题目意思:给出一个无向图,n个顶点,n-1条边。每条边有权值w,表示流量。 流量:本来我实在没理解题目样例的解释,后来问了一位大佬的解,秒懂了.其实边权可以理解成水管的粗细,水能流多少。 比如1->4-3 首先1->4可以通过13的水,由于4->3水管只有5的大小,所以1-4-3只能流出5.再比如1->4->5 之前1->4->3 已经流出了5 那么1->4->5 剩下还有8,粗细为10的可以全部通过,所以1->4->5流出是8. 题目要求的是,以某个点为根,计算根到所有叶子节点的流量和最后再取最大值 好了题意应该理解了。...

链接：https://ac.nowcoder.com/acm/problem/201400 题意: 给出连通图，由n个点和n-1条边构成，在树上选择一个结点作为根，使得以这个结点为根的所有结点的深度和最小。默认根的深度为0 样例：41 21 31 4 很显然以1为根,depth=1+1+1=3 是最小的如图所示： 现在我们要开始换根了！ 遍历1这个结点的儿子2，3，4 我们以3这个结点为例 换好根的结果如下图所示: 设 f[u]表示以u为根节点,所有点深度和设 dep[N];//dep[u]表示节点u的深度设 cnt[N];//cnt[u]表示节点u下的儿子个数,包含它本身 f[v]=f...

把n个城市分成n/2对，这样n/2对城市之间的长度之和最小。 保证n是均分 样例一：我们最小的分法是1-2,2-3，答案是5+6=11 其他分法均比这个要大 样例二： 我们选择的是1-3,2-4,5-6 合计5+(3+9)+(10+4)=31 我可以发现，选择2个城市，尽可能要不重复，如果出现交叉重复的，那么不能保证最小了，当某个节点x的子树大小为奇数的时候，我们需要加上节点x和父节点的贡献。在dfs到叶子节点的时候，返回上来，判断下该节点子树大小是不是奇数，是奇数加上其贡献即可。 代码： #include <bits/stdc++.h> using namespace st...

题意:给出n道题的分数，给出一个k，要求2个不连续的长度为k的区间分数要最大。 这是一道比较好的前缀和+dp的题目。 由于只存在2个区间，dp1【i】表示i这个位置前面的最大值 dp2【i】表示i这个位置后面的最大值 我们只需要维护这2个dp数组即可，答案就是2个dp数组相加取max 区间为k的和用前缀和来处理 注意开long long #include <bits/stdc++.h> #define INF 0x7f using namespace std; typedef long long ll; const int N=200000+100; ll t; ll ...

题意就是，给出一个字符串S，接着会有n组查询，每组查询会有一个字符串s2，问你这个字符串是不是包含在S中。这里的包含指的是，顺序不改变就行，不一定要紧挨着，一开始我看错了题目，直接上kmp，写了一半发现不行。 这题如果我们暴力去找，我们会发现，中间很多过程都是浪费的，比如S="acccccccccccccccccccccccccca",如果我们要去判断s2="aa" 这个字符串在不在S中，中间这么多c都是无效比较。 那么其实如果能一步知道下一个字符的位置，那该多好，类似于kmp算法的next指针跳跃。这是一个质的飞跃压。 所以我们就可以预处理出一个二维数组 next[i][j] 表示第i个...

这题滑动窗口，首先我那道题，发现是个区间最大值和最小值。很显然，可以用线段树和树状数组或者ST表去强行区间查询。 很不幸，牛客把内存卡的死死的，因为这题我在POJ 2823上做过，那里内存不严格，所以我线段树一发就过了。 这里线段树只能拿70f分。 滑动窗口是个经典的单调队列的题目，本题要求最大值和最小值，是维护2个单调队列，一个单调递减队列，队列头是保证对大值，一个是单调递增队列，保证队头最小值。 那么，我们如何去维护他呢？？ 这里我们以单调递减队列为例。 首先我们要知道，每次算区间的时候，整个区间k相当于移动了一格。那么我们没必要重新去计算。 我们每次去计算的时候，先判断下，队列顶的元素是...