NOI2020 简要题解
command_block
2021-02-03 15:43:03
$$\large\text{Current Score : 400}$$
# D1T1 [美食家](https://www.luogu.com.cn/problem/P6772)
**题意** ： 有一张 $n$ 个点的有向图，第 $i$ 条边从 $v_i$ 连向 $u_i$ ，通过需要 $t_i$ 天。
玩家需要在时刻 $0$ 从点 $1$ 出发，经过 $T$ 个时刻恰好回到点 $1$。旅途中必须一直行走，不能在节点上停留。
每到达一次节点 $u$ ，就会得到 $w_u$ 的收益。
此外，还有 $m$ 次突发事件，形如 $(u,t,w)$ ，表示在时刻 $t$ 恰好在节点 $u$ 就能得到 $w$ 的额外收益。
求出收益的最大值。
$n\leq 50,t_i\leq 5,m\leq 500,T\leq 10^9$
------------
- 子问题 : $t=1,m=0$
此时所有边的耗时均为 $1$ ，且没有突发事件。
容易想到如下 $\rm DP$ :
设 $f[t][u]$ 为在时刻 $t$ 到达节点 $u$ 所能得到的最大收益。
则有转移 $f[t][u]=w[u]+\max\limits_{v\rightarrow u}f[t-1][v]$
可以用 $\{\max,+\}$ 矩阵乘法来描述转移。具体地，构造转移矩阵 $A[v][u]=[v\rightarrow u]w[u]$
若将 $f[t][\_]$ 看做一个向量法，则有 $f[t]=f[t-1]\times A$，即 $f[k]=f[0]\times A^k$。
由于矩阵乘法有结合律，使用矩阵快速幂即可加速转移。
- 原问题
现在我们要处理两个问题，一是边权，而是美食节。
对于一条长度为 $d$ 的边，可以将其拆成 $d$ 个点的一条链，其中点权均为 $0$。
但是，这样会使得总点数增大至 $wm$ 级别，无法承受。
可以让多条不同的出边共用同一条链，这样总点数就是 $nw$ 级别，可以承受。
有美食节的一轮中，转移是特殊的，不能直接使用一般的转移矩阵。
我们可以一段段加速转移，在遇到美食节时停止并处理特殊转移。
这就要求我们需要 $k$ 次将指定向量转移若干轮。
若每次都使用矩阵快速幂，复杂度为 $O(k(nw)^3\log T)$ ，无法通过。
注意到，对于矩阵 $A,B$ 和向量 $T$，有 $T\times (A\times B)=(T\times A)\times B$。
若按照前者计算，需要先计算矩阵乘法，但按照后者计算，就只需要计算向量和矩阵的乘法。
具体地，对于每个 $2$ 的幂预处理出转移矩阵，然后按位拆分后乘到向量中即可。
复杂度为 $O((nw^3)\log T+k(nw)^2\log T)$ ，别看数值复杂度达到了 $8\times 10^8$ ，其实可以轻松通过。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 255
using namespace std;
const ll INF=1ll<<60;
int N;
struct Matrix
{ll a[MaxN][MaxN];}A,pw[35];
void times(Matrix &C,const Matrix &A,const Matrix &B)
{
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
C.a[i][j]=-INF;
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
for (int k=1;k<=N;k++)
C.a[i][k]=max(C.a[i][k],A.a[i][j]+B.a[j][k]);
}
void times(ll *C,const Matrix &A)
{
static ll S[MaxN];
for (int i=1;i<=N;i++)
{S[i]=C[i];C[i]=-INF;}
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
C[i]=max(C[i],S[j]+A.a[j][i]);
}
void trans(ll *C,int t)
{
for (int i=0;i<30;i++)
if (t&(1<<i))
times(C,pw[i]);
}
struct Data{int tim,u,w;}b[MaxN];
bool cmp(const Data &A,const Data &B)
{return A.tim<B.tim;}
ll ans[MaxN];
int n,m,T,k,w[MaxN];
int main()
{
scanf("%d%d%d%d",&n,&m,&T,&k);
for (int i=1;i<=n;i++)scanf("%d",&w[i]);
N=n*5;
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
A.a[i][j]=-INF;
for (int u=1;u<=n;u++){
A.a[u][u+n]=0;
A.a[u+n][u+2*n]=0;
A.a[u+2*n][u+3*n]=0;
A.a[u+3*n][u+4*n]=0;
}
for (int i=1,u,v,d;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
A.a[u+(d-1)*n][v]=w[v];
}
pw[0]=A;
for (int i=1;i<30;i++)
times(pw[i],pw[i-1],pw[i-1]);
for (int i=1;i<=k;i++)
scanf("%d%d%d",&b[i].tim,&b[i].u,&b[i].w);
sort(b+1,b+k+1,cmp);
for (int i=1;i<=N;i++)ans[i]=-INF;
ans[1]=w[1];
for (int i=1;i<=k;i++){
trans(ans,b[i].tim-b[i-1].tim);
ans[b[i].u]+=b[i].w;
}trans(ans,T-b[k].tim);
printf("%lld",ans[1]<0 ? -1 : ans[1]);
return 0;
}
```
# D1T2 [命运](https://www.luogu.com.cn/problem/P6773)
**题意** ： 给出一棵 $n$ 个点的树，以 $1$ 为根。
给出 $m$ 条树上路径 $(u,v)$ ，满足 $u$ 是 $v$ 的祖先。
给树的每条边染色（黑白），使得每条路径中至少有一条黑边，求方案数。答案对 $988244353$ 取模。
$n,m\leq 5\times 10^5$
------------
好题。
设 $f[u,k]$ 表示考虑一端在 $u$ 的子树中的所有路径，未满足的路径另一端深度最大值为 $k$ 的方案数。要求 $k<dep_u$。
若不存在未满足的路径，则记为 $f[u,0]$。
答案为 $f[1,0]$。
考虑所有从 $u$ 开始的路径 $(u,t)$ ，求出 $d=\max dep_t$。未考虑任何子树时，边界为 $f[u,d]=1$。
对于子树 $v$ ，有转移 :
$$f'[u,k]=f[u,k]\sum\limits_{i\leq dep_u}f[v][i]+\sum\limits_{\max(k_1,k_2)=k}f[v,k_1]f[u,k_2]$$
若边 $(u,v)$ 的权值为 $1$ ，则可以满足 $v$ 的所有路径，状态 $[v,k_1],[u,k_2]$ 合并之后会变成 $[u,k_2]$。
若边 $(u,v)$ 的权值为 $0$ ，状态 $[v,k_1],[u,k_2]$ 合并之后会变成 $[u,\max(k_1,k_2)]$。
可以进一步写成 :
$$f'[u,k]=f[u,k]\sum\limits_{i\leq dep_u}f[v][i]+f[v,k]\sum\limits_{i\leq k}f[u,i]+f[u,k]\sum\limits_{i\leq k}f[v,i]-f[u,k]f[v,k]$$
考虑优化，记 $g[u,k]=\sum\limits_{i\leq k}f[u,i]$ ，则转移可以写作 :
$$f'[u,k]=f[u,k]\big(g[v,dep_u]+g[v,k]\big)+f[v,k]g[u,k]-f[u,k]f[v,k]$$
注意到 $f$ 有值的位置不多，考虑使用线段树合并优化转移。
并不需要在线段树中维护 $g$ ，而只需要维护 $f$ 的区间和，然后一边合并一边计算。类似 [P5298 [PKUWC2018]Minimax](https://www.luogu.com.cn/problem/P5298)。
首先查询 $g[v,dep_u]$ ，记为一个固定常数 $C$。
若 $v$ 树为空，则打一个区间乘 $\big(C+g[v,k]\big)$ 的标记。
若 $u$ 树为空，则打一个区间乘 $g[u,k]$ 的标记。
具体实现见代码。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 500500
using namespace std;
const int mod=998244353;
vector<int> g[MaxN];
int dep[MaxN];
void pfs(int u)
{
for (int i=0,v;i<g[u].size();i++)
if (!dep[v=g[u][i]]){
dep[v]=dep[u]+1;
pfs(v);
}
}
struct Data{
int l,r,s,tim;
inline void ladd(int c)
{s=1ll*s*c%mod;tim=1ll*tim*c%mod;}
}a[MaxN*22];
int tn,rt[MaxN];
int cre(){a[++tn].tim=1;return tn;}
inline void up(int u)
{a[u].s=(a[a[u].l].s+a[a[u].r].s)%mod;}
inline void ladd(int u)
{
if (a[u].tim!=1){
if (a[u].l)a[a[u].l].ladd(a[u].tim);
if (a[u].r)a[a[u].r].ladd(a[u].tim);
a[u].tim=1;
}
}
int to;
void add(int l,int r,int &u)
{
if (!u)u=cre();
if (l==r){a[u].s=(a[u].s+1)%mod;return ;}
int mid=(l+r)>>1;ladd(u);
if (to<=mid)add(l,mid,a[u].l);
else add(mid+1,r,a[u].r);
up(u);
}
int wfr,ret;
void qry(int l,int r,int &u)
{
if (!u)return ;
if (r<=wfr){ret=(ret+a[u].s)%mod;return ;}
int mid=(l+r)>>1;ladd(u);
qry(l,mid,a[u].l);
if (mid<wfr)qry(mid+1,r,a[u].r);
}
int C;
int merge(int u,int v,int su,int sv)
{
if (!u){a[v].ladd(su);return v;}
if (!v){a[u].ladd(C+sv);return u;}
if (a[u].l==a[u].r)
a[u].s=(1ll*a[u].s*(C+sv)+1ll*a[v].s*(su+a[u].s))%mod;
else {
ladd(u);ladd(v);
a[u].r=merge(a[u].r,a[v].r,(su+a[a[u].l].s)%mod,(sv+a[a[v].l].s)%mod);
a[u].l=merge(a[u].l,a[v].l,su,sv);
up(u);
}return u;
}
int n,h[MaxN];
void dfs(int u)
{
to=h[u];add(0,n,rt[u]);
for (int i=0,v;i<g[u].size();i++)
if (dep[v=g[u][i]]>dep[u]){
dfs(v);
wfr=dep[u];ret=0;qry(0,n,rt[v]);C=ret;
rt[u]=merge(rt[u],rt[v],0,0);
}
}
int m;
int main()
{
scanf("%d",&n);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}dep[1]=1;pfs(1);
scanf("%d",&m);
for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
if (dep[u]>dep[v])swap(u,v);
h[v]=max(h[v],dep[u]);
}dfs(1);
ret=wfr=0;qry(0,n,rt[1]);
printf("%d",ret);
return 0;
}
```
# D1T3 [时代的眼泪](https://www.luogu.com.cn/problem/P6774)
**题意** : 区间定值域顺序对数。
$n\leq 10^5$
------------
见 [[DS记录]P6579 [Ynoi2019] Happy Sugar Life](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p6579-ynoi2019-happy-sugar-life)
# D2T1 [制作菜品](https://www.luogu.com.cn/problem/P6775)
**题意** : 本题是构造题。
有 $n$ 种原料，第 $i$ 种原料有 $d_i$ 克，所有原料共有 $m\times k$ 克。
玩家需要制作 $m$ 道菜，每道菜恰使用 $k$ 克原材料，且至多使用两种原材料。
构造一组做菜的方案，或指出无解。
$n\leq 500,m,k\leq 5000$ ，保证 $n-2\leq m$。
------------
观察数据范围，发现 $m$ 和 $n-1,n-2$ 的大小关系是解决本题的关键信息。
- **引理** $m\geq n-1$ 时必然有解。
考虑归纳，当 $n=1$ 时显然。
否则，考虑最少的原料，若数量 $\geq k$ ，则说明 $m\geq n$ ，用该原料做一道菜，做完后仍有 $m\geq n-1$。
若 $<k$ ，则配合最多的原料制作一道菜（一定能做出来）， $m$ 减少 $1$ 的同时 $n$ 至少减少 $1$ ，仍满足 $m\geq n-1$。
对于 $m\geq n-1$ 的部分分，按照上述过程贪心构造即可。
对于 $m=n-2$ 的 情况，考虑一组解，在做同一个菜的两个原料之间连边，由于只有 $n-2$ 条边，所以最少有两个联通块。
不难想到将整个集合剖分成两个 $m=n-1$ 的情况。
这相当于要求 $(|S|-1)k=\sum\limits_{i\in S}d_i$ 即 $-k=\sum\limits_{i\in S}(d_i-k)$
`bitset` 优化可行性背包，复杂度为 $O\Big(\frac{n^2k}{w}\Big)$。
构造方案时，利用 DP 数组容易判定 选/不选 该物品是否可能可行。
```cpp
#include<algorithm>
#include<cstdio>
#include<bitset>
#define MaxN 505
#define MaxK 10500
using namespace std;
struct Data{int x,p;}s[MaxN],st[MaxN];
bool cmp(const Data &A,const Data &B)
{return A.x<B.x;}
int k;
void constr(Data *a,int n,int m)
{
for (int i=1;i<=m;i++){
int p1=0,sav=m*k;
for (int i=1;i<=n;i++)
if (a[i].x>0&&a[i].x<sav)
{sav=a[i].x;p1=i;}
if (a[p1].x>=k){
printf("%d %d\n",a[p1].p,k);
a[p1].x-=k;continue;
}
int p2=0;sav=0;
for (int i=1;i<=n;i++)
if (a[i].x>sav&&i!=p1)
{sav=a[i].x;p2=i;}
printf("%d %d %d %d\n",a[p1].p,a[p1].x,a[p2].p,k-a[p1].x);
a[p2].x-=k-a[p1].x;a[p1].x=0;
}
}
int n,m;
bitset<MaxN*MaxK> e[MaxN];
bool fl[MaxN];
void solve()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++)
{scanf("%d",&s[i].x);s[i].p=i;}
if (m>=n-1)constr(s,n,m);
else {
const int Zero=MaxN*MaxK/2;
e[0][Zero]=1;
for (int i=1;i<=n;i++){
int c=s[i].x-k;
if (c>0)e[i]=e[i-1]|(e[i-1]<<c);
else e[i]=e[i-1]|(e[i-1]>>(-c));
}
if (!e[n][Zero-k]){puts("-1");return ;}
else {
for (int i=1;i<=n;i++)fl[i]=0;
int now=Zero-k;
for (int p=n;p;p--)
if (!e[p-1][now])
{fl[p]=1;now-=s[p].x-k;}
int tn=0;
for (int i=1;i<=n;i++)if (fl[i])st[++tn]=s[i];
constr(st,tn,tn-1);
tn=0;
for (int i=1;i<=n;i++)if (!fl[i])st[++tn]=s[i];
constr(st,tn,tn-1);
}
}
}
int main()
{
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```
# D2T2 [超现实树](https://www.luogu.com.cn/problem/P6776)
好题。
注意到 : 存在无穷多个无法长出的树 $\Leftrightarrow$ 存在深度无穷大的无法长出的树。
我们不妨设定一个很大的深度 $d$ ，然后考虑所有深度为 $d$ 的树 $S$，若存在某一棵无法长出，则树林是不完备的。
考虑化简集合 $S$ ，若树 $A$ 能生长出树 $B$ ，则无需判定树 $B$。
手玩不难发现，只需要考虑“链树” ，即除去叶子后为一条链的树。任意一棵树都能由等高的链树长出。
由此，若 $T$ 集合中存在非链树，则不可能长成掉任何一棵链树，这样的树可以抛弃。
现在 $T$ 中只剩下链树。对于链树中的某点 $u$ ，存在下列四种情况 :
- ① 左侧为叶子或链，右侧为空
- ② 左侧为叶子或链，右侧为叶子
- ③ 右侧为叶子或链，左侧为空
- ④ 右侧为叶子或链，左侧为叶子
对于左右两侧都是叶子的点，则认为同时满足 ②④。
按照这个规则建立四叉树，合并后搜索。
子树 $u$ 是完备的，当且仅当下列条件之一成立 :
- 某棵链树中 $u$ 是叶子
- $u$ 的各个子树都完备
复杂度 $O(n)$。
```cpp
```
# D2T3 [翻修道路](https://www.luogu.com.cn/problem/P6777)
咕。