爱悠闲 > 相关文章 >

BZOJ 2759 一个动态树好题 Link-Cut-Tree+扩展欧几里得

【屯计划】【#1】
既然停课了就趁这半个月时间屯一波解锁一下人生成就 已屯:                          13 【BZOJ】【P3697】【采药人的路径】【题解】【点分治】 【BZOJ】【P2697】【特技飞行】【题解】【贪心】 【BZOJ】【P2298】【HAOI2011】【problem a】【题解】【dp+二分】 【BZOJ】【P2527】【Poi2011】【Meteors】【题解】【整体二分】 【BZOJ】【P2212&P3702】【Poi2011】【Tree Rotations
ACM知识点学习链接
数组 POJ2481树状数组 HDU4302 map或者线段   5、计算几何 旋转卡壳学习                                          HDU4533矩形切割                                                  计算几何的各种 6、组合数学 http://www.aiuxian.com/article/p-852135.html2 http://www.aiuxian.com/article/p-852126.html 容斥原理学习 7、数论 数论小结 polya 计数法,burnside定理 学习小结 8、其他 十个利用矩阵乘法解决的经典题目 POJ数学题目                       HDU题目分类
欧几里得原理及扩展欧几里得原理(Euclidean Theory and Extended Euclidean Theory)学习笔记
题记:这是我第四次复习扩展欧几里得原理,因为不常用到,想要使用的时候又想不起细节,总是要查资料,于是索性这次整理一下欧几里得原理及其扩展原理存档至博客以备查用。 一、欧几里得原理 欧几里得原理(Euclidean Theory)是初等数论中求两正整数最大公约数(Greatest Common Divisor, GCD)的方法。欧几里得原理在中国古代又称“辗转相除法”,这一称法揭示了其求最大公约数的过程。 对于两个正整数a,b,记其最大公约数为gcd (a,b)。 那么我们有 gcd (a,b
扩展欧几里得及组合数递推模板
继续数学部分的学习,温故知新。 学习扩展欧几里得可以参考: 扩展欧几里得学习小记 - 将狼踩尽 19891101 - 博客园 欧几里得+扩展——数论总结2 - _%Corey的日志 - 网易博客 #define i64 __int64 i64 Extended_Euclid (i64 a,i64 b,i64 &x,i64 &y) {//扩展欧几里得算法,求ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b) i64 d; if (b==0
【BZOJ2396 || POJ3318】神奇的矩阵 || Matrix Multiplication
【Description】 给出三个行数和列数均为N的矩阵A、B、C,判断A*B=C是否成立。 【Data Range】 N <= 1000, 矩阵中的数字 ∈ 【0, 1000】 【Analysis】 直接AXB 再判与C是否相等是 O(N3) 的 一个基于概率的算法是随机生成一个 N乘1 的矩阵R 然后判断 A * B * R 是否等于 C * R ,而前者相当于 A * ( B * R ) 与后者一样都可以在O( N2 )的时间里算出来 如果算出来的结果相等,几乎可以肯定A*B和C也是相等的。 【Code】 BZOJ上一直RE,正在问admin要数据 POJ上可过
hdu 1576 A/B 扩展欧几里德
题目:要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我们给定的A必能被B整除,且gcd(B,9973) = 1)。 INPUT 数据的第一行是一个T,表示有T组数据。 每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。 OUTPUT 对应每组数据输出(A/B)%9973。 Sample Input 2 1000 53 87 123456789 Sample Output 7922 6060 题目分析:刚看到这个题目,就知道是数论
莫比乌斯反演学习小记
其实这东西压根还没学懂。。。先记录下学习资料 http://www.aiuxian.com/article/p-1658274.html 莫比乌斯反演入门 - qw4990的专栏 莫比乌斯反演 - pi9nc的专栏 又见莫比乌斯反演 - ACdreamer HDU 4746 Mophues - KIDxの博客 - ITeye技术网站 数学-莫比乌斯和容斥 - 随笔分类 - 将狼踩尽 19891101 - 博客园 上述第一篇博文里的提到的 BZoj 2818 用欧拉函数就能做。博文里 的代码貌似过不了,我自己敲了一下午居然也没过。。。。 这里有一份能过的: BZOJ 2818 gcd - KQZXCMH的专栏 - 博客频道
线段题目分类+简单解释
结果不一样 //fzu 1608 更新后,查找总区间的长度时传递 //zoj 2706 讲区间值替换为平均值 //poj 3368 求有序数组区间出现频率最多次数 //zoj 2859 二维线段,求矩阵部分最大值 //hdu 3074 水,求区间乘积 //bzoj 1798 区间乘一个数,区间加一个数,求区间和。注意乘和加的关系。 //bzoj 1102 线段一个节点一个节点的建,保存上一次结果,以及序列长度即可 //poj 2482 可以转化成多个矩形求交的覆盖次数最大
ACM省赛东北赛大概计划
三维的计算集合,至少用一周的时间。(一周) 5.动态规划:理解动态规划的思想,熟练应用长见的动态规划问题,比如训练指南上的问题。(一周) 6.练习搜索类型的题目,常用的剪枝优化方法,BFS。 了解双向广搜,迭代加深搜,A*。A掉10道左右题目(一周) 7. 字符串相关算法,比如KMP, trie,AC自动机,最长公共前最,常用的库函数(一周) 8. 数论相关:N个数最大公约数,最小公倍数,扩展欧几里得,素数判断,质因数分解,欧拉函数,矩阵运算,快速幂。(一周) 大数处理,打印表格。 时间比较紧张。。。
【搜索】[SCOI2009] 生日快乐 BZOJ 1024
[SCOI2009]生日快乐 BZOJ 1024 Time Limit: 1 Sec  Memory Limit: 162 MB Description windy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。windy主刀,每一切只能平行于一块蛋糕的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N 块蛋糕,windy必须切 N-1 次。为了使得每块蛋糕
HDU 3049 Data Processing 数论题解
2:6 又是一条数论题目,最近学习数论,看完书本感觉并不能掌握数论的,还是需要多多练习,多运用才能掌握这个思想武器的。 本题可以简单点过,不需要太高级的数论内容; 但是也可以运用数论的内容,可以应用上三个数论的内容: 1 扩展欧几里得 2 快速求模 3 乘法逆元(inverse of modulo) 2  快速求模,也可以生成一个数组,因为这里最大是40000,故此数值不大,可以使用数组,然后查表,速度很快。 但是这里使用快速的时间效率也几乎接近常数,没必要保存一个数组。如下面的
辗转相除法---欧几里得算法
的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式。 辗转相除法最早出现在欧几里得的几何原本中(大约公元前300年),所以它是现在仍在使用的算法中最早出现的。这个算法原先只用来处理自然数,但在19世纪,辗转相除法被推广至其他类型的数,如高斯整数和一元多项式。自此,现代抽象代数概念如欧几里得整环开始出现
AC自动机的一些题目及思路
即可。时间复杂度O(L)。 二、运用Fail 【例】BZOJ 2434 阿狸的打字机 题目大意: 给出一个打字机的操作序列(总长不超过10^5):在槽尾加一小写字母;删除最后一字母;槽不变,打印当前行。保证打印不超过N(1 <= N <= 10^5)次。给出M(1 <= M <= 10^5)个询问(x, y),查询第x次打印的串在第y次打印的串中出现了几次。 算法分析: 首先把这些串全部存起来是不现实的,那么我们想到使用Trie来存储,并建立成AC自动机。 我们把fail指针全部反向形成
zoj 1450 Minimal Circle(最小覆盖圆)
详见链接地址 我在纸上画了一遍,成功找到圆心~~~这个蛮理解的,自己画一遍就出来了。 测试了下时间复杂度,1.1W的点,最多循环次数在10+W,最少的2W左右,上面文章里也有简单证明,这个算法是O(n)的 后查了多个博客的算法,发现加个random_shuffle(p,p+n); 快了好多。可能数据不够随机吧。而且在BZOJ的这个,如果不随机,就过不去,估计是因为不是随机的,交换次数多然后精度损失了。BZOJ的数据卡精度的。 #include <queue> #include <stack
BZOJ】初级水列表——献给那些想要进军BZOJ的OIers
BZOJ初级水列表——献给那些想要进军BZOJ的OIers 顺便纪念我的BZOJ 50_Problems_ACCEPTED 代码长度解释一切! 注:以下代码描述均为C++ RunID User Problem Result Memory Time Code_Length 695765 Eolv 1000 Accepted 804 kb 0 ms 118 B 739478 Eolv 2463 Accepted 804 kb 0 ms 134 B 696662 Eolv 1968
[bzoj]bzoj题目汇总
啊。。终于把之前的文(fei)章(hua)补上来了。。。有种如释重负的感觉。。。 有很多都不需要我来讲解。。。 我网站这文章: 链接地址 下面是bzoj我做过的部分题目汇总 [SCOI2006]整数划分  链接地址 这道网上都说要尽量分给3。。。不然就分给2。。我也不知道为什么,最开始我还以为是尽量均分呢。。。 要用高精。 代码:链接地址 [SCOI2009]骰子的学问 链接地址 呃。。这道看看规律吧。。 这个blog写的很详细链接地址 代码:链接地址 [SCOI2009]粉刷匠 链接
BZOJ 3680 吊打XXX 模拟退火
首先这应该改名叫吊打出题人 题目大意:给定n个质点,求重心 这n个质点的重心满足Σ(重心到点i的距离)*g[i]最小 模拟退火的裸 尼玛交了两篇 死活过不去 各种改参数 最后发现是我的INF不够大 尼玛! 这INF开0x3f妥妥过不去。。。起码要max_of _long_long附近才可以 最后写了10188MS,BZOJ倒数第一……这也是种艺术啊0.0 #include<cmath> #include<cstdio> #include<cstring> #include
【BZOJ1011 || HNOI2008】遥远的行星
【题目描述】 直线上N颗行星,X=i处有行星i,行星J受到行星I的作用力,当且仅当i<=AJ.此时J受到作用力的大小为 Fi->j=Mi*Mj/(j-i) 其中A为很小的常量,故直观上说每颗行星都只受到距离遥远的行星的作用。请计算每颗行星的受力,只要结果的相对误差不超过5%即可. 搞笑 O(∩_∩)O 【简要分析】 看数据范围我就萎了, 然后 乱搞也只得10分 事实证明就是根据可以有5%的误差乱搞= = 这位仁兄推出了个式子(屌霸天)! 链接地址 设f[i]为第i个行星受到的引力,g[i
BZOJ 1088 水模拟
BZOJ水一道~ 枚举前两个位置是否放雷,模拟向下推,可以则ans++ #include "stdio.h" #include "string.h" int a[10010],b[10010],n; int judge() { int i; for (i=3;i<=n;i++) { b[i]=a[i-1]-b[i-1]-b[i-2]; if (b[i]<0) return 0; if (b[i]>1) return 0
POJ 1006 Biorhythms
,...,mk], i = 1,2,...,k 这里谈谈我自己的理解,就是通过不断的构造,Mi*(m/mi)=1(mod mi) 这个就是数论中求一个数关于mod的逆,具体可以参考有关数论的书 其中Mi*mi = m,m就是所有mi的乘积。。注意哦,这里各个mi必须互素,不然就失效。(如果不互素怎么办?那就化作互素呗,有兴趣可以参考数论的相关教材) 然后解就是ans = M1*m/m1*b1+M2*m/m2*b2……  (mod  m)     怎么理解最后一个式子呢,你想想。最后一个式子是不是mod mi