当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6436:Problem K. Pow2

题目描述
SillyDarkGK has two type of numbers:
type1. 2^x. (2, 4, 8, 16, …)
type2. -(2^x). (-2, -4, -8, -16, …)
He wants a new number S, for getting S, he should choose some numbers that the sum of them is S.
For example, if SillyDarkGK wants 5, he can use 2, 2, -1, -1, -1, 8 and -4 to get it. (He can use number arbitrary times.)
(S is very big, so we will give you a 01-string to describe it.)
Choosing is boring, so SillyDarkGK wants to choose numbers as fewer as possible. To increase the difficulty, SillyDarkGK can’t use some special numbers.
(We will also give you two 01-string to describe what you can’t use.)
it’s guaranted that there is at least one way to solve it and answer won’t exceed
1e9.
输入解释
Multiple query.
On the first line, there is a positive integer T, which describe the number of data. Next there are T groups of data.
for each group, the first line have a positive integer n which describe the number of bits of S.
and on the second line there is an n-length-01-string to describe S, from low to high. On the third line there is an n-length-01-string which describe the type1 number that you can’t use, from low to high, if there is a ’1’ on the x-th digit, you can’t use two
to the power of x.
On the last line there is an n-length-01-string which describe the type2 number that you can’t use, from low to high, if there is a ’1’ on the x-th digit, you can’t use minus two to the power of x.
There is a blank line before each groups of data.
T<=1000, n<=100000, sum of n<=1000000, answer won’t exceed 1e9
输出解释
Your output should include T lines, for each line, output the answer for the corre- sponding datum.
输入样例
3
6
110010
110101
011111
9
100101110
011111111
111111111
5
11111
00000
00000
输出样例
3
233
2

提示
for the first datum, SillyDarkGK will use 4, 16 and -1;
for the second datum, SillyDarkGK will use 1 for 233 times; for the third datum, SillyDarkGK will use 32 and -1.
来自杭电HDUOJ的附加信息
Recommend chendu

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6436

最后修改于 2020-10-25T23:31:19+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
4000/2000MS(Java/Others) 524288/524288K(Java/Others)