Can you answer these queries? 题目 给定N个元素，操作M次区间修改和区间查询，区间修改是把区间内所有元素各自进行开方，区间查询是查询这个区间的和。初始元素小于 分析 对于此题，开方的操作是很难上下传递的，而我们知道开方速度是很快的，我测了一下1e18开方只需要6次，所以我们完全可以使用暴力来修改，假如全都修改到了1，也就6*1e5的样子。对于区间和已经等于区间长度的，就不再往下递归进行修改了，因为没必要。 坑点 输入的区间不一定是前者小于后者每一组输出要多输出一个空行 AC代码 #include <iostream> #include <algo...

Count the Colors 题目 在[0,8000]区间进行N次区间染色，后涂的色可以覆盖之前涂的色，问N次染色之后，能看见的颜***间数量各是多少？ 分析 其实这题区间覆盖这部分很好做，不需要离散化，因为只有8000长度的区间。我们要注意的是，需要将区间改成左开右闭的形式，比如给[0,2]，[2,4]区间染色，要变成给[1,2],[3,4]染色。这样才不会有冲突。然后N次染色之后，将有色的区间进行统计一下，能合并的就合并。然后输出就可以了 AC 代码 #include <iostream> #include <algorithm> #include <ve...

Mayor's posters 题目 有一面墙，现在有M张海报要贴，海报的高度和墙的高度一样，每张海报会给出区间范围[l,r]，问最终墙上可见的海报有多少张？墙的宽度: 分析 首先这题的墙的范围很大，所以必须离散化，然后在离散化之后的数据上建立线段树。 要点 这题对于染色后连续的区间[l,r]有可能离散化会在建立线段树的时候分开，所以最好在区间[l,r]中间加一个点[l,mid,r]，这样如果染色[l,r]，就会pushdown到[l,mid],[mid+1,r]。 但是数据比较谁水，不加也能过 AC代码（无插点）插点也很简单 #include <iostream> #includ...

Just a Hook 题目 给定一个区间[1,N]，里面的元素都是1，现在有M次区间修改的操作，每次会选择一个区间将其置为1或2，或3，问最后区间[1,N]的元素总和为多少？ 分析 这是一道典型的区间覆盖问题，用线段树可以很好的解决。只需要在定义结点的时候，加上sum和tag就行。sum表示此结点对应区间的总和，tag表示要将其后代置为tag。tag = 1，2，3。所以pushdown和pushup就可以很容易想出来,具体看代码 AC代码 #include <iostream> #include <algorithm> #include <stdio.h&gt...

243. 一个简单的整数问题2 AC代码 #include <iostream> #include <cmath> #include <cstring> using namespace std; const int maxn = 1e6+10; typedef long long ll; const int mod = 1000000007; int N,M; int arr[maxn]; struct node{ ll l,r; ll sum,add; }tr[maxn*4]; void pushup(int u){ tr[...

Mysterious Bacteria 题目 意思就是给一个数x，现在要将它表示称次方形式，问最高能表示成多少次方？比如： 25 最高能表示成，它的次方形式表示最高是2次方 分析 这题最开始我写成了二分，按理说是可以过的，但是被WA飞了。好了，现在讲质因数分解做法。我们对N进行质因数分解的：那么如果我们想要讲底数变成一个数，那么我们可以将次方的gcd提取出来，将剩余的数相乘，就比如: 如果N是正数，那么答案就是质因数分解后各个质因数幂的gcd如果是负数，我们需要将上面得出的gcd减小到最大的一个奇数，so只要不断除以2就行，直到不能够再整除 AC 代码 #include <algorit...

GCD - Extreme (II) 题目 题意很简单，就是给定一个N，让求出N范围内的所有gcd（i,j）的和，时限：10s 分析 当我看见这题是时限我就觉得不简单，同时数据量N太大，都到4e6了。但是这题N范围内的答案都需要去求，因为这题没法在线处理，所以考虑暴力的优化。我们需要去枚举什么变量,可以发现两个数去找gcd是个非常麻烦的事，因为a的情况xb的情况的数量级就已经爆炸了。所以我们可以考虑枚举gcd去找a，b。 关于gcd，我们可以知道:是互质的，而互质我们可以想到欧拉函数。假如一个数b，b/c = a ，那么与a互质的共有E[a]个数，这些数乘以c之后与b的gcd就是c。所以我们就...

