【Codeforces Round #517 B. Curiosity Has No Li】DP+记录路径

B. Curiosity Has No Limits

题意

题意就是给你一个A序列和一个B序列
让你构造一个t序列，t序列满足
$a_i=t_i|t_{i+1}$
$b_i=t_i$&$t_{i+1}$

做法

赛中自己没什么想法，于是就写了个dp
dp[i][j]表示第i个位置放j是否合法，
每次更新之后记录路径，
之后dp到n逆向暴力跑就可以了

代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
int dp[maxn][4];
int pre[maxn][4];
int t[maxn];
int a[maxn],b[maxn];
int main()
{
    int n;scanf("%d",&n);for(int i=1;i<=n-1;i++) scanf("%d",&a[i]);for(int i=1;i<=n-1;i++) scanf("%d",&b[i]);for(int i=0;i<=3;i++) dp[1][i]=1;int flag=0;for(int i=2;i<=n;i++){
    if(a[i-1]==0){
    if(b[i-1]==0){
    if(dp[i-1][0]){
    pre[i][0]=0;dp[i][0]=1;}}else{
    flag=1;break;}}else if(a[i-1]==1){
    if(b[i-1]==2||b[i-1]==3){
    flag=1;break;}else if(b[i-1]==0){
    if(dp[i-1][0]){
    pre[i][1]=0;dp[i][1]=1;}if(dp[i-1][1]){
    pre[i][0]=1;dp[i][0]=1;}}else{
    if(dp[i-1][1]){
    pre[i][1]=1;dp[i][1]=1;}}}else if(a[i-1]==2){
    if(b[i-1]==1||b[i-1]==3){
    flag=1;break;}else if(b[i-1]==0){
    if(dp[i-1][0]){
    pre[i][2]=0;dp[i][2]=1;}if(dp[i-1][2]){
    pre[i][0]=2;dp[i][0]=1;}}else{
    if(dp[i-1][2]){
    pre[i][2]=2;dp[i][2]=1;}}}else{
    if(b[i-1]==0){
    if(dp[i-1][0]){
    pre[i][3]=0;dp[i][3]=1;}if(dp[i-1][1]){
    pre[i][2]=1;dp[i][2]=1;}if(dp[i-1][2]){
    pre[i][1]=2;dp[i][1]=1;}if(dp[i-1][3]){
    pre[i][0]=3;dp[i][0]=1;}}else if(b[i-1]==1){
    if(dp[i-1][1]){
    pre[i][3]=1;dp[i][3]=1;}if(dp[i-1][3]){
    pre[i][1]=3;dp[i][1]=1;}}else if(b[i-1]==2){
    if(dp[i-1][2]){
    pre[i][3]=2;dp[i][3]=1;}if(dp[i-1][3]){
    pre[i][2]=3;dp[i][2]=1;}}else{
    if(dp[i-1][3]){
    pre[i][3]=3;dp[i][3]=1;}}}}int tt=0;for(int i=0;i<=3;i++){
    if(dp[n][i]) tt=1;}if(flag==1||tt==0){
    printf("NO\n");return 0;}else{
    for(int i=0;i<=3;i++){
    if(dp[n][i]) t[n]=i;}for(int i=n-1;i>=1;i--){
    t[i]=pre[i+1][t[i+1]];}printf("YES\n");for(int i=1;i<=n;i++) printf("%d ",t[i]);}return 0;
}