EXAM-2018-8-3

D H

喜闻乐见的水题

J

lower_bound + upper_bound

一个可以查找第一个大于，另一个可查找第一个不小于。

F

找规律+奇偶分析

偶数好找，就是奇数的问题。然后我们可以发现，只有当总数是偶数时会与中间发生偏差。

C

显而易见最短路？

最近做了很多类似的题目，看似毫无规律的数，可以通过图论解决。

这题我们可以连接两个数，比如说25与257之间价值为7，但是我们肯定不能有那么多个点，可以对n取模，让两点之间有不同长度的边，然后点是取模n+1，构造一个0作为起点，终点是1，跑最短路。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=100010,maxm=2000010;

int n,m,first[maxn],ans,d[maxn],s,t;

struct edge

{

    int from,v,w;

} e[maxm];

struct Node

{

    int x,d;

    bool operator <(const Node &b)const

    {

        return d>b.d;

    }

} cyc;

priority_queue<Node>q;

void add(int u,int v,int w)

{

    ans++;

    e[ans].v=v;

    e[ans].w=w;

    e[ans].from=first[u];

    first[u]=ans;

}

int dijkstra()

{

    memset(d,0x3f,sizeof(d));

    d[s]=0;

    q.push((Node)

    {

        s,d[s]

    });

    while(!q.empty())

    {

        cyc=q.top();

        q.pop();

        if(cyc.d!=d[cyc.x])continue;

        int x=cyc.x;

        for(int i=first[x]; i; i=e[i].from)

            if(d[e[i].v]>d[x]+e[i].w)

            {

                d[e[i].v]=d[x]+e[i].w;

                q.push((Node)

                {

                    e[i].v,d[e[i].v]

                });

            }

    }

    return d[t];

}

int main()

{

    scanf("%d",&n);

    for(int i=1; i<=n; i++)for(int j=0; j<=9; j++)add(i,((i-1)*10+j)%n+1,j);

    for(int j=1; j<=9; j++)add(0,j+1,j);

    s=0;

    t=1;

    printf("%d",dijkstra());

    return 0;

}

K

必须先拿钥匙才能开门（废话）

预处理出生再每个们能到达的最大区间

加边时当钥匙在左边，方向是钥匙到房间。

当钥匙在右边，方向是房间到钥匙。

跑一个拓扑排序，然后再extend该房间能扩大的最大区间

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int read()

{

    int i=0,f=1;char c;

    for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());

    if(c=='-')c=getchar(),f=-1;

    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';

    return i*f;

}

const int maxn=1e6+8;

struct node

{

    int u;

    int v;

    int next;

}s[maxn<<2];

int n,m,q,p[maxn],l[maxn],r[maxn],id[maxn];

int len,head[maxn],ru[maxn];

queue<int>Q;

void add(int u,int v)

{

    s[++len].u=u;

    s[len].v=v;

    s[len].next=head[u];

    head[u]=len;

    ru[v]++;

}

void extend(int i)

{

    while(1)

    {

        int bz1=1,bz2=1;

        if(l[i]==1)bz1=0;

        if(r[i]==n)bz2=0;

        if(bz1)

        {

            if((!p[l[i]-1])||(p[l[i]-1]>=l[i]&&p[l[i]-1]<=r[i]))l[i]=l[id[l[i]-1]];

            else bz1=0;

        }

        if(bz2)

        {

            if((!p[r[i]])||(p[r[i]]>=l[i]&&p[r[i]]<=r[i]))r[i]=r[id[r[i]+1]];

            else bz2=0;

        }

        if(!bz1&&!bz2)break;

    }

}

void topsort()

{

    for(int i=1;i<=n;i++) if(id[i]==i&&!ru[i]) Q.push(i);

    while(!Q.empty()){

        int u=Q.front();Q.pop();

        extend(u);

        for(int i=head[u];i;i=s[i].next){

            if(!(--ru[s[i].v])) Q.push(s[i].v);

        }

    }

}

int main()

{

    int x,y;

    n=read();

    m=read();

    q=read();

    for(int i=1;i<=n;i++) id[i]=l[i]=r[i]=i;

    while(m--) x=read(),p[x]=read();

    for(int i=1;i<=n;i++){

        if(!p[i]) id[i+1]=id[i];

        else p[i]<=i?add(id[i+1],id[i]):add(id[i],id[i+1]);

    }

    for(int i=1;i<=n;i++) l[id[i]]=min(l[id[i]],l[i]),r[id[i]]=max(r[id[i]],r[i]);

    topsort();

    for(int i=1;i<=n;i++) l[i]=l[id[i]],r[i]=r[id[i]];

    while(q--){

        x=read(),y=read();

        y>=l[x]&&y<=r[x]?puts("YES"):puts("NO");

    }

    return 0;

}

地址EXAM-2018-8-3

巴特西

EXAM-2018-8-3

EXAM-2018-8-3

D H

J

F

C

K

最新文章

热门文章