Codeforces Round #297 (Div. 2)B Pasha and String

B. Pasha and String

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Pasha got a very beautiful stringsfor his birthday, the string consists of lowercase Latin letters. The letters in the string are numbered from 1 to|s|from left to right, where|s|is the length of the given string.

Pasha didn’t like his present very much so he decided to change it. After his birthday Pasha spentmdays performing the following transformations on his string—each day he chose integeraiandreverseda piece of string (a segment) from positionaito position|s|-ai+1. It is guaranteed that2·ai≤|s|.

You face the following task: determine what Pasha’s string will look like aftermdays.

Input

The first line of the input contains Pasha’s stringsof length from2to2·105characters, consisting of lowercase Latin letters.

The second line contains a single integerm(1≤m≤105)— the number of days when Pasha changed his string.

The third line containsmspace-separated elementsai(1≤ai;2·ai≤|s|)—the position from which Pasha started transforming the string on thei-th day.

Output

In the first line of the output print what Pasha’s stringswill look like aftermdays.

Sample test(s)

input

abcdef12

output

aedcbf

input

vwxyz22 2

output

vwxyz

input

abcdef31 2 3

output

fbdcea

初看是模拟题,结果看了一下时间复杂度,,模拟坑定超时。

ai和s+1-ai是对称的,所以反转偶数次的相当于没翻转,奇数次的要翻转,所以我们只要统计每个字母翻转的次数,用前缀和处理。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define maxn 200005#define inf 0x3f3f3f3fchar s[maxn];int m;int sum[maxn];int p[maxn];int main(){int n;int ss;//freopen("in.txt","r",stdin); while(~scanf("%s",s)){scanf("%d",&m);ss=strlen(s)-1;memset(p,0,sizeof p);for(int i=0;i<m;i++){scanf("%d",&n);p[n-1]++;p[ss-n+1+1]–;}sum[0]=p[0];if(sum[0]%2==1)swap(s[0],s[ss]);for(int i=1;i<=ss/2;i++){sum[i]=sum[i-1]+p[i];if(sum[i]%2==1){swap(s[i],s[ss-i]);}}printf("%s\n",s); }}

,再回头,便生出无限羁绊。那是彼此的刺在对方心里留下的痕迹,

Codeforces Round #297 (Div. 2)B Pasha and String

相关文章:

你感兴趣的文章:

标签云: