2018.9.10离线赛 by Satori

於英朗

2023-12-01

T1——satellite(3907)

Description:

有一个环形道路,城市 $i$ 与城市 $i+1$ 相连,每个城市之间有 $dis_i$ ,每个城市有补给 $val_i$ .现在询问对于每个城市 $i$ 做为起点,能否完成环游一圈,即再回到起点 $i$ .
$n \le 10^6$

Solution:

首先一看数据范围,不难猜想是此题是一个 $\Theta(n)$ 的算法.
初次有一个这样的式子 $\sum_{i} (val_i-dis_i) >0$
再分析一下,要达到 $\Theta(n)$ 肯定是要预处理什么东西.( $dis$ , $val$ 的前缀和?)
然后再模拟一下小数据,发现这个顺时针走,或逆时针走,效果都是一样的.
那么比较容易想到长度为 $2n$ 的前缀和.
那么问题变成了对于 $x$ ,所有向后n个的前缀和的大小的最小值是否大于等于 $sum_{x-1}$
再考虑单调队列维护一下.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;

template<class T>inline void Rd(T &x){
    x=0;char c;
    while((c=getchar())<48);
    do x=(x<<1)+(x<<3)+(c^48);
    while((c=getchar())>47);
}

#define N 2000002

int n;
int val[N];

struct p100{

    int dis[N];
    ll sum[N];
    int Q[N],L,R;
    bool f[N],g[N];

    void go(bool *ans){
        REP(i,1,n) val[i+n]=val[i],dis[i+n]=dis[i];
        REP(i,1,n<<1) sum[i]=sum[i-1]+val[i]-dis[i];
        L=R=0;
        REP(i,1,n){
            while(R && sum[i]<sum[Q[R-1]]) --R;
            Q[R++]=i;
        }
        REP(i,1,n) {
            if(Q[L]<i) ++L;
            ans[i]=(sum[Q[L]]-sum[i-1]>=0);
            while(L<R && sum[i+n]<sum[Q[R-1]]) --R;
            Q[R++]=i+n;
        }
    }

    void solve(){
        REP(i,1,n)Rd(val[i]),Rd(dis[i]);

        go(f);
        reverse(val+1,val+1+n);
        reverse(dis+1,dis+1+n);
        SREP(i,0,n)dis[i]=dis[i+1];
        dis[n]=dis[0];
        go(g);

        ll ans=0;
        REP(i,1,n)ans+=(f[i] || g[n-i+1])?i:0;
        printf("%lld\n",ans);
    }
}p2;

int main(){
//  freopen("satellite.in","r",stdin);
//  freopen("satellite.out","w",stdout);
    scanf("%d",&n);

    p2.solve();
    return 0;
}

T2——reisen(3908)

Description:

有 $n$ 个人,其中有一个人是杀手,其余都是平民.现在有 $m$ 个关系,表示 $x$ 知道 $y$ 的身份.
现在警察要在策略最优的情况下查出杀手并保证自己的安全.注意:警察一查到该人是杀手,那警察就会被杀!求查出杀手的概率.
$n \le 200000 , m \le 300000$

Solution:

首先分析一下,要保证策略最优,即查的人尽量少,而知道的人尽量多.
即优先查入度为 $0$ 的点.这样就可以获得这个点延伸的点.
这里在看一下 $m$ 的范围,很容易想到图会有环,那么就需要 $tarjan$ 缩点.
其实想到这里题差不多就没了…但是此题比较毒瘤吧…有较多的细节.
首先,查完 $n-1$ 个人,最后一个人即可推断.
再是这个关系是单向的,是一个有向图,即缩点时要判重边
以及一些要特判. $eg$ : $n=1$ ,为 $0$ , $m=0$ 时,为 $\frac{1}{n}$ .

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;

template<class T>inline void Rd(T &x){
    x=0;char c;
    while((c=getchar())<48);
    do x=(x<<1)+(x<<3)+(c^48);
    while((c=getchar())>47);
}

#define N 200002
#define M 300002

int n,m;
int qwq,head[N];
struct edge{
    int to,nxt;
}E[M<<1];
inline void addedge(int x,int y){E[qwq]=(edge){y,head[x]};head[x]=qwq++;}
vector<int>G[N];

int dfn[N],low[N],tim;
int stk[N],top;
int Id[N],tot;
bool vis[N];
int sum[N],degree[N];

map<int,bool>mp[N];

