企业官网建设流程全解析

当今做哪个网站致富,龙岗-网站建设深圳信科,手机建设网站的目的,建设银行网站打印账单这是我 OI 生涯里见过的最难的黄题。# 问题描述给定一棵有根二叉树#xff0c;包含 $2n-1$ 个节点#xff0c;其中 $n$ 个叶子#xff0c;每个叶子有一个真假值#xff08;True/False#xff09;#xff0c;每个非叶子点有一个运算符#xff08;AND 或 OR#xff09;。…这是我 OI 生涯里见过的最难的黄题。# 问题描述给定一棵有根二叉树包含 $2n-1$ 个节点其中 $n$ 个叶子每个叶子有一个真假值True/False每个非叶子点有一个运算符AND 或 OR。黑恶势力以下简称黑按照一个固定顺序 $p_i$ 询问叶子的值但这个~~人工智能~~人会跳过不必要的询问即当结果已确定时。你需要1. 为每个叶子分配真假值使得黑的询问次数尽到达最大值。2. 在询问次数最多的前提下使根节点的值为 True。# 问题分析1. 懒一点1. AND 节点当左子树为 False 时不需要询问右子树。2. OR 节点当左子树为 True 时不需要询问右子树。2. 定义询问的次数1. 对于叶子询问次数就是它在序列中的索引。2. 对于非叶子点询问次数取决于它子树的求值顺序和短路规则。3. 防止 TLE1. 最大化整棵树的最终确定时间。2. 在多个方案都能达到最大确定时间时选择根为 True 的结果。# 算法思路对于每个节点 $u$我们需要维护两个值## DP 法则1. $f_u(0)$以 $u$ 为根的子树当 $u$ 的值为 False 时的最大确定时间。2. $f_u(1)$以 $u$ 为根的子树当 $u$ 的值为 True 时的最大确定时间。## 状态转移方程设 $u$ 的两个子节点为 $a$ 和 $b$### 情况 1$u$ 是 AND 节点1. 当 $u \text{False}$ 时- 情况 A$a \text{False}$$b$ 任意。- 确定时间 $\min(f_a(0), \text{位置}(b))$取较早判刑的一个。- 情况 B$a \text{True}$$b \text{False}$。- 确定时间 $f_b(0)$。2. 当 $u \text{True}$ 时- 必须 $a \text{True}$ 且 $b \text{True}$。- 确定时间 $\max(f_a(1), f_b(1))$需要两个都为真才能确定。### 情况 2$u$ 是 OR 节点1. 当 $u \text{False}$ 时- 必须 $a \text{False}$ 且 $b \text{False}$。- 确定时间 $\max(f_a(0), f_b(0))$。2. 当 $u \text{True}$ 时- 情况 A$a \text{True}$$b$ 任意。- 确定时间 $\min(f_a(1), \text{位置}(b))$。- 情况 B$a \text{False}$$b \text{True}$。- 确定时间 $f_b(1)$。## 算法步骤1. 初始化- 对于叶子节点 $i$$f_i(0) f_i(1) pos[i]$在询问序列中的位置。2. 后序遍历- 从叶子向上计算每个节点的 $f_u(0)$ 和 $f_u(1)$。- 记录达到最大确定时间时子节点的值选择。3. 选择最优方案- 比较根节点的 $f_{root}(0)$ 和 $f_{root}(1)$。- 优先判刑 $f_{root}(1)$如果相等或更大。4. 回溯构造解- 从根节点开始根据记录的选择向下分配叶子的值。AC code#include bits/stdc.h using namespace std; const int maxnn 1000005; int n, root; int op[maxnn]; int lc[maxnn], rc[maxnn]; int pos[maxnn]; int mt[maxnn][2]; int cl[maxnn][2], cr[maxnn][2]; vectorint adj[maxnn]; void bt() {//这个题太BT了pwp root n 1; vectorint parent(2*n, 0); stackint st; parent[root] -1; st.push(root); while (!st.empty()) { int u st.top(); st.pop(); int cnt 0; for (int v : adj[u]) { if (v parent[u]) continue; parent[v] u; if (cnt 0) lc[u] v; else if (cnt 1) rc[u] v; cnt; st.push(v); } } } int main() { scanf(%d, n); for (int i 1; i n-1; i) { int v n i; scanf(%d, op[v]); } for (int i 0; i 2*n-2; i) { int u, v; scanf(%d%d, u, v); adj[u].push_back(v); adj[v].push_back(u); } bt(); for (int i 1; i n; i) { int leaf; scanf(%d, leaf); pos[leaf] i; } for (int i 1; i n; i) { mt[i][0] mt[i][1] pos[i]; } stackpairint,int st; st.push({root, 0}); while (!st.empty()) { int u st.top().first; int state st.top().second; st.pop(); if (u n) continue; if (state 0) { st.push({u, 1}); if (rc[u]) st.push({rc[u], 0}); if (lc[u]) st.push({lc[u], 0}); } else { int a lc[u], b rc[u]; mt[u][0] mt[u][1] -1; for (int va 0; va 1; va) { for (int vb 0; vb 1; vb) { if (mt[a][va] -1 || mt[b][vb] -1) continue; int vu, tu; if (op[u] 0) { vu va vb; if (va 0 vb 0) tu min(mt[a][va], mt[b][vb]); else if (va 0 vb 1) tu mt[a][va]; else if (va 1 vb 0) tu mt[b][vb]; else tu max(mt[a][va], mt[b][vb]); } else { vu va | vb; if (va 1 vb 1) tu min(mt[a][va], mt[b][vb]); else if (va 1 vb 0) tu mt[a][va]; else if (va 0 vb 1) tu mt[b][vb]; else tu max(mt[a][va], mt[b][vb]); } if (tu mt[u][vu]) { mt[u][vu] tu; cl[u][vu] va; cr[u][vu] vb; } } } } } int rv; if (mt[root][1] mt[root][0]) rv 1; else rv 0; vectorint ans(n1, 0); stackpairint,int sa; sa.push({root, rv}); while (!sa.empty()) { int u sa.top().first; int vu sa.top().second; sa.pop(); if (u n) { ans[u] vu; } else { int va cl[u][vu]; int vb cr[u][vu]; sa.push({rc[u], vb}); sa.push({lc[u], va}); } } for (int i 1; i n; i) { printf(%d, ans[i]); } printf(\n); return 0; }