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[*N];
int num[N];
int cnt[N*]; 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+);
int m, mm=;
cin>>m;
for(int i=; i<m; ++i){
scanf("%d", &num[i]);
++cnt[num[i]];
} int len = strlen(mp+);
for(int i=; i<=len/; ++i){
if(cnt[num[i]] + cnt[len-num[i]+])%!=){
int x = num[i];
int begin = x, end= len-x+;
if(begin > end) my_swap(begin, end);
my_reverse(begin, end);
}
}
printf("%s\n", mp+);
}
 /*
思路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[*N];
int cnt[N*];//统计每一个位置交换的次数 int main() {
scanf("%s", mp+);
int m, mm=;
scanf("%d", &m) ;
int len = strlen(mp+);
while(m--){
int x;
scanf("%d", &x);
++cnt[x], ++cnt[len-x+];
} for(int i=; i<=len/; ++i)
cnt[i] += cnt[i-];//第i个位置交换,那么第i+1,i+2..len/2个位置也一定发生交换 for(int i=; i<=len/; ++i)
if(cnt[i]%!=)//奇数位置交换
swap(mp[i], mp[len-i+]);
printf("%s\n", mp+);
}
上一篇:Linux 磁盘管理,Linux vi/vim


下一篇:WPF、Sivelright、UWP