HZNU Training 20 for Zhejiang Provincial Competition 2020

A - Adventure A

线段树相关

G - %yclB

简单最短路；

题意：给你一张图，可以把k个边变成0,求最短路。

解法：考虑每一条边都只有两种情况，变成0，和不变成0，设 dis [ i  [[ j ] 表示：取了 j 个0，更新过来最短路。

那么就只有两种情况。变成 0 和 不变成0，

更新最短路，保存等级即可，即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll INF=1e14;
const int  inf =0x3f3f3f3f;
int head[N],ecnt,K,n,m;//cnt main里初始化为0，head main初始化为-1
struct edge{int v;long long w,next;}e[N*10];//注意有重边，乘10
struct node{
    int id;ll dis;int lev;//id点，dis距离
    node(int x,ll y,int z){id=x,dis=y;lev=z;}
    friend bool operator<(node a,node b){
    return a.dis>b.dis;//距离小的出队
    }
};
ll  dis[N][15];
bool done[N][15];
void add(int u,int v,ll w){//加边
    e[ecnt].v=v,e[ecnt].w=w,e[ecnt].next=head[u],head[u]=ecnt++;
}
void init(){
    memset(head,-1,sizeof head);
    ecnt=0;
}
void dijkstra(){

    memset(done,0,sizeof done );
    memset(dis,inf,sizeof dis);
    priority_queue<node>Q;
    Q.push(node(1,0,0));dis[1][0]=0;
    // node tmp;
    while(!Q.empty()){
    // tmp=Q.top();Q.pop();
    int u=(Q.top()).id,lv=(Q.top()).lev;Q.pop();
    if(done[u][lv])continue;
    done[u][lv]=1;
    for(int i=head[u];~i;i=e[i].next){

    int v=e[i].v;ll w=e[i].w;
    
    if(dis[v][lv]>dis[u][lv]+w){
    dis[v][lv]=dis[u][lv]+w;
    Q.push(node(v,dis[v][lv],lv));
    }
    
    if(lv<K&&dis[v][lv+1]>dis[u][lv]){
        dis[v][lv+1]=dis[u][lv];
        Q.push(node(v,dis[v][lv+1],lv+1));
    }

    }
    }
       
}
int main(){
    int  t;
    scanf("%d",&t);
    while(t--){
    scanf("%d %d %d",&n,&m,&K);
    init();
    int u,v;ll w;
    for(int i=1;i<=m;i++){
    scanf("%d %d %d",&u,&v,&w);
    add(u,v,w);
    }
    dijkstra();
    ll ans=INF;
    for(int i=0;i<=K;i++)ans=min(ans,dis[n][i]);
    printf("%lld
",ans);
    }
    // system("pause");

    return 0;
}

H - %yclC

 POJ - 2452 

题意：求一个最大区间，使得区间中间的元素都大于l， 小于 r ；

解法：暴力更新 , 处理出每个点可向右延伸的最大长度，然后枚举每个点这个区间的最大值，

#include<cstdio>
#include<algorithm>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ldb;
typedef double db;
const double eps=1e-8;
const int N=1e5+5;
const ll MOD=998244353;
int a[N],len[N];
int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)len[i]=1,scanf("%d",&a[i]);
        for(int i=n;i>=1;i--){
            while(i+len[i]<=n&&a[i]<a[i+len[i]])len[i]+=len[i+len[i]];
        
        }
        int ans=-1;
        for(int i=1;i<=n;i++){
            int cur=-1,Max=-1;
            for(int j=1;j<len[i];j++){
                if(a[i+j]>Max)Max=a[i+j],cur=j;
            }
            ans=max(ans,cur);
        }
        printf("%d
",ans);
    }   
    // system("pause");
    return 0;
}