- 博客(112)
- 资源 (1)
- 收藏
- 关注
RSS订阅
转载 O(N)求1-N的逆元
原地址：http://www.2cto.com/kf/201401/272375.html新学的一个求逆元的方法：inv[i] = ( MOD - MOD / i ) * inv[MOD%i] % MOD证明：设t = MOD / i , k = MOD % i则有 t * i + k == 0 % MOD有 -t * i == k % MOD
2016-05-14 21:59:06
1077
原创 2016 大连 J Find Small A · 二进制
这个题面看着好懵逼啊题意实际上就是问，给你一堆32位整数，对于每个数字，把每8位算成一个数，统计有多少个97，即字符“A”的ASCII码值。写完这题都还在懵逼#include <cstdio>#include <algorithm>using namespace std;int n,ans;long long p,x;int main(){ p=255; ...
2018-03-12 15:45:13
283
原创 2016 大连 H To begin or not to begin · 简单博弈
k 是偶数的话，先手的概率是 ((n+2)/3)/(n+1) 大于后手的概率 k 是奇数的话，那先手后手概率都是1/2#include<bits/stdc++.h>using namespace std;int main(){ int T; int n; while(~scanf("%d",&n)){ if(n&1) ...
2018-03-12 15:37:04
393
原创 2016 大连 F HDU 5976 Detachment · 逆元+数学分析
仰慕：http://blog.csdn.net/qq_34374664/article/details/53466435#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define f(i,x,y) for...
2018-03-12 15:29:58
240
原创 2016 大连 E HDU 5975 Aninteresting game · 树状数组
树状数组原理题。题目大意实际上是问，从1-n建立一个树状数组，1.第一个询问就是求从L到R的lowbit(i)之和，这个我们可以转换为求1-R的lowbit(i)之和，类似求前缀和。那么1-R的lowbit(i)怎么求呢。如果写出1-16的lowbit值就可以发现实际上lowbit(i)是有很强的规律的：根据lowbit的定义，转化成10进制实际上就是，对于一个数i，含有的最大的2的次方的因子就是...
2018-03-12 15:27:41
416
原创 2016 大连 D HDU5974 A Simple Math Problem · 数论
转化成用gcd做以后，然后简化公式，结论题_(:з」∠)_（不过我算不出来就是了2333#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define ll long longll a,b,i,j,c,d...
2018-03-12 15:08:29
592
原创 2016 大连 B HDU5972 Regular Number · bitset
每个位置可以和多种数字匹配，然后就用bitset来存，这样每次匹配都还是O(1)的复杂度#include <cstdio>#include <cstring>#include <bitset> #include <algorithm>using namespace std;#define f(i,x,y) for (int i=x;i<...
2018-03-12 15:07:42
242
原创 2016 大连 A HDU 5971 Wrestling Match · 模拟
用并查集先将所有的联通块处理出来，然后对于每个联通块，选定已经确定的好/坏选手为起点开始判断，直到遍历完整个联通块。特殊情况：如果整个联通块中都没有已经确定的选手，那么整个联通块都是无法判断的#include <cstdio>#include <algorithm>#include <cstring>#include <vector>usin...
2018-03-12 15:06:57
140
原创 C语言：从入门到弃坑
在uestc写的第一篇blog。。。留念一下。。。算作复习C++了。。。如果看这篇blog还看不懂的话，退群吧。=============分割线==============2017.9.21更新1.0写一个程序，目的是为了什么，通俗易懂的讲，给你一些原始数据，让你经过一些乱七八糟的操作以后得出一个结果，那个结果就是我们想要得到的东西。原始数据通称为输入，得到的结果通称作为输
2017-09-21 15:20:50
946
1
原创 [BZOJ 1050] HAOI 2006 旅行comf · Kruskal
网上有非常吊炸天的LCT做法并不会23333用Kruskal来做的思路比较神奇但是很简单首先把所有的边按照权值排序顺次枚举每一条边，从这条边开始做Kruskal，直到S和T联通，这就是一个可行解，然后判断出分数最小的一个解 复杂度O(M^2)与普通的kruskal代码略有不同，条件稍加修改#include #include #include #include usi
2017-07-25 16:20:46
303
原创 [BZOJ 1029] JSOI 2007 建筑抢修 · 贪心+堆
这题很类似线段覆盖和工作安排，因此考虑用贪心，但是贪心肯定是会被卡的，所以考虑优化。假设已经花费了now个单位时间，那么对于当前t号建筑，有两种情况：1.now+t.cost2.找到之前已经修过的建筑中，花费时间最多的p号建筑，如果p.cost>t.cost，那么再判断一下用t来替换p是否可行，即now+t.cost-p.cost这个的意义就相当于线段覆盖中，把t和p分别看成两条线
2017-07-23 16:17:30
342
原创 [BZOJ 1025] SCOI 2009 游戏 · DP
emmmmm....想到要求最小公倍数的种数但是不会做啊qaq看了题解才明白....我好菜啊....orz:题解#include #include #include #include using namespace std;#define f(i,x,y) for (int i=x;i<=y;i++)const int N = 1005;long long p[N]
2017-07-22 11:52:53
218
原创 [BZOJ 1084] SCOI 2005 最大子矩阵 · 简单DP
比较魔性的题目 m具体转移方程可直接看代码#include #include #include #include using namespace std;#define f(i,x,y) for (int i=x;i<=y;i++)const int N=105;int n,m,k;int s[N][3],ans;int work1(){ int f[N][N]; m
2017-07-22 09:41:43
339
原创 [BZOJ 4300] 绝世好题 · 乱搞
想到了就是绝世傻题，想不到就是绝世神题。我属于后者orz：http://www.cnblogs.com/albert7xie/p/4963400.html#include using namespace std;const int N=1e5+10;int n,f[35],ans,x;int main(){ scanf("%d",&n); for (int i=1;i<
2016-04-23 19:09:43
501
原创 [BZOJ 1036] ZJOI 2008 树的统计Count · 树链剖分
拖了超级久的树链剖分终于真正写了一次。个人感觉就是，代码长只是因为函数有点多，总体思想和代码都很水，除了两边dfs外基本就是裸的线段树了。这不是一篇比较好的树剖的讲解代码真的很水啊。。。。#include using namespace std;#define f(i, x, y) for (int i = x; i <= y; ++ i)#define ff(i, x,
2016-04-06 17:12:27
435
原创 Graph · 图的联通 + 矩阵快速幂
来源：知乎题意请戳上方↑首先有两个很好玩的性质：1.有向图的一个强连通分量的周期d = 所有环的长度的最大公约数1.有向图的周期D = 所有强连通分量的周期di的最小公倍数然后如果要求最小的满足，由于k可能很大，那么用类似倍增的思想来求，我一开始傻*用的二分，T出一片天。另外因为，矩乘的时候要压位。#include using namespace std;
2016-04-04 17:34:01
937
原创 Move · 卡特兰数 + 组合数学 附逆元
比较经典的数论好题。大意：从(0,0)出发，每次可以向(i+1,j),(i+1,j+1),(i+1,j-1)三个方向走，但是要求不能经过第四象限，问到(n,0)有多少种走法。每走一步都会在横坐标上前进一个，所以肯定是走n步，只需要考虑纵坐标就行了。如果不考虑直走的情况，,枚举k表示上去了多少步，那么既然最终要到(n,0)肯定是要上去多少步还要下来多少步，那其实这就是个卡特兰数啦，然后剩
2016-04-03 19:10:45
531
原创 [poj 2417] Discrete Logging · BSGS
BSGS，baby step giant step，大步小步法，很形象的概括了这个算法的核心，算法用于解决一个很经典的问题:，给定A，B，P，其中P为素数，求一个可行解x大步小步法算法详解：猛戳这里#include #include #include #include #include using namespace std;#define ll long long
2016-02-15 22:55:27
596
原创 [BZOJ 2301] HAOI 2011 Problem b · 莫比乌斯
这题和Bzoj1101有区别吗。。。囧。。。题解：狂戳这里#include #include #include using namespace std;const int N=1e5+5;int p[N],tot,check[N+10];int moblus[N],sum[N];int a,b,c,d,k,T,ans;void init(){ memset(check
2016-02-05 11:31:21
490
原创 [BZOJ 1101] POI 2007 Zap · 莫比乌斯 & 分块 超详细题解
初学莫比乌斯反演，翻了大量的题解才搞懂这题，所以决定自己写一个最详细的题解，虽然有些繁琐，但是每一步推导都十分详细。神犇就不要嘲讽我了2333首先，我们定义题目即要求由于d是给定的，所以另可以转化为，到这个地方的话题中所给的d就已经再没有用处了，不要和下文中的d混淆。由莫比乌斯函数的性质即将原本的和式转化为 ①，注意这里的d和题目中给定的d不是指的同一个东
2016-02-05 11:12:28
2472
1
原创 [BZOJ 2194] 快速傅立叶之二 · FFT
求这个式子不好搞啊，然后我们就把B翻一下好了！变成然后我们发现，i+(n-1-i+k)=n-1+k，只与k有关了！然后我们另，这个就很显然一个裸的卷积了，FFT模板直接上所以最后对应的是C(0~n-1)对应D(n-1,n+n-2)。#include #include #include #include #include using namespace std;#
2016-02-04 23:56:52
778
1
原创 FFT
感觉也不是很会FFT，先把板子敲会再说吧= =两条模板题_(:зゝ∠)_UOJ #34#include #include #include #include using namespace std;#define f(i,n) for (int i=0;i<n;i++)const int N=4*1e5+5;const double pi=acos(-1);int
2016-02-04 23:39:44
482
原创 [POJ 1228] Grandpa's Estate · 凸包
题目大意：给出一些点，保证是一个凸包上的顶点或边上的点，问这个凸包是否是唯一确定的，即是否能在凸包外再添加一点使得凸包变得更大。思路：首先可以确定，对于凸包上的两个顶点，如果这两个点的连边上没有点的话，那么我们可以加一个点使得凸包变得更大（如图）那么我们只要确定是否每两个相邻的顶点的边上是否已经有点就可以了。判断方法：首先，对于三点i,i+1,i+2，如果向量和的叉积为0，则这三点
2015-12-25 21:29:01
507
原创 [hdu 1348] Wall · 凸包
大概就是，给你n个点和一个值L，求这n个点的凸包，然后求与凸包相距l的外圈的周长。结果=凸包的周长+半径的L的圆的周长求凸包：首先将n个按x坐标排序，然后选第一个点作为一个确定的点（最左边的点肯定在凸包上）然后分两步，先求上凸包，再求下凸包。求上凸包时，我们将目前已经在凸包里的点压入栈中，当做到第i号点的时候，如果发现向量在向量的逆时针方向，那么说明top是凸包内的点而
2015-12-20 17:04:59
576
原创 [NOIp 2015] 对D1T2的一些拓展研究
随便口胡，错误一大堆，欢迎打脸D1T2因为只有n条边，所以只存在简单环，那我们把这个问题复杂一下，每个人可能能告诉多个人，也就是边的数量大于n，那么这样的话就会出现复杂环了。如果还是直接用tarjan求的话肯定是错的，因为tarjan每次找的是一整个大环。在这里想到了一种比较简单的解法。我们每次选一个没有走过的点开始DFS，并一路将走到的点压入存路径的栈中，同时用visit[i]表示i
2015-11-18 12:31:32
899
原创 [POJ 3744] Scout YYF I · 概率DP & 矩阵快速幂
题目大意：一个数轴上有n个地雷，坐标给定，熊孩子一开始在位置1，每次向前跳1格的概率是p，跳两格的概率是1-p，求他安全跳过这n个地雷的概率。第一次写概率DP，WA了两发以后莫名其妙就AC了。。。太弱了。。。首先对于一个地雷，我们肯定是要一次跳两格来过去；而每两个地雷之间的区间是安全的，我们可以直接用f[i]=f[i-1]*p+f[i-2]*(1-p)推算，f[i]表示到位置i的概率。假设
2015-11-09 21:52:22
872
原创 [BZOJ 2079] Poi 2010 Guilds · 思路题
大意就是给你一个无向图，把图上的点染成红黑色，要求红色点要至少和一个黑色点相连，黑色点同理。那么如果我们有一个联通块，可以把它先做成一棵生成树，那么奇数层的染红色，偶数层的染黑色，就可以满足题意。那么不满足情况的条件就是某个联通块只有1个点。原本可以用并查集处理出每个联通块有多少个点然后判断，但实际上就是杀鸡用牛刀了。。。（好吧其实只是我爆了系统栈）我们只需要知道是否存在大小为1的
2015-11-05 17:11:15
689
原创 [Vijos 1629] 八 · 容斥原理
求[a,b]中能被8整除但不能被给定n个数整除的数的个数，转化为分别求[1,a-1]和[1,b]中的数的个数。然后首先在区间[1,x]中能被8整除的数的个数是x/8，但是有的是不符合要求的。要求不能被给定的n个数整除，我们就把能被这n个数整除的同时又能被8整除的数去掉。原本是奇加偶减，但是一开始选取了一个8，所以反过来 ，具体见代码。#include #include #inc
2015-10-29 17:01:05
711
原创 [HDU 4135] Co-prime · 容斥原理
题意为求[a,b]中与n互质的数的个数。可以将问题转化为，求出[1,a]和[1,b-1]中与n互质的数的个数然后用前者减去后者，就是答案。然后求[1,a]区间中与n互质的数的个数实际上又可以转为求与n不互质的数的个数，在n小的时候可以用欧拉函数求，但是像这题n比较大的时候就适合用容斥原理。容斥原理思想请自行百度。。。orz：http://www.cnblogs.com/jiangj
2015-10-29 10:35:31
509
原创 『Citric』天空中的繁星 · DP
天空中的繁星 天空中的繁星天空中的繁星 【问题描述】Lemon最近买了一台数码相机。某天Lemon很无聊，于是对着夜空拍了一张照片，然后把照片导入了电脑。Lemon想依靠电脑的力量，完成他小时候经常做却从来没有成功过的事情：数天空中有多少颗星星。Lemon已经把相片处理成了黑白的，也就是说，每个像素只可能是两个颜色之一，白或黑。Lemon定义像
2015-10-26 16:34:15
951
原创 [TYVJ 1927] 『Citric II』一道防AK好题 · 模拟
出题人真是丧(gan)心(de)病(piao)狂(liang)！题面说的各种玄乎各种牛逼然而却毫无卵用对于最后一组a b c ,因为要加上lastans以后=0，所以明显倒数第二组的解就是ans=-a然后我们把这个ans代入上一组数据的表达式，就可以得到一个关于上上组数据的解，然后不断向前推，结果就出来了。就出来了。出来了。来了。了。。简直丧心病狂#incl
2015-10-25 21:57:17
1176
原创 [BZOJ 1597] Usaco2008 Mar 土地购买 · 斜率优化DP
拿到手的时候根本想不到是斜率优化。。。然而思路太神了。对于两块地x1*y1 x2*y2，如果x1这样我们可以得出平方级别的DP方程：现在开始斜率优化：假设j>k且j优于k，那么满足化简得到然后就随便写写呗~虽然各种奇葩错误WA了无数次#include #include #include #include using namespace std;#defin
2015-09-18 20:46:07
1359
原创 [BZOJ 3040] 最短路(road) · 堆优化dijkstra
堆优化dijkstra写法很多，我用的是系统堆priority_queue,见上一篇blog这题空间卡的太紧了#include #include #include #include using namespace std;#define ll long long const int M=10000005;const int N=1000005;int node[M],nx
2015-09-15 12:17:09
868
原创 [HDU 2544] 最短路 · 堆优化dijkstra
模板题用来练手。现在来说一般的图论题目都很难用普通dijkstra过掉，而SPFA又很不稳定，还是学了一下国际公认的堆优化dijkstra。简单来说，堆优化dij就是把for循环找最小的d[i]那维用堆来做，将O(n)降成了O(logn)。关于一个小问题见程序注释【据说priority_queue常数巨大 ，不管了】#include #include #include #
2015-09-14 22:57:13
1944
原创 [BZOJ 1010] HNOI 2008 玩具装箱toy · 斜率优化DP
第三次做这题终于A掉了，了结了一个心病。首先还是列出裸的DP方程：表示当前这个容器的末尾是第i个，上一个的末尾是第j个，si是对玩具长度做的前缀和。那么用斜率优化的话，我们还是设x>y且x优于y,可以得到这个式子：然后为了方便化简，我们设Ti=i+Si,P=L+1，就可以得到这个式子：这样就可以直接斜率优化搞了，如果斜率优化有不理解的可以看我的BZOJ 3156的题解，还是
2015-09-11 12:45:15
463
原创 [BZOJ 3156] 防御准备 · 斜率优化DP
跟佣神(orz)请教了一番大概会了基础的斜率优化：基础的斜率优化一般就是两种情况：（斜率式子）i 且i单调减。对于第一种情况，也就是斜率单调增的，维护队头很好理解，维护队尾的时候，因为我们要保证斜率递增，所以如果(q[r],q[r-1])的斜率大于(i,q[r])，那么我们就把r给踢掉。第二种情况就直接反过来想就可以了。对于这题：f[i]表示在第i个点上放守卫塔，裸的方程为
2015-09-10 22:15:45
399
原创 [BZOJ 2190] SDOI 2008 仪仗队 · 欧拉函数
首先要知道的是，对于两个点(x1,y1) (x2,y2)，如果他们的连线上不存在别的整点，也就是能直接互相看见，那么应该满足gcd(x1-x2,y1-y2)=1。对于这道题目，也就是求对于左下的那个点有多少个点死能直接看见的。为了方便，我们把左下的点设为(0,0)，对于第0行和第0列，只有(0,1)和(1,0)是能直接看见的；对于剩下的1~n-1行和1~n-1列，
2015-09-09 14:45:39
533
原创 [HDU 2692] Ball · 二分答案+最短路
这是个WA的程序。。。有待填坑。。。不过我也没看出来哪里错了。。。这只是个草稿。。。#include #include #include using namespace std;#define sc scanf("%d%d",&c,&r)#define rep(i,c) for (int i=1;i<=c;i++)const int inf=1e9+7;cons
2015-09-04 21:27:41
694
原创 [HDU 3306] Another kind of Fibonacci · 矩阵快速幂
矩阵乘法一眼题。首先我们根据题意，可以得到，那么我们既然要求 ，可以通过求 ，而求就要在矩阵中维护，和所以我们可以得到这样一个矩阵
2015-09-04 20:22:29
481
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人