2015-2016 Petrozavodsk Winter Training Camp, Makoto rng_58 Soejima Сontest 4 C - Jump

题目链接https://odzkskevi.qnssl.com/fcd8a1339876f4d6914fb1c103e9a676?v=1525698047

题意:给定一个无限的数轴上的n(n<=200)个整点 {a_i}(0<=a_i<=10^4)。给出Q(Q<=10^5)次询问,每次询问给出两个点s,t,问最少经过多少次操作从s到达t。一次操作定义为选择一个i,然后从当前位置x跳到位置2a_i-x

思路:考虑选出一个操作序列后s到了t,则我们可以列出如下等式2(a_{i1}-a_{i2}+a_{i3}-...+(-1)^{k-1}a_{ik}-(-1)^{k-1}s)=t,移项一下得到2(a_{i1}-a_{i2}+a_{i3}-...+(-1)^{k-1}a_{ik}=t+(-1)^{k-1}s,即可等价为从0走到t+(-1)^{k-1}s,我们对k分奇偶讨论,用bfs预处理出f[i][0/1]即从0奇数步和偶数步到i的最短路径,然后询问就O(1)了。

#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
const int M=1e4+10;
const int OFFSET=1e5/2; 
int n,q,s,t,i,a[205],f[N][2];
bool vis[N][2];
queue<pair<int,int> >Q;
int main(){
    read(n);
    for (i=1;i<=n;i++) read(a[i]);
    memset(f,-1,sizeof(f));
    f[OFFSET][0]=0;
    Q.push(MP(0,0));
    vis[OFFSET][0]=1;
    while (!Q.empty()){
        int x=Q.front().first,y=Q.front().second;Q.pop();
        for (i=1;i<=n;i++){
            int cur=2*a[i]-x;
            if (cur+OFFSET<0||cur+OFFSET>N-10||vis[cur+OFFSET][y^1]) continue;
            vis[cur+OFFSET][y^1]=1;
            f[cur+OFFSET][y^1]=f[x+OFFSET][y]+1;
            Q.push(MP(cur,y^1));
        }
    }
    for (read(q);q--;){
        read(s),read(t);
        int ans=-1;
        if (s+t+OFFSET<=N-10&&f[s+t+OFFSET][1]!=-1){
            if (ans==-1) ans=f[s+t+OFFSET][1];
            else ans=min(ans,f[s+t+OFFSET][1]);
        }
        if (t-s+OFFSET>=0&&f[t-s+OFFSET][0]!=-1){
            if (ans==-1) ans=f[t-s+OFFSET][0];
            else ans=min(ans,f[t-s+OFFSET][0]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注