void tarjan(int x){
    dfn[x]=low[x]=++tim;
    stk[++top]=x;
    vis[x]=1;
    for(int i=head[x];~i;i=E[i].nxt){
        int y=E[i].to;
        if(!dfn[y]){
            tarjan(y);
            chkmin(low[x],low[y]);
        }
        else if(vis[y])chkmin(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        tot++;
        do{
            Id[stk[top]]=tot;
            sum[tot]++;
            vis[stk[top]]=0;
        }while(x!=stk[top--]);
    }
}

int main(){
//  freopen("reisen.in","r",stdin);
//  freopen("reisen.out","w",stdout);

    mcl(head,-1);

    scanf("%d%d",&n,&m);

    REP(i,1,m){
        int x,y;
        Rd(x),Rd(y);
        addedge(x,y);
    }   
    REP(i,1,n) if(!dfn[i]) tarjan(i);   

    REP(x,1,n){
        for(int i=head[x];~i;i=E[i].nxt){
            int y=E[i].to;
            if(Id[x]!=Id[y] && !mp[Id[x]][Id[y]]){
                mp[Id[x]][Id[y]]=1;
                G[Id[x]].pb(Id[y]);
                degree[Id[y]]++;
            }
        }
    }

    int res=0;
    bool find=0;

    REP(i,1,tot) res+=(!degree[i]);
    REP(i,1,tot){
        if(sum[i]==1 && !degree[i]){
            bool chk=0;
            SREP(j,0,G[i].size()){
                int y=G[i][j];
                if(degree[y]>1)chk=1;
                else {chk=0;break;}
            }
            if(chk)find=1;
        }       
        if(find){
            res--;
            break;
        }
    }

    if(!m)printf("%.6lf\n",(db)1/n);
    else if(n==1)puts("1.000000");
    else printf("%.6lf\n",(db)(n-res)/n);
    return 0;
}

T3——subway(3909)

Description:

有一个 $n$ 个点, $m$ 条边的的图,特殊地,每条边有颜色.
而 $x$ 到 $y$ 的花费为上次边的颜色与当前边的颜色不同时为 $1$ ,否则为 $0$ .
求 $1$ 到 $n$ 的最小花费.
$n,m \le 500000$

Solution:

一眼看上去就是一个最短路问题,不同的是路径的权值还关心上次的路径的颜色.
而且这个 $n,m$ 的范围都挺大的.所以不能直接最短路.
那么在分析一下,此题特殊点就是边的颜色.
那么我们就从颜色入手.将边按颜色划分.
首先考虑将关键点找出来,令(x,c)表示之前一趟车做的是c,现在位置在x.
很容易发现点的个数最多只有 $4m$ 个.边是 $6m$ 条
连边就是 $(x,0)<->(x,c) (y,0)<->(y,c) (x,c)<->(y,c)$ .
然后可以 $0->c$ 的花费为 $1$ ,剩下的花费为 $0$ ,跑一边最短路
这里跑最短路用滚动队列.

Code:

#include<bits/stdc++.h>
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i<i##_end_;++i)
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;--i)
#define db double
#define ll long long 
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define MINF 0xc0c0c0c0
#define Sz(A) sizeof(A)
#define mcl(A,b) memset(A,b,Sz(A))
#define mcp(A,b) memcpy(A,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T &x,T y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
typedef pair<int,int>PII;

template<class T>inline void Rd(T &x){
    x=0;char c;
    while((c=getchar())<48);
    do x=(x<<1)+(x<<3)+(c^48);
    while((c=getchar())>47);
}

#define N 500002
#define M 1000002

int n,m;

int qwq,head[N];
struct edge{
    int to,nxt;
}E[N<<2];
void addedge(int x,int y){E[qwq]=(edge){y,head[x]};head[x]=qwq++;}

vector<int>X[M],Y[M],G[2][N];

int tot;
int vis[N];
int stk[N],top;
int dis[N];
queue<int>Q[2];

void dfs(int x){
    int y;
    vis[x]=1;
    G[1][x].pb(tot);
    G[0][tot].pb(x);
    for(int i=head[x];~i;i=E[i].nxt){
        int y=E[i].to;
        if(vis[y])continue;
        dfs(y);
    }
}

void Init(int col){
    int x,y;
    top=qwq=0;
    mcl(head,-1);
    SREP(i,0,X[col].size()){
        x=X[col][i],y=Y[col][i];
        addedge(x,y);
        addedge(y,x);
        stk[++top]=x,stk[++top]=y;
    }
    REP(i,1,top)if(!vis[stk[i]]){
        ++tot;
        dfs(stk[i]);
    }
    REP(i,1,top){
        vis[stk[i]]=0;
        head[stk[i]]=-1;
    }
}

int bfs(){
    int cur=0;

    mcl(dis,INF);

    Q[cur].push(1);
    dis[1]=0;

    while(!Q[cur].empty()||!Q[!cur].empty()){
        if(Q[cur].empty())cur=!cur;
        int x=Q[cur].front(),y;Q[cur].pop();
        SREP(i,0,G[0][x].size()){
            int y=G[0][x][i];
            if(dis[y]==INF){
                dis[y]=dis[x];
                Q[cur].push(y);
            }
        }
        SREP(i,0,G[1][x].size()){
            int y=G[1][x][i];
            if(dis[y]==INF){
                dis[y]=dis[x]+1;
                Q[!cur].push(y);
            }
        }
    }
    return dis[n]==INF?-1:dis[n];
}
int main(){
//  freopen("subway.in","r",stdin);
//  freopen("subway.out","w",stdout);
    Rd(n),Rd(m);
    tot=n;
    int mx=0,a,b,c;
    REP(i,1,m){
        Rd(a),Rd(b),Rd(c); 
        chkmax(mx,c);
        X[c].pb(a);
        Y[c].pb(b);
    }
    REP(i,1,mx) Init(i);
    printf("%d\n",bfs());
    return 0;
}

Summary:

但今天的策略执行的还是比较流畅的.先打完暴力…~~除了T2~~,然后开始想正解.
总体来说,题的码量偏大…以及难度顺序有点颠倒.其它还好.
评价:较良心出题人.

2018.9.10离线赛 by Satori

T1——satellite(3907)

T2——reisen(3908)

T3——subway(3909)

相关阅读

相关文章

相关问答

相关文档