10.20考试

2017-10-20

T1

求给定两个起点和终点，求公共路径长度。

看到时很迷，即使hjl大佬说了也没理解，后来看了下题解。
就是跑四遍最短路（spfa或dijkstra，据说dijkstra快一些）。
方法：枚举x,y,判断其是不是都在最短路上,并对其距离取max。

上h大佬代码

#include<deque>
#include<cstdio>
#define re register int
#define fp(i,a,b) for(re i=a,I=b;i<=I;++i)
#define chkmax(a,b) (a<b?a=b:0)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void sdf(T&x){
    char c;re y=1;while(c=gc(),c<48||57<c)if(c=='-')y=-1;x=c^48;
    while(c=gc(),47<c&&c<58)x=(x<<1)+(x<<3)+(c^48);x*=y;
}
const int N=1505,M=2250010,inf=1e9;
typedef int arr[N];
struct edges{int nx,to,w;}e[M<<1];
int n,m,s1,s2,t1,t2,tot,ans;arr S1,S2,T1,T2,fi,vis;
inline int abs(const re&a){return a<0?-a:a;}
inline void add(re u,re v,re w){e[++tot]=(edges){fi[u],v,w};fi[u]=tot;}
inline void spfa(re s,re*dis){
    fp(i,1,n)dis[i]=inf,vis[i]=0;dis[s]=0;
    deque<int>q;q.push_back(s);re u,v;
    while(!q.empty()){
        u=q.front();q.pop_front();vis[u]=0;
        for(re i=fi[u];i;i=e[i].nx)
            if(dis[v=e[i].to]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    if(q.empty()||dis[v]>dis[q.front()])q.push_back(v);
                    else q.push_front(v);
                    vis[v]=1;
                }
            }
    }
}
inline int chk(re x){return S1[x]+T1[x]==S1[t1]&&S2[x]+T2[x]==S2[t2];}
int main(){
	file("together"); 
    sdf(n);sdf(m);sdf(s1),sdf(t1);sdf(s2),sdf(t2);
    fp(i,1,m){re u,v,w;sdf(u),sdf(v),sdf(w);add(u,v,w),add(v,u,w);}
    spfa(s1,S1),spfa(t1,T1),spfa(s2,S2),spfa(t2,T2);
    fp(i,1,n)if(chk(i))fp(j,i+1,n)if(chk(j))chkmax(ans,abs(S1[i]-S1[j]));
    printf("%d",ans);
return 0;
}

T2

求长度在[S,T]范围内的子序列平均值的最大值
方法：
可以二分平均值为k，记S[i]=S[i-1]+a[i]-k
那么只要在[i-T+1,i-S+1]内存在j使得S[i]>=S[j]
当前的K就合法。

T3

数学题，推公式。