NOIP 2013

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

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

D1T1 转圈游戏

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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判连通性了，强行增加码量。还好在赛前刚给别人讲过倍增，这题满分了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#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 积木大赛

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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就是答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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求最短路即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#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
*/
散装题解
#noip
NOIP 2013
https://izard.space/2018/09/26/NOIP-2013/
作者
forever_you
发布于
2018年9月26日
许可协议