Dylan's Blog
Dylan's Blog

NOIP2013提高组 解题报告

收录于 OI
  约 11100 字 预计阅读 23 分钟  - 次阅读   - 条评论  

NOIP2013 提高组 解题报告

Day1

转圈游戏

题意分析

容易看出每次进行一轮，x=(x+m)% n（出题人很好心地让位置从0开始）。

一共进行了10k轮，则x=(x+$10^k$m)% n。

根据数据范围和上面的式子分析，这道题的关键是求$10^k$。

再进一步，求$10^k$% n。

几个有用的结论

  1. (ab)% c=[ (a % c)(b % c)] % c

    简单的证明一下：（带余除法）

    设a=xc+p,b=yc+q；

    ab=(xc+p)(yc+q)=xyc$^2$+xcq+pyc +pq，则ab % c=pq % c；

    a % c=p，b % c=q，[ (a % c)(b % c)] % c=pq % c；

    则有ab % c=[ (a % c)(b % c)] % c。

  2. 设r[i]=10$^i​$ % n，则对于任何正整数n，r[1],r[2],r[3]…为循环数列。

这个结论看起来有点武断，但是应该是正确的。比赛的时候可以打表找规律。

不会证明……不过大概可以考虑2$^k$% n和5$^k$% n的性质。

朴素找循环节

根据结论2，r[ ]是循环数列，那么我们如果假定循环节长度不大，我们就可以在较短的时间里找到规律，从而直接计算r[k]。

又由结论1，有：

推论1.1

$$ r[i]=10^{i} \bmod n=\left(10^{*} 10^{i-1}\right) \bmod n=(10 \bmod n)^{*} r[i-1] $$

由此我们找到了r[ ]的递推式，但是要发现规律还要一些处理。

根据公式，一旦r[i]的值在之前出现过，那么接下来一定就是同样的循环节，所以我们考虑用used[ ]来保存某一个值是否用过。又为了在重复出现时快速定位之前出现的位置，我们令used[ ]为int类型，used[x]存放上一个满足r[i]=x的i值。

当某次发现used[r[i]]不为0时，确定循环节及计算r[k]的方法如下：

如图，当used[r[i]]≠0时，

循环节长度T=i-used[r[i]]，

在开始循环之前的部分长度为used[r[i]]-1，

则从循环节开始到k的距离d=k-(used[r[i]]-1)，

r[k]在循环节中的位置为d % T，

