NOI2019 简要题解
command_block
2021-06-14 22:13:05
$$\large\text{Current Score : 300}$$
# D1T1 [回家路线](https://www.luogu.com.cn/problem/P5468)
**题意** ： 有 $n$ 个站点，编号分别为 $1\sim n$。玩家想要从站点 $1$ 前往站点 $n$。
初始时刻为 $0$ 。有若干趟列车，第 $i$ 班次从 $u_i$ 开往 $v_i$ ，在时刻 $p_i$ 上车，时刻 $q_i$ 下车。
玩家在站点等待会增加烦躁值。具体地，若在某个站点连续等待了 $t$ 秒，则烦躁值增加 $At^2+Bt+C$ ，其中 $A,B,C$ 为给定常数。
若在时刻 $z$ 到达终点，则烦躁值额外增加 $z$。
输出完成任务所积累的最小烦躁值。
$n\leq 10^5,m\leq 2\times 10^5$ ，时限$\texttt{1s}$。
------------
签到题。
记 $f_u(t)$ 为在 $t$ 时刻出现在站点 $u$ 所需累积的最小烦躁值。
为了处理 $z$ ，我们将 $B$ 加一，然后坐车会减少 $q-p$ 的烦躁值。
对于某一班列车 $(u,v,p,q)$，有转移 ：
$$
\begin{aligned}
f_v(p+t)&\leftarrow f_u(p)+At^2+Bt+C\\
f_v(t)&\leftarrow A(t-p)^2+B(t-p)+C+f_u(p)\\
&=At^2+(B-2Ap)t+\big(C+f_u(p)-Bp+Ap^2\big)
\end{aligned}
$$
于是可以将 $f_u(t)$ 表示成若干个二次函数取 $\max$ 的形式。
按照出发时刻从早到晚考虑列车。
当查询 $f_u(p)$ 时，将早于（含）时刻 $p$ 到达的列车的二次函数取出，求 $\max$。
然后将产生的二次函数贡献至 $f_v$ （暂不生效）
能发现，所有二次函数的二次项系数是一样的，而一次项系数单调减小，于是可以维护（$n$ 个）凸壳。
复杂度 $O\big((n+m)\log n\big)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define pb push_back
#define MaxN 100500
#define MaxM 1000500
using namespace std;
const ll INF=1ll<<60;
struct Line{
int k;ll b;
ll get(int x){return 1ll*k*x+b;}
};
bool chk(Line A,Line B,Line C){
ll x1=A.k-B.k,x2=C.k-B.k,
y1=A.b-B.b,y2=C.b-B.b;
return x1*y2-y1*x2<=0;
}
int A,B,C;
struct Hull
{
vector<Line> q;
int p=0;
void add(Line L){
while(q.size()>=2&&chk(q[q.size()-2],q.back(),L))q.pop_back();
q.pb(L);
}
ll qry(int t)
{
if (q.empty())return INF;
while(p+1<q.size()&&q[p].get(t)>=q[p+1].get(t))p++;
return 1ll*A*t*t+q[p].get(t);
}
}H[MaxN];
struct Trans{int u,v,p,q;Line t;}l[MaxM];
int n,m,p1[MaxM],p2[MaxM];
bool cmp1(int A,int B){return l[A].p<l[B].p;}
bool cmp2(int A,int B){return l[A].q<l[B].q;}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);
for (int i=1;i<=m;i++){
scanf("%d%d%d%d",&l[i].u,&l[i].v,&l[i].p,&l[i].q);
p1[i]=p2[i]=i;
}sort(p1+1,p1+m+1,cmp1);sort(p2+1,p2+m+1,cmp2);
ll ans=INF;
H[1].add((Line){B,C});
int p=1;
for (int i=1;i<=m;i++){
int k=p1[i];
for (;l[p2[p]].q<=l[k].p;p++)if (l[p2[p]].t.b!=INF){
int v=l[p2[p]].v,t=l[p2[p]].q;
H[v].add(l[p2[p]].t);
if (v==n)ans=min(ans,1ll*A*t*t+t+l[p2[p]].t.get(t)-C);
}
ll buf=H[l[k].u].qry(l[k].p);
if (buf==INF){l[k].t.b=INF;continue;}
l[k].t=(Line){B-2*A*l[k].q,C+buf-1ll*B*l[k].q+1ll*A*l[k].q*l[k].q};
}
for (;p<=m;p++)
if (l[p2[p]].v==n&&l[p2[p]].t.b!=INF){
int t=l[p2[p]].q;
ans=min(ans,1ll*A*t*t+t+l[p2[p]].t.get(t)-C);
}
printf("%lld",ans);
return 0;
}
```
# D1T2 [机器人](https://www.luogu.com.cn/problem/P5469)
**题意** : 有从左到右一排柱子，第 $i$ 个柱子的高度为 $h_i$。
实验时，会选择一根柱子 $s$ ，并在上面放置两个机器人。机器人只能在相邻的柱子之间移动。
第一个机器人会一直向左平移，但无法移动到比 $s$ 高的柱子上。
第一个机器人会一直向右平移，但只能移动到比 $s$ 低的柱子上。
现在我们需要设置 $\{h_{1\sim n}\}$ ，满足下列条件 ：
- $h_i\in[L_i,R_i]$
- 无论测试起点 $s$ 选在哪里，两个机器人走过的柱子数目的差 $\leq 2$
求方案数，答案对 $10^9+7$ 取模。
$n\leq 300,L,R\leq 10^9$
------------
首先观察合法方案的条件。
对于最右侧的最大值，在上面放置机器人可以走遍整个序列，且从其余的位置出发不能跨越这个位置。
考虑区间 $\rm DP$ ，设 $dp[l,r,x]$ 表示区间 $[l,r]$ 内的数最大值恰为 $x$ 的方案数。
枚举最右侧最大值所在位置 $mid$ 以及两侧的最大值，有转移 ：
$$dp[l,r,x]=\sum\limits_{mid}\sum_{k\leq x}dp[l,mid-1,k]\times \sum_{k<x}dp[mid+1,r,k]$$
此时 $mid$ 可能的取值只能是中点附近的 $O(1)$ 个。因此，可能的 $[l,r]$ 远远不到 $O(n^2)$ ，当 $n=300$ 时只有 $m=2518$ 个。
记忆化搜索可以通过 $L,R$ 较小的点，获得 $50'$。
注意到 $x$ 可能非常大，不能直接记录在状态中。将值域离散化，划分为若干个区间，每个区间内的 $x$ 的转移都是相同的。
不难发现，$dp[l,r,x]$ 是关于 $x$ 的分段函数，且每一段都是 $O(r-l)$ 次的多项式。（其前缀和自然也是 $O(r-l)$ 次多项式）
于是，对每一段分别进行 DP，只需要转移出前 $O(r-l)$ 个状态，然后就能进行拉插。
拉插的下标连续，故容易线性求出。有 $O(n)$ 个值域区间，每个区间要处理 $m$ 个状态，复杂度为 $O(n^2m)$。
```cpp
```
# D1T3 [序列](https://www.luogu.com.cn/problem/P5470)
- [题解 【P5470 [NOI2019] 序列】](https://www.luogu.com.cn/blog/command-block/solution-p5470)
# D2T1 [弹跳](https://www.luogu.com.cn/problem/P5471)
**题意** : 给出 $n$ 个二维点，每个点向某个矩形内连边，求单源最短路。卡空间。
$n\leq 7\times 10^4,m\leq 1.5\times 10^5$。
------------
套路题。
考虑用数据结构模拟 Dijkstra 的过程。
用堆维护目前最短的转移，每次转移时，找出矩形内尚未到达的点，确定这些点的 $dis$ ，向堆中加入这些点的出边。
这需要一个支持矩阵内找点的数据结构。
可以用线段树套 `std::set` 做到时间 $O(n\log^2n)$ 空间 $O(n\log n)$。也可以用 $\rm KDT$ 做到时间 $O(n\sqrt{n})$ （略微卡常）空间 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#include<set>
#define MaxN 70500
#define pb push_back
#define Pr pair<int,int>
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
int w,to;Pr wfs;
set<Pr> s[MaxN<<2];
void add(int l=1,int r=w,int u=1)
{
s[u].insert(wfs);
if (l==r)return ;
int mid=(l+r)>>1;
if (to<=mid)add(l,mid,u<<1);
else add(mid+1,r,u<<1|1);
}
bool vis[MaxN];
int wfl,wfl2,wfr,wfr2,tot,tp[MaxN];
void upd(int l=1,int r=w,int u=1)
{
if (wfl<=l&&r<=wfr){
set<Pr>::iterator it;
while(1){
it=s[u].lower_bound(mp(wfl2,0));
if (it->fir>wfr2)break;
tp[++tot]=it->sec;
if (vis[tp[tot]])tot--;
s[u].erase(it);
}return ;
}int mid=(l+r)>>1;
if (wfl<=mid)upd(l,mid,u<<1);
if (mid<wfr)upd(mid+1,r,u<<1|1);
}
struct Data{
int l1,r1,l2,r2,t;
bool operator < (const Data &B) const
{return t>B.t;}
};
vector<Data> g[MaxN];
int dis[MaxN];
priority_queue<Data> q;
void del(int u)
{
vis[u]=1;
for (int i=0;i<g[u].size();i++){
g[u][i].t+=dis[u];
q.push(g[u][i]);
}
}
int n,m,h;
int main()
{
n=read();m=read();w=read();h=read();
for (int i=1;i<=n;i++){
to=read();
wfs=mp(read(),i);
add(1,w,1);
}for (int i=1;i<=w*4;i++)
s[i].insert(mp(n+1,0));
Data sav;
for (int i=1,u;i<=m;i++){
u=read();sav.t=read();
sav.l1=read();sav.r1=read();
sav.l2=read();sav.r2=read();
g[u].pb(sav);
}del(1);
while(!q.empty()){
Data u=q.top();q.pop();
wfl=u.l1;wfr=u.r1;
wfl2=u.l2;wfr2=u.r2;
tot=0;upd();
for (int i=1;i<=tot;i++){
dis[tp[i]]=u.t;
del(tp[i]);
}
}
for (int i=2;i<=n;i++)
printf("%d\n",dis[i]);
return 0;
}
```
# D2T2 [斗主地](https://www.luogu.com.cn/problem/P5472)
一副牌一共有 $n$ 张牌，初始时从上到下依次标号为 $1 - n$。标号为 $i$ 的牌**分数**是 $f(i)$。在 本题，$f(i)$ 有且仅有两种可能：$f(i) = i$ 或 $f(i) = i^2$。
洗牌环节一共分 $m$ 轮，这 $m$ 轮洗牌依次进行。第 $i$ 轮洗牌时：
拿出从最上面往下数的前 $A_i$ 张牌，形成两堆牌（某一堆可能为空）
对两堆牌进行合并。当第一堆牌还剩下 $X$ 张，第二堆牌还剩下 $Y$ 张的时候，以 $\dfrac{X}{X+Y}$ 的概率取第一牌堆底，放入新的第三堆牌的最上面， $\dfrac{Y}{X+Y}$ 的概率取第二牌堆底，放入新的第三堆牌的最上面。
一直取到两堆牌都为空为止。这样我们就完成了一轮洗牌。
询问 $m$ 轮洗牌完成后最终每个位置上的牌的
$Q$ 次询问你在经历了这 $m$ 轮洗牌后，各个位置上的牌的**期望分数**。
答案对 $998244353$ 取模。
$n\leq 10^7,m\leq 5\times 10^5$。
------------
命运题。
# D2T3 [I 君的探险](https://www.luogu.com.cn/problem/P5473)
**题意** : 本题是交互题。
有一张 $n$ 个点 $m$ 条边的无向图，点编号为 $0\sim n-1$ ，你需要通过交互得知图的具体形态。
点有点权，为 $0$ 或 $1$。初始时均为 $0$。
有下列四种操作 ：
- ① 查询给定点 $x$ 的点权。
- ② 将 $x$ 以及与 $x$ 相连的点的点权取反。
- ③ 报告找到了一条直接连接 $x,y$ 的无向边。
- ④ 询问与 $x$ 相连的边是否已全部找到。
其中操作 ①②④ 的次数限制分别为 $L_q,L_m,L_c$。
交互库是 inactive 的。
- $n=2\times 10^5,m=3\times 10^5,L_q=L_m=10^7,L_c=2\times m$
- $n=2\times 10^5,m=n-1,L_q=L_m=19\times n,L_c=0$
对于每个 $u>0$ ，存在 $v<u$ 使得 $u,v$ 直接相连。
------------