zzhaire

题解

算法模板(1) 随笔(3)

/ 注册

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

牛可乐的翻转游戏 60%

思路这个题感觉只能枚举所有的翻转模式但是这样明显会超时, 有然后想了想,其实可以只枚举第一行的所有状态然后找到一个不会影响前面行的翻转模式, 记录最少的翻转次数即可 N * M = 100 * 10 , 刚好时间复杂度翻转模式 : 对于上一行, 没有到位的棋子 , 逐个翻转下一行 ,...

C C++ 状态压缩枚举模拟

2025-02-26

0 17

扫雷MINE

思路 N * 2 的矩阵那就尝试枚举第一列的每个格子，有雷或者没有雷，时间复杂度O(2 ^ N) ，这里N = 10000 明显会超时这个题我看了下其他人的题解，一种是用暴力搜索，然后大量的减枝 , 另一种是用递推关系式, 有点像动态规划 1. 暴力搜索减枝版用 a[N]存第一列的...

C C++ 动态规划暴力搜索

2025-02-26

0 16

丢手绢

思路枚举环形数组, 然后找比周长一半大的, 最小的那个, 然后用周长减去这个值, 就是答案 ac代码 #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; ...

C C++ 数组枚举

2025-02-25

0 11

字符串

思路滑动窗口确保窗口里面的值包含26个字母如果不包含, 窗口就往右边伸展如果已经包含, 就尝试左边缩小窗口 ac代码 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; const int i...

C C++ 滑动窗口数组

2025-02-25

0 16

货仓选址

思路找中间点, 奇数则找这个点, 偶数则在中间随便取一个点就行, 或者端点也可以把距离加起来就ok了这个题也是acwing 基础课的模板题 ac 代码 #include <bits/stdc++.h> using namespace std; const int N = 1e5 +...

C C++ 数组

2025-02-25

0 17

二分

思路说是二分然而这个题和二分没有任何的关系可以转换下思路等价的意思, 是根据教练所说的信息, 枚举所有的数字, 找到满足条件最多的那个就行当然不能从 (-inf , +inf ) 枚举, 根据教练所说的, 再这些区间端点枚举就好用map <int ,int > 做...

C C++ 前缀和数组

2025-02-25

0 14

激光炸弹

思路二维前缀和 ,模板题 ac 代码 #include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int N = 5010;//这个N表示点最多的...

C C++ 前缀和

2025-02-25

0 21

中位数图

思路首先找到这个数字 , 然后以这个数字为轴, 左右尝试扩展区间方便起见, 可以把这个数字设置为 0 ,比他大的设置为1 , 比他小的设置成-1 (自己比较也一样的) 然后就可以以这个点为中心, 开始左右区间进行枚举 [-------left------------b----------...

C C++ 数组模拟

2025-02-25

0 14

值周

思路不同于校门外的树 ,这一题要用到差分数组优化(这一部分内容可以看acwing基础模板) 可以先尝试构造差分数组, 然后再还原回来考虑到可能多次取重叠的区间, 最后还原的时候, 需要找到原来那些不被破坏的点,进行统计 ac代码 #include <bits/stdc++.h> ...

C C++ 数组差分前缀和

2025-02-25

0 13

校门外的树

思路 https://ac.nowcoder.com/acm/problem/16649 第一题直接使用暴力即可, 后面几个题需要用到差分数组(值周) ,请看该题题解朴素代码 #include <bits/stdc++.h> using namespace std; const int...

C C++ 数组

2025-02-25

0 13