威风镰鼬

题解

/ 注册

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

题解 | #[NOIP2013]火柴排队#

思路稍微用点群论的知识，我们可以感觉出它要我们求逆序对。于是我们可以先把a和b的数字和离散化结果记录下来，然后用x存储置换后的结果，然后套个归并排序的板子就OK啦。代码 #include<bits/stdc++.h> using namespace std; const int ma...

离散化归并排序 NOIP

2021-08-18

1 464

题解 | #[NOIP2017]棋盘#

思路没啥思考过程，照着题目跑bfs就过了。大概就是跑的时候记格子的花费和是否用过魔法。记录颜色时+1是因为比较方便区分白色。剪枝直接把同一格子花费大的剪掉就行了。正确性的大概考虑：若经过同一格子两次，用魔法的状态肯定是一样的，并且金币只会递增。（不知所云）代码 #include<bits/...

搜索 NOIP 普及组 bfs 最短路

2021-08-06

2 424

题解 | #[NOIP2004]合并果子#

思路贪心正解。用优先队列，每次把最小的两个果子合并了，得到的是最优解。代码 #include<bits/stdc++.h> using namespace std; priority_queue<int,vector<int> , greater<int&g...

贪心 NOIP

2021-07-06

2 516

题解 | #道路铺设#

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

dfs 普及组贪心 NOIP

2021-07-06

6 379

题解 | #道路建设#

思路最小生成树板子题，用Kruskal硬过就行了。算法流程：初始设点在集合A，无连边；将图中的边按照权值从小到大排序，然后从最小的边开始连接（使用并查集）；将边的两端点加入集合B，如果当前边的两个端点不都在集合A，则进行连接；选择m-1条边的时候刚好将m个点连上，此时判断权值之和是否大于c。代码...

最小生成树 Kruskal NOIP

2021-06-12

1 430

题解 | #回文串#

回文串思路这道题我先写了马拉车（不会的可以去学一学，能以O(n)复杂度求最长回文串长度），A了之后看数据范围，发现暴力也是能过的。需要注意点一些细节：（我被坑过的点）马拉车记得在要在字符串前面加多一个字符防止越界。暴力算法不要列举区间再判断是否回文，先列举中心点再求回文长度更快。同时注意字符串长...

回文普及组马拉车 NOIP

2021-06-11

1 526

题解 | #[NOIP2016]回文日期#

[NOIP回文日期] 思路纯模拟题，前面几发没看到范围写错了没过，总的来说还是很简单的。最快的方式是打表，挑出回文日期然后判断每一个回文日期是否在起末日期之间就行了。暴力也是可以过的（估计数据强一点就不一定了），当然要打表就得暴力嘛……如何判断回文？日期是八位整数，使用取模和除法运算就能判断，不建...

回文日期 NOIP

2021-06-10

2 662

题解 | #[NOIP2014]寻找道路#

[NOIP2014]寻找道路思路首先要把一些不满足条件的点剔除掉，然后就是求最短路的事情了。要找不满足条件的点，可以反向建边，然后从终点出发，标记每一个经过的点。那么剩下没有走过的点就可以去掉了。代码 #include<bits/stdc++.h> using namespace ...

最短路提高组图论 NOIP bfs

2021-06-09

1 694

题解 | #[NOIP2001]数的划分#

[NOIP2001]数的划分思路 dfs的简单题，数据很弱，注意每次减的数都比上一次当要大，分的方式就不会重复了；方案数+1的条件是n减k个数后刚好等于零（也可以理解为k个非递减的数之和等于n）代码 #include<bits/stdc++.h> using namespace st...

dfs 普及组搜索 NOIP 2星

2021-06-09

8 643