题解：P11091 [ROI 2021] 工作报告 (Day 1)
Cuber1024_zhb · · 题解
好题。
由于每一个非叶子节点，都要在每个儿子中选择一个备选序列以任意顺序拼接起来，使得整个序列有序，不难发现我们只需要关注序列的左右边界即可。
发现每个非叶子节点，其直接儿子只有最多
对于每一个节点，设
时间复杂度
这个状态似乎不是很好优化，转移好像也套不了数据结构，观察性质。
注意到对于两个区间
所以，我们每次跑完 dp 维护
进一步的一个小优化，就是当只有一个儿子的时候，可以直接继承。
这时，时间复杂度就是
如果根节点存在区间，即有解。有解情况下要输出方案，很简单，跟 dp 流程一样，再跑一遍 dfs 导路径即可。
要注意一些细节。有一些数组不开滚动或者开局部会爆炸，但是开了全局可能会导致遍历的时候共用相互影响。要注意这一点。别问我怎么知道的。
::::success[AC CODE]
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
const int N = 1e5+5, LOGN = 23, M = 270, INF = 0x3f3f3f3f;
vector<int> g[N];
pair<int,int> range[N * LOGN];
int cnt = 0;
int pl[N], pr[N];
int ans[N], dp[M];
vector<pair<int,int> > vec;
stack<int> stk;
void dfs(int id)
{
if(g[id].size() == 0)
return;
if(g[id].size() == 1) // 直接继承
{
dfs(g[id][0]);
pl[id] = pl[g[id][0]];
pr[id] = pr[g[id][0]];
return;
}
int i, j, k, s;
for(int to : g[id])
{
dfs(to);
for(i = pl[to]; i <= pr[to]; i++) // 初始化
ans[range[i].first] = INF;
}
int to, U = 1 << g[id].size(), temp;
for(i = 0; i < g[id].size(); i++)
{
to = g[id][i];
for(j = pl[to]; j <= pr[to]; j++)
{
memset(dp, 0x3f, sizeof(dp));
dp[1 << i] = range[j].second;
for(s = 1; s < U; s++) // 枚举左边界对应区间
{
if(s & (1 << i))
{
for(k = 0; k < g[id].size(); k++)
{
if(i != k && (s & (1 << k)))
{
temp = lower_bound(range+pl[g[id][k]], range+pr[g[id][k]]+1, make_pair(dp[s ^ (1 << k)], -1)) - range; // 二分找到最优区间，利用系统自带pair的比较
if(temp != pr[g[id][k]] + 1)
{
dp[s] = min(dp[s], range[temp].second);
}
}
}
}
}
ans[range[j].first] = min(ans[range[j].first], dp[U - 1]); // 得到每一个左边界对应的最小右边界
}
}
vec.clear();
for(int to : g[id])
{
for(i = pl[to]; i <= pr[to]; i++)
{
if(ans[range[i].first] != INF)
{
vec.push_back(make_pair(range[i].first, ans[range[i].first]));
ans[range[i].first] = INF; // 避免重复加入同一个区间
}
}
}
sort(vec.begin(), vec.end());
for(i = 0; i < vec.size(); i++) // 单调栈去除冗余的区间
{
while(!stk.empty() && vec[stk.top()].second >= vec[i].second)
stk.pop();
stk.push(i);
}
pl[id] = cnt+1;
while(!stk.empty())
{
range[++cnt] = vec[stk.top()];
stk.pop();
}
pr[id] = cnt;
reverse(range+pl[id], range+pr[id]+1); // 注意经过栈之后排序时从大到小，要手动翻转过来
}
vector<int> res[N];
int lst[M], use[M];
void solve(int id, int pos) // 导方案
{
if(g[id].size() == 0)
{
res[id].push_back(range[pos].first);
return;
}
if(g[id].size() == 1)
{
res[id].push_back(g[id][0]);
solve(g[id][0], pos);
return;
}
int i, j, k, s;
int to, U = 1 << g[id].size(), temp;
for(i = 0; i < g[id].size(); i++)
{
to = g[id][i];
for(j = pl[to]; j <= pr[to]; j++)
{
if(range[j].first != range[pos].first) // 找到答案对应的左边界
continue;
memset(dp, 0x3f, sizeof(dp));
dp[1 << i] = range[j].second;
lst[1 << i] = i;
use[1 << i] = j;
for(s = 1; s < U; s++)
{
if(s & (1 << i))
{
for(k = 0; k < g[id].size(); k++) // 与 dfs 逻辑一样
{
if(i != k && (s & (1 << k)))
{
temp = lower_bound(range+pl[g[id][k]], range+pr[g[id][k]]+1, make_pair(dp[s ^ (1 << k)], -1)) - range;
if(temp != pr[g[id][k]] + 1)
{
if(range[temp].second < dp[s])
{
dp[s] = range[temp].second;
lst[s] = k;
use[s] = temp;
}
}
}
}
}
}
if(dp[U-1] == range[pos].second)
{
s = U - 1;
vector<pair<int,int> > son;
while(s)
{
res[id].push_back(g[id][lst[s]]);
son.push_back(make_pair(g[id][lst[s]], use[s])); // 注意不能直接递归，因为会破坏 lst,use 数组
s ^= (1 << lst[s]);
}
for(auto t : son)
{
solve(t.first, t.second);
}
reverse(res[id].begin(), res[id].end());
return;
}
}
}
}
int main()
{
int n, m, x, op, i, j;
cin >> n;
for(i = 1; i <= n; i++)
{
cin >> op >> m;
if(op == 1)
{
for(j = 1; j <= m; j++)
{
cin >> x;
g[i].push_back(x);
}
}
else
{
pl[i] = cnt+1;
for(j = 1; j <= m; j++)
{
cin >> x;
range[++cnt] = make_pair(x, x);
}
pr[i] = cnt;
sort(range+pl[i], range+pr[i]+1);
}
}
dfs(1);
if(pl[1] > pr[1])
{
cout << "No";
return 0;
}
cout << "Yes\n";
solve(1, pl[1]);
for(i = 1; i <= n; i++)
{
for(int temp : res[i])
cout << temp << " ";
cout << endl;
}
return 0;
}::::