Meul

题解

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1)

/ 注册

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

NC50528

NC50528 题意给你一个长度为n的数组，依次求长度为k的区间中的最小值，最大值为多少。思路单调队列（双端队列）时间复杂度单调队列性质：队列中的元素其对应在原来的列表中的顺序必须是单调递增的。队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以求最小值的做法：维护一个单调队...

单调队列双端队列

2020-03-29

0 640

NC4853C

题意由小写英文字母组成的长度为n的一个字符串，求不相同的长度为k的子串的数量对1e9+7取模。思路正难则反正难则反，我们求所有不同的子串，不如把所有子串的数量求出来再减掉所以相同的子串数量。若不去重求所有长度为k的子串的数量，则可由推出到第个数为止长度为的子串数量。不难理解,代表的是到...

DP

2020-03-28

4 809

NC15553

NC15553 题意给你n个数，选2个长度为k的连续区间，求他们加起来的和最大为多少？思路前缀和预处理，然后利用前缀和计算k个数的最大数为多少，然后预处理从左边遍历到i为止最大的区间长度为k的和为多少，从右边遍历到i为止最大的区间长度为k的和为多少。扫一遍要选的第一个区间，扫的过程如果左右还有...

2020-03-27

28 905

NC13230

NC13230 题意输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。需要求出所有可能...

区间DP

2020-03-26

1 780

NC50439

NC50439 题意有n个士兵，每个士兵战斗力为v[i]，添加这个士兵则上场的总士兵数量要小于s[i]，求最高战斗力？n(1≤n≤10^5)v,s(1≤v≤10^9,1≤s≤n) 思路贪心+优先队列或multiset一开始想到01背包变形，如果按照这个思路去解，会发现随着s[i]的变化（即背包的...

multiset 贪心优先队列

2020-03-26

0 687