Q779’s Blog

洛谷P6216 回文匹配 题解 题目链接：P6216 回文匹配 题意：对于一对字符串 \((s_1,s_2)\)，若 \(s_1\) 的长度为奇数的子串 \((l,r)\) 满足 \((l,r)\) 是回文的，那么 \(s_1\) 的“分数”会增加 \(s_2\) 在 \((l,r)\) 中出现的次数。 现在给出一对 \((s_1,s_2)\)，请计算出 \(s_1\) 的“分数”。 答案对 \(2 ^ {32}\) 取模。 容易发现这就是个Manacher+KMP Manacher用于找出奇回文串，KMP用于找出 \(s_2\) 在 \((l,r)\) 中的出现位置 难点在于如何计算这个次数 对于每个极大回文串（长度小于 \(|s_2|\) 的不考虑） 它一定包含了在同一回文中心的更小的回文串 如abbba还包含了bbb,b 如果暴力去求解，时间复杂度为 \(O(n^2)\) 于是想到前缀和来加快运算 我们可以在匹配成功时将 \(s_2\) 左端点位置标记为 \(1\) 考虑一个回文串，x为任意字符 str:xxxxxxx pos:1234567 它对答案的贡献为sum_6...

洛谷P6327 区间加区间sin和 题解 题目链接：洛谷P6327 区间加区间sin和 题解 题意：维护一个数据结构，支持 区间加 \(v\) 询问区间 \(\sum\limits_{i=1}^{r}\sin a_i\) 注意到 \[ \begin{aligned} \sin(a+x)&=\sin a\cos x+\cos a \sin x\\ \cos(a+x)&=\cos a\cos x-\sin a \sin x \end{aligned} \] 直接维护即可两个量即可 注意点： 更新的时候拿之前更新过的sin去更新cos，爆零。 不开long long，爆零。 不下传标记，爆零。 可以适当卡卡常（逃 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e5+15) #define ls(at) (at<<1) #define rs(at) ...

