約瑟夫環——POJ3379

約瑟夫環——POJ3379

題目描述：

給出一個長度是n的字符串環，每次擱k個加入字符串中對應位置的字母序的下一個字母，執行m次，問最後一次插入的是什麼字母。

大致思路：

正著想的話只能用模擬的方法解決，但是m有10^9這麼大，而把問題倒過來想一下的話，那就變成了給出一個n+m的字符串每次擱k個字符刪掉一個，最後剩下一個長度為n的字符串，問起始位置是什麼字母。這樣的話就變成了約瑟夫問題，約瑟夫環問題可以在不用考慮內容的情況下計算出最後剩下元素的位置。又因為字符串是一個環，所以可以假定開始的位置就是1，最後操作結束的位置就是最後一個元素對應的位置。這樣的過程就只需要記錄一下這個位置被去掉了多少次即可。

過程跟約瑟夫環的過程類似，利用公式f(i) = (f(i-1)+m) % i。而如果利用這個公式遞推的話時間復雜度還是O（m）的，所以利用一個小條件，k<=10000，所以這樣的話每次就可以刪除y=(m-x)/(k+1)+1個結點了。然後利用公式，下一次開始的位置就是x+y*(k+1)，需要注意的是，如果更新過後的x並沒有超過m的話那麼x是需要減掉y的，因為去掉了y個結點，所以編號要減掉y，而如果超過m的話，那麼就不用考慮去掉的元素，因為去掉的元素編號一定在現在位置的後面，這樣只需要把x模m就可以了，之後根據公式，將得到的x模（m-y），更新m。一直進行這樣的過程，把n+m減到n停止，過程中因為是從1開始計數的，所以只需要統計一下過程中有多少次操作位置是1即可。最後把統計的結果和位置代入字符串中，輸出對應字母即可。

代碼：

#include 
#include 
#include 

using namespace std;

const int maxn = 10000 + 10;
int n,m,k;
char a[maxn];

int main() {
    while (scanf("%d%d%d",&n,&k,&m) != EOF) {
        scanf("%s",a+1);
        m += n;
        int sum = 0;
        int x = 1;
        while (m > n) {
            if (x == 1) sum++;
            int s = min(m-n,(m-x)/(k+1)+1);
            x += s*(k+1);
            if (x > m) x -= m;
            else x -= s;
            m -= s;
            x %= m;
            if (!x) x = m;
        }
        sum %= 26;
        a[x] = (a[x] - 'A' + sum) % 26 + 'A';
        cout<