Q779’s Blog

OI模板-数学 注意，本文不同于 OI数学总结-数论 或其他总结类文章 本文倾向于代码实现，只是因为数论的内容与代码联系紧密，并且数论内容较多，因此显得较为相似。 最大公约数 gcd 最大公约数指能够整除多个不全为零的整数的最大正整数 常用性质： \(a\times b = \gcd(a,b) \times \mathrm{lcm}(a,b)\) int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } // 注意这份代码对于(+,-)的情况会求出负数 扩展欧几里德算法(Exgcd) 板子题： P5656 【模板】二元一次不定方程 (exgcd) 若 \(b \ne 0\) ，扩展欧几里得算法求出的可行解必有 \(|x| \le b ,|y| \le a\) 。 int exgcd(int a,int b,int &x,int &y) { int d=a; if(!b)x=1,y=0; else d=exgcd(b,a%b,y,x),y-=a/b*x; ...

OI模板-算法 三分法 板子题：P3382 【模板】三分法 时间复杂度 \(O(-\log \epsilon)\) #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cstdarg> #include <cmath> #include <iomanip> #include <random> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define double long double #define N ((int)(15)) const double eps = 1e-6; int n; double l,r,a[N]; double f(double x) { ...

OI模板-计算几何 二维凸包 Andrew 时间复杂度 \(O(n \log n)\) #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e5+15) int n; struct vct { double x,y; vct operator-(const vct &o)const { return (vct){x-o.x,y-o.y}; } }p[N],ans[N]; int stk[N],top,used[N]; int cmp(vct a,vct b) { return a.x==b.x?a.y<b.y:a.x<b.x; } double cross(vct a,vct b) { return a.x*b.y-a.y*b...

洛谷P2391 白雪皑皑 题解 题目链接：P2391 白雪皑皑 题意： 现在有 \(n\) 片雪花排成一列。 pty 要对雪花进行 \(m\) 次染色操作，第 \(i\) 次染色操作中，把第 \(((i\times p+q)\bmod n)+1\) 片雪花和第 \(((i\times q+p)\bmod n)+1\) 片雪花之间的雪花（包括端点）染成颜色 \(i\)。其中 \(p,q\) 是给定的两个正整数。他想知道最后 \(n\) 片雪花被染成了什么颜色。没有被染色输出 \(0\)。 \(1\leq n\leq 10^6,~1\leq m\leq 10^7\)。 保证 \(1\leq m\times p+q,m\times q+p\leq 2\times 10^9\)。 一句话题意：线性区间推平（区间赋同一个值），全局询问。 我们模拟赛t3，也是我想了几个月结果有原题的东西，不写题解亏大了 考虑倒序处理修改，因为一个位置的值一定由它最后一次被修改的数决定 暴力推平？对于被推平的点，不可以再推了，所以我们要跳过它 这就需要维护每个点右侧的那个未被推平的结点 可以考虑链表或者并...

洛谷P2024 [NOI2001] 食物链 题解 题目链接：P2024 [NOI2001] 食物链 题意：动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。 现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这 N 个动物所构成的食物链关系进行描述： 第一种说法是1 X Y，表示 X 和 Y 是同类。 第二种说法是2 X Y，表示 X 吃 Y 。 此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 当前的话与前面的某些真的话冲突，就是假话 当前的话中 X 或 Y 比 N 大，就是假话 当前的话表示 X 吃 X，就是假话 你的任务是根据给定的 N 和 K 句话，输出假话的总数。 \(1 \le N \le 5\times10^4,~1 \le K \le 10^5\) 考虑种类并查集。 我们维护三个并查集，分别存同类、食物和天敌 这里...

