一:前置芝士: 1.树状数组(不会树状数组来打这个?(大雾 ) 2.主席树（不会主席树来打这个?(巨雾 ) 3.前缀和 (不会前缀和来打这个?(神雾 ） 4.权值线段树 (不会权值线段树来打这个?(仙雾) ) 5.看这篇文章的你需要用主席树将求区间kth练得比较熟，并且要理解其原理。 二:分(che)析(dan): 首先,我们知道,主席树其实是一颗具有n个根的树(介于树与森林之间)。第i个根所形成的树(为了简写,我们用T(i)表示)其实就相当于将序列1->i依次添加进一个权值线段树所形成的树。 我们又知道，权值线段树所储存的信息其实是它所管的区间中数字的数量，所以，对于区间l->r...

这是一个普通人都想得出来的超简单但很有用的优化。  -----序言  给一个题:   计算n!的阶乘,n<=10000，时限500ms。   一.各种算法 要是你打普通高精乘低精,辣么恭喜您GG，要是您不爽时限，给他加大成1000ms，恭喜您,还是GG。   于是，您就可以光荣的放弃打普通高精乘低精的想法，于是您注意到，当n=10000时，2s还是跑得动的。   于是，您决定打表...然鹅，毒瘤的题中，当n=10000时,|ans|=35660，然后。。。打表GG。   于是您又灵机一动，决定分块打表。您发现，n=1000时，500ms可以轻松跑动，于是就诞生了此题的分块打表法:打表出n...

update:添加了数学公式markdown 洛谷博客地址：https://www.luogu.com.cn/blog/KingofNight/post-shuo-lun-zheng-shuo-fen-kuai-ji-yang-xi-zheng-ming 一.复杂度证明 引理一:对于任意一个正整数$x$,$[\frac 的种类的数量在$\sqrt$级 证明:将$d$分为小于等于$\sqrt\(与大于\)\sqrt$的两部分 1.当$d\leq\sqrt$时: 假设每个$[\frac]\(都不一样,最多也就\)\sqrt$个值 2.当$d>\sqrt$时: \([\frac{x}{d}]&...

此题其实比较水的。。。   首先我们来分析题目，我们假设，贝茜和艾尔西在i点相遇后贝西开始扛艾尔西，那么代价为多少呢？   显然，代价=贝茜到i点的最小代价+艾尔西到i点的最小代价+贝茜和艾尔西一起到n点的最小代价。   我们分开解决，首先贝茜到i点的最小代价=走的最少步数*b，而走的步数，我们跑一遍以spfa(1)就可以轻松求出来了！   同理。艾尔西，我们跑spfa(2)就可以求出，而共同走到n，我们跑spfa(n)即可~   意思是，我们先跑三遍spfa:spfa(1),spfa(2),spfa(n),分别求出1到i的步数,设为dis[i][1].2到i的最小步数,设为dis[i][2]...

这题，主要是维护平方和来判断区间是否连续，但这里任然有两个问题：   1.值域为1e9，极限下，long long是一定会爆炸的   2.正如讨论区的，平方和可以被hack   那么该如何解决这个问题呢？   我的想法是——离散化！   离散化后，值域的极限就在1e6，假设这5e5个数，每个都是1e6，平方和也才5e17，long long是不会爆炸的。   离散化后，虽说hack的几率就减小了，但是，为了准确性，我们可以同时再维护个和(我觉得，这样应该很难被hack了吧。。。)   所以我们完成这题，可以先将原数，以及opt==1时的数字离散化一波，再进行操作！   具体的操作跟其他题解差不...

#include<bits/stdc++.h> using namespace std; const int N=100001; int a[N],b[N],c[N]; inline string zhuan(int x){//int转化string  string ant=""; while(x){ ant=char(x%10+'0')+ant; x/=10; } return ant; } inline bool cmp(string x,string y){//比较两个高精string数的大小  int len=x.size(),ten=y.size();...

这玩意儿,效率一般...     本来估摸复杂度为O(nlogn),但似乎用stl后更高?   代码:   //#pragma GCC optimize()//手动Ox优化 #include<bits/stdc++.h> using namespace std; const int N=1e5+1; vector<int>s; int siz; int main(){     int n;     scanf("%d",&n);     for(int i=1;i<=n;++i){         int x;         scan...

#include<bits/stdc++.h> using namespace std; const int N=1e8+1; int las[N],nex[N],sta[N],top; bool f[N]; inline void fsbz(int maxe){     int over=sqrt(maxe);     for(int i=2;i;i=nex[i]){         if(i>over){     &nbsp...

推导   假设,我们已经求出有一对x,y满足ax+by=gcd(a,b)。   我们想要求最小非负整的x,那么必须要减去一个能减的 最大值,我们设减去一个D,则方程变为: a(x-D)+by+aD=gcd(a,b)   整合一下： a(x-D)+b(y-aD/b)=gcd(a,b)   我们知道,gcd(a,b)是整数,我们假设aD/b不为整数。 则对应的’y’(现在的y)为小数,不成立,所以aD/b是整数 即aD%b=0。   又因为aD%a=0,所以aD一定而且只需是a,b的倍数,所以aD=k(Lcm(a,b))=abk/gcd(a,b)   两边同时除a   D=k*b/gcd(a,b)...

本题解讲的是快速暴力组合数的方法，需要知道以下知识(能做此题的大佬应该都知道吧。。。)：   欧拉筛，组合数公式,卡速米(这个应该没人会吧？) 否则将引起不适   设π(x->y)为从x连乘到y(数学公式编译器崩了。。。)   组合数，大家都知道，公式为C(n,m)=!n/(!m*!(n-m)) 我们将它化简一下:π(m+1->n)/!(n-m)(当然,如果n-m>m,我们可以将m替换为n-m进行优化)    然后，我们手算是将所有数列举出来再一一 **约分** ，   我们知道，约分就是约掉分子分母的公因数，   那么如果我们将分子分母的数全部转换成几个质数相乘的形式，然后...

看了此题,发现是求中位数,自然而然的想到了求kth   求kth有多种,我用的是权值线段树,即记录x的个数,但,我们看题，发现a[i]可以高达1e9,一个数组是开不完的,   不过万幸的是n只到了1e5,而求kth只需要知道大小关系就行,不需要知道具体的值,所以,我们可以用离散化来搞定它！    这里说一下stable_sort,它其实跟sort差不多,不过区别在于相同元素sort后的值是一样的！所以stable_sort极适合用于离散化    那么问题来了,假如我们用离线算法,各种判断,骚操作,眼花缭乱,本蒟蒻的内心qwq 所以,我们可以考虑在线算法！    我们动态将此时的a[i] (离散...

这题其实就是高斯求和问题，即1+...+x=x（x+1）/2。   由此，我们就可以用递推的思想来解决问题：   include<bits/stdc++.h> using namespace std; int main() { //freopen("ask.in","r",stdin); //freopen("ask.out","w",stdout); long long n,r=0; cin>>n; for(int i=1;i<=999;++i) { r+=i; if(r==n) {...

这道题,发现暴力能过时,喷了3k的血。。。本人花了近半小时打表找规律。。。然后真找出来一些了。。。   1.f[x^n]=f[x]*(x^(n-1))   2.设x,y为不相同的质数,则f[x^a*y^b]=lcm(f[x^a],f[y^b])。   3.对于一个质数x,他的f[x]极小(似乎都很小??)   对于一个n,我们就可以将他进行质因数分解:设n=x^ay^b...   然后我们暴力求出f[x],f[y],套上规律一,求出f[x^a],f[y^b],再套规律二,就可以求出来了。。。   分析:因为n<=706150,所以我们最多只需要暴力7个素数,而经试验,每个素数的f最多只有...

提供一个新思路   这题,我们假设n个数分别为a1,a2,a3,a4,a5...an,且对于任意   1<=i<j<=n满足ai<aj   而他们两两之和即为输入的各数字,从中,我们不难推出对于输入的数字中(我们把它们按从小到大排序,分别设为m1,m2...)   一定满足:m1=a1+a2,m2=a1+a3(我们可以用反证法证明结论)   但m3有两种情况:m3=a1+a4或者m3=a2+a3,我们无法判断,那么,   为什么我们不能把a2+a3的情况排除呢？   所以我们可以这样做: 同样枚举a1(1->m1/2),然后算出a2,a3。这时,我们对a2+a3的...