codeforces B. Pasha and String（贪心）

题意：给定一个长度为len的字符序列，然后是n个整数，对于每一个整数ai，

将字符序列区间为[ai,len-ai+1]进行反转。求出经过n次反转之后的序列！

/*
     思路1：将区间为偶数次的直接去掉！对剩下的区间进行反转。超时了，智商上的压制...
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#define N 100005
using namespace std;
char mp[2*N];
int num[N];
int cnt[N*2];

void my_swap(int &a, int &b){
    a^=b;
    b^=a;
    a^=b;
}

void my_reverse(int x, int y){
    for(int i=x, j=y; i<j; ++i, --j){
        char tmp = mp[i];
        mp[i] = mp[j];
        mp[j] = tmp;
    }
}

int main() {
     scanf("%s", mp+1);
    int m, mm=0;
    cin>>m;
    for(int i=0; i<m; ++i){
        scanf("%d", &num[i]);
        ++cnt[num[i]];
    }

    int len = strlen(mp+1);
    for(int i=1; i<=len/2; ++i){
        if(cnt[num[i]] + cnt[len-num[i]+1])%2!=0){
            int x = num[i];
            int begin = x, end= len-x+1;
            if(begin > end) my_swap(begin, end);
            my_reverse(begin, end);
        }
    }
    printf("%s\n", mp+1);
}

/*
    思路2：仔细分析，每一个反转的区间左右是对称的，如果[ai, len-ai+1]区间进行反转，
    那么就有str[ai]与str[len-ai+1]交换，str[ai+1]与str[len-ai]交换.....
    也就是ai位置发生交换，那么ai+1，ai+2...len/2也一定发生交换。如果ai位置的交换的次数
    为偶数就不用交换，为奇数就进行交换！
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#define N 100005
using namespace std;
char mp[2*N];
int cnt[N*2];//统计每一个位置交换的次数 

int main() {
    scanf("%s", mp+1);
    int m, mm=0;
    scanf("%d", &m) ;
    int len = strlen(mp+1);
    while(m--){
        int x;
        scanf("%d", &x);
        ++cnt[x], ++cnt[len-x+1];
    }

    for(int i=2; i<=len/2; ++i)
        cnt[i] += cnt[i-1];//第i个位置交换，那么第i+1,i+2..len/2个位置也一定发生交换 

    for(int i=1; i<=len/2; ++i)
        if(cnt[i]%2!=0)//奇数位置交换
            swap(mp[i], mp[len-i+1]);
    printf("%s\n", mp+1);
}