威风镰鼬

题解

/ 注册

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

题解 | #子串#

思路被这道题坑了，看完题意秒写Kmp，交了之后只过了90%，各种改最后才发现没有考虑ABCDEF的情况。（啊太粗心了）做法：第一层循环是进制数k，递归或者循环+reverse得出字符串s，然后如果kmp得t是s的子串，则直接输出yes结束程序，如果k到16还是没有退出，那么输出no。怕麻烦不想写k...

字符串 kmp

2021-06-16

1 681

题解 | #华华给月月准备礼物#

思路二分答案，如果满足条件的就向右逼近。判断一个答案是否满足条件，只需要对所有木棍求能分的段数之和是否大于等于k就好了。代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int ma...

排序二分

2021-06-16

1 385

题解 | #[NOIP2004]FBI树#

思路题目要求的是后序遍历，我们可以从根结点出发，查找左右子树，达到叶子结点时返回类型flag，然后决定父节点的类型。代码 #include<bits/stdc++.h> using namespace std; int len,n; string s; void f(string...

树二分字符串

2021-06-16

1 497

题解 | #小G有一个大树#

思路题目都没看懂就莫名其妙A了，“如果结点数相同输出编号小的”，是指平衡点的编号吗？下面题解是按照这样理解的。我先讲一下做题思路吧，数据规模很小，1e3，所以可以把每一个节点当作根去找树的最大深度，最大深度最小的第一个节点可以作为平衡点。找到平衡点之后再来一个push_up对他每一个子节点计算树的...

dfs 树图论

2021-06-16

1 703

题解 | #树上子链#

思路对于一个起始点x，最大子链是从x开始或者从x的子节点开始的最大子链。答案是从x作为起始点得到的最大子链的最大值，起点在dfs过程中走一遍就不会超时了。然后就是树形dp的问题啦。坑点:要开ll，同时注意所有点权值都为负数的情况。代码 #include<bits/stdc++.h> ...

dfs 树图论树形dp

2021-06-16

1 481

题解 | #小木乃伊到我家#

思路写一个Dijkstra堆优化的模板供大家参考一下。（码风比较丑，不要介意）代码 #include<bits/stdc++.h> using namespace std; const int maxn=200005,maxm=500005; struct E{ int n...

最短路 dijkstra

2021-06-15

1 445

题解 | #珂朵莉的数列#

思路可以顺便把这道一模一样的题给A掉Luogu P5463 小鱼比可爱（加强版）各位可以做完《逆序数》再过来，我是用归并排序写的。考虑到对于一个逆序对<i,j>，i∈[l,m],j∈[m+1,r]，那么它是所有区间[x,y]，x∈[l,i]，y∈[j,r]中的逆序对，每一次merge计...

树状数组归并排序离散化

2021-06-15

1 555

题解 | #情人节的电灯泡#

思路把n*n的矩阵摊平成一条直线，就可以用线段树的方法解决啦！n<1000，所以展成直线就是1e6的单点修改+区间求和。个人码风问题我全开ll了，第一发因为update写错了爆零（我太菜了）代码 #include<stdio.h> #include<iostream>...

线段树

2021-06-15

2 526

题解 | #[USACO 2009 Oct G]Heat Wave#

思路这道题很开放，spfa能过、Dijkstra能过，普通求法（见代码）也能过。这边供上一个Dijkstra堆优化板子求最短路。坑点：注意优先队列默认是从大到小的，重载运算符要写a.dis>b.dis，别把堆优化做成堆劣化。 Dijkstral代码 #include<bits/stdc...

最短路普及组图论

2021-06-13

1 658

题解 | #Tree Recovery#

思路线段树裸题，区间修改+区间查询，板子如下。需要注意的一个坑点就是读命令的时候不要漏掉换行符。（个人码风习惯把int改成ll，各位还是要注意别爆了）代码 #include<bits/stdc++.h> #define int ll using namespace std; type...

线段树

2021-06-12

2 510