codeforces 484C Strange Sorting Codeforces Round #276 (Div. 1) C

思路:首先他是对1到k 元素做一次变换，然后对2到k+1个元素做一次变化。。。。依次做完。

如果我们对1到k个元素做完一次变换后，把整个数组循环左移一个。那么第二次还是对1 到 k个元素做和第一次一样的变换，再左移，再对1 到 k个元素做和第一次一样的变换，依次做完n-k+1即可。

假设题目要求的变换为C 循环左移变换为P。那么对于每次查询相当于做 n-k+1 （CP）变换。最后把答案再向右移动n-k+1 回到原来位置即可。

那么问题就解决了效率每次查询n log（n-k+1）

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<string>

#include <iostream>

#include<vector>

#define MAXN 1000050

#define lson i<<1

#define rson i<<1|1

#define LL long long

using namespace std;

char s[MAXN];

char a[MAXN];

int p[MAXN];

int ans[MAXN];

int tmp[MAXN];

int main() {

	int n, m;

	scanf(" %s", s);

	n = strlen(s);

	scanf("%d", &m);

	for (int i = 0; i < m; ++i) {

		int k, d;

		scanf("%d%d", &k, &d);

		for (int i = 0; i < n; ++i)

			p[i] = ans[i] = i;

		int cid = 0;

		for (int x = 0; x < d; ++x)

			for (int j = x; j < k; j += d)

			{

				p[cid++] = j;

			}

		int last = p[0];

		for (int j = 0; j <n-1;++j)

			p[j] = p[j + 1];

		p[n-1] = last;

		int x = n - k + 1;

		while (x) {

			if (x & 1) {

				for (int j = 0; j < n; ++j)

					tmp[j] = ans[p[j]];

				for(int j=0;j<n;++j)

					ans[j]=tmp[j];

			}

			for (int j = 0; j < n; ++j)

				tmp[j] = p[p[j]];

			for (int j = 0; j < n; ++j)

				p[j] = tmp[j];

			x >>= 1;

		}

		for (int j = 0; j < n; ++j)

		{

			a[j] = s[ans[(j + k - 1) % n]];

		}

		for (int j = 0; j < n; ++j)

			s[j] = a[j];

		printf("%s\n", s);

	}

}

巴特西

codeforces 484C Strange Sorting Codeforces Round #276 (Div. 1) C

最新文章

热门文章