- 博客(91)
- 收藏
- 关注
RSS订阅
原创 Min_25筛--简明版
强烈推荐链接一.前置技能埃式筛法：标记素数的倍数（线性筛是标记每个数的素数倍数）积性函数性质:(积性函数比如欧拉函数需要条件gcd(a,b)=1，完全积性函数不需要）二.适用范围min2.5筛:质数幂的多项式（完全积性函数）求(杜教筛：可以利用狄利克雷卷积转换为数论函数，方便求前缀和)显然min2.5筛似乎适用更广些时间复杂度： 空间复杂度：...
2019-09-25 20:29:42
267
原创 2019ICPC南昌网络赛-- Enju With math problem（素数间隔与欧拉函数性质）
一.题目及背景与华工院赛一道题很像，那题ME的题解链接题目链接题目已经保证是连续的欧拉函数二.性质①10^9的最大素数间隔为300②积性函数性质，均为素数，三.分析①由于区间只有100<300，可能里面没有素数②先假设有素数，那就是华工那道题的方法，暴力判断p欧拉函数是否=p-1，见上面链接如果全为合数，将其拆分成p*q，q为一个小素数，只...
2019-09-09 20:45:32
294
原创 2019CCPC网络赛HDU6706--huntian oy(杜教筛+GCD性质+欧拉函数性质)
一.前置技能GCD性质（Me的）欧拉函数性质狄利克雷卷积+杜教筛（也是Me的）二.题意及分析题目链接题意：推导：这里直说关键结论，结论更详细推导推荐这篇博客①由GCD性质，②因为gcd=1，这道题a和b没作用了③由欧拉函数性质（hdu3501），左半部分有j与i互素约束，和为n*euler(n)右半部分N>1,不大于...
2019-08-24 14:23:57
310
1
原创 2019HDU多校九6683--Rikka with Geometric Sequence(杜教筛+分块)
参考链接一.前置知识莫比乌斯反演数论分块杜教筛（这里是筛欧拉函数,参见此文二、①--b）二.题意及分析①题意：给出1~n，求其中子序列能组成等比数列的数目②初步分析：设公比为，首项为p，末项为q，都为整数。由于很容易知道q必须要整除a^(k-1)。而这样末项q有种。而对于分母上，每一个a，由开头公比定义，还有一个约束条件，就是必须有一个小于a并与a互质的数...
2019-08-20 23:37:25
349
原创 HRY and mobius 19华工I--莫比乌斯函数性质与杜教筛
杜教筛模板链接华工题目链接万恶之源--bzoj2440 完全平方数 应该是这道题前身。进阶版--【SPOJ】DIVCNT2题意： 给n,k， 求一.核心莫比乌斯函数平方及以上因子=0，无平方因子（即素因子次数最大为1）=，如果都当成1来算，他们前缀和不正是：等价于小于等于n，不含平方因子的个数和二.化简证明：第一种：容斥...
2019-04-27 17:59:17
478
原创 从狄利克雷卷积到杜教筛【模板】
更多思路参考洛谷日报是个好东西more一.狄利克雷卷积①完全积性函数：引入他们因为前缀和好求，第一个为1，第二个为n，第三个为不完全积性函数：②公式：f一般为待求的，比如g一般根据③中三个关系，自己构造的，比如③常用关系：a.b.c.（有上面两个式子得）④例子：见下二.杜教筛 一般n达到1...
2019-04-15 20:44:21
342
原创 莫比乌斯反演入门--化简比较烦
一.莫比乌斯函数特点是，分解的素因子中有平方因子则为0，否则素因子个数奇偶性决定正负1。线性筛大全，含莫比乌斯二.莫比乌斯反演公式用的最多是第二条性质：已知，可得①注意反演的意义：个人拙见是类似反函数把Y=F(x)写成X=F(y)的形式，因为有时F(Y）比F(X)更容易求。为啥引入莫比乌斯函数：实际上消去同类项，比如f(2)出现3次，必然要两项为...
2019-04-09 23:39:41
635
原创 原根和离散对数BSGS求法（高次同余方程）
原根&离散对数一.原根1.定义:（a与m互质）使成立的最小的d(记住原根是a，不是d!)2.原根的性质:一般给出p（有时叫m）1.具有原根的数字仅有以下几种形式:,(p是奇质数)2.一个数的最小原根的大小不超过3.原根个数Φ(Φ(m))个，m为质数则原根个数Φ(m-1）3.求解原根的基本步骤:判断一个数是否有原根。(通过性质1,枚举质数即可) 求得最小...
2019-04-07 00:18:53
802
原创 生成函数/母函数--排列组合的多项式写法
母函数理解（强烈建议）母函数代码一.分类普通型母函数 (1+ax)^n多项式展开 组合问题 指数型母函数 展开式，分母比上面多个n! 排列问题 二.形式理解：①每个括号代表一种物品的取法②*可以类比逻辑与，+代表逻辑或因此(1+x)(1+x^2)可以理解为，从1个质量为...
2019-04-03 23:59:57
1950
原创 HDU 3292 佩尔方程入门+矩阵快速幂--你想解二元二次方程吗？
题意：求x^2-n*y^2=1 按x排序第k大的解。一.原理佩尔方程：X^2-d Y^2=1,d不为完全平方数的整数，有无穷多个解为什么d不能为完全平方数：(x+y)(x-y)=1 x只能取正负1，y取0，就不会有无穷多组解递推式如下：于是构造矩阵：二.具体实现：①search():x1,y1可以暴力解得，因为以x排序,x与...
2019-04-03 23:08:56
531
原创 poj 1061 青蛙的约会 --扩展欧几里得 解二元一次不定方程例题
扩展欧几里得详解（转）解题步骤两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永...
2019-04-03 20:05:24
264
原创 PTA STL string--估值一亿的AI核心代码 --2019天梯赛L1-64
string更详细用法本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：无论用户说什么，首先把对方说的话在一行中原样打印出来； 消除原文中多余空格：把相邻单词间的多个空格换成 1 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉； 把原文中所有大写英文字母变成小写，除了I； 把原文中所有独立的can you、could you对应地换成I can、...
2019-04-01 22:19:43
1341
2
原创 STL常用数据结构应用
各种使用函数还有algorithm可以看别的博客学习，这里重点讲应用。1.vector[]遍历，emplace_back,size,clear sort(v.begin(),v.end()); == end()-1,begin(）应用：特别是要开二维数组，要节省空间的时候而且长度不定的时候特别好用，图中的邻接表就是很好的例子。邻接表中一维数组存储顶点，一维vector存储该...
2018-06-10 16:33:24
658
1
原创 数字图像处理大作业--均值滤波和方框滤波（盒子滤波）python实现
一.均值滤波：图片中一个方块区域（一般为3*3）内，中心点的像素为全部点像素值的平均值。均值滤波就是对于整张图片进行以上操作。我们可以看下图的矩阵进行理解：缺陷：均值滤波本身存在着固有的缺陷，即它不能很好地保护图像细节，在图像去噪的同时也破坏了图像的细节部分，从而使图像变得模糊，不能很好地去除噪声点。原图：对比图：...
2019-12-02 22:18:51
3759
原创 HDU6319--Ascending Rating（单调队列复习）
忘了单调队列，顺便存下模板注意算count的是，各自窗口内最大值更新次数（开始读错题），而且这里应该维护反向递减序列，而正向是不行的比如3 1 2 4，答案应该是2，而维护正向递增单调队列会得出3，因为第一个较大元素可能会丢失。单调队列核心：无脑入队，次优值/出窗口范围出队，保持单调性。用到最长上升子序列的O(nlogn)贪心的思想：（之前博客提过，链接）对于一个...
2019-10-11 14:42:47
169
原创 自然语言处理--MM、RMM算法及Python 复习
注意文本的格式，建议UTF-8防止出现不可见字符导致无法匹配class CSegment: def __init__(self, MaxLen, seg): self.MaxLen = MaxLen # 初始化MaxLen self.seg = seg # 初始化分隔符 # 初始化词典(数据类型为dict) se...
2019-09-30 11:57:06
959
原创 E. Fruit Slicer--计算几何+两圆公切线
https://open.kattis.com/problems/fruitslicer很明显，直线是两圆公切线的时候，经过的圆最多，而n只有100，公切线最多4条，只需要(n^2）暴力枚举两圆公切线，然后再(n)得到公切线经过圆的数目，最后取max即可。复杂度O(n^3)级别#include<cmath>#include<cstdio>#include&l...
2019-09-22 21:12:24
820
1
原创 Codeforces Round #587 (Div. 3)C--White Sheet（矩形交，三种解法）
http://codeforces.com/contest/1216/problem/C题意:白色矩形是否被黑色矩形完全覆盖，是输出NO解法:如果只说对角线没说明是哪条对角线： if(a1.x1>a1.x2)swap(a1.x1,a1.x2); if(a1.y1>a1.y2)swap(a1.y1,a1.y2);if(a2.x1>a2.x2)swap...
2019-09-22 08:48:55
216
原创 2019沈阳网络赛H-Texas hold'em Poker（大模拟）
题目链接-H存每种牌的出现次数，然后从大到小找，用多个ans数组存大小。虽然代码长但是很稳。WA点：①10不能算两个字符，应该拆开考虑②相同时候，多开个数组记录。#include<bits/stdc++.h>using namespace std;int a[100010][14];int sum[100010];string name[10001...
2019-09-14 17:11:55
956
原创 2019华南理工大学“三七互娱杯”程序设计竞赛F HRY and ec-final--素数间隔与欧拉函数
一.背景题目链接补这题，是因为昨天网络赛碰到一道素数间隔的题（非常相似，但是作法有差异）二.重要性质：①10^9的最大素数间隔为300②(p为素数)三.思路这题数据范围是1e9，而且给出区间是300，根据素数间隔规律，区间里必有一个素数，只要看该素数的欧拉函数值是否对应即可，有两种方法：a.按顺序找，直到符合为止（本代码方法）b.找欧拉函数区间里最...
2019-09-09 20:13:58
260
原创 2019南京网络赛B. super_log--欧拉降幂
我对欧拉降幂的理解(19.4.6)原题CodeForces 906D Power Tower 有限幂塔函数模板（此题参考）BZOJ 3884 无限次模板一.题意及分析题意：求log*a(x)>=b，最小x分析：可以看出是单调递增，显然取等号，x最小...
2019-09-03 00:26:19
234
1
原创 2019牛客多校第五场--C generator 2 (BSGS优化)
一.题意题目链接二.分析①手动递推或矩阵快速幂，推出：xn=b + ba + ba^2 + ba^3 + ... + ba^(n - 1) + x0a^n②用等比数列求和公式，然后因为要求n，把a^n单独放出来：③经典的BSGS，原算法复杂度肯定TLE因为有这步：long long m=ceil(sqrt(C))需要用分块的思想，即利用“大...
2019-08-26 21:30:03
208
原创 2019牛客第十场D--Han Xin and His Troops（扩展中国剩余定理（CRT）模板题+大数）
扩展CRT自行百度__int128貌似也可以主要结果会大于1e18,要用到大数，这个大数模板搜了很久才搜到，顺便存下#include<bits/stdc++.h> using namespace std; const int base = 1000000000;const int base_digits = 9; struct bigint { //...
2019-08-17 17:03:50
166
原创 2019牛客多校第九场B-Quadratic equation（二次剩余模板题）
题目链接简单讲下二次剩余，详细讲解可以找篇博客，判断是否有解核心是利用费马小定理，然后构造平方差公式转化成二次剩余做得少，临时搬了个板子（这板子还是有时会RE），没想到这板子少了一句话然后一直莫名WA我们只要化简成X^2%mod=c就可以套模板了，观察到①^2-4*②得到下列式子：解出来x-y再与x+y联立即可，注意在同余方程下除法要用逆元计算即可。#inc...
2019-08-16 00:47:19
171
原创 7月及8月总结
这几场多校打的不好，感觉题目很多很综合很灵活，看似能套板子其实是另一种神奇的算法，有种学了却用不上的无力感。补题同时还不能忘掉英语，毕竟很多少见的算法，国外网站会讲的更详细（比如），光看CSDN还是容易被误导。就比如HDU第五场的Pohlig Hellman算法（当时BSGS超时，因为n是1e18，复杂度是根号p），据说是CTF密码学算法，然鹅赛后百度，鲜有提及这个算法（据说用来算椭圆？...
2019-08-14 17:40:18
190
原创 2019HDU多校第五场1004--Equation（分区间讨论思想）
一.题意：http://acm.hdu.edu.cn/showproblem.php?pid=6627给出所有a[i]，b[i]和c的情况下求x的所有解，无解输出-1；二.分析观察到绝对值函数具有一定单调性及对称性，必有且仅有一个零点，且在零点处正负发生变化。所以我们可以求出每个零点，划分为n+1个区间，先假设x接近负无穷，即去绝对值为-ax-b，判断x是否在区间内...
2019-08-13 18:25:42
126
原创 2019HDU多校1001 Fraction--辗转相除求分数不等式
方法出处：辗转相除求中间值当套路题记录一下吧，有点像扩展欧几里得，但是不完全是。这道是有点新颖，而这场另一道数学题更是没见过，现场大力莽BSGS果然超时T_T（据说CTF中最短路级别的难度？？？）一.思路：bx≡a(mod p)可以转换为：bx-kp = a.因为a的范围是(0,b)，化成，求最小b步骤：1、看两个数字之间是否有整数，如果有，那么取x为之间最小的整数，...
2019-08-06 17:52:59
181
原创 6月总结
①cf为主，div3四题，其实思路都有了，就是最近打的少了。②新学：无③期末考前复习，后台基本掌握，但前端方面，比如div，还是要自己多设计设计。端午回家恰逢老弟高考，考后陪他玩了一晚，感觉他心态的确很好，我预感他考得很好，果然月底得知老弟超常发挥考上一本，每次回家对他的指导没有白费，所以大考还是心态最重要。（自己心态一直不好，得好好吸取教训吧~）④emmm期末考太水了感觉....
2019-06-10 00:34:23
101
原创 LOJ504 ZQC的手办--线段树最值及位置+优先队列
#include <bits/stdc++.h>using namespace std;#define inf 1000000007typedef pair<int,int>pii;const int maxn = 500000+10;int n,m;int w[maxn];vector<int>ans;inline int read(...
2019-05-31 17:24:15
225
原创 春节十二响(树剖)
正解应该是启发式合并#include <stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;typedef long long ll;const int maxn = 200000+10;#define inf 10...
2019-05-31 17:23:41
156
原创 5月第五周总结
①这周主要补题，包括周四的个人赛的题目，普遍一两题，但自己最多只能切三题，太菜了！对线段树，STL的优先队列掌握不错！但dp、网络流需要系统学习！连网络流都不会，太菜了！补了一些cf题，维持手感。②学习后缀数组，复习了核心的三个数组和LCP相关问题，还需要系统打套题！复习了大数模板，高精度还是Python好用！③周末主要领航面试、写暑期寻访策划，队友那些女生策划很细致；计网易错点 一些...
2019-05-31 17:14:58
130
原创 个人赛C 柠檬树2--树链剖分+维护最值出现次数/LCA
给一棵树，维护上面两点最短路径中结点的最大值及最大值出现次数#include <stdio.h>#include<string.h>#include<algorithm>using namespace std;const int maxn = 300010+10;#define inf 1000000005typedef pair<int...
2019-05-25 16:51:06
172
原创 个人赛 FGH 补题（二分+取模+set）
DIJ大水题略过，C另外开一篇G 潘神的魔鬼训练（二分）暴力n^3肯定TLE，由三角形给出两边长度a,b，第三边长度限制为/a-b/~a+b，二分查找即可记得排序。。#include <bits/stdc++.h>using namespace std;int a[1005],b[1005],c[1005];int main(){ int N,M,L; ...
2019-05-25 16:50:08
179
原创 2019GDCCPC省赛补题BC
重现赛多组输入真烦→_→，感觉如果比赛，B和E有可能题意读错会WAB Build Tree关键：结点总数是个等比数列和#include <bits/stdc++.h>using namespace std;typedef long long ll;int k;ll m,n; ll p; ll a[300000]; ll mpow(ll a, ll b)...
2019-05-25 16:49:45
185
原创 五月第4周总结
①这周主要补题，包括省赛和周四的个人赛、牛客河北省赛的题目，基本能单切4t，中规中矩，对二分，STL掌握不错，但数据结构运用不够灵活，仍需加强，分治和区间DP也需要加强。②刷了一些题，学习了一些线段树的非常规做法③面试过了，社会实践学分不用愁了，不过队友都是女生，有一定压力。网建大作业基本完成 学习冥想，核心觉察及接受不是阻止。盘坐，吸 →屏 →呼，注意力在呼吸，吸数1呼数2、或平...
2019-05-24 11:08:24
152
原创 POJ 3237 Tree /BZOJ 2157旅游 -- 树链剖分边权处理+取反
类似SPOJ QTREE模板题，还是要注意跳过LCA！！！（因为用最深的点权维护边权，LCA其实是上一个点的边权，不管update还是query）只不过多了个取相反数操作关于区间取相反数，如果是维护区间和，就加个负号；但如果是维护最大值，应该最大值最小值互换。注释部分，表示按位取反如何维护最值（与本题无关）①POJ 3237 Tree#include <stdio...
2019-05-17 20:56:40
204
原创 Codeforces #560 (Div. 3)--D E 假设思想/区间重叠贡献次数
A注意下标 B排序扫一遍C 贪心，以为是O(N^2）其实O(N) DAlmost All Divisors题意：输入一堆数，看是否能找到一个数的所有因子（不包括1和它本身）包含所有输入的数思路：分解因子，但要分解那个数呢？有个小思想注意下。假设思想：假设输入的就是某个数的所有因子，则这个数取最小的话，一定 等于最小因子*最大因子（易得）再将这个数分解因子...
2019-05-17 20:55:55
180
原创 LOJ 6029 市场--线段树区间更新之分块除法
题目链接参考链接一、题意：四种区间操作：加、除（向下取整）、询问区间和、询问最小值二、思路：第一想到的是将除d变成乘1/d，但是由于不一定是整除，所以除法和加法运算顺序不同，会影响结果。比如 3和3，先除2后加结果是2，先加后除2答案是3第二既然区间更新不好做，那可以暴力单点更新？显然这种第51号元素的做法妥妥的TLE~所以我们要想怎么保持区间更新，然后尽量把除法...
2019-05-17 20:55:05
459
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人