hdu5375 Gray code

The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only onebit (binary digit). The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.



Now , you are given a binary number of length n including ‘0’ , ’1’ and ‘?’(? means that you can use either 0 or 1 to fill this position) and n integers(a1,a2,….,an) . A certain binary number corresponds to a gray code only. If the ith bit of this gray code is 1,you can get the point ai.
Can you tell me how many points you can get at most?

For instance, the binary number “00?0” may be “0000” or “0010”,and the corresponding gray code are “0000” or “0011”.You can choose “0000” getting nothing or “0011” getting the point a3 and a4.

 

输入

The first line of the input contains the number of test cases T.

Each test case begins with string with ‘0’,’1’ and ‘?’.

The next line contains n (1<=n<=200000) integers (n is the length of the string).

a1 a2 a3 … an (1<=ai<=1000)

 

输出

For each test case, output “Case #x: ans”, in which x is the case number counted from one,’ans’ is the points you can get at most

 

样例输入

2

00?0

1 2 4 8

????

1 2 4 8

样例输出

Case #1: 12

Case #2: 15

题意：给出一个2进制（含有‘？’的可以填‘0’ 或 ‘1’） 每一位都对应着一个值 问怎样填这些值能使得到的值最大？ 。。。 （做比赛的时候给整懵了 没写出来、、  然后理了下思路发现有的地方想多了 有的地方没想到。。。 关键是当第一位二进制数是‘1’ 要加上的、、、因为这个位数不够直接补‘0’ 的、 模拟一下就。）

 自然二进制码转换成二进制格雷码, 方法是保留二进制码的最高位作为格雷码的最高位而次高位格雷码为二进制码的高位与次高位异或。。

#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
typedef double de;
const LL oo = 0x3f3f3f3f;
const LL maxn = 1e6+7;
const LL mod = 1e9+7;
char str[maxn];
LL as[maxn];
int main()
{
    LL i, cas=1, T, ans, len, mark, s1, s2;
    char start, en;
    scanf("%lld", &T);
    while(T--)
    {
        scanf("%s", str+1);
        len = strlen(str+1);

        for(i = 1; i <= len; i++)
            scanf("%lld", &as[i]);
        ans = mark = 0; start = '0';
        ///start ‘？’的 起始位置 en ‘？’终止为止 mark ‘？’的个数
        for(i = 1; i <= len; i++)
        {
            if(str[i] == '?')
            {
                mark ++;
                ans += as[i];
                if(mark == 1) s1 = as[i];///s1区间最小值
                else s1 = min(s1, as[i]);
            }
            else
            {
                s2 = as[i];///当前位置对应值
                en = str[i];///记录字符类型
                if(mark > 0)
                {
                    ans += s2; ///如果有‘？’ 需要将‘？’右面第一位的值加上
                    if(mark%2 == 1 && start != en)///‘？’有奇数个并且两端的字符类型不同需要减去那个最小的
                        ans -= min(s1, s2);
                    if(mark%2==0 && start == en)///‘？’有偶数个并且两端的字符类型相同需要减去那个最小的
                        ans -= min(s1, s2);
                }

                mark = 0;
                start = str[i];///更新初始位置
                if(i == 1 && str[i] == '1') ans += as[i];///第一位是‘1’要直接加上
                if( i > 1 && str[i-1] != '?' && str[i] != str[i-1])///可以转换为格雷码对应的‘1’ 加上这个值
                    ans += as[i];
            }
        }
        printf("Case #%lld: %lld
", cas++, ans);
    }
    return 0;
}