ZOJ3803
简单DP，写个DP能写成这样，我是多么的弱！！！！
Function
Time Limit: 2 Seconds Memory Limit: 65536 KB
Let x is a binary number with n digits (AnAn-1An-2…A2A1). And we can encode it as G(x) = x ⊕ ⌊x / 2⌋ or as C(x) = (2n - x) mod 2n, where “⊕” is bitwise XOR operation and “⌊x⌋” indicates the largest integer which is not greater than x.
For some reasons, Alice encodes her password P into G(P), and additionally, she encodes P into C(P). And she writes G(P) and C(P) in a paper. However, something terrible happened. A bug ate some parts of the paper, so some digits are unreadable now. Alice is so worried that she want you to determine the values of these digits using the readable digits.
Input
There are multiple test cases. For every test case, it has 2 lines of same number of digits describe G(P) and C(P). In every line, it only contains ‘1’, ‘0’ and ‘?’. Unreadable digits are denoted with symbol ‘?’. The length of every line in the input is up to 105.
Output
If it is impossible to restore G(P) and C(P), you should output “IMPOSSIBLE” (without quotes).
If G(P) is unique, you should output “UNIQUE” (without quotes) in the first line. Then output restored G(P) and C(P) in the same format.
If there are two or more possible G(P) that can be restored using the readable digits. You should output “AMBIGUOUS” (without quotes) and the number of possible G(P). The number may be very large, so the answer should modulo 109 + 7.
Sample Input
1110
0101
11??
01??
111?
100?
Sample Output
UNIQUE
1110
0101
AMBIGUOUS 3
IMPOSSIBLE
Hint
In the second sample case, the three possible situations are:
1.G(1001) = 1101, C(1001) = 0111
2.G(1010) = 1111, C(1010) = 0110
3.G(1011) = 1110, C(1011) = 0101 很明显的一个DP。 因为只需要知道当前位是什么，以及前面是不是全0 就可以转移了。 因为G(x)就是相邻两位取异或，C(x) 就是最后一个1位是不变的，后面的都是取反。 比赛做的时候各种if else 乱搞，把转移的所有情况手动列出，太挫了，然后记录路径的时候输出又写错了，调试半天。这个状态简单太差，以现在的状态去比赛，简直就是受虐，sad。 以后把代码实现都想得很明白了再写代码了！！！！！ 代码：
#include <stdio.h>
#include
#include
#include
#include
#include <string.h>
#include
#include
#include
#include <math.h>
using namespace std;
const int MAXN = 100010;
const int MOD = 1e9+7;
int dp1[MAXN][2][2];//dp1[i][j][k]: 前i位，j为0表示前面全0，j为1表示不全为0，k是当前位状态
int pre1[MAXN][2][2];//记录路径
int pre2[MAXN][2][2];
void Add1(int &a,int b){//0是无解，1是唯一解，2是多解
if(a == 0)a = b;
else if(a == 1){
if(b == 1)a = 2;
else if(b == 2)a = 2;
}
}
char str1[MAXN],str2[MAXN];
void Add2(int &a,int b){//取模加法
a += b;
if(a >= MOD)a -= MOD;
}
int a[MAXN];
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
while(scanf(“%s%s”,str1,str2) == 2){
int n = strlen(str1);
reverse(str1,str1+n);//反转
reverse(str2,str2+n);
memset(dp1,0,sizeof(dp1));
if(str2[0] == ‘0’)dp1[0][0][0] = 1;//最低位
else if(str2[0] == ‘1’)dp1[0][1][1] = 1;
else {
dp1[0][0][0] = 1;
dp1[0][1][1] = 1;
}
for(int i = 0;i < n-1;i++)
for(int j = 0;j < 2;j++)//前面是否全0
for(int k = 0;k < 2;k++){//当前位
if(dp1[i][j][k] == 0)continue;
for(int nk = 0;nk < 2;nk++){//下一位
if(str1[i] == ‘0’ && nk != k)continue;//k和nk异或为0
if(str1[i] == ‘1’ && nk == k)continue;//k和nk异或为1
if(str2[i+1] != ‘?’){
if(j == 0 && nk != str2[i+1]-‘0’)continue;//要相同
if(j == 1 && nk == str2[i+1]-‘0’)continue;//要相反
}
int nj = j|k|nk;
Add1(dp1[i+1][nj][nk],dp1[i][j][k]);
pre1[i+1][nj][nk] = j;
pre2[i+1][nj][nk] = k;
}
}
int ans1 = 0;
int tj = -1;
int tk = -1;
for(int j = 0;j < 2;j++)
for(int k = 0;k < 2;k++){
if(str1[n-1] == ‘0’ && k == 1)continue;
if(str1[n-1] == ‘1’ && k == 0)continue;
if(dp1[n-1][j][k] == 0)continue;
Add1(ans1,dp1[n-1][j][k]);
if(dp1[n-1][j][k]){
tj = j;
tk = k;
}
}
if(ans1 == 0){
printf(“IMPOSSIBLE\n”);
continue;
}
if(ans1 == 1){
printf(“UNIQUE\n”);
for(int i = n-1;i >= 0;i–){
a[i] = tk;
int nj = pre1[i][tj][tk];
int nk = pre2[i][tj][tk];
tj = nj;
tk = nk;
}
for(int i = n-1;i >= 0;i–){
if(i == n-1)printf(“%d”,a[i]);
else printf(“%d”,a[i]^a[i+1]);
}
printf(“\n”);
int tmp1 = 0;
while(tmp1 < n && a[tmp1] == 0 )tmp1++;
for(int i = n-1;i >= 0;i–){
if(i > tmp1)printf(“%d”,!a[i]);
else printf(“%d”,a[i]);
}
printf(“\n”);
continue;
}
memset(dp1,0,sizeof(dp1));
if(str2\[0\] == '0')dp1\[0\]\[0\]\[0\] = 1;
else if(str2\[0\] == '1')dp1\[0\]\[1\]\[1\] = 1;
else {
dp1\[0\]\[0\]\[0\] = 1;
dp1\[0\]\[1\]\[1\] = 1;
}
for(int i = 0;i < n-1;i++)
for(int j = 0;j < 2;j++)
for(int k = 0;k < 2;k++){
if(dp1\[i\]\[j\]\[k\] == 0)continue;
for(int nk = 0;nk < 2;nk++){
if(str1\[i\] == '0' && nk != k)continue;
if(str1\[i\] == '1' && nk == k)continue;
if(str2\[i+1\] != '?'){
if(j == 0 && nk != str2\[i+1\]-'0')continue;
if(j == 1 && nk == str2\[i+1\]-'0')continue;
}
int nj = j|k|nk;
Add2(dp1\[i+1\]\[nj\]\[nk\],dp1\[i\]\[j\]\[k\]);
}
}
ans1 = 0;
for(int j = 0;j < 2;j++)
for(int k = 0;k < 2;k++){
if(str1\[n-1\] == '0' && k == 1)continue;
if(str1\[n-1\] == '1' && k == 0)continue;
if(dp1\[n-1\]\[j\]\[k\] == 0)continue;
Add2(ans1,dp1\[n-1\]\[j\]\[k\]);
}
printf("AMBIGUOUS %d\\n",ans1);
}
return 0;
}
写的if else 乱搞的挫代码。。。。 贴出来纪念我逗比的人生吧！
#include <stdio.h>
#include
#include
#include
#include
#include <string.h>
#include
#include
#include
#include <math.h>
using namespace std;
const int MAXN = 100010;
const int MOD = 1e9+7;
int dp1[MAXN][2][2];
int pre1[MAXN][2][2];
int pre2[MAXN][2][2];
void Add1(int &a,int b){
if(a == 0)a = b;
else if(a == 1){
if(b == 1)a = 2;
else if(b == 2)a = 2;
}
}
char str1[MAXN],str2[MAXN];
char str[MAXN];
void Add2(int &a,int b){
a += b;
if(a >= MOD)a -= MOD;
}
int a[MAXN];
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
while(scanf(“%s%s”,str1,str2) == 2){
int n = strlen(str1);
reverse(str1,str1+n);
reverse(str2,str2+n);
memset(dp1,0,sizeof(dp1));
if(str2[0] == ‘0’)dp1[0][0][0] = 1;
else if(str2[0] == ‘1’)dp1[0][1][1] = 1;
else {
dp1[0][0][0] = 1;
dp1[0][1][1] = 1;
}
for(int i = 0;i < n-1;i++)
for(int j = 0;j < 2;j++)
for(int k = 0;k < 2;k++){
if(dp1[i][j][k] == 0)continue;
if(str1[i] == ‘0’){
if(str2[i+1] == ‘0’){
if(j == 0){
if(k == 0){
Add1(dp1[i+1][j][k],dp1[i][j][k]);//0->0
if(dp1[i][j][k]){
pre1[i+1][j][k] = j;
pre2[i+1][j][k] = k;
}
}
}
else {
if(k == 1){
Add1(dp1[i+1][1][k],dp1[i][j][k]);//1->1
if(dp1[i][j][k]){
pre1[i+1][1][k] = j;
pre2[i+1][1][k] = k;
}
}
}
}
else if(str2[i+1] == ‘1’){
if(j == 0){
if(k == 1){
Add1(dp1[i+1][1][k],dp1[i][j][k]);//1->1
if(dp1[i][j][k]){
pre1[i+1][1][k] = j;
pre2[i+1][1][k] = k;
}
}
}
else {
if(k == 0){
Add1(dp1[i+1][j][k],dp1[i][j][k]);//0->0
if(dp1[i][j][k]){
pre1[i+1][j][k] = j;
pre2[i+1][j][k] = k;
}
}
}
}
else {
if(k == 0){
Add1(dp1[i+1][j][k],dp1[i][j][k]);//0->0
if(dp1[i][j][k]){
pre1[i+1][j][k] = j;
pre2[i+1][j][k] = k;
}
}
else{
Add1(dp1[i+1][1][k],dp1[i][j][k]);//1->1
if(dp1[i][j][k]){
pre1[i+1][1][k] = j;
pre2[i+1][1][k] = k;
}
}
}
}
else if(str1[i] == ‘1’){
if(str2[i+1] == ‘0’){
if(j == 0){
if(k == 1){
Add1(dp1[i+1][1][0],dp1[i][j][k]);//1->0
if(dp1[i][j][k]){
pre1[i+1][1][0] = j;
pre2[i+1][1][0] = k;
}
}
}
else{
if(k == 0){
Add1(dp1[i+1][1][1],dp1[i][j][k]);//0->1
if(dp1[i][j][k]){
pre1[i+1][1][1] = j;
pre2[i+1][1][1] = k;
}
}
}
}
else if(str2[i+1] == ‘1’){
if(j == 0){
if(k == 0){
Add1(dp1[i+1][1][1],dp1[i][j][k]);//0->1
if(dp1[i][j][k]){
pre1[i+1][1][1] = j;
pre2[i+1][1][1] = k;
}
}
}
else{
if(k == 1){
Add1(dp1[i+1][1][0],dp1[i][j][k]);//1->0
if(dp1[i][j][k]){
pre1[i+1][1][0] = j;
pre2[i+1][1][0] = k;
}
}
}
}
else {
if(k == 1){
Add1(dp1[i+1][1][0],dp1[i][j][k]);//1->0
if(dp1[i][j][k]){
pre1[i+1][1][0] = j;
pre2[i+1][1][0] = k;
}
}
else{
Add1(dp1[i+1][1][1],dp1[i][j][k]);//0->1
if(dp1[i][j][k]){
pre1[i+1][1][1] = j;
pre2[i+1][1][1] = k;
}
}
}
}
else {
if(str2[i+1] == ‘0’){
if(j == 0){
if(k == 0){
Add1(dp1[i+1][j][k],dp1[i][j][k]);//0->0
if(dp1[i][j][k]){
pre1[i+1][j][k] = j;
pre2[i+1][j][k] = k;
}
}
if(k == 1){
Add1(dp1[i+1][1][0],dp1[i][j][k]);//1->0
if(dp1[i][j][k]){
pre1[i+1][1][0] = j;
pre2[i+1][1][0] = k;
}
}
}
else {
if(k == 0){
Add1(dp1[i+1][1][1],dp1[i][j][k]);//0->1
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[1\]\[1\] = j;
pre2\[i+1\]\[1\]\[1\] = k;
}
}
if(k == 1){
Add1(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);//1->1
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[1\]\[1\] = j;
pre2\[i+1\]\[1\]\[1\] = k;
}
}
}
}
else if(str2\[i+1\] == '1'){
if(j == 0){
if(k == 0){
Add1(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[1\]\[1\] = j;
pre2\[i+1\]\[1\]\[1\] = k;
}
}
if(k == 1){
Add1(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[1\]\[1\] = j;
pre2\[i+1\]\[1\]\[1\] = k;
}
}
}
else {
if(k == 0){
Add1(dp1\[i+1\]\[j\]\[k\],dp1\[i\]\[j\]\[k\]);
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[j\]\[k\] = j;
pre2\[i+1\]\[j\]\[k\] = k;
}
}
if(k == 1){
Add1(dp1\[i+1\]\[1\]\[0\],dp1\[i\]\[j\]\[k\]);
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[1\]\[0\] = j;
pre2\[i+1\]\[1\]\[0\] = k;
}
}
}
}
else {
if(k == 0){
Add1(dp1\[i+1\]\[j\]\[0\],dp1\[i\]\[j\]\[k\]);
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[j\]\[0\] = j;
pre2\[i+1\]\[j\]\[0\] = k;
}
Add1(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[1\]\[1\] = j;
pre2\[i+1\]\[1\]\[1\] = k;
}
}
else {
Add1(dp1\[i+1\]\[1\]\[0\],dp1\[i\]\[j\]\[k\]);
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[1\]\[0\] = j;
pre2\[i+1\]\[1\]\[0\] = k;
}
Add1(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
if(dp1\[i\]\[j\]\[k\]){
pre1\[i+1\]\[1\]\[1\] = j;
pre2\[i+1\]\[1\]\[1\] = k;
}
}
}
}
}
int ans1 = 0;
int tj = -1;
int tk = -1;
for(int j = 0;j < 2;j++)
for(int k = 0;k < 2;k++){
if(str1\[n-1\] == '0' && k == 1)continue;
if(str1\[n-1\] == '1' && k == 0)continue;
Add1(ans1,dp1\[n-1\]\[j\]\[k\]);
if(dp1\[n-1\]\[j\]\[k\]){
tj = j;
tk = k;
}
}
if(ans1 == 0){
printf("IMPOSSIBLE\\n");
continue;
}
if(ans1 == 1){
printf("UNIQUE\\n");
for(int i = n-1;i >= 0;i--){
a\[i\] = tk;
int nj = pre1\[i\]\[tj\]\[tk\];
int nk = pre2\[i\]\[tj\]\[tk\];
tj = nj;
tk = nk;
}
for(int i = n-1;i >= 0;i--){
if(i == n-1)printf("%d",a\[i\]);
else printf("%d",a\[i\]^a\[i+1\]);
}
cout<<endl;
int tmp1 = 0;
while(tmp1 < n && a\[tmp1\] == 0 )tmp1++;
for(int i = n-1;i >= 0;i--){
if(i > tmp1)printf("%d",!a\[i\]);
else printf("%d",a\[i\]);
}
cout<<endl;
continue;
}
memset(dp1,0,sizeof(dp1));
if(str2\[0\] == '0')dp1\[0\]\[0\]\[0\] = 1;
else if(str2\[0\] == '1')dp1\[0\]\[1\]\[1\] = 1;
else {
dp1\[0\]\[0\]\[0\] = 1;
dp1\[0\]\[1\]\[1\] = 1;
}
for(int i = 0;i < n-1;i++)
for(int j = 0;j < 2;j++)
for(int k = 0;k < 2;k++){
if(dp1\[i\]\[j\]\[k\] == 0)continue;
if(str1\[i\] == '0'){
if(str2\[i+1\] == '0'){
if(j == 0){
if(k == 0)Add2(dp1\[i+1\]\[j\]\[k\],dp1\[i\]\[j\]\[k\]);//0->0
}
else {
if(k == 1)Add2(dp1\[i+1\]\[1\]\[k\],dp1\[i\]\[j\]\[k\]);//1->1
}
}
else if(str2\[i+1\] == '1'){
if(j == 0){
if(k == 1)Add2(dp1\[i+1\]\[1\]\[k\],dp1\[i\]\[j\]\[k\]);//1->1
}
else {
if(k == 0)Add2(dp1\[i+1\]\[j\]\[k\],dp1\[i\]\[j\]\[k\]);//0->0
}
}
else {
if(k == 0)Add2(dp1\[i+1\]\[j\]\[k\],dp1\[i\]\[j\]\[k\]);//0->0
else Add2(dp1\[i+1\]\[1\]\[k\],dp1\[i\]\[j\]\[k\]);//1->1
}
}
else if(str1\[i\] == '1'){
if(str2\[i+1\] == '0'){
if(j == 0){
if(k == 1)Add2(dp1\[i+1\]\[1\]\[0\],dp1\[i\]\[j\]\[k\]);//1->0
}
else{
if(k == 0)Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);//0->1
}
}
else if(str2\[i+1\] == '1'){
if(j == 0){
if(k == 0)Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);//0->1
}
else{
if(k == 1)Add2(dp1\[i+1\]\[1\]\[0\],dp1\[i\]\[j\]\[k\]);//1->0
}
}
else {
if(k == 1)Add2(dp1\[i+1\]\[1\]\[0\],dp1\[i\]\[j\]\[k\]);//1->0
else Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);//0->1
}
}
else {
if(str2\[i+1\] == '0'){
if(j == 0){
if(k == 0)Add2(dp1\[i+1\]\[j\]\[k\],dp1\[i\]\[j\]\[k\]);
if(k == 1)Add2(dp1\[i+1\]\[1\]\[0\],dp1\[i\]\[j\]\[k\]);
}
else {
if(k == 0)Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
if(k == 1)Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
}
}
else if(str2\[i+1\] == '1'){
if(j == 0){
if(k == 0)Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
if(k == 1)Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
}
else {
if(k == 0)Add2(dp1\[i+1\]\[j\]\[k\],dp1\[i\]\[j\]\[k\]);
if(k == 1)Add2(dp1\[i+1\]\[1\]\[0\],dp1\[i\]\[j\]\[k\]);
}
}
else {
if(k == 0){
Add2(dp1\[i+1\]\[j\]\[0\],dp1\[i\]\[j\]\[k\]);
Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
}
else {
Add2(dp1\[i+1\]\[1\]\[0\],dp1\[i\]\[j\]\[k\]);
Add2(dp1\[i+1\]\[1\]\[1\],dp1\[i\]\[j\]\[k\]);
}
}
}
}
ans1 = 0;
tj = -1;
tk = -1;
for(int j = 0;j < 2;j++)
for(int k = 0;k < 2;k++){
if(str1\[n-1\] == '0' && k == 1)continue;
if(str1\[n-1\] == '1' && k == 0)continue;
Add2(ans1,dp1\[n-1\]\[j\]\[k\]);
}
printf("AMBIGUOUS %d\\n",ans1);
}
return 0;
}
