Sigma Function 题目 给定一个n<=1e12,求在n之前的正整数，有多少个约数之和为偶数。 分析 我在题目的公式上看了半天推不出结论来。此题十分适合打表观察规律，所以可以打表看看。打表结果： 1 : odd 2 : odd 3 : even 4 : odd 5 : even 6 : even 7 : even 8 : odd 9 : odd 10 : even 11 : even 12 : even 13 : even 14 : even 15 : even 16 : odd 17 : even 18 : odd 19 : even 20 : even 21 : even ...

Harmonic Number (II) 题目 给你上图所以函数，现在要算n<=1e9的结果，共T<=1000组 分析 我看网上好多人都做成了找规律，其实这是一个数学题，我参考了这位大佬的博客：传送门下面开始以图例方式讲解我们要求的结果其实就是下图中所有竖线的总长度然后我们知道这是一个反比例函数，其对称轴是y = x所以我们可以考虑只计算一半"面积"的方案。所以我们可以将下图计算结果*2然后再减去下图的计算结果，个长度就是 所以这里理解了，将很容易写出代码了 AC代码 #include <iostream> #include <algorit...

Goldbach's Conjecture 题目 T组询问，每组询问是一个偶数n,验证哥德巴赫猜想回答n=a+b且a，b(a<=b)是质数的方案个数. 分析 我们知道1e7之前有不到1e6个质数，所以我们用埃氏筛法预先把质数筛选出来，vis[]保存是否是质数，P[]从小到大保存质数。对于一个n，只需遍历质数表，假如遍历到P[i]，只需看n-P[i]是否大于P[i]，并且n-P[i]是质数，如果n-P[i]<P[i]直接break就行 AC 代码 #include <iostream> #include <algorithm> using namespace...

E - Leading and Trailing 题目 给定两个数n,k 求n^k的前三位和最后三位n是int范围， 分析 求后三位很简单，就是在快速幂的过程中模1000即可。但是求前三位就比较难处理了，用快速幂解决不了。这里我们可以考虑将其转换成double,如果可以转换成double计算，我们只要取出double结果的前三位就可以了。这里开始讲高中的数学导数：对于任意一个数，都可以转换成导数的形式，比如,所以这里的可以转换成.x表示次方的整数部分，y表示次方的小数部分,我们可以发现无非是将的小数点往右移动x位而已。所以我们只需要将的小数点往右移动2位，此时整数部分就有3位了，然后转换成in...

Pairs Forming LCM 题目 Find the result of the following code:A straight forward implementation of the code may time out. If you analyze the code, you will find that the code actually counts the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j).题意就是，这个函数的复杂度很高，让你写出一个程序来实现同样的功能。 分析 n 是a，b 的最小公倍...

Trailing Zeroes (III) 题目 You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 12...*N. For example, 5! = 120, 120 contains one zero on the trail.就是找最小的N，使得N！末尾有x个0，输出N，若不存在输出impossible 分析 其实这个题上个暑假就做过，但是当时求一个N！末尾0的个数怎么推...

Aladdin and the Flying Carpet 题目 给一对数字 a，b ，a是一个长方形的面积，问有多少种整数的边的组合可以组成面积为a的长方形，要求最短的边不得小于b。一共询问T<=4000次 分析 首先我们把面积进行质因数分解，得 所以其因子个数就是 此题目的就是让选出合法的因子，我们可以发现x*y = N，选x选y都一样，x!=y,所以本题答案就是 res = cnt/2-小于b的因子,因为本题只需要长方形，所以cnt/2，会自动把x*x = N这种情况去掉。 关于为何打一个小于1e6的质数表就够了 因为我们是要用质数表来选质因数分解，假如N中有且仅有一个因子x且大于...

坑点 cout 换行请用cout<<'\n',大量使用cout<<endl，评测机不好会导致超时(亲身经历 luogu P1440) 二分 二分过程最好用mid = (l+r)>>1 (l+r)/2 结果会舍去小数，也就是a+b是正数的时候，值变小，但是是负数的时候，值变大。 比如1.5,和-1.5 。所以对于结果是正数，是向下取整，是负数的话，是向上取整 (l+r)>>1 正宗的向下取整multiset 使用lower_bound 最好使用multiset自带的lower_bound,upper_bound也一样使用普通的lower_b...

