题意：给定一个长度为len的字符序列，然后是n个整数，对于每一个整数ai，
将字符序列区间为[ai,len-ai+1]进行反转。求出经过n次反转之后的序列！
1 /* 2 思路1：将区间为偶数次的直接去掉！对剩下的区间进行反转。超时了，智商上的压制... 3 */ 4 #include<iostream> 5 #include<cstdio> 6 #include<algorithm> 7 #include<stack> 8 #include<cstring> 9 #include<vector> 10 #define N 100005 11 using namespace std; 12 char mp[2*N]; 13 int num[N]; 14 int cnt[N*2]; 15 16 void my_swap(int &a, int &b){ 17 a^=b; 18 b^=a; 19 a^=b; 20 } 21 22 void my_reverse(int x, int y){ 23 for(int i=x, j=y; i<j; ++i, --j){ 24 char tmp = mp[i]; 25 mp[i] = mp[j]; 26 mp[j] = tmp; 27 } 28 } 29 30 int main() { 31 scanf("%s", mp+1); 32 int m, mm=0; 33 cin>>m; 34 for(int i=0; i<m; ++i){ 35 scanf("%d", &num[i]); 36 ++cnt[num[i]]; 37 } 38 39 int len = strlen(mp+1); 40 for(int i=1; i<=len/2; ++i){ 41 if(cnt[num[i]] + cnt[len-num[i]+1])%2!=0){ 42 int x = num[i]; 43 int begin = x, end= len-x+1; 44 if(begin > end) my_swap(begin, end); 45 my_reverse(begin, end); 46 } 47 } 48 printf("%s\n", mp+1); 49 }
1 /* 2 思路2：仔细分析，每一个反转的区间左右是对称的，如果[ai, len-ai+1]区间进行反转， 3 那么就有str[ai]与str[len-ai+1]交换，str[ai+1]与str[len-ai]交换..... 4 也就是ai位置发生交换，那么ai+1，ai+2...len/2也一定发生交换。如果ai位置的交换的次数 5 为偶数就不用交换，为奇数就进行交换！ 6 */ 7 #include<iostream> 8 #include<cstdio> 9 #include<algorithm> 10 #include<stack> 11 #include<cstring> 12 #include<vector> 13 #define N 100005 14 using namespace std; 15 char mp[2*N]; 16 int cnt[N*2];//统计每一个位置交换的次数 17 18 int main() { 19 scanf("%s", mp+1); 20 int m, mm=0; 21 scanf("%d", &m) ; 22 int len = strlen(mp+1); 23 while(m--){ 24 int x; 25 scanf("%d", &x); 26 ++cnt[x], ++cnt[len-x+1]; 27 } 28 29 for(int i=2; i<=len/2; ++i) 30 cnt[i] += cnt[i-1];//第i个位置交换，那么第i+1,i+2..len/2个位置也一定发生交换 31 32 for(int i=1; i<=len/2; ++i) 33 if(cnt[i]%2!=0)//奇数位置交换 34 swap(mp[i], mp[len-i+1]); 35 printf("%s\n", mp+1); 36 }
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/4382105.html，如需转载请自行联系原作者