等差数列&等比数列小结 高一自学的时候瞎总结写的（好吧我现在还是高一 2022.5.7） 感觉丢在文件夹里吃灰没啥用，就放上来了 一、等差数列 等差数列通项公式 \[ a_n = a_1+(n-1)d \] \(S_n\) 表示等差数列 \(\{a_n\}\) 的 前 \(n\) 项和 \[ \begin{aligned} S_n &= \sum\limits_{i=1}^{n}a_n\\&=na_1+\dfrac{n(n-1)}{2}d\\&=\dfrac{d}{2}n^2+\left(a_1-\dfrac{d}{2}\right)n \end{aligned} \] 易知 \[ \begin{aligned} S_n&=\dfrac{n(a_1+a_n)}{2}\\&=\dfrac{n(a_m+a_{n-m+1})}{2} \end{aligned} \] \[ S_{2n-1}=(2n-1)a_n \\S_{2n}=n(a_n+a_{n+1}) \] \(\{a_n\}\) 为等差数列当且仅当 \[ S_n=An^2+Bn+...

线段树空间开4倍的原因 如果证明有错欢迎指出。 对于长为 \(n\) 的序列，显然以其构建的线段树有 \(n\) 个叶子节点 此时线段树的高度为 \(k=\left\lceil{\log_2 n}\right\rceil+1\) （第一层的高度为 \(1\) ） 通过等比数列求和公式 \[ \begin{aligned} S_n= \begin{cases} na_1,&q=1 \\\\ \dfrac{a_1\left(1-q^n\right)}{1-q} = \dfrac{a_1-a_nq}{1-q} ,&q\ne 1 \end{cases} \end{aligned} \] 可知 至多有 \(\dfrac{1\times(1-2^k)}{1-2} = 2^k-1\) 个结点 即有 \(2^{\left\lceil{\log_2 n}\right\rceil+1}-1\) 个结点 根据 \[ \begin{aligned} &\left\lceil{x}\right\rceil- \left\lfloor{x}\right\rfloor=\begin{c...

主定理 证明先不写 将一个规模为 \(n\) 的问题，通过分治得到 \(a\) 个规模为 \(n/b\) 的子问题，每个递归带来的额外计算为 \(f(n)\) ，则有 \[ T(n)=aT(n/b)+f(n) \] 其中 \(a,b\) 为常数， \(n\in \mathbb{N}^*,a\ge 1,b > 1,n/b\) 解释为 \(\left\lfloor{\dfrac{n}{b}}\right\rfloor\) 或 \(\left\lceil\dfrac{n}{b}\right\rceil\) 若 \(\exists \epsilon > 0\) 使得 \(f(n)=O(n^{\log_b{a}-\epsilon})\)，则 \(T(n)=\Theta(n^{\log_ba})\) 若 \(\exists \epsilon \ge 0\) 使得 \(f(n)=\Theta(n^{\log_ba}\log^\epsilon n)\)，则 \(T(n)=\Theta(n^{\log_ba}\log^{\epsilon+1}n)\) 若 \(\exists \eps...

杂题选做[2] 今天加大了难度 \(🤤\) ，但是q779太菜了 一些q779感觉较难的题会单独写题解（逃 一些收获： 求最小环要先给图赋值 INF ，而且 INF 不能开 0x3f3f3f3f3f3f3f3f ，会爆 long long 的 long long的话用 0x1f1f1f1f1f1f1f1f 差不多（逃 然后别忘了判重边 匈牙利叫Hungary（逃 P2738 [USACO4.1]篱笆回路Fence Loops 最小环，建图麻烦，要去个重 题解：link 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x1f1f1f1f1f1f1f1f namespace FastIO { #define gc() readchar() #define pc(a) putchar(a) #define SIZ (int)(1e6+15) char buf1[SIZ],*p1,*p2; char r...

杂题选做[1] 第一次发这种类型文章 好吧，其实是我刷题太少了，所以开始补了 \(😅\) 一些收获：（q779脑回路清奇，所以会想出很多乱七八糟的） DP有个无后效性：某阶段的状态一旦确定，则此后过程的决策不再受此前各种状态及决策的影响 暴力也是可以剪枝的 \(a_n=a_1+(n-1)d\) P1209 [USACO1.3]修理牛棚 Barn Repair 贪心。木板可以随便切，所以每次切间隔最大的。 #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1005) int n,m,a[N],b[N],res; signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("check.in","r",stdin); // freopen("check.out...

[计算几何] 使用叉积计算直线交点 upd.本文写于远古时期，有空再来修改。 已知直线 \(AB\) 和 \(CD\) ，其交点为 \(P\) ， 求 \(P\) 的坐标。 计算几何中一般存储向量 \(\mathbf{p},\mathbf{v}\) 表示起点的向量和方向向量 例如直线 \(AB\) 一般存储为 \(\overset{\longrightarrow}{OA},\overset{\longrightarrow}{AB}\) const double eps=1e-10; struct vct{double x,y;}p[N]; #define pf(x) ((x)*(x)) vct operator+(vct a,vct b){return {a.x+b.x,a.y+b.y};} vct operator-(vct a,vct b){return {a.x-b.x,a.y-b.y};} vct operator*(vct a,double b){retur...

半平面交的交集问题&POJ2451 Uyuw’s Concert 题解 前言 初学半平面交，就遇到了这样巨大的坑，也是挺无语… 判断交集为空的情况 poj2451 Uyuw’s Concert Description Prince Remmarguts solved the CHESS puzzle successfully. As an award, Uyuw planned to hold a concert in a huge piazza named after its great designer Ihsnayish. The piazza in UDF - United Delta of Freedom’s downtown was a square of [0, 10000] * [0, 10000]. Some basket chairs had been standing there for years, but in a terrible mess. Look at the following graph. In this case we hav...

UVA12307 Smallest Enclosing Rectangle 题解 upd.20220429 由于q779太菜，导致代码出了点锅，已经重新修改 题目链接：UVA12307 Smallest Enclosing Rectangle 题意：多组数据，给定平面上的 \(n\) 个点，分别求出周长最小、面积最小的矩形，使得所有的点均被矩形覆盖 数据范围： \(3\le n \le 10^5\) ，\(-10^5 \le x,y \le 10^5\) 看到本题，容易想到 P3187 解法是旋转卡壳 要求的是矩形，因此考虑维护三个点： \(a\) 代表当前枚举直线对面的边 \(b\) 代表当前枚举直线右侧最远的点 \(c\) 代表当前枚举直线左侧最远的点 如下图所示 其中，\(a\) 使用叉积比较，\(b,c\) 则使用点积比较 方便起见，我们称当前的底边长为 \(\text{T}\) （即图中的q[1]到q[2]） 可以发现 \(\text{T = L}+\text{R}-\text{d}\) \(\text{L}\) 表示向量 \(s_i\to c\) 在 \(\te...

洛谷P4159 [SCOI2009] 迷路 题解 题目链接：P4159 [SCOI2009] 迷路 题意：该有向图有 \(n\) 个节点，节点从 \(1\) 至 \(n\) 编号，windy 从节点 \(1\) 出发，他必须恰好在 \(t\) 时刻到达节点 \(n\)。 现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？ 答案对 \(2009\) 取模。 注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。 题目给出了邻接矩阵 首先，根据矩阵乘法的性质，我们可以发现 不考虑题目的限制，当矩阵仅由01构成时 \(M^2\) 的意义就是只通过两条边（此时边权均为 \(1\) ）能到达每个结点的方案数 则此时答案就是 \(M^t\) 可是题目给出的矩阵，至多有 \(10\) 怎么办呢？考虑把它转化新的矩阵（仅有01构成的） 对于初始矩阵的每个节点，把它化为 \(x_i\) 个结点 其中 \(x_i\) 表示出边边权的最大值 如下图 “拆点”操作 可以发现这样的话仍然是满足题意的 为什么呢？因为可以更新答案的那条路径 一定走到了 \(x_i...

洛谷P3829 [SHOI2012]信用卡凸包 题解 题目链接：P3829 [SHOI2012]信用卡凸包 题意： 给定若干个“信用卡”，求其“凸包”周长 这个题其实看上去很不可做，其实很简单 注意到（搬了一张图，来自link，不过这篇题解的代码好像挂了） 显然，由图可知，我们求的所谓凸包 就是信用卡上面那四个点组成的点集的凸包加上一个圆的面积 关于如何理解这个图形的周长恰好包括一个圆 大家就想象一只小乌龟从一点开始走，走了一大圈又回到了起点 它旋转的角度正好为 \(2\pi\) 那么这道题就变成数学题了，如何处理这4个点？ 再看图，可以发现这个圆对求凸包真的一点用都没有 直接把那四个点组成的新矩形当作处理对象 然后运用一点初中知识就可以求出来了 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF ((int)0x3f3f3f3f3f3f3f3f) #define inf ((int)0xc0c0c0c0c0c0c0c0) #define N (...