数论定理 最大公约数gcd 对于多个数求gcd有 素数个数估计函数 表示[0,x]中有多少个素数 切比雪夫定理 对于所有大于1的整数n，至少存在一个质数p，符合n < p < 2n 数学公式 海伦公式求三角形面积 公式中a，b，c分别为三角形三边长，p为半周长，S为三角形的面积。 求卡特兰数 (递推方式) int N; ll f[maxn]; f[0] = 1;f[1] = 1; for(int i = 2;i<=N;i++){ for(int j = 0;j<=i-1;j++){ f[i] += f[j] * f[i-1-j]; }...

Bi-shoe and Phi-shoe 题目 给出n个数字的序列a[]，对于每个数字ai找到一个欧拉函数值大于等于ai的数bi，求找到的所有数bi的最小值之和sum 分析 这是第二次写关于欧拉函数的题，这是使用了欧拉函数打表的模板，然后再处理一下最优值就可以了，其实也可以排序之后用二分。 需要处理的地方： for(int i = 1;i<maxn;i++) mp[E[i]] = min(mp[E[i]],i)这一句是将欧拉函数值E[i]一样的,取i较小的那个for(int i = maxn-2;i>=1;i--) if(mp[i+1]) mp[i] = min(mp[i+1],m...

Parity game 题目 有一个长度为n的序列给出Q条限制l,r,str str==odd 表示[l,r]区间内的数的和是奇数，否则为偶数请你输出最小的不满足条件的编号-1（即最后一个满足的），如果全部满足，输出总数Q！ 分析 算是一个带权并查集的模板题。dis[i]记录他到根结点的距离，假如a，b现在已经加入并查集了，现在要查询a，b之间的奇偶，只需要abs(dis[a]-dis[b])，然后拿此结果与当前answer进行比较就行了。不匹配，就break。 坑点：c++的取余可以是负数，在比较奇偶时加上绝对值 AC代码 #include <iostream> #include...

Connections in Galaxy War 题目 假设有编号从0开始的n个点，每个点都有一个非负权值p[i]。现在有没有重边的m条边和Q个操作。对于操作有两种类型destroy a b 表示摧毁a,b点之间的边query a 表示从a出发能到的点中,权值比a大权值最大,在权值最大前提下编号最小的点。如果没有这样的点输出-1。 分析 此题如果在线处理询问的话，不得不面对一个问题，也就是并查集的拆分，拆分后维护就变得异常困难。所以我们可以将问题存储在栈里面，先处理好并查集的最终状态，然后反向处理，也就是相当于是合并，这是并查集所擅长的。有一点需要注意：map<pii,bool>...

Supermarket 题目 超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.每天只能卖一个商品.现在你要让超市获得最大的利润. 分析 首先涉及到最大利润，那么我们到方案要尽可能到让利润大的商品卖出去，可以考虑利润从大到小排序发现一些什么性质。当我们选择了当前利润最大的商品，我们需要考虑：1.查询他的当前截止日期，如果已经过期了，就不卖了。2.如果卖掉这个商品，截止日期在他之后的所有商品相当于保质期天数-1 并查集怎么去实现 这里有一点难思考，我们用一个数组fa[]来保存商品的截止日期，如果一件商品的截止日期是d，fa[d] = -1,就表示第d...

A Bug's Life 题意 题意很简单，就是给M组虫虫谁喜欢谁的关系，然后判断一下有没有同性恋的虫虫。坑点：每一组数据输出之后还需要输出一个空行 分析 此题我以前用过二分图来做，这里用带权并查集做。如果存在这么一串关系，x->y->z(x喜欢y，y喜欢z),然后存储x,y,z到根结点的距离，dis[x] = 0,dis[y] = 1,dis[z] = 2,如果此刻又来了一个喜欢关系x->z，我们发现dis[x]%2 == dis[z]%2，所以x,z他们是同性关系，所以发现了同性恋虫虫一句话：如果两个到根结点的距离是奇偶性相同的结点相爱，那么他两必定有一位是同性恋 AC代...