//184K 0MS C++
#include <cstdio>
#include <cstring>
using namespace std;
char NP[65]; //-1: n, 1: p
char str[80];
char digitUsed[80];
char binaryExpression[80];
int caseNum;
int length;
long long val;
void solve(long long val) {
long long curLeftVal = val;
int curDigitPos = 1;
while(1) {
// printf("%lld\n", curLeftVal);
if (curDigitPos == length) {
if (curLeftVal != 0) {
if (curLeftVal - NP[curDigitPos] != 0) {
printf("Impossible\n");
return;
} else {
binaryExpression[curDigitPos] = 1;
}
} else if (curLeftVal == 0) {
binaryExpression[curDigitPos] = 0;
}
break;
}
if (curLeftVal & 1) {
curLeftVal -= NP[curDigitPos];
binaryExpression[curDigitPos] = 1;
} else {
binaryExpression[curDigitPos] = 0;
}
curLeftVal >>= 1;
curDigitPos++;
}
for (int i = length; i >= 1; i--) {
printf("%d", binaryExpression[i]);
}
printf("\n");
}
int main() {
scanf("%d", &caseNum);
for (int i = 0; i < caseNum; i++) {
memset(NP, 0xff, sizeof(NP));
memset(digitUsed, 0, sizeof(digitUsed));
memset(binaryExpression, 0, sizeof(binaryExpression));
scanf("%d", &length);
scanf("%s", str);
for (int i = 0; i < length; i++) {
if (str[i] == 'p') {
NP[length - i] = 1;
}
}
scanf("%lld", &val);
solve(val);
}
}
一道比较trick的题,不看答案,我估计只会暴搜.
具体是这么操作的:
对于某个数N,现在有K位可以用来表示,每一位可能是n或p,称这个数组为NP,
那么先从最后一位L(权值最小)开始,如果N是奇数的话,那么L这一位不管是p还是n,都必须是1,否则就不可能满足N是奇数的条件,
取了1之后,N根据p或n, -/+1,
如果N是偶数的话,L这一位就只能取0,否则不可能满足N是偶数的条件,这种情况下,N不变,
那么对于前K-1位,则必须能够表示 N/2(因为前一位被处理以后,剩下没有被表示的数是N, 将最后一位去掉以后,整个数组右移一位,这时候就是一个K-1位的数了,表示的值也要除以2,因此是K-1位表示N/2)这个数,否则就不能满足K位表示N这个数的条件,这样,就将问题的规模从(K位,N) 缩小为 (K-1位, N(偶数)N+/-1(N是奇数)/2)。
就这样处理,直到到了最高一位, 不可能再向高位扩展,这时候,这一位必须能够表示当前的N, 否则就impossible,
能表示的前提下,N只能是0, 1(最高一位是p) 或 -1(最高一位是n)。
这种办法只能强记了,我绝对想不出来的.
标签:1023,int,curDigitPos,NP,poj,long,curLeftVal,binaryExpression From: https://blog.51cto.com/u_9420214/6332970