百度之星 2011 初赛二 第一题
2011年6月12号晚7点，参加了百度之星2011的初赛。
首先不得不说的是，百度的评测结果实在太慢了，昨天下午才通知结果，而且还没有具体情况(如提交的哪题通过了几个测试点)，只告知晋级名单。
我只做了第一题，后两题看了下没啥头绪就睡觉了，我纯粹就是玩玩而已，没想到只做一题也能晋级，太无语了^_^
第一题 Problem
一个圆环上有n个位置，这n个位置按顺时针依次标号为1,2,…,n。初始时，圆环的每个位置上都有一个1至n之间的整数，且每个整数只出现一次。
圆环可以顺时针旋转也可以逆时针旋转，给位置a和b，可以交换a和b两位置上的整数。请问通过旋转和交换，能否使得第i个位置上的数正好是i。
第一题 Solution
关键看n和b-a的关系，如果两者最大公约数为1，那么肯定可以，否则在不同的槽中进行排序看看最终结果(步长为gcd)，有点类似希尔排序的一部分。
#include <stdio.h>int n, a, b;int s, g;int arr[1000];int GCD(int a, int b){if (0 == b)return a;return GCD(b, a%b);}void sort(){int i, j;for (i = g; i < n; i++) {int tmp = arr[i];for (j = i - g; j >= 0; j -= g) {if (tmp > arr[j])break;arr[j+g] = arr[j];}arr[j+g] = tmp;}}int main(){int ans;int i, j;while (scanf("%d", &n) != EOF) {if (0 == n)break;scanf("%d %d", &a, &b);s = b - a;for (i = 0; i < n; i++)scanf("%d", arr+i);g = GCD(n, s);if (1 == g) {printf("Yes\n");continue;}sort();ans = 1;for (i = 0; i < n; i++) {if (arr[i] != i + 1) {ans = 0;break;}}if (ans)printf("Yes\n");elseprintf("No\n");}return 0;}