HZNU Training 25 for Zhejiang Provincial Competition 2020

H

hdu 1599

HDU - 1599 

floyd求最小环。

我们注意到 Floyd 算法有一个性质：在最外层循环到点  k 时（尚未开始第  k次循环），最短路数组  中，  表示的是从  到  且仅经过编号在  区间中的点的最短路。

考虑枚举到k的时候，前面的以k为中转点的 i，j 最短路都已经求出，实际上dis( i , j )最优，

那么以 i  j  k 为顶点构成的三元环，实际就是   dis ( i , j )  + mp( i , k)  +mp ( j ,k) ;

 但三个inf加起来会爆int

#include<bits/stdc++.h>
using namespace std;
const int inf=1e7;
const int N=1e2+5;
int gp[N][N],dis[N][N];
int n,m,ans;
void floyd(){
    ans=inf;
    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
            ans=min(ans,dis[i][j]+gp[k][i]+gp[k][j]);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }

    }
    if(ans==inf)puts("It's impossible.");
    else printf("%d
",ans);

}
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            gp[i][j]=dis[i][j]=inf;
        }
    }
}
int main(){
    while(~scanf("%d %d",&n,&m)){
        init();
    int u,v,w;
    while(m--){
        scanf("%d %d %d",&u,&v,&w);
        if(gp[u][v]>w)gp[u][v]=gp[v][u]=dis[u][v]=dis[v][u]=w;
    }
    floyd();
    }
    // system("pause");
    return 0;
}

E - E

 CodeForces - 1249D1 

给出一些区间，如果说一个整点包含 > k 个区间，那么必须要删除若干个点，求最小删除点个数。

解法：如果一个整点包含大于k个区间，那么删掉最右的区间是正确的，因为它还可能影响后面的区间。

从左到右维护一个集合，枚举每一个整点的包含区间，挨个删除即可。而且这样不会重复，删过的点不会再删。

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define pb push_back
#define se second
const int N=1e3+5;
struct point{int s,e,id;}p[N];
bool cmp(point a,point b){return a.s<b.s;}
set< pair<int,int> >st;
int main(){

    int n,k;
    scanf("%d %d",&n,&k);
    int maxe=0,maxs=1e6;
    for(int i=1;i<=n;i++){
        scanf("%d %d",&p[i].s,&p[i].e);
        p[i].id=i;
        maxs=min(maxs,p[i].s);
        maxe=max(maxe,p[i].e);
    }
    sort(p+1,p+1+n,cmp);
    int pos=1;
    pair<int,int>cur;
    vector<int>ans;
    for(int i=maxs;i<=maxe;i++){
        
        while(pos<=n&&p[pos].s<=i){
            st.insert(mp(p[pos].e,p[pos].id));
            pos++;
        }

        while(!st.empty()&&(st.begin()->fi)<i){
            st.erase( st.begin() );
        }
        while(st.size()>k){cur=*(--st.end());ans.pb(cur.se);st.erase(cur);}
    
    }

    int len=ans.size();
    sort(ans.begin(),ans.end());
    printf("%d
",len);
    for(int i=0;i<len;i++){
        printf("%d%c",ans[i],i==len-1?'
':' ');
    }
    // system("pause");
    return 0;
}