https://ac.nowcoder.com/acm/problem/50940 题意: 多次操作，每次增加一个数字，求数字个数为奇数时的区间中位数 解法： 平衡树模板题。 还能删除数字，求前驱后继排名 代码： #include <bits/stdc++.h> #define ll long long #define sc scanf #define pr printf using namespace ...

https://ac.nowcoder.com/acm/problem/13249 题意: 给一棵树，每个点有一个值 k[i]，表示取这个点的话可以将这个点到根节点的所有点里，例句这个点距离小于 k[i] 的点变成黑色，求所有点都变成黑色最少取几个点。 解法： 贪心，从根节点向上遍历，如果这个结点的值等于0，那么我们取这个点，反之，不取这个点 所以维护一个数组 a，表示还能取的点的个数，然后遍历的同时维护一下即可。 注意可能存在取已经被染成黑色的结点，比如 贪心的话，首先取 4 号点...

https://ac.nowcoder.com/acm/problem/13886 题意: 给一棵树，保证树的结点个数是偶数，定义点对的价值是他们的距离，求将这棵树分成 n/2 个点对之后，这些点对的最小价值。 解法： 贪心的考虑，我们希望使得一颗树内的点两两组合，这样代价会最小，如果这棵树的结点个数是偶数个的话，我们将他在树内的所有结点两两结合。否则，为了代价最小，我们选择子树的根节点向子树外连边，其他的偶数个结点连边，这样代价会最小。 所以答案就是所有奇数个数节点的子树的根节点到他爸爸的距离。就和树剖的dfs1一样，先求出子树的大小，...

A、大吉大利 考虑二进制的每一位，只有两位同时为1的数字取与操作，才会对答案贡献，直接枚举即可。（没乘 1LL WA一发） #include <bits/stdc++.h> #define ll long long #define sc scanf #define pr printf using namespace std; const int MAXN = 2e5 + 5; int a[64]; int...

题意： 给一个长度为 1e6 的串，多次判断一个串是否是这个串的子串 做法： 显然直接暴力会超时，我们可以考虑在主串中判断子串的过程，实际上就是在主串当前位置之后找到一个等于子串当前位置的字符，这一过程显然是可以预处理的，所以我们预处理从每个位置开始，在他后面的离他最近的各个字母的位置，这样每次查询的时候，知找子串在主串中下一个匹配的位置，同时向后移一位即可，主串中没有子串匹配的位置，那么输出No，否则Yes，所以对于每次询问只需要查询子串的长度次，时间复杂度  代码: #include <bits/stdc++.h> #includ...

题目链接： https://ac.nowcoder.com/acm/problem/50528 题意： 给 n, k，n 个数字，求所有长度为 k 的区间的最小值和最大值 做法： 单调队列，考虑维护一个单调递增/减的队列，并用滑动窗口的方法使得队列的首尾位置相差<=k，这样每次队首的位置都是长度为 k 的区间的最大/小值 代码： #include <bits/stdc++.h> #define ll long long #define sc scanf #define&nbsp...

rt

题目链接： https://ac.nowcoder.com/acm/problem/15553 题意： 有 n 个数字，你可以选择两段长度为 k 的连续的区间，并且这两个区间不能重叠，每个区间的价值等于区间中 k 个数字的和，问两个区间加起来的最大价值。 题解： 考虑只取一段的情况，滑动窗口统计一下易每个点作为终点的区间价值，然后取最大值就可以了 那么我们接着来考虑取两段的情况，假设我们已经取了一段  以 i 结束的长度为 k 的区间，为了让两段区间不重叠，我们还可以取所有结尾  满足 ，因为我们会遍历每个位置作为&n...

题目链接： https://ac.nowcoder.com/acm/problem/13230 题意： 给你两个字符串，把他们拼成一个字符串，并且A，B字符串中字符的的相对位置不变 定义字符串的价值为他的最长回文子串的长度，求拼成的字符串的最大价值 题解： 考虑区间 dp，这里我们假设第一个字符串是 ，第二个字符串是  设 表示取第一个字符串的  和第二个字符串的   能否构成回文串。 并且这个状态是可以转移的，  如果第一个字符串的&nbs...

题目链接： https://ac.nowcoder.com/acm/contest/1080/C 题意： 有 n 个士兵，每个士兵有两个值 v[i], s[i]，分别表示第 i 个士兵的战斗力 v[i] 和他的限制人数 s[i] 限制人数的意思是，如果选择这个士兵 k，那么选择的人数不能超过 s[k] 求选择若干个士兵的最大战斗力。 解法： 首先考虑为了使若干个士兵的最大战斗力最大，我们肯定希望人数尽量多，并且他们的战斗力尽量高。 所以我们首先将士兵按照限制人数 s[i] 从大到小排序，为了使人数最多，我们从左往右取士兵，考虑一下边界情况，由于士...

https://codeforces.com/contest/1326 A - Bad Ugly Numbers 输出n位数，使得这个数字不能被它含有的单个数字整除 特判掉1，直接输出233-- || 277-- 就可以了，比赛的时候**输出了一个 288--，然后整了半天。 #include <bits/stdc++.h> #define ll long long #define sc scanf #define pr printf using namespace&n...

https://codeforces.com/contest/1327 A - Sum of Odd Integers 将数字 n 分成 k 个互不相等的奇数，首先 n 和 k 对 2 取模要相等，不然不可能分成 k 个奇数，其次考虑 k 个不同的奇数能组成的最小的数字是否大于等于 n 即可 #include <bits/stdc++.h> #define ll long long #define sc scanf #define pr printf using namesp...

https://ac.nowcoder.com/acm/contest/4784 A、膜法匹配 状压枚举行，复杂度 过了，过的有点莫名其妙。还跑得贼快 15ms https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43198784 B、阶乘 枚举质因子 p，求出那个质因子的个数之后。通过二分来check 个数是否足够就可以了。 考虑check的时候，（实际上就是某场div2的C），二分质因子 p 的倍数，假设我们现在选择 p*mid，我们不考虑每个数字含有的 p 的个数...

https://blog.nowcoder.net/n/066d16beb8184993ae08ce476a668143