无    2018-02-02 13:42:26    237    0    0

Description


题面可以搓->[这里]

已知平面内 N 个点的坐标,求欧氏距离下的第 K 远点对。


Solution

旋转卡壳的方法被Cls一秒钟驳回了。
考虑暴力求出n2个点对距离,维护一个2k大小的小根堆,堆顶就是答案了。
直接求肯定超时,可以用KD-Tree来优化暴力~
每次对一个点在KD-Tree上求其与所有点的距离(过程就是求最远点的距离,能入堆就入堆,不能可以直接结束访问)。呃为什么看起来就是暴力啊......
打完就A辣真高欣♪(^∇^*)


  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <queue>
  4. using namespace std;
  5. typedef long long LL;
  6. const LL inf = 1e15;
  7. const int N = 1e5 + 50;
  8. struct P {int d[2];} p[N], v; int n, k, D;
  9. priority_queue <LL, vector<LL>, greater<LL> > q;
  10. inline LL pow(LL x) {return x * x;}
  11. inline LL min(LL a, LL b) {return a < b ? a : b;}
  12. inline LL max(LL a, LL b) {return a > b ? a : b;}
  13. inline bool cmp(P a, P b) {
  14. return a.d[D] == b.d[D] ? a.d[!D] < b.d[!D] : a.d[D] < b.d[D];
  15. }
  16. template <class T> inline void in(T & x) {
  17. x = 0; int f = 1; char ch = getchar();
  18. for (; ch < '0' || ch > '9';) {if (ch == '-') f = -1; ch = getchar();}
  19. for (; ch >= '0' && c
无    2018-01-24 20:25:20    127    0    0

由于博主们(?)都很良心没有扯杂七杂八的东西,所以我也不啰嗦了。

标注[1]:后缀数组图片支持来自于[这位大佬]

标注[2]:基数排序图片支持来自于[这位大佬]

基数排序

大佬请跳过。
是一种稳定的、Θ(n)级别的排序方式,这年头极好用的。
现有一组数据:73,14,81,22,55,65,43,28,39,93
我们首先只按照个位数进行桶排序,并相应记录下标,仍然得到一个无序数列。

图片标题

然后在此次的基础上只考虑十位数进行排序。我们发现这成了一个有序数列!

图片标题

依次类推,如果有百位数、千位数,同样排序至最高位。

  • 显然也可以从高位排起。

实现

所谓SA

有必要在开头就阐明的东西:

  • SA(Suffix Array)数组:排名为i的后缀是[SA[i],n)
  • Rank数组:[i,n)后缀的排名为i(求的过程中直接离散化)

所谓后缀数组就是指SA,由于SARank的反函数,所以任意得到一个都可以在Θ(n)的时间内得到第二个。

先展示代码如下:

  1. inline int cmp(int *f,int x,int y,int w) {return f[x]==f[y]&&f[x+w]==
无    2018-01-18 19:11:35    234    0    0

题目描述

提交可以搓->[这里]

某人在玩一个非常神奇的游戏。这个游戏中有一个左右各n个点的二分图,图中的边会按照一定的规律随机出现。
为了描述这些规律,某人将这些边分到若干个组中。每条边或者不属于任何组(这样的边一定不会出现),或者只属于一个组。
有且仅有以下三类边的分组:

  • 这类组每组只有一条边,该条边恰好有50%的概率出现。
  • 这类组每组恰好有两条边,这两条边有50%的概率同时出现,有50%的概率同时不出现。
  • 这类组每组恰好有两条边,这两条边恰好出现一条,各有50%的概率出现。

组和组之间边的出现都是完全独立的。
某人现在知道了边的分组和组的种类,想要知道完美匹配数量的期望是多少。你能帮助她解决这个问题吗?


做法可以说是非常玄学的了......

考虑将两条边一组的拆了,用有25%(-25%)的概率同时出现来弥补多(少)算的。
然后就是求完美匹配期望了。
实不相瞒,如果真的考这道题我说不定连单纯的完美匹配数都不会求......23333

  1. #include<cstdio>
  2. #include<map>
  3. using namespace std;
  4. typedef long long LL;
  5. const int N=16,Mod=1e9+7;
  6. const int inva=Mod+1>>1,invb=Mod+1>>2;
  7. int n,m,tot;map<int,int> f[1<<N];
  8. struct E {int S,p,c;} e[N*N<<2];
  9. inline void Add(int &x,int add) {x=(x+add)%Mod;}
  10. inline void in(int &x) {
  11. x=0;int f=1;char ch=getchar();
  12. for(;ch<'0'||ch>'9';) {if(ch=='-') f=-1;ch=getchar();}
  13. for(;ch>='0'&&ch<='9';) x=x*10+ch-'0',ch=getchar();x*=f;
  14. }
  15. inline int dfs(int S) {
  16. if(!S) return 1;
  17. int T,T0=S>>n,S0=S^(T0<<n);
  18. if(f[
无    2018-01-17 21:00:10    228    0    0

题目描述

提交可以搓->[这里]

战线可以看作一个长度为n的序列,现在需要在这个序列上建塔来防守敌兵,在序列第i号位置上建一座塔有Ci的花费,且一个位置可以建任意多的塔,费用累加计算。有m个区间[L1,R1],[L2,R2],,[Lm,Rm],在第i个区间的范围内要建至少Di座塔。求最少花费。


根据线性规划不是裸题就是神题定律,此题是一道裸题。
如题目给出的那样建立线性规划,然后用对偶型求解。
发现了一种快一点的打faOvO

  1. #include<cstdio>
  2. #include<cmath>
  3. using namespace std;
  4. const int N=1005,M=10005;
  5. const double inf=1e20,eps=1e-8;
  6. int n,m,top,q[M];double A[N][M];
  7. inline int read() {
  8. int x=0,f=1;char ch=getchar();
  9. for(;ch<'0'||ch>'9';) {if(ch=='-') f=-1;ch=getchar();}
  10. for(;ch>='0'&&ch<='9';) x=x*10+ch-'0',ch=getchar();x*=f;
  11. return x;
  12. }
  13. inline void pivot(int l,int e) {
  14. double t=A[l][e];A[l][e]=1,top=0;
  15. for(int i=0;i<=n;++i) A[l][i]/=t;
  16. for(int i=0;i
无    2018-01-17 20:55:45    234    0    0

题目描述

提交可以搓->[这里]

3N个数,你需要选出一些数,首先保证任意长度为N的区间中选出的数的个数K个,其次要保证选出的数的个数最大。


由于线性规划除了裸题就只有神题,所以这道题是个裸题。
实际上它已经将A、B、C三个矩阵描述得很清楚了。
若用usedi表示第i个数是否被选,被选为1,否则为0,有:
最大化:

i=1xusediVi

其中满足约束:

i=12n+1j=ii+n1usediKused1,used2,......0

可以直接用单纯形来解。

无    2018-01-17 07:34:09    192    0    0

题目描述

提交可以搓->[这里]

给出一个带权的连通无向图,对于其中的每条边i,在原来边权的基础上,其边权每增加1需要付出的代价为Ai,边权每减少1需要付出的代价为Bi,现在指定该图的一棵生成树,求通过修改边权,使得该生成树成为图的一棵最小生成树,需要付出的最少总代价。


显然树上边只要减,非树边只要加。
一条边i(u,v)被选在最小生成树中的条件是:u,v之间没有路径j比这条边更短。
于是我们就有了一组式子:wixiwj+xj,即:xi+xjwiwj
最小化的就是iTreecixi,单纯形对偶xing求解。

考虑将kb的诗改编一下:单纯形,你单纯地很行。

  1. #include<cstdio>
  2. #include<cmath>
  3. using namespace std;
  4. const int N=1005,M=4005;
  5. const double eps=1e-7,inf=1e10;
  6. struct G {int u,v,w,op;} g[N];
  7. struct E {int v,w,id,nt;} e[N];
  8. int n,m,tot,cnt,h[N],fa[N],dep[N],val[N],pos[N];double ans,B[M],C[N],A[N][M];
  9. inline void add(int u,int v,int w,int id) {
  10. e[++tot]=(E){v,w,id,h[u]
无    2018-01-16 13:15:58    71    0    0

题目可以搓->[这里]

这是一道luo题,题目要求:

最小化:

i=1Mcixi

满足:

j=1Maijxjbix1,x2,x3.....0

这里的aij表示[LxjiRxj]。就是一道线性规划裸题。最大化只要求它的对偶线性规划:

最大化:

i=1Mbixi

满足:

i=1Maijxicjx1,x2,x3......0

然后我们就可以直接上单纯形求解了呀~
发现单纯形跑得好慢QwQ......

  1. #include<algorithm>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<cmath>
  5. using namespace std;
  6. const int N=1005,M=10005;
  7. const double eps=1e-7,inf=1e10;
  8. int n,m;double ans,B[M],C[N],A[M][N];
  9. inline int in() {
  10. int x=0,f=1;char ch=getchar();
  11. for(;ch<'0'||ch>'9';) {if(ch==
无    2018-01-14 20:25:58    181    0    0

题目可以搓->[这里]

其实并不是一道很难的题,只要会打LCT和一点点生成函数(或者说只要记得这两个函数的生成函数形式的话)最多两个小时应该就可以AC了?然而我对泰勒展开什么的一窍不通啊......

首先,根据基本的生成函数,我们可以知道:

ex=iZxii!sin(x)=iZ(1)ix2i+1(2i+1)!

然后接下来的做法可以说是非常暴力了。
注意到大家的智商(?)只有[0,1],指数级增长的话在十几项之后就趋近于0了,经过实验(?)维护到第1517项可以满足精度。
怎么维护呢?又是一个很给力的答案:根据二项式定理,对每对(A,B)用组合数暴力计算维护。
接下来就是裸的LCT操作,计算答案时一个个加上就好了。

cy叫我衡量一下Thuwc的难度......只看这一道题的花......除了不会它们的生成函数表达式之外......这道题的难度在哪里......?而且据说现场还有个栏目叫做“小R教你学数学”,把泰勒展开式写在里面了......

  1. #include<algorithm>
  2. #include<cstring>
  3. #include<cstdio>
  4. using namespace std;
  5. #define swap(a,b) tmp=a,a=b,b=tmp
  6. #define get(x) (t[(t[(x)].f)].c[1]==(x))
  7. c
无    2018-01-14 17:40:19    28    1    1
这个是连浅谈都不敢直接讲了......
剧毒

写在前面

关于置换群和Po´lya定理,曾今第一次翻的时候除了懵逼还是懵逼,然后发现现在一看居然懂了一点......所以随便写一写吧,以后应该是会改的。
相比于直接给出定理,私下更喜欢证明和推导过程,如果您不感兴趣,自然也可以跳过,只知道定理是不影响解题的。


概念性的东西总是要放在最前面。请至少对概念有个印象,以便于提到时如果想不起来至少知道到哪里翻。


群的定义

给定一个集合G={a,b,c...}和集合G上的二元运算,并满足:

  • 封闭性:a,bG,cG,ab=c
  • 结合律:a,b,cG,(ab)c=a(bc)
  • 单位元:eG,aG,ae=ea=a
无    2018-01-12 20:49:16    182    0    0
为什么是浅谈呢,还是因为我也不是很会
主要是数学什么的太高深了,所以等以后我觉得自己会了再写一遍吧......

写在前面

利用FFT可以加快卷积的速度。再离散正交变换的理论中,已经证明在复数域内,具有循环卷积特性的唯一变换是DFT(Discerte Fourier Tansform),所以,FFT是更简单、最高效的离散正交变换。但是众所周知,由于涉及到复数即大量浮点数的运算,FFT(Fast Fourier Transform)无论是速度还是精度都是一个问题。

在需要很准确的精度或者需要支持取模的时候就得用到数论来代替它了,名字叫做NTT(Fast Number-Thearetic Transform)。

其中关于原根的解释以及证明我也不是很能搞得懂......不过鉴于是信息学奥林匹克竞赛选手,可以先不了解其证明,知道运用就OK了。


Fast Fourier Transform实现原理

学过了Fast Fourier Transform之后我们可以发现,FFT实现的主要依据就是ωn的三个性质

  • ωnn=1
  • ωn0,ωn1......ωnn1互不相同
  • ωn2=ωn/2,ωdndk=ωnk,
1/2