萌新6：正义从不打背身（打表找规律）

题目描述

*"正义之枪从不打背身"*。小x最近迷上了无畏契约，钟爱"正义"这把武器。可他使用该武器有一条原则：不击杀（打不中）背对自己的敌人。小x实力强大，对于所有直面自己的敌人都能一击毙命。

在一次游戏中。小x面前有nnn个点位，从左往右序依次为1,2,3,……，n1,2,3,……，n1,2,3,……，n。每个点位上都有一个敌人。

每个敌人要么正面朝向小x,要么背面朝向小x。

小x实力强大，打算强迫这n个敌人玩mmm轮小游戏之后再对每个人开枪。

游戏规则如下：

在第iii轮小游戏中，依次执行以下所有操作：

* 序号为[1,i][1,i][1,i]的点位上的敌人位置改变。改变规则为: 从1,2,3,……，i1,2,3,……，i1,2,3,……，i 变为i，i−1,……,3,2,1i，i-1,……,3,2,1i，i−1,……,3,2,1(原来位于i号位置的敌人更换到1号位置，位于i-1号位置的敌人更换到2号位置……）

* 序号为[1,i][1,i][1,i]的点位上的敌人原地旋转180°。

所有小游戏过后，小x想知道。目前在每个点位的敌人是否被击败。

输入描述:

第一行输入两个整数 n,mn,mn,m接下来一行输入一个仅由'P'和‘B'组成的字符串s。si=′P′s_i='P'si=′P′ 表示第i个点位的敌人当前正面对小x。si=′B′s_i='B'si=′B′表示第i个点位的敌人当前正背对小x。对于所有数据保证：1≤m≤n≤2×1061\le m \le n\le 2\times 10^61≤m≤n≤2×106。∣s∣=n|s|=n∣s∣=n

输出描述:

输出一行n个整数。对于第i个数，如果目前位于第i个点位的敌人被击败则输出1，否则输出0。

示例1

输入

复制3 3 PPP

3 3
PPP

输出

复制0 0 1

0 0 1

做法

题解：

因为题目给出的操作是比较固定的，所以我们猜测估计会出现什么规律，为了找到规律所以要先暴力打个表，思路其实挺明确的。

我们暴力模拟里面的反转过程，看看进行 i 次后每个位置上的人原本的编号是多少，以及翻转情况

cin>>n>>m;
vector<int> a(n+1);for(int i=1;i<=n;i++)a[i]=i;for(int i=1;i<=m;i++){for(int j=1;j<=i/2;j++)//反转swap(a[j],a[i-j+1]);for(int j=1;j<=i;j++)vis[a[j]]^=1;//[1,i]方向取反printf("%2d:",i);//第i轮游戏for(int j=1;j<=i;j++)//位置变化cout<<a[j]<<" ";cout<<endl;printf("  :");for(int j=1;j<=i;j++)cout<<(vis[a[j]]?"*":"-")<<" ";//*是反转，_是不反转cout<<endl;
}输出：1:1:*2:2 1:* -3:3 1 2:* * -4:4 2 1 3:* * - -5:5 3 1 2 4:* * * - -6:6 4 2 1 3 5:* * * - - -7:7 5 3 1 2 4 6:* * * * - - -8:8 6 4 2 1 3 5 7:* * * * - - - -9:9 7 5 3 1 2 4 6 8:* * * * * - - - -
10:10 8 6 4 2 1 3 5 7 9:* * * * * - - - - -
11:11 9 7 5 3 1 2 4 6 8 10:* * * * * * - - - - -
12:12 10 8 6 4 2 1 3 5 7 9 11:* * * * * * - - - - - -
13:13 11 9 7 5 3 1 2 4 6 8 10 12:* * * * * * * - - - - - -
14:14 12 10 8 6 4 2 1 3 5 7 9 11 13:* * * * * * * - - - - - - -
15:15 13 11 9 7 5 3 1 2 4 6 8 10 12 14:* * * * * * * * - - - - - - -找出的规律是：在n个数中，从m开始，每次-2，一共（m+1）/2个数。这些位置是反转了的。其他位置都不变

#include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
int main(){scanf("%d%d",&n,&m);cin>>s;s="a"+s;for(int i=1,j=m;i<=(m+1)/2;i++,j-=2){//反转了的if(s[j]=='P') cout<<0;else cout<<1;if(i!=s.size()-1)cout<<" ";}int j;if(m%2) j=2;else j=1;for(int i=(m+1)/2+1;i<=m;i++,j+=2){if(s[j]=='P') cout<<1;else cout<<0;if(i!=s.size()-1) cout<<" ";}for(int i=m+1;i<s.size();i++){//n>mif(s[i]=='P') cout<<1;else cout<<0;if(i!=s.size()-1) cout<<" ";}
}