POI2011 移方块

题目:

  Byteasar 给他的儿子 Bytie 买了一盒共 块积木,他将这些积木从 编号,并按照一定的顺序摆成一排。Bytie 要将这些积木按照编号从小到大的顺序重新排列,但他只能做下面两种操作:
  操作 :将最后一个积木移到最前面。
  操作 :把第三个积木移到最前面。
  我们将连续进行 次同一个操作称为“一块操作”,表示为
  你需要帮助 Bytie 写一个程序,告诉他有没有一个操作序列能够使积木按照编号从小到大的顺序重新排列,并告诉他操作序列。

思路:

  因为相同置换的序列可以通过操作 相互转化,所以问题就变成了把当前置换转换成一个 置换。那么一个比较简单的办法就是从 依次把它们放到 后面。
  而操作 可以看作把第 个数字向前移 位。设 后面的距离,如果满足 有解,只要一直做 操作 次即可。这样就只把 挪到了 后,其他数字相对位置不变。
  如果 无解,那么就一定能 挪到 后两个的位置(也就是 这样),这时可以通过 移到 后面,但是这样会使 后面的两个数交换位置,所以如果此时 ,就会破坏前面排好序的数字。手玩一些数据发现如果出现这种情况好像就是无解的(证明不是很会)。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 2005, M = N * N;

vector<int> vec, ans;

void exgcd(int a, int b, int &d, int &x, int &y) {
    if(!b) {x = 1; y = 0; d = a; return;}
    exgcd(b, a % b, d, y, x); y -= a / b * x;
}
int calc(int a, int b, int c) { // ax = c (mod b)
    int x, y, d;
    exgcd(a, b, d, x, y);
    if(c % d) return -1;
    a /= d; b /= d; c /= d;
    return ((ll) x * c % b + b) % b;
}

int a[N], b[N];

int main() {
    // freopen("data.in", "r", stdin);
    int n, p;
    scanf("%d", &n);
    rep(i, 1, n) {
        scanf("%d", a + i);
        b[i] = a[i];
        if(a[i] == 1) p = i;
    }
    vec.push_back(n - p + 1);
    rep(i, p, n) a[i - p + 1] = b[i];
    rep(i, 1, p - 1) a[i + n - p + 1] = b[i];
    rep(i, 2, n) {
        rep(j, 1, n) if(a[j] == i) p = j;
        if(p == i) continue;
        vec.push_back(n - p + 1);
        int d = (p - i + n) % n;
        int stp = calc(2, n - 1, d);
        bool flag = false;
        if(stp == -1) {
            if(i == n - 1 || i == n) return puts("NIE DA SIE"), 0;
            stp = calc(2, n - 1, d - 1); 
            flag = true;
        }
        while(stp--) {
            vec.push_back(2);
            vec.push_back(-1);
        }
        if(flag) {
            vec.push_back(1);
            vec.push_back(-2);
        }
        vec.push_back(i - 1);
        drep(j, p - 1, i) a[j + 1] = a[j];
        a[i] = i;
        if(flag) swap(a[i + 1], a[i + 2]);
    }
    int lst = vec[0] % n;
    for(int i = 1; i < vec.size(); i++) {
        int t = vec[i] % n;
        if((lst < 0) == (t < 0))
            lst += t;
        else {
            lst %= n;
            if(lst) ans.push_back(lst);
            lst = t;
        }
    }
    if(lst) ans.push_back(lst);
    if(ans.empty()) return puts("0"), 0;
    printf("%d\n", (int) ans.size());
    for(int x : ans) printf("%d%c ", abs(x), (x < 0 ? 'b' : 'a'));
    puts("");
    return 0;
}