此博客停更

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4373

强制在线。。只能想到数据结构-。-

标算表示想不到-。-||| %Claris

我的做法是，用线段树维护区间最小值，区间哈希值，哈希采用平方和的方法(from 比利)，对于一个知道了首项和公差的等差数列，其数列

$hash 值= n·a[1]·a[n]+ \frac{n(n-1)(2n-1)·k^2}{6}$

然后。。

-->http://www.lydsy.com/JudgeOnline/problem.php?id=2657

嘛，两个三角形最多只有一条公共边-。-，然后以每个三角形为顶点与相邻的三角形连边，这样构成一棵树。。然后跑直径就好了

$O(N)$

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 200010
int i,j,k,m,n,x,y,cnt,last[N],z,who,dep[N],Dep;
struct edge{int to,next;}e[N<<1];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt,e[++cnt]=(edge){u,last[v]},last[v]=cnt;}
struct Edge{int l,r;bool operator <(const Edge&b)const{return(l<b.l)||(l==b.l)&&(r<b.r);}};
map<Edge,int>mp;
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa)dfs(y,x);
	if(Dep<dep[x])Dep=dep[x],who=x;
}
inline void Add(int x,int y){
	if(mp[(Edge){x,y}]!=0)add(mp[(Edge){x,y}],i),mp[(Edge){x,y}]=0,mp[(Edge){y,x}]=0;
	else mp[(Edge){x,y}]=i,mp[(Edge){y,x}]=i;
}
int main(){
	for(n=read(),i=1;i<n-1;++i){
		x=read(),y=read(),z=read();
		Add(x,y),Add(x,z),Add(y,z);
	}
	dfs(1,0),Dep=0,dep[0]=0,dfs(who,0);
	printf("%d",Dep);
}

-->http://www.lydsy.com/JudgeOnline/problem.php?id=2226

跟比利做题时不时就会出现这种我还没做过的题$0.0$

$O(T\sqrt n)$

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000010
#define ll long long
int i,j,k,m,n,x,y,T,phi[N],o;ll ans;
int main(){
	phi[1]=1;
	for(i=2;i<=N;++i)if(!phi[i])for(j=i;j<=N;j+=i){
		if(!phi[j])phi[j]=j;
		phi[j]=phi[j]/i*(i-1);
	}
	for(ans=0,T=read();T--;){
		for(ans=0,n=read(),o=sqrt(n),i=1;i<=o;++i)if(n%i==0){
			if(i!=1)ans+=1ll*i*phi[i]/2;
			else ans+=1;
			if(i*i!=n)ans+=1ll*n/i*phi[n/i]/2;
		}
		printf("%lld\n",1ll*ans*n);
	}
}

-->http://qiancl.is-programmer.com/user_files/qiancl/Image/Problem%204289.%20--%20PA2012%20Tax.html

PA的题短小精悍-。-

考虑每条边建立一个点，边与边的转移可以通过枚举中间点，把与中间点有关的边暴力抠出来排序，从小到大加，从以中间点为终点的向以x点为起点的连边，边权为原边权，再连向下一条，边权是与上一条的差，再与上一条连边权为0的边，图构好后，直接跑最短路就行了

#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define ll long long
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 200010
#define pk push_back
const ll inf=1ll<<60;queue<int>q;bool vis[N<<1];
int i,j,k,m,n,x,y,z,cnt,last[N<<1];ll dis[N<<1];
struct node{int u,v,w;bool operator <(const node&b)const{return w<b.w;}};
struct edge{int to,next,v;}e[N*6];
#define add(u,v,w) (e[++cnt]=(edge){v,last[u],w},last[u]=cnt)
vector<node>E[N<<1];
int main(){
	for(n=read(),m=read(),i=2;i<=m+1;++i){
		x=read(),y=read(),z=read();
		E[x].pk((node){i<<1,(i<<1)-1,z}),E[y].pk((node){(i<<1)-1,i<<1,z});
		if(x==1)add(1,(i<<1)-1,z);if(y==1)add(1,i<<1,z);
		if(y==n)add((i<<1)-1,2,z);if(x==n)add(i<<1,2,z);
	}
	for(i=1;i<=n;++i){
		int len=E[i].size();sort(E[i].begin(),E[i].end());
		for(j=0;j<len;++j)add(E[i][j].u,E[i][j].v,E[i][j].w);
		for(j=0;j<len-1;++j)add(E[i][j].v,E[i][j+1].v,E[i][j+1].w-E[i][j].w),add(E[i][j+1].v,E[i][j].v,0);
	}
	for(i=2;i<=m+1<<1;++i)dis[i]=inf;q.push(1);
	while(!q.empty()){
		int k=q.front();q.pop(),vis[k]=1;
		for(int i=last[k],y;i;i=e[i].next)if(dis[y=e[i].to]>dis[k]+e[i].v){
			dis[y]=dis[k]+e[i].v;
			if(!vis[y])vis[y]=1,q.push(y);
		}vis[k]=0;
	}
	printf("%lld\n",dis[2]);
}

