- 博客(272)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 hdu 6134 Battlestation Operational (莫比乌斯反演+反演一般做法)
题目链接：哆啦A梦传送门题意：求f(n)=∑i=1n∑j=1i⌈ni⌉[gcd(i,j)==1]f(n)=\sum_{i=1}^{n}\sum_{j=1}^{i}\lceil \frac{n}{i} \rceil [gcd(i,j)==1]f(n)=∑i=1n∑j=1i⌈in⌉[gcd(i,j)==1]题解：参考博客：神犇此公式大部分都是参考博客里面的。我们先化简一下：f(n)=...
2019-06-21 16:54:17
255
原创 bzoj 2693 jzptab（莫比乌斯反演+积性函数线性筛一般套路）
题目：Description求 ∑i=1n∑j=1mlcm(i,j)\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)∑i=1n∑j=1mlcm(i,j)Input一个正整数T表示数据组数，接下来T行每行两个正整数表示N和M(T<=10000,N,M<=10000000)OutputT行，每行一个整数表示第i组数据的结果Sample Input...
2019-06-18 13:07:27
236
原创 自己的一点（求积性函数前n项和）杜教筛总结（其实也是瞎抄的）
杜教筛可以解决哪一类的问题：例如题目给你一个函数，让你求它的前项和$\sum_{i=1}^{n}f(i)$，但是这个n很大（n=1e10），显然在秒数级是不能算出来的，之前我们有学过拉格朗日插值定理求前n项和，它的复杂度与这个函数最高阶k紧密相连，差不多为O(k)，但是你要想用拉格朗日插值法，你得知道这个函数f为多项式函数才行。比如让你求前n项欧拉函数和，莫比乌斯前n项和，你就用不上这个拉格...
2019-05-02 13:44:43
409
原创 回顾在acm集训队的两年时光
从大一到现在，已经差不多两年了，现在的我，依稀清楚的记得17年10月份时，16级师兄来教室的宣讲会，第一次知道acm,知道这是一个学算法的训练队，当时自己连什么是算法都不知道，一听到这个词，心就牢牢的被套住了。在当时听完集训队教练的宣讲会后，我记得当时自己发了一个朋友圈，写着——再次找到一个能让我不舍昼夜的目标！此后就整天到晚猫在电脑前学算法，刷题。大一的很多课都逃了，逃课就为了学算法。虽说逃了不...
2019-09-06 12:00:10
2291
转载 指数循环节与斐波那契模p循环节
指数循环节：anmod p=an%ϕ(p)+ϕ(p)mod p (n≥ϕ(p))a^nmod\ p=a^{n\%\phi(p)+\phi(p)}mod\ p \ (n\geq\phi(p))anmod p=an%ϕ(p)+ϕ(p)mod p (n≥ϕ(p))斐波那契模p循环节：对于一个正整数n，我们求Fib数模n的循环节的长度的方...
2019-08-27 23:26:14
632
原创 二次剩余
参考博客1：参考博客2参考博客3二次剩余形式：x2≡n mod px^2\equiv n\ mod\ px2≡n mod p，给定n，p，求解x？这里我们只谈论p为奇素数。p为2时，答案不是0就是1，这点在下面代码有体现（代码是照搬的）。简明扼要：首先先判断勒让德符号(Legendre symbol) (ap)=ap−12(\frac{a}{p}...
2019-08-27 22:22:54
688
原创 hdu 6706 huntian oy（杜教筛）
题目链接：哆啦A梦传送门题解：f(n,a,b)=∑i=1n∑j=1igcd(ia−ja,ib−jb)[gcd(i,j)==1]f(n,a,b)=\sum_{i=1}^{n}\sum_{j=1}^{i}gcd(i^a-j^a,i^b-j^b)[gcd(i,j)==1]f(n,a,b)=∑i=1n∑j=1igcd(ia−ja,ib−jb)[gcd(i,j)==1]我们得知道有这个公式：gc...
2019-08-25 20:13:23
365
原创 H-subsequence 2（拓扑排序）2019牛客多校
题目链接；题意：有一串我们不知道由什么字符组成的长度为n的字符串，现在给你m个提示，每次会提示未知字符串中的两个字符以及这两个在原串的长度，接着会有原串的相对位置子字符串。让你还原出原来的串，如果还原不了，输出-1。题解：因为我们能知道这些字符的前后关系。这时拓扑排序就是解决这类问题的：经常用于完成有依赖关系的任务的排序。它是先将依赖关系建好边，然后每次从入度为0的点开始...
2019-08-20 22:34:09
207
原创 C-generator 2 （BSGS）2019牛客第五场
题目链接：题意：给出n,x0,a,b,p,且xi=(a∗xi−1+b)modpn,x_0,a,b,p,且x_{i}=(a*x_{i-1}+b) mod pn,x0,a,b,p,且xi=(a∗xi−1+b)modp多组测试用例，每组测试用例为v，找到最小的i，使得满足xi%p=vx_i \% p=vxi%p=v题解：我们知道xn=an∗x0+an−1b+an−2b+...+bx_...
2019-08-20 22:15:23
249
原创 G—subsequence 1 2019牛客第五场 （组合数+dp）
题目链接：题意：给出两个数字串s，t，找出s的子序列，满足大于t的方案数？题解：参考博客：组合数学+dp。对于长度大于t的s的子序列，都满足。现在考虑长度等于t的s子序列。dp[i][j]表示s的前i为，t的前j位满足的条件数。转移方程见标程。#include<bits/stdc++.h>using namespace std; typede...
2019-08-20 13:52:44
188
原创 D—triples I 2019牛客多校第四场
题目链接：题意：给出一个数a，让你找出尽可能少的几个3的倍数，使得这些数字或运算为a。题解：参考官方题解：每一个二进制位mod 3要么为1，要么为2,。那么我们就可以分类讨论了。代码：#include<bits/stdc++.h> using namespace std; typedef unsigned long long LL; vect...
2019-08-20 13:14:30
137
原创 B - generator 1（十进制矩阵快速幂） 2019多校第五场
题意：给定x0,x1,a,b,n,mod，求Xn%mod，n<=1e6题解：矩阵快速幂，因为n很大，故这里用十进制快速幂#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e6+10;char s[maxn];int mod;st...
2019-08-05 10:01:04
154
原创 hdu 6590 Code （判断两凸包是否相交）19_hdu多校
题目链接：参考博客：题意：给定一组（x1,x2,y）,其中y为1或0，问是否有一组（w1，w2，b），使得上述的每一个（x1，x2，y）都满足x1*w1+x2*w2+b在y=1时大于0，在y=-1时小于0.题解：我们可以将(x1,x2)看成是坐标点，那么题目就可看成，能否找出一条直线，将1点与-1点分开。也就是我们可以求1点的凸包以及-1点的凸包。然后我们再判断这两个凸包...
2019-07-30 23:33:58
892
原创 hdu 6579 Operation （线性基求区间最大值）
题目链接：题意：有n个数，q个询问。每个询问有两种操作。当opt=0时，在[l,r]区间中，任意挑选数，异或最大值。当opt=1时，添加一个数x在后面。题目还要在线。每次的l，r都要跟上次的opt=0操作得到结果异或，(l^ans)%n+1，(r^ans)%n+1，x^ans。题解：参考博客：参考博客1：将出现位置靠右的数字尽可能地放在高位。因为题目是异或...
2019-07-30 18:02:52
344
原创 B-xor（线性基求交+线段树） 2019牛客多校第4场
题目链接：题意：有n个集合，每个集合有若干元素，一个集合i能表示x，当且仅当存在一个集合i的子集合，这里面的元素异或值为x。有m个询问：每个为x,l,r，如果任意一个集合i (i在[l,r])都能表示x，输出YES，否则输出NO。题解：我们给每个集合求一个线性基，如果该集合能表示x，说明x在线性基里面。题目现在是多询问，而且是多集合，那么也就是要求多个集合的线性基的交，假设x...
2019-07-29 21:41:46
341
原创 D—Big Integer （质因子分解）2019牛客多校
题目链接：题意：有这样一些数，全部由1组成，例如：1,11,111,1111,…定义A(n)为第n大的数，计算: ∑i=1n∑j=1m[A(ij)≡0(modp)]\sum_{i=1}^{n}\sum_{j=1}^{m}[A(i^j)\equiv 0 ( mod p)]∑i=1n∑j=1m[A(ij)≡0(modp)]我们设：A(n)=10n−19A(n)=\frac{10^n-1}{9...
2019-07-29 13:47:20
355
原创 hdu 6055 Regular polygon (找出正方形)
题目链接：题意：给n个不同的整数点，问：能找出多少个不同的正多边形？题解：因为都是整数点，故只会出现正四方形，题目就变成了找正边多形的个数。我们枚举正方形的一边，在左右两边看是否能找到满足条件？#include<bits/stdc++.h>using namespace std;struct point{ int x,y;} p[600];...
2019-07-24 22:20:31
194
原创 BM线性递推
如果一个数列、其能够通过线性递推而来:例如使用矩阵快速幂优化的 DP 大概都可以丢进去则使用 BM 即可得到任意 N 项的数列元素模板：#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector&g...
2019-07-24 20:09:58
1033
原创 线性基
参考博客：参考博客1：参考博客2：线性基的性质：1，原数集中的数字异或出来的值域与线性基中的元素以后出来的值域相等。2，线性基中没有异或和为零的非空子集。3，线性基中的选取元素的每一种方案，都对应一个异或值，不存在多种选取方案对应同一个异或值的情况。4，线性基二进制最高位互不相同。5，线性基中元素互相异或，异或集合不变。6，线性基是满足以上性质的最小集合。...
2019-07-21 16:54:09
337
原创 51Nod 1227 平均最小公倍数（杜教筛）
题目链接：哆啦A梦传送门题意：求∑i=ab1i∑j=1ilcm(j,i)\begin{aligned}\sum_{i=a}^{b}\frac{1}{i}\sum_{j=1}^{i}lcm(j,i)\end{aligned}i=a∑bi1j=1∑ilcm(j,i)我们设：ans=∑i=1n1i∑j=1ilcm(j,i)=∑i=1n1i∑j=1ii∗jgcd(i,j)=∑d=1nd∑i...
2019-07-19 19:14:57
189
原创 51Nod 1237 最大公约数之和 V3 (杜教筛)
题目链接：哆啦A梦传送门 题意：求：∑i=1n∑j=1ngcd(i,j)\begin{aligned}\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\end{aligned}i=1∑nj=1∑ngcd(i,j)题解：∑i=1n∑j=1ngcd(i,j)=∑d=1nd∑i=1n∑j=1ngcd(i,j)=d=∑d=1nd∑i=1nd∑j=1ndgcd(i,j)...
2019-07-17 18:12:20
172
原创 51Nod 1238 最小公倍数之和 V3 (杜教筛)
题目链接：哆啦A梦传送门题意：求 ∑i=1n∑j=1nlcm(i,j)\begin{aligned}\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)\end{aligned}i=1∑nj=1∑nlcm(i,j)我们设:ans=∑i=1n∑j=1nlcm(i,j)=∑d=1nd∑i=1nd∑j=1nd[(i,j)=1]i∗j\begin{aligned}an...
2019-07-17 17:09:11
171
原创 hdu 1085 Holding Bin-Laden Captive!（生成函数）
题目链接：哆啦A梦传送门题意：已知有a个1，b个2，c个5，问：最小不能组成的数是多少？解：1，a==0时，此时最小不能组成的数是1。2，当a+2*b<4时，此时最小不能组成的数是a+2*b+1。3，其它条件，最小不能组成的数是a+2*b+5*c+1。我们知道当a+2*b>=4且a！=0时，单单这两个数字的组合，就能构成范围在 [1,a+2*b]中的任何一...
2019-07-15 19:36:50
138
原创 hdu 4405 Aeroplane chess（期望dp与概率dp的一般解法）
题目链接：哆啦A梦传送门题意：某个人要从1点走到n点，每次向右走的步数为抛骰子决定，骰子有六面，每面被抛出的概率为1/6。此外，还有m条直达航线，每条为x，y，表示可以直接从点x到点y，而不用去抛骰子。问：到达n点的期望抛骰子次数是多少？题解：跟之前做的期望dp一个样。我们只要按有向图的路线走就行了。设dp[i]为在i点，并且到目标位置的期望次数。显然状态转移方程为：...
2019-07-15 17:59:39
206
原创 zoj 3754 One Person Game（期望dp）
题目链接：哆啦A梦传送门题意：有三个骰子，分别有k1，k2，k3面，初始分数为0，每摇动骰子后，如果三个面分别为a，b，c，那么将分数置零，否则加上a+b+c的分数，当分数大于n时结束。问：期望次数是多少次？题解：参考博客：设dp[i]表示分数为i，到达目标状态需要的期望，p[j]表示摇骰子分时为j的概率，p0表示初始分数。那么我们可以得到转移方程：很显然我们要求...
2019-07-15 16:34:50
162
原创 poj 3744 Scout YYF I （概率dp）
题目链接：哆啦A梦传送门题意：一条路上有n个炸弹，每个炸弹的位置为x，一个人从1开始出发， 每次可以走一步或者走两步，走一步的概率为p，走两步的概率为1-p。问：安全通过这条路的概率是多少？题解：我们将全场分段走，保证每段的末尾至少有一个炸弹，然后求每一段安全通过的概率。每一段都是独立的，也就是最后通过全程的概率为通过每一段概率的乘积。我们设dp[i]为安全通过i点的概...
2019-07-15 14:49:57
135
原创 poj 2096 Collecting Bugs （期望dp）
题目链接：哆啦A梦传送门题意：一个软件有s个系统，n个bug，每个系统有无数个bug，每天可以找出一个bug。问：每个系统至少找出一个bug，并且所有种类的bug都找出来的期望天数？算法合集之《浅析竞赛中一类数学期望问题的解决方法》题解：参考博客1：参考博客2期望dp。我们设dp[i][j]表示已在j个系统中找出了i个bug，并且距离目标状态的期望天数。很显然d...
2019-07-15 13:20:45
161
原创 F. Tokitsukaze and Strange Rectangle（树状数组+离散化）
题目链接：哆啦A梦传送门题意：二维平面上有n个点，定义一个奇怪的矩形，它是以 l=<x，x<=r，y>=a，每个这样的矩形包含了一些点，问：有多少个不同的矩形。两个矩形不同当且仅当至少有一个点不同。题解：我们先按y从大到小排，x从小到大。这样我们就相当于有一条扫描线，从上往下扫。每到一条扫描线，我们会增加t个新点，我们以添加的每个新点i为结束的集合。此时我们...
2019-07-14 18:00:31
317
原创 E. Tokitsukaze and Duel （博弈）
题目链接：哆啦A梦传送门题意：有长度为n的字符串，每个字符为'0'或'1'，两个人轮流玩游戏，每次可以任取长度为k的连续子串，将它们改成相同的串（要么为1，要么为0），谁先把串弄成全部相同，谁就win。问：先手win，还是后手win。题解：还是跟之前玩的博弈类似，两人都是最聪明的，那么也就是说，字符串一旦给定，其实已经定好了是先手win，还是后手win。先手如果不能在第一次出手就...
2019-07-14 13:22:32
453
2
原创 poj 2391 Ombrophobic Bovines (二分+dinic)
题目链接：哆啦A梦传送门题意：一个n个点无向图，每个点有Ai头牛，每个点的牛棚能容纳Bi头牛，有m条边，每条边有一个权值为w，表示u点到v点需用多少时间，现在要使得所有牛都跑进牛棚，问：最快多久能跑进去，如果不能全部跑进去，输出-1。题解:二分时间：每次二分跑一次dinic，如若满流，则此时间满足条件。建模：给每个点i拆点为 (i，i1)。原点s到每个点i建边，权值为Ai。...
2019-07-12 15:45:55
162
原创 poj 2396 Budget (有源汇上下界网络流)
题目链接：哆啦A梦传送门题意：有n行m列个方格，每个方格有未知的数，现在有这些条件：第一行n个数，表示方格每行的总和。第二行m个数，表示方格每列的总和。接着有q个条件，每个条件为x,y,op,z，表示第x行第y列的值条件为z。输出满足上述条件的n*m方格，如果没有的话，输出：IMPOSSIBLE。题解：参考博客：参考博客2参考博客3无源汇上下界可...
2019-07-10 19:37:01
190
原创 E. Vus the Cossack and a Field (规律题)
题目链接:哆啦A梦传送门题意:给出原始n行m列矩阵A，他的反置矩阵为B(与A相对应的位置取反)。原始矩阵 ： A第一次可以变成：[ABBA]\begin{bmatrix} A&B \\ B& A\end{bmatrix}[ABBA]以此类推。现在有q个询问，每次询问左上角为(x1,y1)，右下角为(x2,y2)的矩阵的总和。我们可以发现N行...
2019-07-09 20:06:42
458
1
原创 hdu 1828 Picture （扫描线+线段树 求多矩形总周长）
题目链接：哆啦A梦传送门题意：给出n个矩形围城的多边形，求它们的总周长。题解：参考博客：跟hdu 1542解法差不多，也是扫描线求。对于扫描线从下往上扫，每次横轴的长度为=|上一次的有效长度-这次的有效长度|。对于竖轴的长度，我们在每个节点添加lc，rc，num，分别表示该节点的左右端点是否被覆盖（lc，rc为1表示被覆盖），num表示此节点代表的区间里有多少条线段。那...
2019-07-09 15:04:20
272
原创 hdu 1542 Atlantis （扫描线+离散化线段树求多矩形总面积）
题目链接：哆啦A梦传送门题意：给n个矩形，求它们的总面积，覆盖的只算一次。每个矩形给出左下点和右上点。参考博客1：参考博客2扫描线从下往上扫描，每次求出该扫描线的有效长度，再与两条线之间的高度相乘就是最后的面积。线段树更新，遇到该边为矩形的下边就加进去，遇到该边为矩形的上边就减掉。代码：#include<cstdio>#include<...
2019-07-09 13:39:45
274
原创 poj 2528 Mayor's posters（线段树+离散化）
题目连接：哆啦A梦传送门题意：有n张海报，每个海报有左右区间 [l,r]。在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报。题解：离散化+线段树。参考博客：假设更新区间包含当前节点区间，将当前区间直接修改颜色。假设更新区间不完全包含或者不包含当前区间，将当前区间的颜色给左右子节点。这里使用离散化线段树，因为坐标范围太大，而这里又不需要求总长之类的，我们只需只...
2019-07-08 19:33:52
123
原创 hdu 5352 MZL's City (最小费用最大流)
题目链接：哆啦A梦传送门题意：n座城市，m年修复这个国家，每年有如下3种操作之中一个，k表示每一年最多修复城市k座。现在所有的城市和道路都被摧毁了。有m年时间修复这个国家。操作分三种：1 x：最多修复与x相连通的城市k座（包括x）。2 x y：修复城市x与城市y的双向道路。3 p：接着有p对 （x,y），表示摧毁城市x与城市y的双向道路。输出：能修复最多多少个城市？接着输出...
2019-07-07 22:57:26
240
原创 poj 3068 "Shortest" pair of paths (最小费用最大流)
题目链接：哆啦A梦传送门题意：有n个点，m条有权值的单向边，现在让你找出两条从0点到n-1点的路径，要求这两条路径的费用尽可能的少，并且这两条边没有公共点（也就是所给的边只能使用一次）。要是找不到两条边，输出：Not possible。反之输出总费用。题解：我们先将题目给的数据点都先+1。建模：源点0到第一个点建边，权值为2，费用为0。将题目给的数据边连边，权值为1，费用为该边...
2019-07-07 12:26:23
217
原创 hdu 4309 Seikimatsu Occult Tonneru ( dinic+二进制求最小费用)
题目链接：哆啦A梦传送门题意：给出n个城市，每个城市有人，现在要使得所有城市的人尽量都掩藏在隧道中。这些城市之间有三种可互相连通的通道。桥：可以通过桥从u点到v点。但是这个桥坏了，只能给一人通过，不过我们要是花费w钱的话，这座桥就可通过任意次数。 路：可以通过路从u点到v点 隧道：可以通过隧道从u点到v点，此外这个隧道可以掩藏w人。现在我们要在花费尽可能少的情况下，掩藏更多的人。...
2019-07-06 23:18:56
163
原创 网络流模板
dinic模板：struct edge{ int from,to,w,next;}e[N<<1];int cnt;int dep[1111],head[2111];//queue<int> que;void init(){ memset(head,-1,sizeof(head)); cnt=0;}void add(in...
2019-07-06 18:47:30
129
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人