http://www.51nod.com/Contest/ContestDescription.html#!#contestId=79
今天有点浪……
第一题想了一个多小时想到了正解，然后敲到一半就去看lol总决赛了（恭喜IG！！！！！！）
然后就没有然后了……
小D站在一个长度为n的环，环上的位置从0到n-1编号。位置0与位置n-1相邻。对于一个位置i，
小D只能跳到距离位置i不超过R[i]的位置上。
可以顺时针也可以逆时针跳。比如当n=5,R[1]=2时，小D可以跳到的位置集合为{4,0,1,2,3}。 一开始小D站在位置s，
他的终点是位置t。假设每跳一次需要单位时间1。你能求出小D跳到终点的最少需要时间吗？假如无解则输出-1。
注意因为输入规模比较大，R由以下方式生成。
R[i]=(R[i-1]×g+seed)mod~p
其中R[0],g,seed,p是给定的。
第一行给定三个整数，n,s,t。 第二行给定四个整数R[0],g,seed,p。 【数据规模与约定】 对于20%的数据，n≤100 对于40%的数据，n≤1000 对于60%的数据，1≤n≤10^5 对于100%的数据,1≤n≤10^7,0≤s,t<n,1≤p≤n,0≤R[0],g,seed<p
输出一行一个整数，表示最短时间。
9 0 2 1 3 4 7
2
刚看到这道题，我发现我好像很久很久很久以前做过？？？
不过肯定当时是抄题解的，印象不深，没怎么理解。
或者其实我没有做过，我自己yy罢了
首先我一开始去观察那个公式的性质
然后发现没什么规律
貌似就是为了输入方便……
然后我就考虑一个点所能达到的区间
画个图出来发现貌似是用贪心解决区间问题？？？
然后仔细想想好像不是
一个很显然的思路就是每次要跳到最远
然后我就画了几下，发现貌似之前搜过的点就不用再搜了
所以每一个点最多会被检查过一次，复杂度是O（n）的，可以过1e7的数据
但是我发现这涉及到跨越区间的问题（如从n-1跳到0），不好搞
而且s和t的大小关系也不确定
感觉不好实现，感觉会比较复杂
然后就硬着头皮去写，写了没多久，一看时间哇靠比赛要开始了，然后……
后来讲解我看到了标程的写法，在一些处理上非常有技巧性
我需要学习学习。代码有注释
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int MAXN = 1e7 + 10; int R[MAXN], a[MAXN], n, s, t; int g, seed, p, ans; bool val[MAXN]; int main() { scanf("%d%d%d%d%d%d%d", &n, &s, &t, &R[0], &g, &seed, &p); REP(i, 1, n) R[i] = (1ll * R[i-1] * g + seed) % p; REP(i, s, n) a[i - s] = R[i]; //a数组的作用就是把整个数组等价转化成以0为起点，方便后面处理 REP(i, 0, s) a[i - s + n] = R[i]; t = (t - s + n) % n; //注意这里s和t大小不确定 int l = 0, r = 0; _for(ans, 0, n) { if(l + n <= t || t <= r) { printf("%d\n", ans); return 0; } //注意这里是或，可以画图理解 int pl = l, pr = r; //注意l是负的，但是一旦作为数组的下标就要加上n _for(i, pl, 0) { if(val[i + n]) break; //val[i]表示i这个点有没有遍历过 l = min(l, i - a[i + n]), r = max(r, i + a[i + n]), val[i + n] = 1; } for(int i = pr; i >= 0; i--) { if(val[i]) break; l = min(l, i - a[i]), r = max(r, i + a[i]), val[i] = 1; } } puts("-1"); return 0; }
原文：https://www.cnblogs.com/sugewud/p/9902468.html