-->http://qiancl.is-programmer.com/user_files/qiancl/Image/Problem%203072.%20--%20[Pa2012]Two%20Cakes.html

……第一眼挺简单-。-

……第二眼不会-。-|||

……考虑DP$f[i][j]$表示 $a$串取了$i$次，$b$串取了$j$次，于是

$f[i-1][j] -> f[i][j]$

$f[i][j-1] -> f[i][j]$

$f[i-1][j-1] -> f[i][j] (a[i]!=b[j])$

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
    int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
    for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000100
int i,j,k,m,n,x,y,a[N],b[N],rk[N],f[5005][5005],g[N];
int main(){
    for(n=read(),i=1;i<=n;++i)a[i]=read(),rk[a[i]]=i;
    for(i=1;i<=n;++i)b[i]=read();
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j){
            f[i][j]=min(f[i][j],f[i-1][j]+1);
            f[i][j]=min(f[i][j],f[i][j-1]+1);
            if(a[i]!=b[j])f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    printf("%d\n",f[n][n]);
}

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4345

首先考虑第一个问题

定义二元组$(x,y)$表示当前价值为$x$，位置在$y$，则$(x,y)$可以转移到$(x+a[y+1],y+1)$以及$(x-a[y]+a[y+1],y+1)$两个状态，这个先把$a$数组排序，再加个小根堆维护就行了，复杂度$\mathcal{O}\left(k\log k\right)$

-->http://www.lydsy.com/JudgeOnline/problem.php?id=2750

不说什么了，n遍spfa然后Dp

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1550
#define ll long long
int i,j,k,m,n,x,y,cnt,last[N],dis[N],d[N],a[N],b[N];ll ans[50050];
struct edge{int from,to,next,v;}e[50050];bool vis[N];
inline void add(int w,int v,int u){e[++cnt]=(edge){u,v,last[u],w},last[u]=cnt;}
#define met(x,y) memset(x,y,sizeof x)
inline void spfa(int s){
	queue<int>q;met(dis,0x3f),met(vis,0),dis[s]=0,q.push(s);
	while(!q.empty()){
		int k=q.front();q.pop(),vis[k]=1;
		for(int i=last[k],y;i;i=e[i].next)if(dis[y=e[i].to]>dis[k]+e[i].v){
			dis[y]=dis[k]+e[i].v;
			if(!vis[y])vis[y]=1,q.push(y);
		}vis[k]=0;
	}
}
#define mo 1000000007
inline void ad(int&a,int b){a+=b;if(a>=mo)a-=mo;}
inline void ad(ll&a,ll b){a+=b;if(a>=mo)a-=mo;}
void dfs1(int x){vis[x]=1;for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){++d[y];if(!vis[y])dfs1(y);}}
void dfs2(int x){for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){ad(a[y],a[x]);if(!(--d[y]))dfs2(y);}}
void dfs3(int x){b[x]=1;for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){if(!b[y])dfs3(y);ad(b[x],b[y]);}}
int main(){
	for(n=read(),m=read(),i=1;i<=m;++i)add(read(),read(),read());
	for(i=1;i<=n;++i){
		spfa(i),met(vis,0),met(a,0),met(b,0),met(d,0);
		dfs1(i),a[i]=1,dfs2(i),dfs3(i);
		for(j=1;j<=m;++j)if(dis[e[j].from]+e[j].v==dis[e[j].to])ad(ans[j],1ll*a[e[j].from]*b[e[j].to]);
	}
	for(i=1;i<=m;++i)printf("%lld\n",ans[i]);
}