Q779的博客

洛谷P5656 【模板】二元一次不定方程 (exgcd) 题解题目链接：P5656 【模板】二元一次不定方程 (exgcd) 题意：给定不定方程 \[ ax+by=c \] 若该方程无整数解，输出 \(-1\)。若该方程有整数解，且有

2022-05-25 OI

算法数学

洛谷P5851 [USACO19DEC]Greedy Pie Eaters P 题解题目链接：P5851 [USACO19DEC]Greedy Pie Eaters P 题意： Farmer John 有 \(M\) 头奶牛，为了方便，

2022-05-25 OI

算法 DP

洛谷P6216 回文匹配题解题目链接：P6216 回文匹配题意：对于一对字符串 \((s_1,s_2)\)，若 \(s_1\) 的长度为奇数的子串 \((l,r)\) 满足 \((l,r)\) 是回文的，那么 \(s_1\) 的“分

2022-05-25 OI

算法字符串

洛谷P6327 区间加区间sin和题解题目链接：洛谷P6327 区间加区间sin和题解题意：维护一个数据结构，支持区间加 \(v\) 询问区间 \(\sum\limits_{i=1}^{r}\sin a_i\) 注意到 \

2022-05-25 OI

数据结构

等差数列&等比数列小结高一自学的时候瞎总结写的（好吧我现在还是高一 2022.5.7）感觉丢在文件夹里吃灰没啥用，就放上来了欢迎各位指出我的错误（我数学真的烂 \(😓\) 等差数列等差数列通项公式 \[ a_n = a_

2022-05-25 OI

数学

线段树空间开4倍的原因如果证明有错欢迎指出。对于长为 \(n\) 的序列，显然以其构建的线段树有 \(n\) 个叶子节点此时线段树的高度为 \(k=\left\lceil{\log_2 n}\right\rceil+1\) （第一层的

2022-05-25 OI

数学数据结构

主定理证明先不写将一个规模为 \(n\) 的问题，通过分治得到 \(a\) 个规模为 \(n/b\) 的子问题，每个递归带来的额外计算为 \(f(n)\) ，则有 \[ T(n)=aT(n/b)+f(n) \] 其中 \(a,b\) 为

2022-05-25 OI

数学计算复杂性理论

杂题选做[2] 今天加大了难度 \(🤤\) ，但是q779太菜了一些q779感觉较难的题会单独写题解（逃一些收获：求最小环要先给图赋值 INF ，而且 INF 不能开 0x3f3f3f3f3f3f3f3f ，会爆 long lo

2022-05-14 OI

算法图论 DP 数据结构

杂题选做[1] 第一次发这种类型文章好吧，其实是我刷题太少了，所以开始补了 \(😅\) 一些收获：（q779脑回路清奇，所以会想出很多乱七八糟的） DP有个无后效性：某阶段的状态一旦确定，则此后过程的决策不再受此前各种状态及决策的影

2022-05-13 OI

算法 DP 字符串

[计算几何] 使用叉积计算直线交点已知直线 \(AB\) 和 \(CD\) ，其交点为 \(P\) ，求 \(P\) 的坐标。计算几何中一般存储向量 \(\vec{p},\vec{v}\) 表示起点的向量表示和方向向量例如直线

2022-04-29 OI

数学计算几何

半平面交的交集问题&POJ2451 Uyuw's Concert 题解前言初学半平面交，就遇到了这样巨大的坑，也是挺无语... 判断交集为空的情况 poj2451 Uyuw's Concert Description Pri

2022-04-28 OI

算法数据结构计算几何

UVA12307 Smallest Enclosing Rectangle 题解 upd.20220429 由于q779太菜，导致代码出了点锅，已经重新修改题目链接：UVA12307 Smallest Enclosing Rectangl

2022-04-27 OI

算法数据结构计算几何