首页 > 代码库 > bjfu1100 圆环

bjfu1100 圆环

这题也是2011百度之星的一道题。知道做法后代码极简单。

不过我做完后随便上网搜了一下,发现竟然还有很多不同的做法。别的做法我就不管了,我只把我的做法的原理说清楚。我做题时是按如下顺序逐步找到规律的:

① 因为可以旋转,所以a和b的具体值无所谓,只在乎b-a的值;

② 进一步,如果b-a等于1,那么无论原始排列如何,均可达到目标(原理同冒泡排序);

③ 再进一步,如果gcd(n, b-a)等于1,与上一条结果相同。这里的原因熟悉数论的人能秒懂,不懂的自己画一画,想一想吧;

④ 更进一步,如果gcd(n, b-a)=k,则可以将圆环上的数分成k个部分,每个部分内部的数可以任意相互交换(原理同上一条),而部分与部分之间的数不能相互交换(原理仍同上一条)。

有了这个结论,那么只要将圆环进行拆分,拆成k个部分,然后依次看一遍每个位置的数,如果所有的数都在目标位置或者目标位置所在部分的位置,则最终的目标状况是一定能达到的,否则就不能达到。

实现的时候,可以用每个位置的编号模k得到其部分号,不过这么做的话,需要考虑到旋转的问题,因为旋转可能使位置偏离其所属的部分,我的做法是从原始数据中的1开始编号,能解决这个问题。

代码如下:

/* * bjfu1100 * Author    : ben */#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>#include <stack>#include <string>#include <vector>#include <deque>#include <list>#include <functional>#include <numeric>#include <cctype>using namespace std;#ifdef ON_LOCAL_DEBUG#else#endifconst int maxn = 1009;int data[maxn];int gcd(int a, int b) {    int r;    while (b) {        r = a % b;        a = b;        b = r;    }    return a;}int main() {#ifdef ON_LOCAL_DEBUG    freopen("data.in", "r", stdin);#endif    int n, a, b, s, i;    while (scanf("%d", &n) == 1 && n > 0) {        scanf("%d%d", &a, &b);        int _g = gcd(n, b - a);        for (i = 0; i < n; i++) {            scanf("%d", &data[i]);            if (data[i] == 1) {                s = i;            }        }        for (i = 0; i < n; i++) {            int t = (i - s + n + 1) % n;            if ((t % _g) != (data[i] % _g)) {                break;            }        }        printf("%s\n", i < n ? "No" : "Yes");    }    return 0;}

 

bjfu1100 圆环