100+100+0=200，聪明搬题人题面又出锅了。

最短路径(path)

给定有向图，包含 n 个节点和 m 条有向边。

一条A 到 B 的路径是最短路径当且仅当不存在另一条从A 到 B 的路径比它更短。换言之，可能存在多条从 A 到 B 的最短路径。

现在，对于每条边，希望求出有多少条最短路径经过它。

对于 100%的数据，1 <= n <= 1500，1 <= m <= 5000，边权不大于 10000。

HAOI2012 道路

首先可以通过枚举确定起点 \(s\)。因为是有向边，所以不会有算重的情况。

基础的想法是求出从起点开始的最短路计数 \(f\)，由各个点反向跑的最短路计数 \(g\)，那么一条在最短路上的边的答案应该为 \(f_u\times g_v\)。（你可能需要画图理解这个 \(g\)）\(f\) 很好算，求最短路时就可顺便算出。考虑 \(g\) 怎么求。

最短路中有用的边构成的一定是一个 DAG。初始把所有点的 \(g\) 设成 \(1\)，表示从自己往回走的计数。然后按照 DAG 的反向拓扑序用反向边更新，这样求出来的就是 \(g\) 了。

#include<bits/stdc++.h>

using namespace std;

template<class T> T read(){

	T x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x;

}

template<class T> T read(T&x){

	return x=read<T>();

}

#define co const

#define il inline

typedef long long LL;

typedef pair<int,int> pii;

co int mod=1000000000+7;

il int add(int a,int b){

	return (a+=b)>=mod?a-mod:a;

}

il int mul(int a,int b){

	return (LL)a*b%mod;

}

co int N=1501,INF=0x3f3f3f3f;

vector<int> to[N],we[N],id[N];

int dis[N],f[N];

priority_queue<pii,vector<pii>,greater<pii> > pq;

vector<int> e[N],nd[N];

int deg[N],g[N],ans[5001];

deque<int> q;

int main(){

	freopen("path.in","r",stdin),freopen("path.out","w",stdout);

	int n=read<int>(),m=read<int>();

	for(int i=1;i<=m;++i){

		int x=read<int>(),y=read<int>(),w=read<int>();

		to[x].push_back(y),we[x].push_back(w),id[x].push_back(i);

	}

	for(int s=1;s<=n;++s){

		// spfa

		fill(dis+1,dis+n+1,INF),fill(f+1,f+n+1,0);

		dis[s]=0,f[s]=1,pq.push(pii(dis[s],s));

		while(pq.size()){

			int dx=pq.top().first,x=pq.top().second;

			pq.pop();

			if(dx>dis[x]) continue;

			for(int i=0;i<(int)to[x].size();++i){

				int y=to[x][i],w=we[x][i];

				if(dis[y]>dx+w){

					dis[y]=dx+w,f[y]=f[x];

					pq.push(pii(dis[y],y));

				}

				else if(dis[y]==dx+w)

					f[y]=add(f[y],f[x]);

			}

		}

		// count

		for(int x=1;x<=n;++x) e[x].clear(),nd[x].clear(),deg[x]=0,g[x]=1;

		for(int x=1;x<=n;++x)if(to[x].size())

			for(int i=0;i<(int)to[x].size();++i){

				int y=to[x][i];

				if(dis[y]==dis[x]+we[x][i])

					e[y].push_back(x),nd[y].push_back(id[x][i]),++deg[x];

			}

		for(int x=1;x<=n;++x)

			if(!deg[x]) q.push_back(x);

		while(q.size()){

			int x=q.front();q.pop_front();

			for(int i=0;i<(int)e[x].size();++i){

				int y=e[x][i];

				ans[nd[x][i]]=add(ans[nd[x][i]],mul(f[y],g[x]));

				g[y]=add(g[y],g[x]);

				if(--deg[y]==0) q.push_back(y);

			}

		}

	}

	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);

	return 0;

}

数列(seq)

给出一个长度为 n 的数列 A。现有如下两种操作：

修改操作：把数列中第 i 个数改为 x
询问操作：给定一个位置 i，问数列中有多少个位置 j（j>i），满足位置 i 与位置 j间所有的数都不超过 Ai 与 Aj 的较大值。即∀i<k ≤j , Ak ≤ max (Ai,Aj)

现共有 m 个操作，请对每个询问操作做出回答。

对于 100%的数据，n、m<=50000，Ai、x<=100000。

神大OJ 数列(seq)

分块。

对每个块维护单调栈，这样询问的时候自己块内暴力做，其他的二分即可。

修改就对自己所在块暴力重构。

注意细节，比如 i 向右能够覆盖的部分。

#include<bits/stdc++.h>

using namespace std;

template<class T> T read(){

	T x=0,w=1;char c=getchar();

	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*w;

}

template<class T> T read(T&x){

	return x=read<T>();

}

#define co const

#define il inline

typedef long long LL;

co int N=50000+10,B=883+10,M=56+10;

int A[N],bel[N];

int L[M],R[M],st[M][B],top[M];

void change(int l,int r,int st[],int&top){

	top=0;

	for(int i=r;i>=l;--i){

		while(top&&A[st[top]]<A[i]) --top;

		st[++top]=i;

	}

}

int query(int p,int num){

	int ans=0;

	int bl=bel[p],mx=A[p];

	for(int i=p+1;i<=R[bl];++i){

		mx=max(mx,A[i]);

		if(mx<=max(A[p],A[i])) ++ans;

	}

	for(int i=bl+1;i<=num;++i){

		int l=0,r=top[i];

		if(mx==A[p]){

			while(l<r){

				int mid=(l+r+1)>>1;

				if(A[st[i][mid]]>mx) l=mid;

				else r=mid-1;

			}

			if(l==0) ans+=R[i]-L[i]+1;

			else{

				ans+=st[i][l]-1-L[i]+1;

				ans+=l-1+1;

			}

		}

		else{

			while(l<r){

				int mid=(l+r+1)>>1;

				if(A[st[i][mid]]>=mx) l=mid;

				else r=mid-1;

			}

			ans+=l-1+1;

		}

		mx=max(mx,A[st[i][1]]);

	}

	return ans;

}

int main(){

	freopen("seq.in","r",stdin),freopen("seq.out","w",stdout);

	int n=read<int>(),m=read<int>();

	int siz=sqrt(n*log2(n)),num=(n+siz-1)/siz;

	for(int i=1;i<=n;++i) read(A[i]),bel[i]=(i+siz-1)/siz;

	for(int i=1;i<=num;++i){

		L[i]=R[i-1]+1,R[i]=min(i*siz,n);

		change(L[i],R[i],st[i],top[i]);

	}

	for(char opt[2];m--;){

		scanf("%s",opt);

		if(opt[0]=='C'){

			int p=read<int>();

			A[p]=read<int>();

			int bl=bel[p];

			change(L[bl],R[bl],st[bl],top[bl]);

		}

		else printf("%d\n",query(read<int>(),num));

	}

	return 0;

}

圆环面积

平面上有 N 个圆环，第 i 个圆环的中心坐标为 (Xi, Yi)，内径为 di，外径为 Di。求这 N 个圆环的并的面积（即在平面上覆盖的面积大小）。

对于 100%的数据满足 N ≤ 1000, |Xi|, |Yi| ≤ 1000, 0 ≤ di < Di ≤ 250。

NOIP模拟赛？这拿给 World Final 还差不多。

巴特西

test20190829 神大校赛模拟

最短路径(path)

HAOI2012 道路

数列(seq)

神大OJ 数列(seq)

圆环面积

最新文章

热门文章