洛谷P1792 [国家集训队]种树 题解 题目链接：P1792 [国家集训队]种树 题意： A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。 园林部门得到指令后，初步规划出 \(n\) 个种树的位置，顺时针编号 \(1\) 到 \(n\)。并且每个位置都有一个美观度 \(A_i\)，如果在这里种树就可以得到这 \(A_i\) 的美观度。但由于 \(A\) 城市土壤肥力欠佳，两棵树决不能种在相邻的位置（\(i\) 号位置和 \(i+1\) 号位置叫相邻位置。值得注意的是 \(1\) 号和 \(n\) 号也算相邻位置）。 最终市政府给园林部门提供了 \(m\) 棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将 \(m\) 棵树苗全部种上，给出无解信息。 \(m\le n \le 2\times 10^5\)，\(-1000\le A_i\le1000\)。 考虑反悔型贪心，维护一个大根堆，先把所有结点加进去 然后每次取出权值最大的点，把它加入答案 如何反悔呢？ 我们再加入一个权值为 \(a_{l_i} + a_{r_i...

洛谷P1016 [NOIP1999 提高组] 旅行家的预算 题解 题目链接：P1016 [NOIP1999 提高组] 旅行家的预算 题意： 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 \(D_1\)、汽车油箱的容量 \(C\)（以升为单位）、每升汽油能行驶的距离 \(D_2\)、出发点每升汽油价格\(P\)和沿途油站数 \(N\)（\(N\) 可以为零），油站 \(i\) 离出发点的距离 \(D_i\)、每升汽油价格 \(P_i\)（\(i=1,2,…,N\)）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。 \(N \le 6\)，其余数字$ $。 经典的反悔型贪心 每次碰到一个加油站，烧掉最便宜的油（从上一个位置到现在位置） 接着退掉比当前加油站贵的油（反悔），然后直接加满当前加油站的油 记得设一个终点站，显然它和起点的距离为 \(d_1\) ，推掉所有多的油 这个油价的维护直接用单调队列维护，这里用deque<node>来搞方便一些 时间复杂度 \(O(n)\)...

洛谷P1631 序列合并 题解 题目链接：P1631 序列合并 题意： 有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到\(N^2\)个和，求这\(N^2\)个和中最小的N个。 对于100%的数据中，满足1<=N<=100000。 维护一个大根堆，初始有 \(N\) 个极大值 贪心地选择较小的 \(A_i\) 和较小的 \(B_i\) 合并 然后有一个简单易懂的剪枝，具体见代码 时间复杂度 \(O(n \log n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> #include <queue> using namespace std; #define...

洛谷P3871 [TJOI2010]中位数 题解 题目链接：P3871 [TJOI2010]中位数 题意： 给定一个由N个元素组成的整数序列，现在有两种操作： 1 add a 在该序列的最后添加一个整数a，组成长度为N + 1的整数序列 2 mid 输出当前序列的中位数 中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个） 例1：1 2 13 14 15 16 中位数为13 例2：1 3 5 7 10 11 17 中位数为7 例3：1 1 1 2 3 中位数为1 对于100%的数据，1 ≤ N ≤ 100,000，0 ≤ M ≤ 10,000 序列中整数的绝对值不超过1,000,000,000，序列中的数可能有重复 考虑维护一个对顶堆，详细见 P1168 然后就是板子题，注意对询问分类讨论 时间复杂度 \(O((n+m) \log (n+m))\) 代码： #include <iostream> #include <string> #include <vector> #include <al...

洛谷P3522 [POI2011]TEM-Temperature 题解 题目链接：P3522 [POI2011]TEM-Temperature 题意： 某国进行了连续 \(n\) ( \(1 \le n \le 1,000,000\)）天的温度测量，测量存在误差，测量结果是第 \(i\) 天温度在 \([l_i,r_i]\) 范围内。 求最长的连续的一段，满足该段内可能温度不降。 不难发现合法区间为 \(\max\{l_i\}>r_{i+1}\) 考虑单调队列维护最大值 注意答案的更新应该用(i-1)-q[st]+1 因为如果有个 \(l_i\) 特别大，把当前维护的合法的 \(l\) 都给pop掉了 计数不应当是从现在的 \(l_i\) 开始，而是最后一个被pop掉的 这样用q[st]正好（我的代码是(l,r]的） 时间复杂度 \(O(n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio>...

洛谷P2422 良好的感觉 题解 题目链接：P2422 良好的感觉 题意： kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 \(A_i\)，\(A_i\) 越大，表示人感觉越舒适。在一段时间 \(\left[i, j\right]\) 内，人的舒适程度定义为 \(\left[i, j\right]\) 中最不舒服的那一天的感受值 \(\times\) \(\left[i, j\right]\)中每一天感受值的和。现在给出 kkk 在连续 \(N\) 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？ 对于 \(100\%\) 的数据，\(1\le N\le 100000\)，\(1\le \texttt{感受值}\le 1000000\)。 题意简化一下就是 找到一个区间，使得区间最小值乘以区间的和最大 考虑每个最小值对区间的贡献 设当前的数为 \(a_i\) ， 它能成为最小值的区间 \([l,r]\) 满足 \(l\in [j+1,i],r\in [i,k-1]\) 其中 \(j\) 是所有 \(a_j <a_i\) 中最大的 \(j\) ，\(k\)...

洛谷P3512 [POI2010]PIL-Pilots 题解 题目链接：P3512 [POI2010]PIL-Pilots 题意：给定 \(n\) 个数，找一个最长区间，使得区间中的最大值减最小值不超过 \(k\) 题面写的太烂了 考虑用两个单调队列分别维护从 \(1\) 到 \(i\) 的最大值和最小值 注意pop()时候的判断，具体见代码 时间复杂度 \(O(n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> using namespace std; // #define int long long // #define INF 0x3f3f3f3f3f3f3f3f #defin...