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。现有如下两种操作：

1. 修改操作：把数列中第 i 个数改为 x
2. 询问操作：给定一个位置 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 神大校赛模拟

原文：https://www.cnblogs.com/autoint/p/test20190829.html