DZY 's BLOG

求树上路径第k大。

主席树。从根往孩子建。查询(x,y)路径时，在第x棵主席树+第y棵主席树-两倍的第lca(x,y)棵主席树上查询即可。还要特判一下lca(x,y)这个节点。

我写的速度慢出翔。QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010,maxm=500010,maxt=4000100;
int p[maxm],n1[maxm],h[maxn],T[maxn],lc[maxt],rc[maxt],s[maxt],a[maxn],bin[maxn];
int val[maxn],anc[maxn][20],dep[maxn],LcaVal,tot=0,ee=0,n,m,q[maxn],vis[maxn]={0};
char buf[8000000],*pt=buf,*o=buf;
inline int getint(){
    int s=0; while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s;
}inline void print(int x){
    char str[12],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;};
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}void build(int l,int r,int &x){
	s[x=++tot]=0;
	if(l==r)	return;
	int mid=l+r>>1;
	build(l,mid,lc[x]);
	build(mid+1,r,rc[x]);
}void modify(int p,int v,int l,int r,int &x){
	s[x=++tot]=s[p]+1;
	lc[x]=lc[p];
	rc[x]=rc[p];
	if(l==r)	return;
	int mid=l+r>>1;
	if(v<=mid)	modify(lc[p],v,l,mid,lc[x]);
	else		modify(rc[p],v,mid+1,r,rc[x]);
}int ask(int a,int b,int c,int l,int r,int k){
	if(l==r)	return l;
	int cnt=s[lc[a]]+s[lc[b]]-(s[lc[c]]<<1),mid=l+r>>1;
	if(LcaVal>=l && LcaVal<=(l+r>>1))	cnt++;
	if(k<=cnt)	return ask(lc[a],lc[b],lc[c],l,mid,k);
	else		return ask(rc[a],rc[b],rc[c],mid+1,r,k-cnt);
}int lca(int u,int v){
	if(dep[u]<dep[v])	swap(u,v);
	int k=dep[u]-dep[v],j=0;
	while(k){
		if(k&1)	u=anc[u][j];
		k>>=1,j++;
	}if(u==v)	return u;
	for(int i=16;~i;i--)
		if(anc[u][i]!=anc[v][i])	u=anc[u][i],v=anc[v][i];
	return anc[u][0];
}int main(){
	fread(buf,1,8000000,stdin);
	n=getint();	m=getint();
	for(int i=1;i<=n;i++)	bin[i]=a[i]=getint();
	memset(h,-1,sizeof(h));
	int x,y;
	for(int i=1;i<n;i++)	ae(getint(),getint());
	sort(bin+1,bin+n+1);
	for(int i=1;i<=n;i++)	a[i]=lower_bound(bin+1,bin+n+1,a[i])-bin;
	build(1,n,T[0]);
	int head=0,tail=1;
	q[0]=vis[1]=dep[1]=1;
	modify(T[0],a[1],1,n,T[1]);
	while(head<tail){
		int u=q[head++];
		for(int i=h[u];~i;i=n1[i]){
			if(!vis[p[i]]){
				modify(T[u],a[p[i]],1,n,T[p[i]]);
				vis[p[i]]=1;
				dep[p[i]]=dep[u]+1;
				anc[p[i]][0]=u;
				q[tail++]=p[i];
			}
		}
	}for(int j=1;j<=16;j++)	
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	int la=0,z,k;
	while(m--){
		x=getint();	y=getint();	k=getint();
		z=lca(x,y);
		LcaVal=a[z];
		if(x==y)	print(bin[a[x]]);
		else	print(bin[ask(T[x],T[y],T[z],1,n,k)]);
		if(m)	*o++='\n';
	}return fwrite(buf,1,o-buf,stdout),0;
}

构造一个n×n的矩阵A。其中A[i][j]=gcd(i,j)。求A的行列式。n<=200w。

一看就不能暴力嘛。

暴力一下求了几个值放到OEIS上查。

结果惊呆了。