则r[k]=r[d % T+used[i]-1。

这里考虑一下数组的范围：

used[ ]存放的是r[i]的值，由模的相关知识知0≤r[i]＜n，故used[ ]的大小只要开到maxn即可。

r[ ]存放余数的值。从最坏角度来讲，有可能到k都没有循环，似乎应该开到maxk，但maxk=10$^9$，空间M=10$^9$×4B=3814.7MB，远超128MB的上限。

我们在这里假定循环节很快就会出现，所以可以将数组开得小一点，还是可以通过所有数据。

 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

/*
    Circle
    loop 10^k times
    x=(x+m)%n
    
    x=x+10^k*m%n
    x=x+10^k%n+m  %n
    
    the key: 10^k %n=
    10^(k+1)%n=10^k%n*10%n;
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxk=10000003;
const int maxn=1000003;
int n,m,k,x;

int mod[maxk];
int used[maxn];
int Mod=-1;
int main()
{
    freopen("circle.in","r",stdin);
    //freopen("circle.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&x);
    mod[1]=10%n;
    used[mod[1]]=1;
    for(int i=2;i<=k;++i)
    {
        mod[i]=10*mod[i-1]%n;
        if(used[mod[i]])
        {
            int T=i-used[mod[i]];
            int d=k-used[mod[i]]+1;
            Mod=mod[d%T+used[mod[i]]-1];
            break;
        }
        else used[mod[i]]=i;
    }
    if(Mod==-1)
    {
        Mod=mod[k];
    }
    int ans=(x+Mod*m%n)%n;
    printf("%d\n",ans);
    return 0;
}

快速模幂

联想：如果k不大时要求计算10$^k$的值，我们会使用快速幂的方法。但是maxk=10$^9$，无法直接计算10$^k$。考虑到只要求其模n的值，我们只要对快速幂的算法稍加修改，在每一步都模n即可。

另外还要注意的是，在快速幂的过程中$10^{\left\lfloor \frac{k}{2} \right\rfloor}$固然不会超过INT_MAX，但是它的平方却有可能。这样如果用int会造成溢出导致错误答案，所以在快速幂时应该使用long long类型。

 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

/*
Circle 
Fastpow
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
long long n,m,k,x;

long long fastpow(int p)
{
    if(p==0)return 1;
    if(p==1)return 10%n;
    if(p==2)return 100%n;
    long long t=fastpow(p/2)%n;
    if(p&1)
        return t*t*10%n;
    else return t*t%n;
}
int main()
{
    freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);

scanf("%lld%lld%lld%lld",&n,&m,&k,&x);

    long long ans=(x+m*fastpow(k)%n)%n;
    printf("%d\n",ans);
    return 0;
}

火柴排队

思路分析

首先对题目中的距离处理一下：

$$ \mathrm{d}=\sum(a i-b i)^{2}=\sum\left(a i^{2}+b i^{2}-2 a i b i\right)=\sum\left(a i^{2}+b i^{2}\right)-\sum a i b i $$

由于a、b两列数是确定的，所以$\sum\left(a i^{2}+b i^{2}\right)$是确定的。要使得d尽可能小，$\sum a i b i$应该尽可能大。

根据数学中排序不等式的相关知识，对于两列数a[ ]、b[ ]的$\sum a i b i$，

有顺序和≥乱序和≥逆序和。

另外，当a[ ]、b[ ]按照顺序和排好后，如果将a[i]、b[i]捆绑着调换位置，这样的操作对答案没有影响。

预处理

由于题目只要求输出最少的交换次数而没有要求输出最小的答案，我们发现ai,bi具体的值对我们是没有用处的，有用的只是它们的相对大小。于是我们可以将a[ ]，b[ ]进行离散化。

这样题目就变成：给定1~n的两个排列a[ ]，b[ ]，求最少交换次数使得所有ai=bi。

猜想

对两个数列都进行操作所得答案与只对其中一个数列进行操作所得结果相等。

快速排序+类冒泡排序

一开始的想法就是模拟交换的过程，联想到冒泡排序。那么如何判别两数是否应该交换呢？

在离散化之后，我们只对b[ ]进行操作。则对于每个b[i]，它的目标位置是满足a[j]=b[i]的j。于是我们可以给b[i]赋一个权值j。

具体步骤是：

  1. 记录a[i]，b[i]原来的位置pos

  2. 将a[ ]、b[ ]分别进行排序。

  3. 对每一个排好序的a[i]、b[i]：

    ​ 令b[i]的权值为a[i].pos

  4. 让b[i]回到原来的位置

  5. 对b[i]进行冒泡操作，记录交换次数

在程序中我们可以分别使用a[ ],aa[ ],b[ ],bb[ ]以加快上述过程。

 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

/*
match
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
void read(int &A)
{
    
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
    
    //scanf("%d",&A);
}
const int maxn=100003;
const int p=99999997;
typedef  const int& cint;
int n;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
struct MATCH
{
    int h,pos;
    friend bool operator<(const MATCH& a,const MATCH& b);
}aa[maxn],bb[maxn];
int a[maxn],b[maxn];
inline bool operator<(const MATCH& a,const MATCH& b)
{
    return a.h==b.h?a.pos<b.pos:a.h<b.h;
}

void input()
{
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(aa[i].h);
        aa[i].pos=i;
    }
    for(int i=1;i<=n;++i)
    {
        read(bb[i].h);
        bb[i].pos=i;
    }
    sort(aa+1,aa+n+1);
    sort(bb+1,bb+n+1);
    for(int i=1;i<=n;++i)
    {
        a[aa[i].pos]=i;
        b[bb[i].pos]=aa[i].pos;
    }
}
int ans=0;
void solve()
{
    bool swaped=true;
    while(swaped)
    {   
        swaped=false;
        for(int i=1;i<=n-1;++i)
        {
            if(b[i]>b[i+1])
            {
                Swap(b[i],b[i+1]);
                swaped=true;
                ++ans;
            }
            
        }
        ans=ans%p;
    }
    
}
int main()
{
    freopen("match.in","r",stdin);
    //freopen("match.out","w",stdout);
input();
   solve();
    printf("%d\n",ans%p);
    return 0;
}

由于这种算法的思想还十分朴素，所以只能得60分，其余的点超时。

逆序对数

逆序对：在数列a[ ]中，若有a[i],a[j]满足i<j 且 a[i]>a[j]，则有序对(a[i],a[j])称为a[ ]的一个逆序对。

在类冒泡排序中，每交换一次，就减少了b[ ]（的权值，下同）的一个逆序对。等到所有的都交换完，那么交换的次数就是逆序对数。

所以我们就可以计算b[ ]的逆序对数。

考虑n个桶cnt[ ]，cnt[x]表示当前位置i之前所有值等于x的元素个数。而每次遇到一个数a[i]，我们令cnt[a[i]]++。

这样一来，cnt[ ].sum(a[i]+1,…n)就是在位置i之前所有比a[i]大的元素的数量，也就是a[i]与其之前的所有a[j]能构成的所有逆序对数。每次将这个值累加，最后就得到了总的逆序对数。

仔细分析一下，这里需要的操作是：维护一个元素值会改变的数列的区间和。

有两种常见的做法：①树状数组，②线段树。

（还有一种是归并排序）

树状数组
 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

//树状数组
int ans=0;
int cnt[maxn],sum[maxn];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int k=1)
{
 cnt[x]+=k;
 for(int i=x;i<=n;i+=lowbit(i))
     sum[i]+=k;
}
inline int Sum(int x)
{
 int summ=0;
 for(int i=x;i>=1;i-=lowbit(i))
 {
     summ+=sum[i];
     summ%=p;
 }
 return summ;
}
void solve()
{
 for(int i=1;i<=n;++i)
 {
     add(b[i]);
     ans+=Sum(n)-Sum(b[i]);
     ans%=p;
 }
}
理论小优化

在上面程序的这个片段：

ans+=Sum(n)-Sum(b[i]);

在这里我们需要的仅仅是cnt[ ].sum(b[i]+1,n)，但是我们却求了cnt[ ].sum(1,n)、cnt[ ].sum(1,b[i])。

所以我们在添加时可以反转一下。

1
2
3
4
5
6
7
8
9

void solve()
{
   for(int i=1;i<=n;++i)
   {
       add(n-b[i]+1);
       ans+=Sum(n-b[i]);
       ans%=p;
   }
}

这样就减少了求前缀和的次数。不过从这道题的时间上看似乎没有多少优化……

重要提醒

题目中要求对答案取模，而且模数不是一般使用的1e9+7，而是不常见的99999997。不然……只有80分。

货车运输

题意分析

给定一个无向图与每条边的权值，接下来多次询问两点间路径上的最小值的最大值。

Floyd

Floyd一般用来求多源两点最短路径，但是将其代码略加修改也可求两点间路径最小值的最大值。但是其时间复杂度为n$^3$，而且用邻接矩阵存储的时候内存会超出限制。

不过在一时想不出算法的时候可以这样取得10分，或者用于小数据的对拍。

 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

/*
truck
Floyd
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=10003;
const int maxm=50003;
const int inf=2147483647;
void read(int& A)
{
   char r;
   for(r=getchar();r<48||r>57;r=getchar());
   for(A=0;r<=57&&r>=48;r=getchar())A=A*10+r-48;
}
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
T Min(const T& a,const T& b){return a<b?a:b;}
int n,m,q;

int d[1003][1003];

void input()
{
   read(n),read(m);
   int x,y,z;
   for(int i=1;i<=n;++i)
   {
       for(int j=1;j<=n;++j)
       {
           d[i][j]=-1;
           if(i==j)
           d[i][j]=inf;
       }
   }
   for(int i=1;i<=m;++i)
   {
       read(x),read(y),read(z);
       if(z>d[x][y])
           d[x][y]=d[y][x]=z;
   }
}
void Floyd()
{
   for(int k=1;k<=n;++k)
   {
       for(int i=1;i<=n;++i)
       {
           for(int j=1;j<=n;++j)
           {
               if(Min(d[k][i],d[k][j])>d[i][j])
                   d[i][j]=d[j][i]=Min(d[k][i],d[k][j]);
           }
       }
   }
}
int main()
{
   freopen("truck.in","r",stdin);
   freopen("truck.out","w",stdout);
   input();
   Floyd();
   read(q);
   int x,y;
   for(int i=1;i<=q;++i)
   {
       read(x),read(y);
       printf("%d\n",d[x][y]);
   }
   return 0;
}

二分答案+DFS

求最小值的最大值，我们想到二分答案。但是在判断答案是否可行时需要注意尽量选择权值大的边。通过这样的算法可以通过25分。

  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

/*
Truck
Binary search + dfs
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=10003;
const int maxm=50003;
const int inf=2147483647;
void read(int& A)
{
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(A=0;r<=57&&r>=48;r=getchar())A=A*10+r-48;
}
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
int n,m,q;

struct EDGE
{
    int to,w,nxt;
    inline void init(int too,int ww,int nxtt)
    {
        to=too,w=ww,nxt=nxtt;
    }
}edge[maxm<<1];
int ek=0,node[maxn];
inline void addEdge(int from,int too,int ww)
{
    edge[++ek].init(too,ww,node[from]);
    node[from]=ek;
}
int maxw=-inf;
void input()
{
    read(n),read(m);
    int x,y,z;
    for(int i=1;i<=m;++i)
    {
        read(x),read(y),read(z);
        if(x!=y)
            addEdge(x,y,z),
            addEdge(y,x,z);
        if(z>maxw)
            maxw=z;
    }
}
bool vis[maxn];
bool can(int k,int a,int b)
{
    if(a==b)return true;
    vis[a]=true;
    for(int i=node[a];i;i=edge[i].nxt)
    {
        #define v edge[i].to
        if(!vis[v]&&edge[i].w>=k)
        {
            if(can(k,v,b))
                return true;
        }
    }
    return false;
}
int BS(int s,int t)
{
    int l=0,r=maxw,mid,ans=-1;
    while(l<=r)
    {
        mid=(l+r)>>1;
        for(int i=1;i<=n;++i)
        {
            vis[i]=false;
        }
        if(can(mid,s,t))
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return ans;
}
int main()
{
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    input();
    read(q);
    int x,y;
    for(int i=1;i<=q;++i)
    {
        read(x),read(y);
        printf("%d\n",BS(x,y));
    }
    return 0;
}

最大生成树+LCA

其实凭题目的描述我们应该隐隐约约感到这应该是一道与树有关的题目，但是苦于这是一张无向图，无法直接应用树上的相关算法。

下面给出解决这个问题的方法。

一个结论

无向图中两点间所有路径中权值最小值最大的那一条一定在该无向图的最大生成树上。

（不一定正确的）证明：

对两点a、b， 假设存在一条不在最大生成树上的路径w，且w上的边的权值最小值比经过最大生成树的路径y的边的权值最小值大，如下图。（黑色表示最大生成树中的边，其余的边未画出。在当前的情况下，左右两部分仅通过y[j]这条边相连通）

设w上的边集为{w1,w2,w3…wm}，y上的边集为{y1,y2,y3…yn}

则有min{w[ ]}＞min{y[ ]}，则存在i,j使w[i]＞y[j]。

根据构造最大生成树的算法（与最小生成树基本相同），我们每次选择权值较大的边连接两个暂未连通的子图。那么我们一定会先选择w[i]，而不会选择y[j]，因为即使路径y在y[j]处断开，最后的树一定也是使所有的点连通的（如下图）。

所以如果按照最大生成树的算法构造后，一定不会出现之前假设的情况。

则无向图中两点间所有路径中权值最小值最大的那一条一定在该无向图的最大生成树上。证毕。

具体步骤

  1. 求出给定无向图的最大生成树（类Kruskal）。

  2. 对于每个输入的两点，求出最大生成树上这两点间路径上的边权最小值。（树链剖分或各种LCA）。

这里我们使用倍增LCA，令ancestor[a][i]表示a节点向上走$2^i$条边后到达的祖先。为了求区间的最小值，我们再开辟一个类似存放方式的数组MIN[a][i]表示a上跳到ancestor[a][i]所经过的边的权值的最小值。

  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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

/*
 truck 
 Max-ST+LCA
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
//tools
void read(int &A)
{
    
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
    
    //scanf("%d",&A);
}
const int maxn=10003;
const int maxm=50003;
const int inf=2147483647;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
T Min(const T& a,const T& b){return a<b?a:b;}
int n,m,q;
//edge & graph
struct EDGE
{
    int from,to,w,nxt;
    inline void init(int fromm,int too,int ww)
    {
        from=fromm,to=too,w=ww;
    }
    inline void link(int nxtt)
    {
        nxt=nxtt;
    }
}edge[maxm<<1];
int ek=0,node[maxn];
bool cmp(const EDGE& a,const EDGE& b){return a.w>b.w;}

inline void addEdge(int from,int too,int ww)
{
    edge[++ek].init(from,too,ww);
}

void input()
{
    read(n),read(m);
    int x,y,z;
    for(int i=1;i<=m;++i)
    {
        read(x),read(y),read(z);
        if(x!=y)
            addEdge(x,y,z);
    }
}

//Union Find
int f[maxn],Size[maxn];
inline int findf(int x)
{
    if(f[x]!=x)
        f[x]=findf(f[x]);
    return f[x];
}
inline void unite(int a,int b)
{
    int fa=findf(a),fb=findf(b);
    if(Size[fa]>Size[fb])
    {
        Swap(fa,fb);
    }
    f[fa]=fb;
    Size[fb]+=Size[fa];
}
bool onTree[maxm];
//Kruskal & make Tree
void Kruskal()
{
    sort(edge+1,edge+ek+1,cmp);
    int edgeIn=0;
    int i;
    for(int i=1;i<=n;++i)
        f[i]=i;
    for(i=1;i<=ek;++i)
    {
        #define fro edge[i].from
        #define tto edge[i].to
        if(findf(fro)!=findf(tto))
        {
            unite(fro,tto);
            onTree[i]=true;
            ++edgeIn;
            if(edgeIn==n-1)
            break;
        }
    }
    for(int j=1;j<=i+1;++j)
    {
        if(onTree[j])
        {
            edge[j].link(node[edge[j].from]);
            node[edge[j].from]=j;
            
            ++ek;
            edge[ek].from=edge[j].to;
            edge[ek].to=edge[j].from;
            edge[ek].w=edge[j].w;
            
            edge[ek].link(node[edge[ek].from]);
            node[edge[ek].from]=ek;
        }
    }
}
int ancestor[maxn][32],minn[maxn][32];
int depth[maxn];
const int max2=14;
void Init(int k)
{
    for(int i=1;i<=max2&&(1<<i)<=n;++i)
    {
        ancestor[k][i]=ancestor[ancestor[k][i-1]][i-1];
        minn[k][i]=Min(minn[ancestor[k][i-1]][i-1],minn[k][i-1]);
    }
    for(int i=node[k];i;i=edge[i].nxt)
    {
        #define v edge[i].to
        if(!depth[v])
        {
            depth[v]=depth[k]+1;
            ancestor[v][0]=k;
            minn[v][0]=edge[i].w;
            Init(v);
        }
    }
}

int maxLimit(int a,int b)//LCA
{
    if(findf(a)!=findf(b))return -1;
    if(a==b)return a;
    
    int ans=inf;    
    if(depth[a]<depth[b])
        Swap(a,b);
    int distance=depth[a]-depth[b];
    for(int i=max2;i>=0;--i)
    {
        if((1<<i)&distance)
        {
            if(minn[a][i]<ans)
                ans=minn[a][i];
            a=ancestor[a][i];
        }
    }
    if(a==b)
        return ans;
    for(int i=max2;i>=0;--i)
    {
        if(ancestor[a][i]!=ancestor[b][i])
        {
            if(minn[a][i]<ans)
                ans=minn[a][i];
            if(minn[b][i]<ans)
                ans=minn[b][i];
            a=ancestor[a][i],b=ancestor[b][i];
        }
    }
    if(minn[a][0]<ans)
        ans=minn[a][0];
    if(minn[b][0]<ans)
        ans=minn[b][0];
    return ans;
}

void solve()
{
    for(int i=1;i<=n;++i)
    {
        if(!depth[i])
        {
            depth[i]=1;
            Init(i);
        }
    }
    read(q);
    int x,y;
    for(int i=1;i<=q;++i)
    {
        read(x),read(y);
        printf("%d\n",maxLimit(x,y));
        //system("pause");
    }
}
int main()
{
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    input();
    Kruskal();  
    solve();
    
    return 0;
}

Day2

积木大赛

题意分析

给定序列h[ ]，和一个空序列x[ ]，每次可以将x[ ]中一个区间内的数加一，求最少的操作次数使x[ ]与h[ ]相同。

暴力
 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

/*
    block
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100003;
int n,h[maxn],sum=0;
int main()
{
    //freopen("block.in","r",stdin);
    //freopen("block.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&h[i]);
    }
    int start=1;
    while(start!=n+1)
    {
        int i;
        for(i=start;i<=n&&h[i]==0;++i);
        start=i;
        if(start!=n+1)
        {
            while(i!=n+1)
            {
                while(i<=n&&h[i]==0)
                    ++i;
                if(i!=n+1)
                {
                    for(;i<=n&&h[i]>=1;++i)
                    --h[i];
                    ++sum;
                }
            }   
        }
    }
    printf("%d\n",sum);
    return 0;
}

在cena上测居然有80分。。

奇怪的优化

我们换一种思路，如图，可以看出盖好每一层所需要的操作次数就是这一层相连的段的个数，因为我们每次操作时可以一次完成一段。那么总的操作次数就是每一层这样的段的个数之和。

统计这样的段的个数的方法：

开辟一个last[ ]数组,last[i]存放当前上一个不小于i的数的位置。

再开辟一个cnt[ ]数组存放每层的段的个数。

读入h[i]时，用j枚举它所占的段(1~h[i])，如果last[j]≠i-1或者i＝1，则说明第j层的上一个段已经结束并且出现了中断。那么第j层的段个数加1，即++cnt[j]。

 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

/*
    Block+
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
void read(int &A)
{
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
const int maxn=100003;
const int maxt=10003;
int n,h[maxn],sum=0,cnt[10003],last[10003],maxi=0;
int main()
{
    //freopen("block.in","r",stdin);
    //freopen("block.out","w",stdout);
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(h[i]);
        if(h[i]>maxi)
            maxi=h[i];
        for(int j=h[i];j>=1;--j)
        {
            if(last[j]!=i-1||i==1)
            {
                ++cnt[j];
            }
            last[j]=i;
        }
    }
    for(int i=1;i<=maxi;++i)
        sum+=cnt[i];
    printf("%d\n",sum);
    return 0;
}

这样可以过90分。

连续非降子序列

考虑一个先上升后下降的区间，例如4 7 3，盖完这个区间所需要的操作次数取决于区间内最大的那个数（7）。因为这样的区间好比一个金字塔，每次操作都可以直接盖完一层。

同时我们发现，这个区间所需要的操作次数可以看作只与前面上升的部分有关，因为后面下降的部分可以在某次操作的时候连带着处理掉。

所以我们需要的就是找出数列内的连续非降子序列。以图中为例，其中69是一个连续非降子序列。但是我们发现6被包括在前一个先上升后下降的区间内。那么6对应的这一层，即第1层，在前面已经被处理掉了。那么对于79，我们只要依次补上绿色，紫色，青色的部分，而每次所需的操作次数就是7、8、9与前一列的高度差。

整理一下思路，最后的步骤就是：找出所有的连续非降子序列，从第二项开始将答案加上这一项与前一项的差值。当然，第一个数要特判一下。

再思考一下，我们发现每次被我们舍掉的连续非降子序列的第一项都有h[i]<h[i-1]，而其他项都有h[i]>=h[i-1]，我们就可以将h[0]设为零，这样可以简化代码。

又由于我们只计算了差值，所以数组也是不需要的了，只要两个变量循环使用即可。

 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

/*
Block
连续非降子序列
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
void read(int &A)
{
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
int n,h1=0,h2,sum=0;
int main()
{
    freopen("block.in","r",stdin);
    //freopen("block.out","w",stdout);
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(h2);
        if(h2>=h1)sum+=h2-h1;
        h1=h2;
    }
    printf("%d\n",sum);
    return 0;
}//可以AC了。

花匠

题意分析

给定一个数列，求最少移除几个数，使得剩下的数列满足下列两个条件之一：

  1. 所有偶数位的数都大于它两边相邻的数。

  2. 所有偶数位的数都小于它两边相邻的数。

    输出最多留下的数的个数。

骗分

时间不够的时候可以考虑只拿前20分。

这里用位运算枚举每一种情况并判断条件是否成立。

 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

/*
   flower
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
inline void read(int &A)
{
   char r;
   for(r=getchar();r<48||r>57;r=getchar());
   for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
const int maxn=100003;
const int maxt=1000003;
const int inf=2147483647;
int n,h[maxn],ans=inf;
int getnum(int x)
{
   int sum=0;
   for(int i=0;i<=n-1;++i)
   {
       if(x&1<<i)
           ++sum;
   }
   return sum;
}
int g[maxn],gk;
void lay(int x)
{
   gk=0;
   for(int i=0;i<=n-1;++i)
   {
       if(!(x&(1<<i)))
       {
           g[++gk]=h[i+1];
       }
   }
}
bool judgeA(int x)
{
   g[gk+1]=0;
   for(int i=2;i<=gk;i+=2)
   {
       if(!(g[i]>g[i-1]&&g[i]>g[i+1]))
               return false;
   }
   return true;
}
bool judgeB(int x)
{
   g[gk+1]=inf;
   for(int i=2;i<=gk;i+=2)
   {
       if(!(g[i]<g[i-1]&&g[i]<g[i+1]))
               return false;
   }
   return true;
}
int main()
{
   freopen("flower.in","r",stdin);
   freopen("flower.out","w",stdout);
   read(n);
   for(int i=1;i<=n;++i)
   {
       read(h[i]);
       if(h[i]==h[i-1])--i,--n;
   }
   if(n==1)
   {
       printf("1\n");
       return 0;
   }
   int tn;
   for(int i=0;i<=(1<<n+1)-2;++i)
   {
       
       if((tn=getnum(i))<ans)
       {
           lay(i);
           if(judgeA(i))
           {       
               ans=tn;
           }
           else if(judgeB(i))
           {
               ans=tn;
           }
       }
   }
   printf("%d\n",n-ans);
   return 0;
}
拐点

考虑一个连续单调的区间，那么在这个区间里最多只能留下两个数。

假设留下的数为a，b，c，（以a＞b＞c为例）：

  1. 若b为偶数位，则b不满足任何一个条件。

  2. 若b为奇数位，则要满足：

    1.  a上一个数＜a

    2.  c下一个数＞c

但是题目要求的是一次只能满足一个条件，所以也不可行。

为了尽量不影响前后的选择，我们在这样的区间里选择留下第一个和最后一个数。可以证明的是如果不选这两个，会有一些可行的情况无法达到，但是所有不选这两个的情况都可以用这两个数的情况代替。

可以看出一个单增区间的第一个元素就是上一个单减区间的最后一个元素，所以我们的寻找过程就像是在依次找数列的极大值和极小值（可以形象地理解成山峰和山谷）。

类似的思路，连续的相同的数只能留一个，在输入的时候去重即可。

另外，第一个点和最后一个点一定可以留下。

如图，假设从2开始形成了一个满足条件的数列，则有两种情况：

  1. h[1]＞h[2]

    那么h[1]可以代替h[2]留下，不影响答案。

  2. h[1]＜h[2]

    那么h[1]加入后，使得原数列：

    如果满足A条件，现在满足B；

    如果满足B条件，现在满足A。

 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

/*
    flower
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
inline void read(int &A)
{
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
const int maxn=100003;
const int maxt=1000003;
const int inf=2147483647;
int n,h[maxn],ans=2;
int main()
{
    freopen("flower.in","r",stdin);
    freopen("flower.out","w",stdout);
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(h[i]);
        if(h[i]==h[i-1])
            --i,--n;
    }
    bool up=bool(h[2]>h[1]);
    for(int i=2;i<=n;++i)
    {
        if(up!=bool(h[i]>h[i-1]))
        {
            ++ans;
            up=!up;
        }
    }
    printf("%d\n",ans);
    return 0;
}
易错点

  1. 可能是题目描述的原因，设留下的数的个数为m，若m为偶，那么g[m]只要在条件A中满足g[m]＞g[m-1]，或者在条件B中满足g[m]＜g[m+1]即可。

  2. 输入时记得去重。

华容道

DFS

用空白块的位置和待移动棋子的位置和时间作为状态，然后DFS。

一个优化是记忆化，维护达到每个状态的最短时间，如果下一次到达这个状态时时间已经超过记下的最短时间，则不再继续向下。

  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

/*
Puzzle
DFS
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
int n,m,q;
int b[33][33];
const int inf=2147483647;
int exx,eyy,sxx,syy,tx,ty,ans;
void input()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&b[i][j]);
        }
    }
}
inline bool can(int x,int y)
{
    return bool(x>0&&x<=n&&y>0&&y<=m&&b[x][y]!=0);
}
const int dx[]={0,-1,0,1,0};
const int dy[]={0,0,1,0,-1};
int used[33][33][33][33];
inline void flag(int ex,int ey,int sx,int sy,int t)
{
    used[ex][ey][sx][sy]=t;
}
inline bool Used(int ex,int ey,int sx,int sy,int t)
{
    return used[ex][ey][sx][sy]!=0&&used[ex][ey][sx][sy]<=t;
}
void dfs(int ex,int ey,int sx,int sy,int t)
{
    if(sx==tx&&sy==ty)
    {
        if(t<ans)ans=t;
        return;
    }
    if(t>ans)return;
    int nx,ny;
    for(int i=1;i<=4;++i)
    {
        nx=ex+dx[i];
        ny=ey+dy[i];
        if(can(nx,ny))
        {
            if(nx==sx&&ny==sy)
            {
                if(!Used(nx,ny,ex,ey,t+1))
                {
                    flag(nx,ny,ex,ey,t+1);
                    dfs(nx,ny,ex,ey,t+1);
                }
            }
            else
            {
                if(!Used(nx,ny,sx,sy,t+1))
                {
                    flag(nx,ny,sx,sy,t+1);
                    dfs(nx,ny,sx,sy,t+1);
                }   
            }           
        }
    }
}
void solve()
{
    if(sxx==tx&&syy==ty)
    {
        ans=1;
        return;
    }
    ans=inf;
    memset(used,0,sizeof(used));
    flag(exx,eyy,sxx,syy,1);
    dfs(exx,eyy,sxx,syy,1);
    if(ans==inf)
        ans=0;
}
int main()
{
    freopen("puzzle.in","r",stdin);
    freopen("puzzle.out","w",stdout);
    input();
    for(int i=1;i<=q;++i)
    {
        scanf("%d%d%d%d",&exx,&eyy,&sxx,&syy);
        scanf("%d%d",&tx,&ty);
        solve();
        printf("%d\n",ans-1);
    }
    return 0;
}

这样可以过40分。

DFS+曼哈顿距离

在DFS时我们考虑一下剪枝。首先如果当前所用时间已经超过当前最段完成时间那么可以直接退出。

还有一种想法，假设待移动棋子和目标位置之间没有任何障碍，而且待移动棋子和空白块之间也没有任何障碍，那么我们可以理想的认为最后的步数就是将空白块移到待移动棋子，然后利用空白块将待移动棋子移到目标位置。也就是空白块到待移动棋子的曼哈顿距离加上待移动棋子到目标位置的曼哈顿距离之和。

不过由于这道题的图实在太小，只有30，所以这样的优化没有太大作用，这里作为参考。

BFS+STLqueue

其实这样的题目一看就应该用BFS来写，我们用一个结构体来存放状态，然后开始BFS。第一次搜到答案时就是最短的时间。

记忆化也是可以用的。不过这里只用记下某个状态（不包括所用时间）是否到过。因为第二次搜到时时间一定没有第一次搜到时时间少。

这里先用STL的队列实现。

  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

/*
Puzzle
BFS，STL queue
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
int n,m,q;
int b[33][33];

int tx,ty,ans;
void input()
{
   scanf("%d%d%d",&n,&m,&q);
   for(int i=1;i<=n;++i)
   {
       for(int j=1;j<=m;++j)
       {
           scanf("%d",&b[i][j]);
       }
   }
}

struct node
{
   int ex,ey,sx,sy,t;
   inline node(){ex=ey=sx=sy=t=0;}
   inline node(
   int exx,int eyy,
   int sxx,int syy
   ):ex(exx),ey(eyy),sx(sxx),sy(syy)
   {}
   inline void input()
   {
       scanf("%d%d%d%d",&ex,&ey,&sx,&sy);
   }
}tmp,bak;
inline bool can(int x,int y)
{
   return bool(x>0&&x<=n&&y>0&&y<=m&&b[x][y]!=0);
}
const int dx[]={0,-1,0,1,0};
const int dy[]={0,0,1,0,-1};
bool used[33][33][33][33];
inline void flag()
{
   used[tmp.ex][tmp.ey][tmp.sx][tmp.sy]=true;
}
inline bool Used()
{
   return used[tmp.ex][tmp.ey][tmp.sx][tmp.sy];
}
void solve()
{
   if(tmp.sx==tx&&tmp.sy==ty)
   {
       ans=0;
       return;
   }
   ans=-1;
   memset(used,0,sizeof(used));
   flag();
   queue<node> qu;
   qu.push(tmp);
   while(!qu.empty())
   {
       bak=qu.front();
       qu.pop();
       int nx,ny;
       for(int i=1;i<=4;++i)
       {
           tmp=bak;
           nx=tmp.ex+dx[i];
           ny=tmp.ey+dy[i];
           if(can(nx,ny))
           {
               Swap(nx,tmp.ex);
               Swap(ny,tmp.ey);
               if(tmp.ex==tmp.sx&&tmp.ey==tmp.sy)//change the chosen one
               {
                   tmp.sx=nx,tmp.sy=ny;
               }
               ++tmp.t;
               if(tmp.sx==tx&&tmp.sy==ty)//arrived
               {
                   ans=tmp.t;
                   return;
               }
               if(!Used())
               {
                   flag();
                   qu.push(tmp);
               }
           }
       }
   }
}
int main()
{
   freopen("puzzle.in","r",stdin);
   freopen("puzzle.out","w",stdout);
   input();
   for(int i=1;i<=q;++i)
   {
       tmp.input();
       scanf("%d%d",&tx,&ty);
       tmp.t=0;
       solve();
       printf("%d\n",ans);
   }
   return 0;
}
BFS+手写queue

接下来用手写的队列实现。这里为简化代码没有使用循环队列，队列元素个数上限可以通过使用STL实现的队列的代码已经随机生成的大数据来测试入队最大次数。

为了达到极限情况，我们生成一张没有障碍的图。

随机数生成器
 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

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
int b[33][33];
int n=30,m=30,q=500;
inline bool can(int x,int y)
{
    return bool(x>0&&x<=n&&y>0&&y<=m&&b[x][y]!=0);
}
int main()
{
    freopen("puzzlet3.in","w",stdout);
    srand(time(NULL));

    cout<<n<<' '<<m<<' '<<q<<endl;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        { 
/*
            int t=rand()%7;
           
            if(t<=4)
                b[i][j]=1;
            else b[i][j]=0;  //生成一张随机的图
            */
            b[i][j]=1;//生成一张没有障碍的图
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cout<<b[i][j]<<' ';
        }
        cout<<endl;
    }
    for(int i=1;i<=q;++i)
    {
        int ex,ey,sx,sy,tx,ty;
        do
        {
            ex=rand()%(n-1)+1;
            ey=rand()%(m-1)+1;
        }while(!can(ex,ey));
        do
        {
            sx=rand()%(n-1)+1;
            sy=rand()%(m-1)+1;
        }while(!can(sx,sy));
        do
        {
            tx=rand()%(n-1)+1;
            ty=rand()%(m-1)+1;
        }while(!can(tx,ty));
        cout<<ex<<' '<<ey<<' ';
        cout<<sx<<' '<<sy<<' ';
        cout<<tx<<' '<<ty<<' ';
        cout<<endl;
    }
    return 0;
}