Harmonic Number 题目 分析 这题的打表比较有意思，一共有的计算量，这里有3秒的时限，是可以进行几次的的计算的，可是我们没办法开一个的数组来保存每一项的值，所以我们可以每隔50个打一个表，这样我们只需要进行一次的计算，之后次询问，每次我们只需要进行至多50次计算就可以了。 AC代码 #include <iostream> #include <algorithm> #include <stdio.h> using namespace std; typedef long long ll; ll T,N; double f[2000010]; ...

The Super Powers 题目 若x可以表示成两种及以上的幂形式，比如，被成为超级power数，现在让输出 范围内的所有超级power数 分析 有限其实就是unsinged long long 的最大值,大概1e19，我们是无法通过直接暴力枚举的，那么就考虑下是否可以优化，题目说到至少要有2个幂形式，所以中的y至少大于等于4，小于63(x = 1除外)。所以我们可以枚举x，,然后的y我们发现，只要y是一个合数，那么至少可以把表示成2种形式。因为x和y的范围都知道了，所以就可以开始枚举了。 关于log函数 当我们要求的y最大是多少，让其不超过unsinged long long的值，数学...

Farey Sequence 题目 F2 = {1/2}F3 = {1/3, 1/2, 2/3}F4 = {1/4, 1/3, 1/2, 2/3, 3/4}F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}Fn表示分子分母小于等于n不可约的分数，之后给n，让算出Fn一共有多少个不可约的分数 分析 不可约其实就是互质，而计算互质就很容易想到欧拉函数，所以这题打一个欧拉函数值的表，然后求个前缀和，就可以了 AC代码 #include <iostream> #include <algorithm> #include <s...

Fantasy of a Summation 题意 给你n,K,mod,让你计算上面代码的结果 分析 这题很明显不能直接暴力，而要从每个元素贡献方面着手，也就是算一下每个元素会被加多少次。 举个例子 以第二个样例为例：2 3 350001 2 1 2 1 2 1 2第二排的1，上面共有2条路径，下面有两条路径。所以就是条路径，转换成公式就是 所以总和就是: AC 代码 #include <iostream> #include <algorithm> #include <stdio.h> using namespace std; typedef long l...

Help Hanzo 题目 T组数据，每组数据给出a，b两个值，让求a<=x<=b中有多少个x是质数 分析 可以发现此题的a，b可以到2e9的范围，所以想要把这么大的范围质数筛选完是不可能的，筛质数有个常用的做法就是筛出sqrt(N)的质数，然后再用这些质数去筛后面的质数。所以我们先把2~2^16范围的质数筛选出来，我们对其之后的合数进行质因数分解 其中必定有一个质数是在2~2^16中，否则这个数一定是大于的，并不在范围内。 所以，我们可以用前预筛选出来的质数(大概6000个)，去对a,b区间去掉合数,这里因为a，b可能非常大，所以我们把[a,b]映射到[0,b-a]。如果我们可...

D - Pairs 题目描述 分析 我们知道这题的元素是,所以两个数的乘积就是,所以我们可以在范围二分输出答案。 举个例子 此数列中，, 假如我们现在二分到了mid = b这个值，第K个值指向这个位置，那么我们只要去判断小于mid的元素个数是否<K，若是则l = mid,之后l会一只往右移动，当仍保持这小于l的元素个数<K,最终l会因为二分走到，不会再离开这个区间了。而r最终也会遇到l，l == r 坑点 由于此题我是二分套二分的思路，而我大量使用了lower_bound和upper_bound，花了很长时间也没调出来，后来是手写的二分，结果还是调了很久，最后发现需要手动处理掉...

#给牛客的问题反馈和建议# 能在博客中加入置顶功能吗？