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); }}
,再回头,便生出无限羁绊。那是彼此的刺在对方心里留下的痕迹,