NOIP 2013 - Forever you~

最近突然想回顾一下历年noip题目，就开个新坑吧，题解就从略了

题目链接 https://vijos.org/p/category/2013

D1T1 转圈游戏

公式就 $(x+m10^k)\%n$ ，现在一眼的事情当时想了很久orz

#include<bits/stdc++.h>
using namespace std;
int power(int x,int n,int mod)
{
    int ans=1;
    while(n)
    {
        if(n&1) ans=1LL*ans*x%mod;
        x=1LL*x*x%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    int n,m,k,x;
    while(scanf("%d%d%d%d",&n,&m,&k,&x)!=EOF)
    {
        int ans=(x+1LL*m*power(10,k,n))%n;
        printf("%d\n",ans);
    }
}

D1T2 火柴排队

首先肯定是小对小，大对大，才能使那个式子最小，这一点可以交换一下然后做差说明。并且题目保证了高度互不相同，也就是给了两个排列，问最少交换相邻元素多少次，才能使两个排列一样，再转化一步，假设第一个排列就是1,2,3,…n，问第二个排列最少交换相邻元素几次才能变成1,2,3,…n，这就是逆序对的定义了。

不知道如果不保证高度互不相同该怎么做orz

当时这个题爆零了，一点也不会QAQ

#include<bits/stdc++.h>
using namespace std;
const int mod=99999997;
#define N 100010
#define rep(i,l,r) for(int i=l;i<=r;++i)

int a[N],b[N],h[N];
int c[N];
int n;
int lowbit(int x)
{
    return x&(-x);
}
int ask(int x)
{
    int ans=0;
    for(;x<=n;x+=lowbit(x))
        ans+=c[x];
    return ans;
}
void change(int x,int y)
{
    for(;x;x-=lowbit(x))
        c[x]+=y;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        rep(i,1,n) scanf("%d",a+i),h[i]=a[i];
        sort(h+1,h+n+1);
        rep(i,1,n) a[i]=lower_bound(h+1,h+n+1,a[i])-h;
        rep(i,1,n) scanf("%d",b+i),h[i]=b[i];
        sort(h+1,h+n+1);
        rep(i,1,n) b[i]=lower_bound(h+1,h+n+1,b[i])-h;

        rep(i,1,n) h[a[i]]=i;
        rep(i,1,n) b[i]=h[b[i]],c[i]=0;
        int ans=0;
        rep(i,1,n)
        {
            change(b[i],1);
            ans+=ask(b[i]+1);
            if(ans>=mod) ans-=mod;
        }
        printf("%d\n",ans);
    }
}

D1T3 货车运输

这个不难看出是最大生成树上倍增求路径边权最小值。要注意的是可能是一个森林，当时蠢的用tarjan判连通性了，强行增加码量。还好在赛前刚给别人讲过倍增，这题满分了。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define dow(i,l,r) for(int i=l;i>=r;--i)
#define N 10010
#define M 50010
const int INF=0x3f3f3f3f;
struct edge
{
    int x,y,c;
} t[M];
int n,m,q;
int fa[N];
bool root[N];
bool cmp(const edge &a,const edge &b)
{
    return a.c>b.c;
}
int getfa(int x)
{
    return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
bool Union(int x,int y)
{
    x=getfa(x);
    y=getfa(y);
    if(x==y) return false;
    fa[x]=y;
    return true;
}
namespace TREE
{
int e,head[M<<1],last[M<<1],w[M<<1],p[N];
int f[N][21],g[N][21];
int deep[N];
void add(int x,int y,int c)
{
    head[++e]=y;w[e]=c;
    last[e]=p[x];
    p[x]=e;
}
void dfs(int x,int pre,int dep)
{
    deep[x]=dep;
    for(int j=p[x];j;j=last[j])
    {
        int y=head[j];
        if(y==pre) continue;
        f[y][0]=x;
        g[y][0]=w[j];
        rep(i,1,20)
        {
            f[y][i]=f[f[y][i-1]][i-1];
            g[y][i]=min(g[y][i-1],g[f[y][i-1]][i-1]);
        }
        dfs(y,x,dep+1);
    }
}
int askmax(int x,int y)
{
    if(deep[x]>deep[y]) swap(x,y);
    int ans=INF;
    dow(i,20,0)
        if(deep[f[y][i]]>=deep[x])
            ans=min(ans,g[y][i]),y=f[y][i];
    if(x==y) return ans;
    dow(i,20,0)
        if(f[x][i]!=f[y][i])
        {
            ans=min({ans,g[x][i],g[y][i]});
            x=f[x][i],y=f[y][i];
        }
    ans=min({ans,g[x][0],g[y][0]});
    return ans;
}

}//TREE

int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,m)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        t[i]=edge{x,y,c};
    }
    sort(t+1,t+m+1,cmp);
    rep(i,1,n) fa[i]=i;
    rep(i,1,m)
    {
        int x=t[i].x;
        int y=t[i].y;
        int c=t[i].c;
        if(Union(x,y))
        {
            TREE::add(x,y,c);
            TREE::add(y,x,c);
        }
    }
    rep(i,1,n) root[getfa(i)]=true;
    memset(TREE::g,INF,sizeof(TREE::g));
    rep(i,1,n)
        if(root[i])
            TREE::dfs(i,0,1);

    scanf("%d",&q);
    while(q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(getfa(x)!=getfa(y)) puts("-1");
        else printf("%d\n",TREE::askmax(x,y));
    }
}

