題意：給定一個長度為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 }
?
)
)
zzuoj 10402: C.機器人)
