cf1010 D. Mars rover(树)
2022/1/3 6:08:45
本文主要是介绍cf1010 D. Mars rover(树),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
有一棵逻辑运算树,叶子节点为输入节点(IN),取值0/1;其他节点有AND/OR/XOR/NOT四种类型,并根据儿子节点取不同的值。输出为根节点的值。
初始每个输入节点的值给定(因此所有节点的值确定)。问单独改变每个输入节点的值而保持其他输入节点不变,输出是多少
思路:
二叉树,每个节点存储节点类型(IN/ANS/OR/XOR/NOT)、节点值、左儿子、右儿子。
dfs1从下往上算出初始所有节点的值。dfs2从上往下,看某个节点的值是否会被儿子影响,若会被某个儿子影响就搜索这个儿子,否则不往下传导。最终得到每个叶子节点能否影响根节点。
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; struct node { int lson, rson; char ty; int val; } tr[N]; int dfs1(int u) { if(!u) return 0; int lv = dfs1(tr[u].lson), rv = dfs1(tr[u].rson); if(tr[u].ty == 'I') return tr[u].val; if(tr[u].ty == 'N') return tr[u].val = !lv; if(tr[u].ty == 'A') return tr[u].val = lv & rv; if(tr[u].ty == 'O') return tr[u].val = lv | rv; if(tr[u].ty == 'X') return tr[u].val = lv ^ rv; } int change[N]; //只记录叶子节点的change值 void dfs2(int u) { if(tr[u].ty == 'I') change[u] = 1; else if(tr[u].ty == 'N') dfs2(tr[u].lson); else if(tr[u].ty == 'A') { if(tr[tr[u].lson].val && !tr[tr[u].rson].val) dfs2(tr[u].rson); else if(!tr[tr[u].lson].val && tr[tr[u].rson].val) dfs2(tr[u].lson); else if(tr[tr[u].lson].val && tr[tr[u].rson].val) dfs2(tr[u].lson), dfs2(tr[u].rson); } else if(tr[u].ty == 'O') { if(tr[tr[u].lson].val && !tr[tr[u].rson].val) dfs2(tr[u].lson); else if(!tr[tr[u].lson].val && tr[tr[u].rson].val) dfs2(tr[u].rson); else if(!tr[tr[u].lson].val && !tr[tr[u].rson].val) dfs2(tr[u].lson), dfs2(tr[u].rson); } else if(tr[u].ty == 'X') dfs2(tr[u].lson), dfs2(tr[u].rson); } signed main() { int n; scanf("%d", &n); char op[6]; for(int i = 1; i <= n; i++) { scanf("%s", op); tr[i].ty = op[0]; if(op[0] == 'I') scanf("%d", &tr[i].val); else if(op[0] == 'N') scanf("%d", &tr[i].lson); else scanf("%d%d", &tr[i].lson, &tr[i].rson); } dfs1(1), dfs2(1); int t = tr[1].val; for(int i = 1; i <= n; i++) if(!tr[i].lson) { printf("%d", change[i] ^ t); } return 0; }
这篇关于cf1010 D. Mars rover(树)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享