威风镰鼬

分类

题解(153)

/ 注册

全部文章（共151篇）

题解 | #滑动窗口#

思路应该是单调队列的板子题吧。我用的是双向队列deque（可能会比较慢）。原理很简单，对于需要输出大的那个数的队列，比较最后的元素是否比新加入的数小，是的话就弹出最后的元素，重复此操作，最终得到一个单调递增的队列。如果队首的元素滑出窗口了，那么直接pop掉，对另外一个队列也是同理。代码 #inc...

deque 队列

2021-07-06

1 529

题解 | #道路铺设#

思路贪心可过，首先我们要把第一个坑填上，如果下一坑比较浅，那么我们肯定会顺便把它也填上，如果比较深的话，需要填的深度就减去了前面坑的深度。代码 #include<bits/stdc++.h> using namespace std; int main(){ int n,a[...

dfs 普及组贪心 NOIP

2021-07-06

6 379

题解 | #xinjun与阴阳师#

思路对于每个选择的点，其周围的点都是不能选的，我们从根结点出发深搜+DP，就能求出答案了。可以参考没有上司的舞会，这道题就是退化版。代码 #include<bits/stdc++.h> using namespace std; const int maxn=500005; str...

dfs 树形dp 搜索动态规划 2星

2021-07-06

0 443

题解 | #xinjun与阴阳师#

思路这是一个分组背包的模板题，套一下下面的板吧！for 所有的组 ----for k=体力 k>0 -------- for 这个组的操作 ------------ dp递推式代码 #include<bits/stdc++.h> using...

分组背包普及组背包动态规划 dp

2021-06-30

0 512

题解 | #[USACO 2009 Ope S]Cow Line#

思路可以使用vector，也可以使用双向队列（deque）去做，幸好数据能过D操作，不然就要手打了。代码 #include<bits/stdc++.h> #define int ll using namespace std; typedef long long ll; deque&l...

deque 普及组队列

2021-06-30

1 437

题解 | #新建 Microsoft Office Word 文档#

思路暴力能过，只不过新加入文档编号cnt不能每次都从1数起，而是要从min（cnt++,x）数起（x为删除文档的最小编号）我最终的做法用了优先队列，如果前面的编号被清除了，就往里面加（空间是够用的）。虽然有点多此一举，但事实证明确实会快一点，下面贴两份代码。优先队列代码 #include<...

优先队列

2021-06-24

1 524

题解 | #[NOIP1998]拼数#

思路这道题数据范围很小，可以直接给字符串排序，大的在前小的在后，然后直接输出就好了。注意如果用strcmp进行字符串大小比较的话，“123”会在"12"之后，所以正确方法应该是s1+s2>s2+s1。代码 #include<bits/stdc++.h> us...

字符串

2021-06-24

5 627

题解 | #[NOIP2011]铺地毯#

思路感觉是入门题，没用到算法。我们从下往上叠地毯，那么我们从上往下数第一个覆盖这个坐标的地毯的编号就是答案了。如果没有找到就输出-1；代码 #include<bits/stdc++.h> using namespace std; struct X{ int a,b,g,k;...

普及组

2021-06-24

3 630

题解 | #数学考试#

思路用前缀和去处理[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]的和。重点是这两个区间不相交，我们如果去枚举两个区间的位置肯定会超时的。那么我们可以考虑一个指针从k出发到n-k，移动过程中记录左边区间的最大值，（可能不变）同时我们右边区间是不断变化的，两者...

dp 前缀和

2021-06-24

1 442

题解 | #单词查找树#

思路正好练习一下Trie的板子，用二维数组去装，son[i][j]表示编号i第j个儿子的编号。因为有无字符的根节点，所以答案是从1开始的，然后往下添加新结点，答案就是最大节点的编号。代码 #include<bits/stdc++.h> using namespace std; in...

字符串 Trie

2021-06-24

3 487