首页 > 代码库 > Math1023
Math1023
题意解释：
题目意思是有一个k位的2进制的数，把他转化成10进制，如果可以转换得到题目要求的数，则输出那个2进制数。但是转换成10进制数固定的加，它还可以减。题目会给出哪一位是+，哪一位是-，分别由p和n代表。比如：
4
ppnn
10
意思是有一个4位的2进制数ppnn代表++--。这里可以这样组合：1110.因为2^3+2^2-2^1-0=10.所以输出1110.
选题原因：
这道题是十进制转换成二进制的数学问题的变形，有规律可循，仔细研究会发现其中的递推关系。
思路：
这道题的思路是从最后一位开始判断，如果N是奇数，那么说明最后一位肯定是1。因为只有最后一位才是0次方，才有可能得到唯一的奇数1。这时如果最后那位是+时，就把N-1再除以2，得到前面的k-1位数；如果最后那位是-时，就把N+1再除以2，得到前面的k-1位数。如果N是偶数，可以断定最后一位是0，那么直接除以2得到前面k-1位得到的数。依次循环至剩下0位即可。如果循环完毕N没有等于0，可以判断为impossible。
注意：因为可以存在负数，上述考虑都是排除负数的情况，有负数也没关系，判断N%2==-1就行了。
4
ppnn
10
对应：
1110
8 + 4 -2 + 0=10
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int main()
{
char str[70];
int res[70];
int T;
int k;
long long N;
cin >> T;
while(T--)
{
cin >> k;
cin >> str;
cin >> N;
for(int i = k - 1; i >= 0; i--)
{
//cout << "str " << i << " = " << str[i] << " N = " << N << endl;
if(str[i]==‘p‘)
{
if(N%2)
{
res[i] = 1;
N = (N-1)/2;
}
else
{
res[i] = 0;
N/=2;
}
}
else
{
if(N%2)
{
res[i] = 1;
N = (N+1)/2;
}
else
{
res[i] = 0;
N/=2;
}
}
}
if(N==0)
{
for(int i = 0; i < k; i++)
cout << res[i];
cout << endl;
}
else
cout << "Impossible" << endl;
}
return 0;
}
Math1023