HDOJ 5375 Gray code 【格雷码】
因为1010这样的二进制码可以换成1111的格雷码所以
遇到?的时候只要判断问号的个数和问号两边的数值即可判断结果
并且在可以变成一串1中只有一个0的情况时,只要选择这一块中a最小的那个数值不加就可以了
实现的话就是全部求和最后减去最小的值
具体见程序……
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define clr(c) memset(c, 0, sizeof(c));
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int MAXL = 200005;
char bin[MAXL];
int a[MAXL];
int T, n;
bool Xor(char a, char b){
int aa = a - '0';
int bb = b - '0';
return aa ^ bb;
}
void Resolve(){
int posL, posR;
char L, R;
int cnt = 0;
ll sum = 0;
posL = 0, posR = 0;
for(int i = 0; i < n; i++){
if(bin[i] == '?'){
cnt++;
posL = i-cnt;
posR = posL + cnt + 1;
}
else{
if(cnt){
if(posL == -1) L = '0';
L = bin[posL], R = bin[posR];
int Min = a[posL+1];
for(int i = posL+1; i <= posR; i++){
sum += a[i];
Min = Min < a[i] ? Min : a[i];
}
if((L == R && !(cnt&1)) || (L != R && (cnt&1))) {sum -= Min; //printf("sum %d
", sum);
}
cnt = 0;
}
//---
else{
if(i != 0) sum += Xor(bin[i-1], bin[i]) * a[i];
else sum += (bin[i]-'0') * a[i];
}
}
}
printf("%d", sum);
}
int main(){
scanf("%d", &T);
for(int Case = 1; Case <= T; Case++){
clr(bin);
clr(a);
scanf("%s", bin);
n = 0;
while(bin[n] != ' ') scanf("%d", &a[n++]);
bin[n] = '0', a[n] = 0;
n++;
printf("Case #%d: ", Case);
Resolve();
puts("");
}
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。