然后欧拉筛出phi。然后就行了。

（求大神告诉我这是为什么）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int flag[2000010],n,m,cnt=0;
long long prime[500000],phi[2000010],maxn=0,an[500010];
char buf[5000000],*o=buf,*pt=buf;
inline long long getint(){
    long long s=0; while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s;
}inline void print(long long x){
    char str[12],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}*o++='\n';
}int main(){
	fread(buf,1,5000000,stdin);
	n=getint();	for(long long i=1;i<=n;i++)	an[i]=getint(),maxn=(an[i]>maxn)?an[i]:maxn; 
	memset(flag,0,sizeof(flag));
	for(int i=2;i<=maxn;i++){
		if(!flag[i])	prime[cnt++]=i,phi[i]=i-1;
		for(int j=0;j<cnt&&prime[j]*i<=maxn;j++){
			flag[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}else	phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}phi[1]=1;
	for(int i=2;i<=maxn;i++)	phi[i]=phi[i-1]*phi[i]%1000003;
	for(int i=1;i<=n;i++)	print(phi[an[i]]);
	return fwrite(buf,1,o-buf,stdout),0;
}

晚上看了会儿线代。

行列式的算法好多。可以根据2×2的矩阵行列式计算方法递归。可以用排列、逆序对的神方法算。

效率比较高的应该是基于行变换的一种算法。

令A为一个方阵。

(a). 若A的某一行的倍数加到另一行得矩阵B，则detB=detA.

(b). 若A的两行互换得矩阵B，则detB=-detA.

(c). 若A的某行乘以k倍得到矩阵B，则detB=k*detA.

如果A为三角阵，则detA等于A的主对角线上元素的乘积。

那么我们只需要通过(a)(b)两种变换得到三角阵，计算m=主对角线上元素的乘积。

如果进行了n次(b)操作，那么detA=(-1)^n * m.

可以发现和高斯消元法还是有一些联系的。这种计算行列式的复杂度是O(n^3)。

这道题的题意就是求无向图的生成树个数。

用行列式计算。先构造Kirchhoff矩阵。

NOI2007《生成树计数》中有涉及到Kirchhoff矩阵。详细证明戳进来。

按照这个方法构造。剩下的就是计算行列式了。

可以用double储存。这样(b)操作方便一些。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double a[20][20];
#define eps 1e-15
inline int dcmp(double p){
        if(fabs(p)<eps)return 0;
        return p>eps?1:-1;
}inline void gauss(int n){
	double tmp=1.0,an=1.0,p;
	for(int i=1,pos;i<=n;i++){
		for(pos=i;(!dcmp(a[pos][i]))&&pos<=n;pos++);
		if(pos>n)	continue;
		for(int j=i;j<=n;j++) swap(a[pos][j],a[i][j]);
		for(int j=i+1;j<=n;j++){
			if(dcmp(a[j][i])){
				if(dcmp(a[i][i])==0||dcmp(a[j][i])==0){	printf("0\n");	return;}
				tmp*=(p=a[i][i]/a[j][i]);
				for(int k=i;k<=n+1;k++) a[j][k]=a[i][k]-a[j][k]*p;
			}
		}
	}for(int i=1;i<=n;i++)	an=an*a[i][i];
	if(n&1)	an*=-1;
	printf("%.0lf\n",fabs(an/tmp));
}int main(){
	int n,m,x,y,tc;	scanf("%d",&tc);
	while(tc--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	a[i][j]=0;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			a[x][y]=a[y][x]=-1;
			a[x][x]+=1;	a[y][y]+=1;
		}gauss(n-1);
	}return 0;
}

题意：给定一颗树。询问一个子树中第k大的节点。

【终于在0:02的时候A掉了=。=】

这几天复习一下数据结构。先复习POJ2104。写可持久化线段树练手先。

然后到了这道题。其实也蛮裸的。

先求出dfs序。记录每个节点开始和结束的时间戳。然后就相当于每个点开始到结束这个区间里求第2*k大。

