Q779的博客

洛谷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$ 的“分数”会增加 $s_2$

2022-05-25 OI

算法字符串

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

2022-05-25 OI

数据结构

等差数列&等比数列小结高一自学的时候瞎总结写的（好吧我现在还是高一 2022.5.7）感觉丢在文件夹里吃灰没啥用，就放上来了一、等差数列等差数列通项公式 a_n = a_1+(n-1)d$S_n$ 表示等差数列 $\{a_n

2022-05-25 OI

数学

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

2022-05-25 OI

数学数据结构

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

2022-05-25 OI

数学计算复杂性理论

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

2022-05-14 OI

算法图论 DP 数据结构

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

2022-05-13 OI

算法 DP 字符串

[计算几何] 使用叉积计算直线交点 upd.本文写于远古时期，有空再来修改。已知直线 $AB$ 和 $CD$ ，其交点为 $P$ ，求 $P$ 的坐标。计算几何中一般存储向量 $\mathbf{p},\mathbf{v}$ 表示起点

2022-04-29 OI

数学咕咕计算几何

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

2022-04-28 OI

算法数据结构计算几何

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

2022-04-27 OI

算法数据结构计算几何

洛谷P4159 [SCOI2009] 迷路题解题目链接：P4159 [SCOI2009] 迷路题意：该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $

2022-04-25 OI

算法数学