LXNHB

题解

c++基础(2) 三分法(1) 二分法(2) 操作系统(7) 算法(2)

/ 注册

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

题解 | #maze# 来自专栏

展示一下我缝缝补补的艰难过程吧，刚开始没有考虑到一个点可以有多个传送门的情况，然后一直33.3%通过率，发现以后改成三维vector数组来存传送门的终点和起点。发现还是WA，网上查了优先队列的资料发现，他的排序方式和sort不一样，sort想要升序排列，需要step<a.step;,但是**优...

C++ 广度优先搜索堆(优先队列) 最短路

2023-11-30

0 316

题解 | #「土」秘法地震# 来自专栏

开始的时候被数据输入给坑了，01矩阵输入的原来是字符。然后可以递推的求出每一个区间范围内的城市的前缀和，然后再求k* k大小区间里的区间和就ok了。求区间和怎么求呢？ #include<bits/stdc++.h> using namespace std; int n,m,k; co...

C++ 前缀和枚举

2023-11-30

0 284

题解 | #八数码# 来自专栏

emmm，其实也不算很难的思路，就是用mp去重并记录走过的路径，就ok了这道题，只需要一个记录路径的mp就行了，map多了会爆内存（别问我是怎么知道的qaq），对了，还有就是二维一维坐标相互转换的方法，最顶上三个函数就是了。 #include<bits/stdc++.h> using n...

C++ 广度优先搜索

2023-11-29

0 303

题解 | #[USACO 2007 Jan S]Protecting the Flowers# 来自专栏

一道简单的套路题，假设有两头牛a，b，这两头牛交换位置不影响前面的情况和后面的情况，因为无论怎么交换，他们的时间消耗总和都是一样的，可以推导出：当满足ta/da<=tb/db时，a牛在前的情况更优，所以按上述推导的公式从小到大排序，n处的结果就是最后答案。看这个题的数据比较大，又需要乘法，所以...

C++ 贪心前缀和

2023-11-29

0 303

题解 | #迷宫# 来自专栏

两种方法思路：将门设置为不可通过，然后计算从起点到终点的直接路径；计算起点到钥匙+钥匙到门+门到终点的路径之和，比较他们两个哪一个更小，如果比较结果等于0x3f3f3f3f的话，说明终点被墙围住了，不可能到达。两个计算模拟了尝试直接到达终点，以及拿钥匙再到终点的这两个过程。如果门挡住去路，那么最短...

C++ 广度优先搜索模拟

2023-11-29

0 389

题解 | #送外卖# 来自专栏

思路：深度代表到达的小区编号，每一个小区都有走a，走b两种选择，走a一定先于走b，因为要确保输出的是最小字典序，在搜索的过程中，如果搜索到了一个曾经访问过的小区，那么一定就陷入了死循环，flag标记为1,为了模拟进入死循环的情况，如果在返回的过程中发现有一个小区曾经访问过，那么当前状态的字符串一定是...

C++ 深度优先搜索

2023-11-28

0 339

题解 | #[NOIP2012]国王的游戏# 来自专栏

首先来看怎么确定高精度的位数，最多有1000各大臣，每个大臣左手数字最大为10000，所以相乘的最差结果就是10^4000，也就是至多是一个4000位的数（大臣手中数字不包括10000）。然后就是基本的高精度乘法和高精度除低精度的除法。 #include<bits/stdc++.h> u...

C++ 贪心数学

2023-11-27

2 370

题解 | #活动安排# 来自专栏

本题可以转化成最多不重叠区间覆盖问题，要想使最多，就要对右区间从小到大排序，然后要对左区间进行特判，找出第一个左边界大于等于上一个区间的右边界的区间作为下一个区间。 #include<bits/stdc++.h> using namespace std; int n; const int...

C++ 贪心

2023-11-27

0 297

题解 | #[HNOI2003]激光炸弹# 来自专栏

一定要注意xx，yy初始化的值，要是r #include<bits/stdc++.h> using namespace std; int n,r; const int M=5005; int a[M][M]; int main(){ cin>>n>>r;...

C++ 动态规划前缀和

2023-11-27

0 278

题解 | #拼数# 来自专栏

这道题不可以直接的用字典序比较 #include<bits/stdc++.h> using namespace std; int n; const int M=25; string a[M]; bool cmp(string a,string b){ return a+b>...

C++ 字符串

2023-11-27

0 220