The Fun Number System
题意
给你一个n,k,和一个长度为k的由′p′,′n′两种字符组成的串S给你一个n,k,和一个长度为k的由'p','n'两种字符组成的串S给你一个n,k,和一个长度为k的由′p′,′n′两种字符组成的串S
S[i]=′p′时对答案的贡献为+2iS[i]='p' 时对答案的贡献为+2^iS[i]=′p′时对答案的贡献为+2i
S[i]=′n′时对答案的贡献为?2iS[i]='n' 时对答案的贡献为-2^iS[i]=′n′时对答案的贡献为?2i
现在每一位可以选择选或者不选现在每一位可以选择选或者不选现在每一位可以选择选或者不选
要构造最终结果为n，输出构造方案，选为1，不选为0要构造最终结果为n，输出构造方案，选为1，不选为0要构造最终结果为n，输出构造方案，选为1，不选为0
做法
可以想到将问题从最后一位入手，因为如果要构造的数n为偶数，最后一位不论是p还是n必然为0，因为之前位不会影响最后一位的奇数性质，所以偶数时直接转化成一个规模更小的问题即可（用前i位构造n/2），而如果n为奇数，就要看当前位是p还是n，若当前位为p，则表示+1,那么当前位为1，问题转换为(用前i位构造n/2),若当前位为n，则表示-1，我们想要构造+1，那么就是+2 -1，也就是前一位+1，这一位-1，所以我们直接n/2,再将n+1即可（也就代表要构造n/2+1）.这样不断将问题规模变小，看最后n是否为0即可判断是否可行。
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 105;
char str[maxn];
int main()
{
int t;scanf("%d",&t);while(t--){
int k;long long n;scanf("%d%s%lld",&k,str,&n);string ans="";int flag=0;for(int i=k-1;i>=0;i--){
if(n&1){
if(str[i]=='p'){
n>>=1;}else{
n>>=1;n++;}ans+='1';}else{
n>>=1;ans+='0';}}if(n) flag=1;reverse(ans.begin(),ans.end());if(!flag) printf("%s\n",ans.c_str());else printf("Impossible\n");}return 0;
}