这样测试之后我们得出队列所需的最大空间约为1000000。

具体代码
  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

/*
Puzzle
BFS+手写queue
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
int n,m,q;
int b[33][33];

int tx,ty,ans;
void input()
{
   scanf("%d%d%d",&n,&m,&q);
   for(int i=1;i<=n;++i)
   {
       for(int j=1;j<=m;++j)
       {
           scanf("%d",&b[i][j]);
       }
   }
}

struct node
{
   int ex,ey,sx,sy,t;
   inline node(){ex=ey=sx=sy=t=0;}
   inline node(
   int exx,int eyy,
   int sxx,int syy
   ):ex(exx),ey(eyy),sx(sxx),sy(syy)
   {}
   inline void input()
   {
       scanf("%d%d%d%d",&ex,&ey,&sx,&sy);
   }
}tmp,bak;
inline bool can(int x,int y)
{
   return bool(x>0&&x<=n&&y>0&&y<=m&&b[x][y]!=0);
}
const int dx[]={0,-1,0,1,0};
const int dy[]={0,0,1,0,-1};
bool used[33][33][33][33];
inline void flag()
{
   used[tmp.ex][tmp.ey][tmp.sx][tmp.sy]=true;
}
inline bool Used()
{
   return used[tmp.ex][tmp.ey][tmp.sx][tmp.sy];
}
//288684
//737993
const int maxnode=1000003;
node qu[maxnode];
int f,t;//队首指针，队尾超尾指针
void solve()
{
   if(tmp.sx==tx&&tmp.sy==ty)
   {
       ans=0;
       return;
   }
   ans=-1;
   memset(used,0,sizeof(used));
   flag();
   f=1,t=1;
   qu[t++]=tmp;
   while(f!=t)
   {
       bak=qu[f];
       ++f;
       int nx,ny;
       for(int i=1;i<=4;++i)
       {
           tmp=bak;
           nx=tmp.ex+dx[i];
           ny=tmp.ey+dy[i];
           if(can(nx,ny))
           {
               Swap(nx,tmp.ex);
               Swap(ny,tmp.ey);
               if(tmp.ex==tmp.sx&&tmp.ey==tmp.sy)//change the chosen one
               {
                   tmp.sx=nx,tmp.sy=ny;
               }
               ++tmp.t;
               if(tmp.sx==tx&&tmp.sy==ty)//arrived
               {
                   ans=tmp.t;
                   return;
               }
               if(!Used())
               {
                   flag();
                   qu[t++]=tmp;
               }
           }
       }
   }
}
int main()
{
   freopen("puzzle.in","r",stdin);
   freopen("puzzle.out","w",stdout);
   input();
   for(int i=1;i<=q;++i)
   {
       tmp.input();
       scanf("%d%d",&tx,&ty);
       tmp.t=0;
       solve();
       printf("%d\n",ans);
   }
   return 0;
}

这两个算法都可以得到70分，但是STL在一般情况下速度会比较慢。

如图是将单个测试点时限设为20秒时两个算法的时间比较，可以看出，手写的队列比STL几乎快一倍。

BFS+SPFA
概述

观察这个题目的特点，我们发现这个图特别小（30×30）。

在这个图上我们可以用空白块的位置和待移动棋子的位置来描述一个状态，那么如果不考虑到达时间的话，一共有304=810000中状态。

状态数也很少。

当空白块移到待选择棋子旁边之后，待移动棋子就可以在不同的状态之间进行转换，这类似于图中各节点之间的边。需要的时间可以看成是节点之间的边权。这道题中边权可以通过BFS预处理得到。

于是我们就可以将各个状态抽象成一个个节点，要 求的 就是从初始状态节点到待移动棋子与目标位置重合的状态的节点间的最小权值和。

这就是图上的最短路。跑一遍SPFA即可。

空白块

先来讲讲空白块的一些东西。我们想象一下空白块的移动过程：与毗邻的位置上的格子交换位置。我们换一种思路想，在一个没有障碍的棋盘里，空白块的移动就近似于在图上自由滑动，这是一个极大的思维突破。

或者说：因为空白块是自由的天使，所以空白块可以自由地飞~~

（来自某题解博客，一下找不到了，抱歉）

具体步骤

  1. 预处理

    在一开始读入图的时候我们要预处理出上述的抽象的图。由于空白块的位置未知，所以我们在这里先只考虑空白块在待移动棋子的四周（最多有4种可能情况）。这样的状态可以用一个三元组表示为(x,y,k)，表示待移动棋子在(x,y)，白格子在它的k方向。

    我们主要考虑待移动棋子的位置，那么在这个状态最多可以让待移动棋子向4个方向移动一格（如果可以的话）。

    把这个过程分解一下，有两个步骤：

    1. 将空白块移到要移动的方向上且毗邻待移动棋子的位置。

    2. 交换空白块和待移动棋子。

    其中第二步只用花费1单位时间，而第一步花费的最少时间可以通过BFS实现。（即空白块“滑动”到那里花的时间/距离）

    所以我们可以用step[i][j][k][h]表示待移动棋子在(i,j)，空白块在它的k方向,要使它移动到h方向毗邻的位置花费的时间。

    **注意：**第一步有可能出现无法到达的情况，BFS返回inf，所以我们在预处理step[i][j][k][h]的时候可以先不加上第二步的1单位时间，后面用到的时候再加。

  2. 处理询问

    1. 计算空白块移动到待移动棋子旁边所花时间

    没有空白块在旁边，待移动棋子不能挪动半步。所以空白块要先移到待移动棋子旁边，可以BFS实现。

    由于空白块可以在待移动棋子的4个方向，所以我们要一直BFS到4个方向都到达，或者全部BFS结束。

    **注意：**如果待移动棋子已经在目标位置则答案为零，不需要移动空白块。（如果忽视就只有65分）

    1. SPFA计算最短路

    在刚开始的时候我们已经预处理出了空白块在待移动棋子旁边的所有状态及之间的转换关系，现在只要计算到达目标状态的最短路即可。

    需要注意的是，出发点可以是空白块在待移动棋子4个方向的4个状态中的任何一个（如果可行的话）。但是SPFA好像只适用于单源最短路？

    思考后我们发现，这4个状态有着共同的来源。即都由空白块原来的位置转换过来。所以我们可以认为存在一个超级源点，这个源点到上述4个状态的边权就是第一步中计算的空白块移动到4个状态所花的时间。

    最后计算这个超级源到目标状态（待移动棋子和目标位置重合）的最短路即可。

    另外，在预处理的时候我们并没有加上空白块和待移动棋子交换的那一单位时间，所以这里在使用step[i][j][k][h]更新最短路时应该加上1。（当然前提是step[i][j][k][h]≠inf）

实现代码
  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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251

/*
Puzzle
BFS+SPFA
    http://www.cnblogs.com/zbtrs/p/5747391.html
    http://blog.csdn.net/fsahfgsadhsakndas/article/details/48784717
    http://blog.csdn.net/u013517878/article/details/40085405
    http://www.cnblogs.com/ivorysi/p/5879100.html
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
void read(int& A)
{
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
int n,m,q;
int b[33][33];
int sx,sy,ex,ey,tx,ty;
const int dx[]={0,-1,0,1,0};
const int dy[]={0,0,1,0,-1};
typedef unsigned int uint;
const int inf=2147483647;
const uint uinf=4294967295u;

void input()
{
    read(n),read(m),read(q);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            read(b[i][j]);
        }
    }
}
struct node
{
    int x,y,dir;
    inline node(){x=y=dir=0;}
    inline node(int xx,int yy):x(xx),y(yy),dir(0){}
    inline node(int xx,int yy,int dirr):x(xx),y(yy),dir(dirr){}
    inline void init(int xx,int yy,int dirr=0){x=xx,y=yy,dir=dirr;}
    inline void redir()
    {
        if(dir==1||dir==3)dir=4-dir;
        if(dir==2||dir==4)dir=6-dir;
    }
    inline void move()
    {
        x+=dx[dir];
        y+=dy[dir];
        redir();
    }
    inline void move(int kk)
    {
        dir=kk;
        move();
    }
};
bool operator==(const node& a,const node& b)
{
    return a.x==b.x&&a.y==b.y;
}
//queue
const int maxnode=1000003;
template<typename T>
struct QUE
{
    T ary[maxnode];
    int f,t;
    
    inline void clear(){f=t=1;}
    inline void push(const T& w){ary[t++]=w;}
    inline bool empty(){return f==t;}
    inline void pop(){++f;}
    inline T& front(){return ary[f];}
};
QUE<node> qu;

uint step[33][33][5][5],d[33][33];
inline bool can(int x,int y)
{
    return bool(x>0&&x<=n&&y>0&&y<=m&&b[x][y]!=0);
}

uint dis(const node& a,const node& b)
{
    if(a==b)return 0;
    memset(d,255,sizeof(d));
    qu.clear();
    qu.push(a);
    d[a.x][a.y]=0;
    node v;
    while(!qu.empty())
    {
        for(int i=1;i<=4;++i)
        {
            v=qu.front();
            v.move(i);
            if(can(v.x,v.y)&&d[v.x][v.y]==uinf)
            {
                d[v.x][v.y]
                =d[qu.front().x][qu.front().y]+1;
                if(v==b)
                {
                    return d[v.x][v.y];
                }
                qu.push(v);
            }
        }
        qu.pop();
    }
    return uinf;
}
void initStep()
{
    memset(step,255,sizeof(step));
    node w,e,r;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
    {
        if(can(i,j))
        {
            b[i][j]=0;//can't move the chosen block
            for(int k=1;k<=4;++k) 
            {
                w.init(i,j);
                step[i][j][k][k]=0;
                for(int h=1;h<=4;++h) //direction from k to h
                {
                    if(h<k)
                        step[i][j][k][h]=step[i][j][h][k];//正反向相同 
                    else if(h!=k)
                    {
                        e=w;
                        e.move(k);
                        r=w;
                        r.move(h);
                        if(can(e.x,e.y)&&can(r.x,r.y))
                        step[i][j][k][h]=dis(e,r);
                    }
                }
            }
            b[i][j]=1;//recovery
        }       
    }
}

uint way[5];
void moveBlank()
{
    //因为空白块是自由的天使，所以空白块可以自由地飞~~
    //所以从待选择棋子到空白块和从空白块到待选择棋子是一样的 
    memset(way,255,sizeof(way));
    b[sx][sy]=0;
    node s;
    for(int i=1;i<=4;++i)
    {
        s.init(sx,sy);
        s.move(i);
        if(can(s.x,s.y))
        {
            way[i]=dis(s,node(ex,ey));
        }
    }
    b[sx][sy]=1;
}

uint dd[33][33][5];
bool in[33][33][5];
uint ans;
void SPFA()
{
    memset(dd,255,sizeof(dd));
    memset(in,0,sizeof(in));
    qu.clear();
    node s,u;
    if(sx==tx&&sy==ty)
    {
        ans=0;
        return; 
    } 
    for(int i=1;i<=4;++i)
    {
        if(way[i]!=uinf)
        {
            s.init(sx,sy,i);
            dd[s.x][s.y][i]=way[i];
            qu.push(s);
            in[s.x][s.y][i]=true;
        }   
    }
    while(!qu.empty())
    {
        u=qu.front();
        qu.pop();
        in[u.x][u.y][u.dir]=false;
        for(int i=1;i<=4;++i)
        {
           s=u;
           s.move(i);
            if(can(s.x,s.y)
            &&step[u.x][u.y][u.dir][i]!=uinf
            &&dd[u.x][u.y][u.dir]+step[u.x][u.y][u.dir][i]+1<dd[s.x][s.y][s.dir])
            {
                dd[s.x][s.y][s.dir]=
                dd[u.x][u.y][u.dir]+step[u.x][u.y][u.dir][i]+1;
                if(!in[s.x][s.y][s.dir])
                {
                    qu.push(s);
                    in[s.x][s.y][s.dir]=true;
                }
            }
        }    
    }

    for(int i=1;i<=4;++i)
    {
        if(dd[tx][ty][i]<ans)ans=dd[tx][ty][i];
    }
}
int main()
{
    freopen("puzzle.in","r",stdin);
    //freopen("puzzle.out","w",stdout);
    input();
    initStep();
    for(int e=1;e<=q;++e)
    {
        read(ex),read(ey),
        read(sx),read(sy),
        read(tx),read(ty);
        ans=uinf;
        moveBlank();
        if(way[1]!=uinf||way[2]!=uinf
         ||way[3]!=uinf||way[4]!=uinf)
        {
            SPFA();
        }   
        if(ans==uinf)
            printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}
关于memset

这里提一下代码里用的memset。它的作用是将某一段内存按字节初始化。

用法：

void * memset ( void * ptr, int value, size_t num )

意义：将ptr开始的长度为num的内存中的所有字节初始化为value。

要讲的是，通常使用的int变量使用4个字节的内存，但是在最左端会有一个符号位来表示这个数的正负。

因此，无法直接用

memset(a,255,sizeof(a));

将一个int数组a初始化为inf（所有的数会变成-1），因为符号位也被修改了。

解决方法有两种：

  1. 降低inf大小的要求

如果对inf的大小没有那么高的要求，则可以用

memset(a,127,sizeof(a));

来将所有a[i]初始化为：

  1. 使用无符号变量

    既然问题出在符号位，那么我们可以使用unsigned a[ ]来避免问题。

    这时可以使用

    memset(a,255,sizeof(a));

将所有a[i]初始化为：

而这个值也足够大作为inf。

更新于 2023-04-05 
本文采用CC BY-NC 4.0许可，转载请注明原文链接
NOIPOIC++
返回 | 主页
0%