或者说...

是这题:http://codeforces.com/gym/100959/attachments/download/4248/20152016-petrozavodsk-winter-training-camp-makoto-rng58-soejima-sontest-4-en.pdf

感谢杨主力@FizzyDavid 带我翻译题面!

给你n个魔法镜子

你需要处理q组询问,每次你要处理

从s到t要走多少步,不能到达输出-1好了

你每一次可以沿着某个魔法镜子镜面对称

例如1 --> (3) --> 5 视为一步

解法:

我们观察

用一次镜子,是从x到达2a_i-x

用两次就是从x到达2a_j-(2a_i-x) = x + 2(a_j-a_i)

所以我们求出所有aj-ai的值

然后我们在起点以及跳过一步的地方

分别计算两点距离差要用几次2(a_j-a_i)才能到达

这个值可以预处理出来

当然,求最小值即可..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[10005];
int a[205];
int b[20005];
int n;
int sum=0;
void bfs(int x)
{
    static int que[10005];
    int front=0,rail=1;
    que[0]=0;
    for (;front<rail;front++)
    {
        int now=que[front];
        int i;
        for (i=0;i<sum;i++)
        {
            if (dp[abs(now-b[i])]==-1)
            {
                dp[abs(now-b[i])]=dp[now]+2;
                que[rail++]=abs(now-b[i]);
            }
            if ((now+b[i]<=10000)&&(dp[now+b[i]]==-1))
            {
                dp[now+b[i]]=dp[now]+2;
                que[rail++]=now+b[i];
            }
        }
    }
}
int calc(int s,int t)
{
    if (abs(s-t)%2==1) return -1;
    return dp[abs(s-t)/2];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%d",&n);
    int i;
    memset(dp,-1,sizeof(dp));
    sum=0;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        int j;
        for (j=0;j<i;j++)
        {
            b[sum++]=a[i]-a[j];
        }
    }
    sort(b,b+sum);
    sum=unique(b,b+sum)-b;
    dp[0]=0;
    bfs(0);
    int m;
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        int min_ans=-1;
        int s,t;
        scanf("%d%d",&s,&t);
        min_ans=calc(s,t);
        int j;
        for (j=0;j<n;j++)
        {
            int ans=calc(a[j]*2-s,t);
            if (ans==-1) continue;
            ans++;
            if ((ans<min_ans)||(min_ans==-1))
            {
                min_ans=ans;
            }
        }
        printf("%d\n",min_ans);
    }
    return 0;
}