2024年4月20日
T422088 「LAOI-4」Colors
摘要： /* 手玩数据，会发现，你找不出可以进行超过两次操作的字符串，大胆假设，加上题目里怪异的k <= 10^18，把k限制在2以内 就没了 */ #include <iostream> #include <algorithm> #include <cstring> using namespace std 阅读全文
posted @ 2024-04-20 20:02 blind5883 阅读(6) 评论(0) 推荐(0) 编辑
P10370「LAOI-4」Mex Tower (Hard ver.)
摘要： /* 和上题一样只不过，是换成了检验答案，还是找规律， 自己看看吧awa O(n) 实际上有点卡数据的意思，但是能过，思想也行，除非极限数据不然卡不掉，卡掉了就在卡掉极限数据 */ #include <iostream> #include <algorithm> #include <cstring> 阅读全文
posted @ 2024-04-20 19:59 blind5883 阅读(17) 评论(0) 推荐(0) 编辑
背包(笔记合集)
摘要： 一般代码只是例子，具体使用依据题目来, DP是a56爆大奖在线娱乐思想，代码都以属性为最大值等等为例子 01背包 最基本的背包 简单说就是有n个物品和容量为m的包，求其max/min/方案数等等即属性 一般转移方程为f[i][j]意思为在前i个里容量为j的情况下的要求的属性 (可忽略)一般这里的转移是在f[i][j 阅读全文
posted @ 2024-04-20 10:06 blind5883 阅读(6) 评论(0) 推荐(0) 编辑
2024年4月14日
P3956 [NOIP2017 普及组] 棋盘
摘要： 暴力bfs /* 这题本身不难, 但是a56爆大奖在线娱乐写难了 就是一个bfs, 没了 但是a56爆大奖在线娱乐的写法恰好犯了一个错误 hark数据 3 5 1 1 0 2 1 1 3 1 1 2 2 0 3 3 0 答案是4而a56爆大奖在线娱乐能输出3 0 -1 -1 1 0 -1 1 -1 0 原因是 a56爆大奖在线娱乐先走到了(2, 2)这时候到(3, 2) 阅读全文
posted @ 2024-04-14 15:25 blind5883 阅读(12) 评论(0) 推荐(0) 编辑
2024年3月26日
欧几里得算法/辗转相除法(证明)
摘要： /* "简单的东西, 往往包含深刻的道理" 回头一看, 发现简单的算法, 证明却不是很简单 前置知识 a|b代表a可以整除b d|a && d|b => d|(xa + yb) (a, b)a56爆大奖在线娱乐a, b的公约数 gcd(a, b)a56爆大奖在线娱乐a, b的最大公约数 证明d|a => id=a, d|b => 阅读全文
posted @ 2024-03-26 15:26 blind5883 阅读(6) 评论(0) 推荐(0) 编辑
2024年3月24日
扩展欧几里得(exgcd)通解及其证明
摘要： exgcd求ax + by = gcd(a, b)中x和y的通解(下面简称通解) 新整理的文章在这，可能不全，这是老文章，新文章 /* 什么是通解 a56爆大奖在线娱乐们知道二元一次方程, 是如果只有一个式子, 那么解会有无数个 而通解就是指让a56爆大奖在线娱乐们只找到一个解就可以推出其他所有解的式子 (注意本证明极其复杂, 请直接 阅读全文
posted @ 2024-03-24 21:36 blind5883 阅读(28) 评论(0) 推荐(0) 编辑
2024年2月29日
最短路算法模版集合
摘要： 例题https://www.luogu.com.cn/problem/P1339 朴素dijkstra (邻接表) dijkstra 正确性来自于贪心 也就是st数组内的数(dist) 必须逐渐变大这样才能保证后面的数更新的时候，当前的第三边dist[t]都是最小值 [详见](https://www 阅读全文
posted @ 2024-02-29 10:55 blind5883 阅读(4) 评论(0) 推荐(0) 编辑
2023年11月30日
ST表
摘要： 新的排版 有点时间补一下这玩意吧 首先先说明RMQ是一类问题, 指 区间最大最小值, 而ST表是解解决RMQ问题的一把手术刀 (手术刀, 锋利但不通用) 作用 O(logn)的预处理 O(1)的区间最大值查询 不可以更改区间数值 原理 原理是倍增 a56爆大奖在线娱乐们将设f[i][j]是从i处向外2^j格里面的最大 阅读全文
posted @ 2023-11-30 17:16 blind5883 阅读(23) 评论(0) 推荐(0) 编辑
2023年11月19日
矩阵
摘要： 矩阵 顾名思义就是一个小破方阵 类似这样 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 这就是一个四行四列的矩阵, 矩阵包含三个信息, 长度, 宽度, 数值 数值就是矩阵里每一位上的数值, 通常用一个数值来存 为了方便使用a56爆大奖在线娱乐们常写成结构体形式 定义 struct Mat { int 阅读全文
posted @ 2023-11-19 08:58 blind5883 阅读(16) 评论(0) 推荐(0) 编辑
扩展欧几里得(及其相关证明)
摘要： /* "数学的恐怖qwq" 想了半天终于明白了, 这里尽量通俗的写出来 扩展欧几里得算法有很多版本 这里写两个, 选择喜欢的使用 扩欧可以解决两项未知解, 具体原理来自裴蜀定理 裴蜀定理:设 a,b 是不全为零的整数, 则存在整数 x,y, 使得 ax+by=gcd(a,b). 而扩欧就可以在求出g 阅读全文
posted @ 2023-11-19 08:57 blind5883 阅读(13) 评论(0) 推荐(0) 编辑