20230926 B 组模拟赛 题解
前言
这次 T1 复杂度写假挂了，100->0，T2T3T4 貌似都是套路题，但是一个都不会，最终得分 0+29+53+0=82。
感觉卷题还是卷得太少了，别人比我多两年积累，以后不能再颓废了。
T1
最开始一眼以为这道题是偏序问题，后面发现不太对劲。
容易发现这是一个类似拓扑排序的东西，那么我们可以考虑类似于拓扑排序的做法。
首先对于每个主题 $j$，把 $r_{i,j}$ 升序排列，然后对于每个主题开一个指针，这样只要知道了每个主题的进度就能 $O(nk)$ 地维护有哪些主题的标准是达到了的。
那么我们可以对每一个模块记有多少主题达标，如果有 $k$ 个主题达标说明这个模块已经可以学习了（类似于拓扑排序中的 $deg=0$）。
啊啊啊题解写着感觉好抽象，总之就是像拓扑排序一样维护即可，复杂度 $O(nk\log n)$（因为要排序）。
值得一提的是我赛时复杂度写假了，以为是排序常数大了，就打了基排。结果实际上由于大样例过水基排过了，但其实在大部分数据下基排比快排慢多了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f;
int n,m,ans;
signed main(){
n=read();m=read();
vector<vector<int> > r(n+5,vector<int>(m+5)),u(n+5,vector<int>(m+5));
vector<vector<pii> > seq(m+5);
vector<i64> sum(m+5,0);
vector<int> cnt(n+5,0),pt(m+5,0);
forup(i,1,n){
forup(j,1,m){
r[i][j]=read();
seq[j].push_back(mkp(r[i][j],i));
}
}
forup(i,1,m){
sort(seq[i].begin(),seq[i].end());
}
forup(i,1,n){
forup(j,1,m){
u[i][j]=read();
}
}
forup(pp,1,n){
bool flag=true;
vector<int> sv;
forup(i,1,m){
while(pt[i]<n&&seq[i][pt[i]].fi<=sum[i]){
cnt[seq[i][pt[i]].se]++;
if(cnt[seq[i][pt[i]].se]==m){
sv.push_back(seq[i][pt[i]].se);
flag=false;
}
++pt[i];
}
}
if(flag) break;
for(auto i:sv){
++ans;
forup(j,1,m){
sum[j]+=u[i][j];
}
}
}
printf("%d\n",ans);
}
T2
貌似是颜色段均摊套路题。
首先每个任务相当于给区间染色，但是区间内每个点染的颜色不同，如何解决呢？
容易发现，若把 $i$ 点的颜色 $c_i$ 改为 $c_i-i$，每个位置前后两个任务的时间差是不会变的，而每个任务染的颜色就相同了。
那么可以直接用珂朵莉树维护了。
关于复杂度，珂朵莉树维护颜色段均摊的复杂度是 $O(n\log n)$ 的。
考虑每次加区间时，区间数量至多加二（就是把原来的某个大区间分成两半，然后加一个进去）。而对于覆盖的区间，每个区间只会被删除一次，势能分析可得对区间的操作数是 $O(n)$ 级别的，而 set 是 $O(\log n)$ 的，故复杂度为 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=0x3f3f3f3f;
i64 n,m,q,Tm;
i64 res[N],ans[N];
i64 l[N],r[N];
struct node{
i64 val,pos;
}s[N];
struct range{
i64 l,r;i64 co;
bool operator <(const range &pp)const{
if(l==pp.l) return r<pp.r;
return l<pp.l;
}
};
set<range> odt;
set<range>::iterator split(i64 l){
set<range>::iterator it=odt.upper_bound(range{l,0,0});
if(it->l==l) return it;
--it;
i64 nc=it->co,nl=it->l,nr=it->r;
odt.erase(it);
odt.insert(range{nl,l-1,nc});
return odt.insert(range{l,nr,nc}).fi;
}
i64 binarysearch(i64 vv){
if(vv<s[1].val) return 0;
i64 ll=1,rr=q,mm;
while(ll<rr){
mm=(ll+rr+1)>>1;
if(s[mm].val<=vv) ll=mm;
else rr=mm-1;
}
return ll;
}
signed main(){
n=read();m=read();q=read();
forup(i,1,m){
l[i]=read(),r[i]=read();
}
forup(i,1,q){
s[i].val=read();s[i].pos=i;
}
sort(s+1,s+q+1,[](node a,node b){
return a.val<b.val;;
});
odt.insert(range{1,n,-inf});
forup(i,1,m){
i64 nw=Tm-l[i];
set<range>::iterator ed=split(r[i]+1),st=split(l[i]);
for(set<range>::iterator it=st;it!=ed;odt.erase(prev(++it))){
if(it->co!=-inf){
res[binarysearch(nw-it->co-1)]+=it->r-it->l+1;
}
}
odt.insert(range{l[i],r[i],nw});
Tm+=r[i]-l[i]+1;
}
fordown(i,q,1){
res[i]+=res[i+1];
ans[s[i].pos]=res[i];
}
forup(i,1,q){
printf("%lld ",ans[i]);
}
}
T3
容易发现，最优路径应该是前半部分单调向上，中间有一段平飞，然后后半部分单调向下，那么我们只考虑前半部分单调向上，后半部分是对称的。
考虑假如已经知道了到 $u$ 的最短时间 $dis_u$，存在一条边 $(u,v)$，那么经过 $u$ 到达 $v$ 的最短时间 $dis_v$ 是多少。
容易发现，是 $\max(dis_u+1,a_v)$，自己模拟一下即可。
然后容易发现，这个式子是可以用 dijkstra 维护的。
具体证明参考 Oi Wiki，总之容易发现这个式子也是满足 $D_y\le D_u$ 的，那么可以用 dijkstra 求出 $1$ 到每个点的时间和 $n$ 到每个点的距离（时间）。
但是这样不能处理中间平飞的那段。
考虑转化一下，容易发现假如中间平飞的距离大于等于 $2$，两端点相连的路径都从平飞变成上升/下降并不会改变总时间。
大概就是从这样：
变成这样：
懒得画图了，将就一下。那么就可以把中间平飞的距离根据奇偶性变为 $0/1$。
设从 $1$ 到 $i$ 的最短路为 $dis_{0,i}$，从 $n$ 到 $i$ 的为 $dis_{1,i}$ 现在分情况讨论：
若平飞段长度为 $0$：
那么平飞段就是一个转折点，设这个点为 $u$。
- 若前后最短路都取高度，即两边路径上均存在一个点使得高度大于路径长度：
那么显然，时间为 $2a_u$，
- 若前后最短路都取路径长度，即路径上不存在一个点使得高度大于路径长度：
容易发现，由于存在转折点，那么必定会一个中心点，使得前后距离相同，由于我们要枚举 $u$，那么必定能找到这个中心点，答案可取 $2\max(dis_{0,u},dis_{1,u})$。
- 若一边取路径长度一边取高度：
类似于第二种，容易发现在取高度那边的最高点上能转化成第一种。
综上，答案取 $2\max(dis_{0,u},dis_{1,u})$。
若长度为 $1$：
那么平飞段就是一条边，设为 $(u,v)$。
证明类似，总之答案取 $2\max(dis_{0,u},dis_{1,v})+1$。
跑两遍 dijkstra 复杂度是 $O(m\log m)$，最终枚举中心点求答案复杂度是 $O(n+m)$ 的，总复杂度为 $O(m\log m)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=1e18;
i64 n,m,a[N],ans=inf;
vector<i64> e[N];
i64 dis[2][N],vis[N];
struct Node{
i64 dis,u;
bool operator <(const Node &r)const{return dis>r.dis;}
};
priority_queue<Node> q;
void dij(int s,int p){
mem(dis[p],0x3f);mem(vis,0);
dis[p][s]=0;
q.push(Node{0,s});
while(q.size()){
int u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto v:e[u]){
if(dis[p][v]>max(dis[p][u]+1,a[v])){
dis[p][v]=max(dis[p][u]+1,a[v]);
q.push(Node{dis[p][v],v});
}
}
}
}
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
}
forup(i,1,m){
i64 u=read(),v=read();
e[u].push_back(v);e[v].push_back(u);
}
dij(1,0);dij(n,1);
forup(i,1,n){
ans=min(ans,max(dis[0][i],dis[1][i])*2);
for(auto j:e[i]){
ans=min(ans,max(dis[0][i],dis[1][j])*2+1);
}
}
printf("%lld\n",ans);
}
T4
首先假如在线做要维护左右两个端点，非常麻烦。那么考虑离线解决。
具体来说，把所有区间和询问挂在右端点上，这样只需要从左到右扫一遍维护左端点即可。
那么考虑对每个点维护能覆盖它的区间中左端点最靠右是多少，若不存在能覆盖它的区间则为 $0$，容易发现只要询问区间 $[l,r]$ 中这个值的最小值大于等于 $l$ 就合法。
证明很简单，首先满足这个条件那么选中的所有区间必定不超出询问区间，且询问区间内每个点都被覆盖（否则那个值就为 $0$ 了），那么必定恰好覆盖询问区间。
考虑如何维护，加新区间是一个区间取 $\max$ 的过程，然后询问是区间求 $\min$。 是一个很板的势能分析线段树
其实仔细分析一下完全不需要写 Segbeats，区间取 $\max$ 后完全可以直接确定区间最小值，就像普通线段树一样写就行了。
复杂度 $O((n+q)\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int n,m,q;
bool ans[N];
vector<int> rg[N];
vector<pii> qry[N];
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int querymin[N<<2],mark[N<<2];
void PushUp(int id){
querymin[id]=min(querymin[id<<1],querymin[id<<1|1]);
}
void PushDown(int id){
mark[id<<1]=max(mark[id<<1],mark[id]);
mark[id<<1|1]=max(mark[id<<1|1],mark[id]);
querymin[id<<1]=max(mark[id],querymin[id<<1]);
querymin[id<<1|1]=max(mark[id],querymin[id<<1|1]);
mark[id]=0;
}
void Update(int L,int R,int X,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
querymin[id]=max(querymin[id],X);
mark[id]=max(mark[id],X);
return;
}
if(mark[id]) PushDown(id);
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
PushUp(id);
}
int Querymin(int L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
return querymin[id];
}
if(mark[id]) PushDown(id);
int res=inf;
if(L<=mid) res=min(res,Querymin(L,R,lson));
if(mid< R) res=min(res,Querymin(L,R,rson));
return res;
}
}mt;
signed main(){
n=read();m=read();q=read();
forup(i,1,m){
int l=read(),r=read();
rg[r].push_back(l);
}
forup(i,1,q){
int l=read(),r=read();
qry[r].push_back(mkp(l,i));
}
forup(i,1,n){
for(auto j:rg[i]){
mt.Update(j,i,j);
}
for(auto j:qry[i]){
ans[j.se]=(mt.Querymin(j.fi,i)>=j.fi);
}
}
forup(i,1,q){
puts(ans[i]?"YES":"NO");
}
}