D2T1 积木大赛

可能太简单，这题没什么印象了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 100010
int n;
int h[N];
int main()
{
    scanf("%d",&n);
    int ans=0;
    rep(i,1,n)
    {
        scanf("%d",h+i);
        ans+=max(0,h[i]-h[i-1]);
    }
    printf("%d\n",ans);
}

D2T2 花匠

当时从最长上升子序列的思路出发，然后推了推，写了个单调队列，具体怎么写的忘了，不过也是AC。实际上最简单的做法只需要扫一遍，求出拐点的个数，加2就是答案了。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 100010
int n;
int a[N];
int main()
{
    scanf("%d",&n);
    int ans=0;
    int now=0;
    rep(i,1,n)
    {
        scanf("%d",a+i);
        if(i==1||a[i-1]==a[i]) continue;
        if(a[i-1]<a[i])
        {
            if(now==-1) ++ans;
            now=1;
        }
        if(a[i-1]>a[i])
        {
            if(now==1) ++ans;
            now=-1;
        }
    }
    printf("%d\n",ans+2);
}

D2T3 华容道

这题xjb搜，就得了5分…

正确做法是bfs预处理，拆点，建图跑最短路。

具体来说：可以观察到只有空白块位于指定块的四方向上，指定块才可以移动。本质上还有另外一种移动方式，就是指定块不动，空白块从它的上/下左/右中的一个移动到另一个。那么这样就可以bfs预处理了，状态也有了，(x,y,k)表示指定块在(x,y)，空白块在相邻的k方向上。spfa求最短路即可。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int INF=0x3f3f3f3f;
const int dx[]= {0,0,1,-1};
const int dy[]= {1,-1,0,0};
const int N=31*31*4;
const int M=4*N;
struct node
{
    int x,y;
} q[32*32*4];
int n,m,k;
int dis[32][32];
int can[32][32];

int e,head[M],last[M],w[M],p[N];
bool vis[N];
int dist[N];
bool ok(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<m && can[x][y];
}

void bfs(int sx,int sy)
{
    memset(dis,INF,sizeof(dis));
    dis[sx][sy]=0;
    int l=0,r=0;
    q[r++]=node{sx,sy};
    while(l!=r)
    {
        int x=q[l].x;
        int y=q[l].y;
        l++;
        rep(i,0,3)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(ok(xx,yy) && dis[xx][yy]==INF)
            {
                dis[xx][yy]=dis[x][y]+1;
                q[r++]=node{xx,yy};
            }
        }
    }
}
int calc(int x,int y,int k)
{
    return x*m*4+y*4+k;
}
void add(int x,int y,int c)
{
    head[++e]=y;
    w[e]=c;
    last[e]=p[x];
    p[x]=e;
}
void init()
{
    rep(i,0,n-1)
    rep(j,0,m-1)
    if(ok(i,j))
    {
        rep(k,0,3)
        {
            int x=i+dx[k];
            int y=j+dy[k];
            if(!ok(x,y)) continue;
            can[i][j]=0;
            bfs(x,y);
            can[i][j]=1;
            rep(h,0,3) if(h!=k)
            {
                int xx=i+dx[h];
                int yy=j+dy[h];
                if(ok(xx,yy) && dis[xx][yy]!=INF)
                    add(calc(i,j,k),calc(i,j,h),dis[xx][yy]);
            }
            add(calc(i,j,k),calc(x,y,k^1),1);
        }
    }
}
void spfa(int sx,int sy)
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(dist,INF,sizeof(dist));
    rep(i,0,3)
    if(ok(sx+dx[i],sy+dy[i]) && dis[sx+dx[i]][sy+dy[i]]!=INF)
    {
        int now=calc(sx,sy,i);
        dist[now]=dis[sx+dx[i]][sy+dy[i]];
        vis[now]=true;
        q.push(now);
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=false;
        for(int j=p[x]; j; j=last[j])
        {
            int y=head[j];
            if(dist[y]>dist[x]+w[j])
            {
                dist[y]=dist[x]+w[j];
                if(!vis[y])
                {
                    vis[y]=true;
                    q.push(y);
                }
            }
        }
    }
}
int work(int x,int y,int sx,int sy,int tx,int ty)
{
    if(sx==tx && sy==ty) return 0;
    can[sx][sy]=0;
    bfs(x,y);
    can[sx][sy]=1;
    spfa(sx,sy);
    int ans=INF;
    rep(i,0,3) ans=min(ans,dist[calc(tx,ty,i)]);
    if(ans==INF) ans=-1;
    return ans;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    rep(i,0,n-1)
    rep(j,0,m-1)
    scanf("%d",&can[i][j]);
    init();
    while(k--)
    {
        int x,y,sx,sy,tx,ty;
        scanf("%d%d%d%d%d%d",&x,&y,&sx,&sy,&tx,&ty);
        --x;--y;--sx;--sy;--tx;--ty;
        printf("%d\n",work(x,y,sx,sy,tx,ty));
    }
}
/*
3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2
*/