然后就是一个主席树了。

根据JC大神的指点结束的时间戳不用占位置了，根据下一个开始的时间戳减一就行。这样可以省一半的空间，也可以省很多时间。

由于spoj太慢加了一个read。后来一不小心就A了。速度还行吧。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int w[200010],lc[2100010],rc[4100010],bin[100010],p[200010],n1[200010],h[100010],ee=0,tot;
int id[100010],sum[2100010],T[100010],num[100010],begin[100010],end[100010],n,c=0;
void read(int &x){
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-48;
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}void dfs(int u,int fa){
	num[begin[u]=++c]=w[u];
	for(int i=h[u];~i;i=n1[i])	if(p[i]!=fa)	dfs(p[i],u);
	end[u]=c;
}void build(int l,int r,int &rt){
	rt=++tot;	sum[rt]=0;	if(l==r)	return;	int m=l+r>>1;
	build(l,m,lc[rt]);	build(m+1,r,rc[rt]);
}void modify(int p,int v,int l,int r,int &rt){
	rt=++tot;	sum[rt]=sum[p]+1;	lc[rt]=lc[p];	rc[rt]=rc[p];	
	if(l==r)	return;	int m=l+r>>1;
	if(v<=m)	modify(lc[p],v,l,m,lc[rt]);
	else		modify(rc[p],v,m+1,r,rc[rt]);
}int ask(int L,int R,int l,int r,int k){
	if(l==r)	return l;	int cnt=sum[lc[R]]-sum[lc[L]],m=l+r>>1;
	if(k<=cnt)	return ask(lc[L],lc[R],l,m,k);
	else		return ask(rc[L],rc[R],m+1,r,k-cnt);
}int main(){
	read(n);	memset(h,-1,sizeof(h));
	for(int i=1;i<=n;i++)	read(w[i]),bin[i]=w[i];
	sort(bin+1,bin+n+1);
	int x,y;
	for(int i=1;i<=n;i++){	w[i]=lower_bound(bin+1,bin+n+1,w[i])-bin;id[w[i]]=i;}
	for(int i=1;i<n;i++)	read(x),read(y),ae(x,y);
	dfs(1,0);	build(1,n,T[0]);
	for(int i=1;i<=n;i++)	modify(T[i-1],num[i],1,n,T[i]);
	int	q;	read(q);
	while(q--){
		read(x);read(y);
		printf("%d\n",id[ask(T[begin[x]-1],T[end[x]],1,n,y)]);
	}return 0;
}

求两个串的最长公共子串。串长250000。

很像上一道题处理d[i]数组。

给第一个串建后缀自动机。

第二个串在上面跑即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510010;
char buf[maxn],*pt=buf;
int l[maxn],fa[maxn],c[maxn][26],rt=1,tot=1,tail=1;
void add(int x){
    int p=tail,np=++tot,r,q;
    l[np]=l[p]+1;   tail=np;
    for(;p&&!c[p][x];p=fa[p])   c[p][x]=np;
    if(!p){ fa[np]=rt;   return;}
    if(l[p]+1==l[q=c[p][x]]){   fa[np]=q;   return;}
    fa[r=++tot]=fa[q];  memcpy(c[r],c[q],sizeof(c[r]));
    l[r]=l[p]+1;    fa[np]=fa[q]=r;
    for(;p&&c[p][x]==q;p=fa[p]) c[p][x]=r;
}int main(){
    fread(buf,1,510000,stdin);  char ch;
    while((ch=*pt++)!='\n') add(ch-'a');
    int p=rt,k=0,x,An=0;    
    while((ch=*pt++)!='\n'){
        if(c[p][x=ch-'a'])    ++k,p=c[p][x],An=max(k,An); else{
            for(;p&&!c[p][x];p=fa[p]);
            if(!p)  p=rt,k=0;   else    k=l[p]+1,p=c[p][x],An=max(k,An);
        }
    }printf("%d\n",An); return 0;
}