G - Gray Code
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87643#problem/G
Description
- Create a 2-bit list: {0, 1}.
- Reflect this list and concatenate it with the original list: {0, 1, 1, 0}.
- Prefix old entries with 0, and prefix new entries with 1: {00, 01, 11, 10}.
- Repeat steps 2 and 3 until the length of all elements is equal to n.
The number n is a length of a Gray code. For example, the code of length 3 is: {000, 001, 011, 010, 110, 111, 101, 100}.
Input
The first line contains a number k written in the binary system. Unreadable digits are denoted with symbol “?”. The second line contains a number x in the same format. The lengths of these numbers are equal and don't exceed 10 5. The numbers may contain leading zeroes.
Output
If there is a unique way to restore the numbers k and x, output them, replacing the symbols “?” with “0” or “1”. If there are multiple ways to restore them, output “Ambiguity”. If Denis or Vanya certainly made a mistake in these numbers, output “Impossible”.
Sample Input
0?1
0?0
Sample Output
011
010
HINT
题意
题目给了一种序列的构造方式
然后给你一个k，判断第k个数是不是说给的x
题解：
找规律题，注意翻转= =
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <string>
#include <ctime>
#include <list>
#include <bitset>
typedef unsigned char byte;
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.txt","r",stdin)
#define pi acos(-1) const char * fail = "Impossible";
const char * more = "Ambiguity";
using namespace std;
const int maxn = 1e5 + ;
int dp[maxn][];
char s1[maxn] , s2[maxn]; int main(int argc,char *argv[])
{
scanf("%s%s",s1+,s2+);
int Length = strlen(s1+);
s1[] = '';
for(int i = Length ; i > ; -- i)
{
if (s2[i] == '')
{
//同号
if (s1[i] == '' && s1[i-] == '') continue;
if (s1[i] == '' && s1[i-] == '')
{
printf("%s\n",fail);
return ;
}
if(s1[i] == '' && s1[i-] == '?')
{
s1[i-] = '';
continue;
}
if (s1[i] == '' && s1[i-] == '')
{
printf("%s\n",fail);
return ;
}
if (s1[i] == '' && s1[i-] == '') continue;
if (s1[i] == '' && s1[i-] == '?')
{
s1[i-] = '';
continue;
}
if (s1[i] == '?' && s1[i-] == '')
{
s1[i] = '';
continue;
}
if (s1[i] == '?' && s1[i-] == '')
{
s1[i] = '';
continue;
}
if (s1[i] == '?' && s1[i-] == '?') continue;
}
if (s2[i] == '')
{
//异号
if (s1[i] == '' && s1[i-] == '') continue;
if (s1[i] == '' && s1[i-] == '')
{
printf("%s\n",fail);
return ;
}
if(s1[i] == '' && s1[i-] == '?')
{
s1[i-] = '';
continue;
}
if (s1[i] == '' && s1[i-] == '') continue;
if (s1[i] == '' && s1[i-] == '')
{
printf("%s\n",fail);
return ;
}
if(s1[i] == '' && s1[i-] == '?')
{
s1[i-] = '';
continue;
}
if(s1[i] == '?' && s1[i-] == '')
{
s1[i] = '';
continue;
}
if(s1[i] == '?' && s1[i-] == '')
{
s1[i] = '';
continue;
}
if(s1[i] == '?' && s1[i-] == '?') continue;
}
}
for(int i=;i<=Length;i++)
if(s1[i]=='?')
{
if(s2[i]!='?')
{
if(s2[i]=='') s1[i]=s1[i-];else s1[i]=''+-(s1[i-]-'');
continue;
}
printf("%s\n",more);
return ;
}
for(int i=;i<Length;i++)
if(s1[i]!=s1[i+])
{
s2[i+]='';
}
else s2[i+]='';
printf("%s\n%s\n",s1+,s2+);
return ;
}