首页 > 代码库 > codeforces 484C Strange Sorting Codeforces Round #276 (Div. 1) C
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 longusing 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。