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