NOI2019 选做

喜欢ヅ旅行 2023-08-17 16:03 54阅读 0赞

施工中……

这里是一个同步赛选手，同步赛打铜了，下面内容来源于互联网，如有雷同敬请谅解……

# d1t1 回家路线 #

[d1t1][]

## 吐槽 ##

本题首先数据范围出的有点水，其次数据有点水，导致这题真的成了签到题。

现场某神仙：我很难见到少于 100 分的选手。

然而我菜死了，做法编假了只拿了 \\(90\\) ……

## 算法 1 ##

设 \\(f(i,j)\\) 表示时刻 \\(i\\) 到地点 \\(j\\) 所需的最少等待时间。  
\\\[f(q\_x,y\_x)=\\min\\\{f(i,j)+F(p\_x-i)\\\} (i\\le p\_x)\\\]枚举时间，对于每个时间点枚举合法状态转移并记录状态即可。

复杂度 \\(O(nT)\\) ，其中 \\(T=\\max\\\{q\_i\\\}\\) 。可以通过。

### 算法1 Code ###

#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; inline int gi() { char c=getchar(); int x=0; for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0'; return x; } const int N=2e5+5; int n,m,a,b,c,x[N],y[N],p[N],q[N],mxt; int f[1005][100005]; bool vis[1005][100005]; inline int F(int x) { return a*x*x+b*x+c; } vector<int> v[N],avi[N]; int main() { freopen("route.in","r",stdin); freopen("route.out","w",stdout); n=gi(),m=gi(),a=gi(),b=gi(),c=gi(); for(int i=1;i<=m;++i) { x[i]=gi(),y[i]=gi(),p[i]=gi(),q[i]=gi(),mxt=max(mxt,q[i]); v[x[i]].push_back(i); } f[0][1]=0,avi[0].push_back(1); for(int t=0;t<=mxt;++t) { for(int it1=0;it1<avi[t].size();++it1) { int i=avi[t][it1]; for(int it2=0;it2<v[i].size();++it2) { int j=v[i][it2]; if(p[j]>=t) { if(!vis[q[j]][y[j]]) { vis[q[j]][y[j]]=true; f[q[j]][y[j]]=f[t][i]+F(p[j]-t); avi[q[j]].push_back(y[j]); } else f[q[j]][y[j]]=min(f[q[j]][y[j]],f[t][i]+F(p[j]-t)); } } } } int ans=2147483647; for(int t=0;t<=mxt;++t) if(vis[t][n]) ans=min(ans,f[t][n]+t); printf("%d",ans); }

## 算法 2 ##

上面那个做法不是出题人的本意（出题人可能为了防爆 `int` 开的 \\(T\\le 10^3\\) ）

正解是斜率优化。设 \\(f(i)\\) 表示通过第 \\(i\\) 条边要等待的最短时间。  
\\\[ f(i)=\\min\\\{f(j)+A(p\_i-q\_j)^2+B(p\_i-q\_j)+C\\\}(q\_j\\le p\_i, y\_j=x\_i) \\\]最后答案为 \\(\\min\\\{f(i)+q\_i\\\}(y\_i=n)\\)

显然上面的式子是一个斜率优化的形式：  
\\\[ f(i)=\\min\\\{f(j)+Aq\_j^2-Bq\_j-2Bp\_iq\_j\\\}+Ap\_i^2+Bp\_i+C \\\]

\\\[ f(j)+Aq\_j^2-Bq\_j-2Bp\_iq\_j\\le f(k)+Aq\_k^2-Bq\_k-2Bp\_iq\_k \\\]

\\\[ (f(j)+Aq\_j^2-Bq\_j)-(f(k)+Aq\_k^2-B)\\le 2Bp\_i(q\_j-q\_k) \\\]

\\\[ \\frac\{g(j)-g(k)\}\{q\_j-q\_k\}\\le 2Bp\_i \\\]

\\\[ (g(x)=f(x)+Aq\_x^2-Bq\_x) \\\]故我们对于每个点维护一个单调队列，分别按 \\(p\_i,q\_i\\) 排序，枚举 \\(p\_i\\) ，将 \\(q\_j\\le p\_i\\) 的点加入队列按上述转移即可。

复杂度 \\(O(m\\log m)\\) 。本题值域很小可以做到排序线性，但没必要。

### 算法2 Code ###

#include<bits/stdc++.h> using namespace std; inline int gi() { char c=getchar(); int x=0; for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0'; return x; } typedef long long ll; const int N=2e5+5,M=1e6+6; int n,m; ll f[N],g[N]; struct node { int u,v,s,e,id; } a[N],b[N]; bool cmpe(node x, node y) { return x.e<y.e; } bool cmps(node x, node y) { return x.s<y.s; } vector<int> st[M]; int l[M],r[M],A,B,C; void update(int x) { int p=b[x].v,i=b[x].id; for(;l[p]<r[p]&&(g[st[p][r[p]]]-g[st[p][r[p]-1]])*(a[i].e-a[st[p][r[p]]].e) >=(g[i]-g[st[p][r[p]]])*(a[st[p][r[p]]].e-a[st[p][r[p]-1]].e);--r[p]) st[p].pop_back(); st[p].push_back(i); ++r[p]; } int F(int x) { return A*x*x+B*x+C; } void solve(int x) { int p=a[x].u; for(;l[p]<r[p]&&(g[st[p][l[p]+1]]-g[st[p][l[p]]]) <=2ll*A*a[x].s*(a[st[p][l[p]+1]].e-a[st[p][l[p]]].e);++l[p]); f[x]=f[st[p][l[p]]]+F(a[x].s-a[st[p][l[p]]].e); g[x]=f[x]+1ll*A*a[x].e*a[x].e-B*a[x].e; } int main() { n=gi(),m=gi(),A=gi(),B=gi(),C=gi(); for(int i=1;i<=m;++i) a[i].u=gi(),a[i].v=gi(),a[i].s=gi(),a[i].e=gi(); sort(a+1,a+1+m,cmps); for(int i=1;i<=m;++i) b[i]=a[i],b[i].id=i,l[i]=0,r[i]=0; st[1].push_back(0); for(int i=2;i<=m;++i) st[i].push_back(m+1); f[m+1]=g[m+1]=1ll<<40; sort(b+1,b+1+m,cmpe); for(int i=1,j=1;i<=m;++i) { for(;j<=m&&b[j].e<=a[i].s;++j) update(j); solve(i); } ll ans=1ll<<60; for(int i=1;i<=m;++i) if(a[i].v==n) ans=min(ans,f[i]+a[i].e); printf("%lld",ans); }

# d1t3 序列 #

[d1t3][]

## Solution ##

我们先考虑两种情况：

首先，当前选出的不公用元素 \\(<K-L\\) ，那么最优策略一定在两个序列中选最大的；

如果当前不共用元素 \\(= K-L\\) ，那我们在以下中取最大的：

1.  \\(a\_i+b\_i\\) 中最大的；
2.  \\(a\_i\\) 取了 \\(b\_i\\) 没取中 \\(b\_i\\) 最大的 + \\(a\_i\\) 最大的；
3.  \\(b\_i\\) 取了 \\(a\_i\\) 没取中 \\(a\_i\\) 最大的 + \\(b\_i\\) 最大的。

上面的选取方式会增加 \\(1\\sim 2\\) 个共用对。

我们可以用五个可删堆来分别维护上述信息。注意要实时统计当前的不共用元素数量。

复杂度 \\(O(n\\log n)\\)

### Code ###

#include<bits/stdc++.h> using namespace std; namespace io { const int SIZE=(1<<21)+1; char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55]; int x; #define gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++) inline int gi (){ for(c=gc();c<'0'||c>'9';c=gc()); for(x=0;c<='9'&&c>='0';c=gc()) x=(x<<1)+(x<<3)+(c&15); return x; } } using io::gi; const int N=2e5+5; struct node { int a,b,id; } s[N]; bool cmpa(node x, node y) { return x.a>y.a; } bool cmpb(node x, node y) { return x.b>y.b; } bool cmpid(node x, node y) { return x.id<y.id; } bool visa[N],visb[N]; typedef pair<int,int> pr; struct heap { priority_queue<pr> q; bool b[N]; void push(int x, int y) { q.push(make_pair(x,y)); } void del(int x) { b[x]=true; } pr top() { while(!q.empty()&&b[q.top().second]) q.pop(); if(q.empty()) return make_pair(-1e9,0); return q.top(); } void pop() { while(!q.empty()&&b[q.top().second]) q.pop(); q.pop(); } void clear() { while(!q.empty()) q.pop(); memset(b,false,sizeof(b)); } } q1,q2,q3,p1,p2; int main() { int T=gi(); while(T--) { q1.clear(),q2.clear(),q3.clear(),p1.clear(),p2.clear(); memset(visa,false,sizeof(visa)); memset(visb,false,sizeof(visb)); int n=gi(),k=gi(),l=gi(),cnt=0; for(int i=1;i<=n;++i) s[i].a=gi(),s[i].id=i; for(int i=1;i<=n;++i) s[i].b=gi(); sort(s+1,s+1+n,cmpa); long long ans=0; for(int i=1;i<=k-l;++i) ans+=s[i].a,visa[s[i].id]=true; sort(s+1,s+1+n,cmpb); for(int i=1;i<=k-l;++i) ans+=s[i].b,visb[s[i].id]=true; sort(s+1,s+1+n,cmpid); for(int i=1;i<=n;++i) { if(!visa[i]&&!visb[i]) { q1.push(s[i].a+s[i].b,i); p1.push(s[i].a,i),p2.push(s[i].b,i); } else if(!visa[i]) q2.push(s[i].a,i),p1.push(s[i].a,i); else if(!visb[i]) q3.push(s[i].b,i),p2.push(s[i].b,i); else ++cnt; } while(l--) { pr a1=q1.top(),b1; pr a2=q2.top(),b2=p2.top(); pr a3=q3.top(),b3=p1.top(); if(cnt) { a1=p1.top(),b1=p2.top(); if(a1.first+b1.first>a2.first+b2.first&&a1.first+b1.first>a3.first+b3.first) { --cnt,p1.pop(),p2.pop(); ans+=a1.first+b1.first; if(!visa[a1.second]&&!visb[a1.second]) { q1.del(a1.second); q3.push(s[a1.second].b,a1.second); } else q2.del(a1.second),++cnt; visa[a1.second]=true; if(!visa[b1.second]&&!visb[b1.second]) { q1.del(b1.second); q2.push(s[b1.second].a,b1.second); } else q3.del(b1.second),++cnt; visb[b1.second]=true; continue; } } if(a1.first>a2.first+b2.first&&a1.first>a3.first+b3.first) { q1.pop(); ans+=a1.first; visa[a1.second]=visb[a1.second]=true; p1.del(a1.second),p2.del(a1.second); } else if(a2.first+b2.first>a3.first+b3.first) { q2.pop(),p2.pop(); ans+=a2.first+b2.first; visa[a2.second]=true; p1.del(a2.second); if(!visa[b2.second]&&!visb[b2.second]) { q1.del(b2.second); q2.push(s[b2.second].a,b2.second); } else q3.del(b2.second),++cnt; visb[b2.second]=true; } else { q3.pop(),p1.pop(); ans+=a3.first+b3.first; visa[a3.second]=true; p2.del(a3.second); if(!visa[b3.second]&&!visb[b3.second]) { q1.del(b3.second); q3.push(s[b3.second].b,b3.second); } else q2.del(b3.second),++cnt; visa[b3.second]=true; } } printf("%lld\n",ans); } }

# d2t1 弹跳 #

[d2t1][]

## Solution ##

考虑 Dijkstra 的算法执行过程：每次选出一个最短路最小的点，用它去松弛其所连接的点。一般我们用堆来维护当前最短路最小的点。

因为在本题中每个点连接的点是一个矩形，同时连接的所有点的边权相等，故我们需要支持矩形取 \\(\\min\\) ，整体查询最小。

我们可以用 KD-Tree 来维护，复杂度 \\(O(n(\\sqrt\{n\}+\\log n))\\) .

### Code ###

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=3e5+5,inf=1<<30; inline void chmin(int& x, int y) { x=(x<y?x:y); } inline void chmax(int& x, int y) { x=(x>y?x:y); } inline int gi() { char c=getchar(); int x=0; for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0'; return x; } bool vis[N]; struct node { int d[2],mx[2],mn[2],l,r; int w,tg,id,mnw,mnid; bool del,alldone; void up(node x) { chmin(mn[0],x.mn[0]); chmax(mx[0],x.mx[0]); chmin(mn[1],x.mn[1]); chmax(mx[1],x.mx[1]); } } st[N]; int now,dis[N],tot,n,m,w,h,rt,nw,x[N],y[N]; int p[N],t[N],l[N],r[N],d[N],U[N]; bool cmp(node x, node y) { return x.d[now]<y.d[now]; } void pushup(node& x) { if(st[x.l].alldone&&st[x.r].alldone&&x.del) { x.alldone=true; return ; } if(x.del) x.w=x.mnw=x.mnid=inf+1; else x.mnw=min(x.w,x.tg),x.mnid=x.id; if(!st[x.l].alldone&&st[x.l].mnw<x.mnw) x.mnw=st[x.l].mnw,x.mnid=st[x.l].mnid; if(!st[x.r].alldone&&st[x.r].mnw<x.mnw) x.mnw=st[x.r].mnw,x.mnid=st[x.r].mnid; x.mnw=min(x.mnw,x.tg); } void pushdown(node x) { chmin(st[x.l].tg,x.tg); chmin(st[x.r].tg,x.tg); } int build(int l, int r, bool d) { int mid=l+r>>1; now=d; nth_element(st+l+1,st+mid+1,st+r+1,cmp); st[mid].mx[0]=st[mid].mn[0]=st[mid].d[0]; st[mid].mx[1]=st[mid].mn[1]=st[mid].d[1]; st[mid].w=st[mid].mnw=st[mid].tg=inf; if(l!=mid) st[mid].l=build(l,mid-1,d^1),st[mid].up(st[st[mid].l]); if(r!=mid) st[mid].r=build(mid+1,r,d^1),st[mid].up(st[st[mid].r]); pushup(st[mid]); return mid; } void del(int u, int x, int y) { if(st[u].alldone||x<st[u].mn[0]||x>st[u].mx[0]||y<st[u].mn[1]||y>st[u].mx[1]) return ; pushdown(st[u]); if(st[u].d[0]==x&&st[u].d[1]==y) { st[u].del=true; pushup(st[u]); return ; } if(!st[st[u].l].alldone) del(st[u].l,x,y); if(!st[st[u].r].alldone) del(st[u].r,x,y); pushup(st[u]); } void cover(int u, int xl, int xr, int yl, int yr, int w) { if(st[u].alldone||xr<st[u].mn[0]||xl>st[u].mx[0]||yr<st[u].mn[1]||yl>st[u].mx[1]) return ; if(st[u].tg<=w) return ; if(xl<=st[u].mn[0]&&st[u].mx[0]<=xr&&yl<=st[u].mn[1]&&st[u].mx[1]<=yr) { chmin(st[u].tg,w); pushup(st[u]); return ; } pushdown(st[u]); if(xl<=st[u].d[0]&&st[u].d[0]<=xr&&yl<=st[u].d[1]&&st[u].d[1]<=yr) chmin(st[u].w,w); if(!st[st[u].l].alldone) cover(st[u].l,xl,xr,yl,yr,w); if(!st[st[u].r].alldone) cover(st[u].r,xl,xr,yl,yr,w); pushup(st[u]); } vector<int> v[N]; int main() { n=gi(),m=gi(),w=gi(),h=gi(); for(int i=1;i<=n;++i) x[i]=st[i].d[0]=gi(),y[i]=st[i].d[1]=gi(),st[i].id=i; st[0].alldone=true; rt=build(1,n,0); for(int i=1;i<=m;++i) { p[i]=gi(),t[i]=gi(),l[i]=gi(),r[i]=gi(),d[i]=gi(),U[i]=gi(); v[p[i]].push_back(i); } dis[1]=0,cover(rt,x[1],x[1],y[1],y[1],0); while(!st[rt].alldone) { int u=st[rt].mnid; if(vis[u]) continue; vis[u]=true; dis[u]=st[rt].mnw; del(rt,x[u],y[u]); for(int i=0;i<v[u].size();++i) cover(rt,l[v[u][i]],r[v[u][i]],d[v[u][i]],U[v[u][i]],dis[u]+t[v[u][i]]); } for(int i=2;i<=n;++i) printf("%d\n",dis[i]); }

# d2t2 斗主地 #

[d2t2][]

## Solution ##

通过观da察biao可以发现， \\(f(i)\\) 是一个二次函数，所以我们只需要求出 \\(f(1),f(2),f(3)\\) 就可以插出所有的 \\(f(i)\\) 。

和暴力一样，我们还是设 \\(F(x,y)\\) 表示两个牌堆分别剩 \\(x,y\\) 张的概率。其中 \\(x,y\\le 3\\) 。推一下可以求出  
\\\[ F(x,y)=\\displaystyle\\frac\{(\\prod\_\{i=x+1\}^\{a\}i)(\\prod\_\{i=y+1\}^\{n-a\}i)\}\{\\prod\_\{i=x+y+1\}^\{n\}i\}\\binom\{n-x-y\}\{a-x\} \\\]

### Code ###

#include<cstdio> inline int gi() { char c=getchar(); int x=0; for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0'; return x; } const int N=1e7+5,Mod=998244353,iMod=Mod+1>>1; int f[N],fac[N],inv[N],i3[N],g[N],tf[5],n,m,t,a; inline int po(int x, int y) { int r=1; while(y) { if(y&1) r=1ll*r*x%Mod; x=1ll*x*x%Mod, y>>=1; } return r; } inline int getw(int x) { if(x<1||x>n) return -1; if(x<=3) return f[x]; int A=((f[1]-2ll*f[2]%Mod+f[3])%Mod+Mod)%Mod; int B=((-5ll*f[1]%Mod+8ll*f[2]%Mod-3ll*f[3]%Mod)%Mod+Mod)%Mod; int C=((3ll*f[1]%Mod-3ll*f[2]%Mod+f[3])%Mod+Mod)%Mod; A=1ll*A*iMod%Mod,B=1ll*B*iMod%Mod; return (1ll*A*x%Mod*x%Mod+1ll*B*x%Mod+C)%Mod; } inline int C(int x, int y) { return 1ll*fac[x]*inv[y]%Mod*inv[x-y]%Mod; } inline int getp(int x, int y) { int w=1ll*fac[a]*inv[x]%Mod*fac[n-a]%Mod*inv[y]%Mod*fac[x+y]%Mod*inv[n]%Mod; return 1ll*w*C(n-x-y,a-x)%Mod; } int main() { n=gi(),m=gi(),t=gi(); for(int i=1;i<=3;++i) f[i]=(t==1?i:i*i); fac[0]=inv[0]=1; for(int i=1;i<=n;++i) fac[i]=1ll*i*fac[i-1]%Mod; inv[n]=po(fac[n],Mod-2); for(int i=n-1;i;--i) inv[i]=1ll*(i+1)*inv[i+1]%Mod; for(int i=1;i<=3;++i) i3[i]=po(i,Mod-2); while(m--) { a=gi(); int tmp=0; for(int i=1;i<=3;++i) { g[i]=getw(a+i),tf[i]=0; if(g[i]!=-1) ++tmp; } for(int i=0;i<=3&&i<=a;++i) for(int j=0;i+j<=3&&j<=tmp;++j) { if(!i&&!j) continue; int p=getp(i,j); tf[i+j]=(tf[i+j]+1ll*i*i3[i+j]%Mod*f[i]%Mod*p%Mod)%Mod; tf[i+j]=(tf[i+j]+1ll*j*i3[i+j]%Mod*g[j]%Mod*p%Mod)%Mod; } for(int i=1;i<=3;++i) f[i]=tf[i]; } for(int i=4;i<=n;++i) f[i]=getw(i); int q=gi(); while(q--) printf("%d\n",f[gi()]); }

# d2t3 I 君的探险 #

[d2t3][]

## Solution ##

据官方题解的一套理论，我们每次随机化一个排列 \\(p\\) ，找到每个点在排列前所连着的点，如果连着的点的个数是奇数则至少可以找到一条。

根据官方题解的结论，至少有 \\(N/3\\) 的点向前面连了奇数条边。

可以使用整体二分找到每个点前面连的点。具体而言，修改左边的所有点，将原本在左边的点和右边颜色变了的点放到左边，其余的点放到右边。

根据官方题解的复杂度分析，由于两边操作量不均等，我们每次需要取三等分点分治。

注意实现的细节，保存询问的信息，保证不进行多余的询问操作。

（算了还是直接去看官方题解吧）

### Code ###

#include "explore.h" #include <bits/stdc++.h> using namespace std; const int N=3e5+5; int n,m,now,p[N]; vector<int> v; bool tmp[N],del[N]; bool mp[N],l[N]; int head[N],nxt[N<<1],to[N<<1],tot; namespace task1 { void solve() { for(int i=0;i<n-1;++i) { if(check(i)) continue; modify(i); l[i]^=1; for(int j=i+1;j<n;++j) { int x=query(j); if(l[j]!=x) l[j]=x,report(i,j); } } } } void addedge(int u, int v) { nxt[++tot]=head[u], head[u]=tot, to[tot]=v; } void solve(int l, int r, vector<int> v, bool d) { if(l==r) { for(int i=0;i<v.size();++i) if(p[v[i]]!=p[l]) { ++now; report(p[v[i]],p[l]); addedge(p[v[i]],p[l]),addedge(p[l],p[v[i]]); } if(!d) modify(p[l]); return ; } // int mid=l+r>>1; int mid=l+(r-l+1)/3; for(int i=l;i<=mid;++i) mp[p[i]]=true; if(d) for(int i=l;i<=mid;++i) modify(p[i]); else for(int i=mid+1;i<=r;++i) modify(p[i]); vector<int> v1,v2; for(int i=0;i<v.size();++i) { int x=query(p[v[i]]); for(int e=head[p[v[i]]];e;e=nxt[e]) x^=mp[to[e]]; if(v[i]<=mid||x) v1.push_back(v[i]); else v2.push_back(v[i]); } for(int i=l;i<=mid;++i) mp[p[i]]=false; solve(l,mid,v1,0),solve(mid+1,r,v2,1); } void explore(int N, int M) { n=N,m=M; if(n<=500) { task1::solve(); return ; } for(int i=0;i<n;++i) p[i]=i; while(true) { int nm=n; n=0; for(int i=0;i<nm;++i) if(!del[p[i]]) p[n++]=p[i]; if(N%10!=7) random_shuffle(p,p+n); v.clear(); for(int i=0;i<n;++i) v.push_back(i); solve(0,n-1,v,1); if(now==m) break; for(int i=0;i<n;++i) if(check(p[i])) del[p[i]]=true; } }

转载于:https://www.cnblogs.com/farway17/p/11259020.html

[d1t1]: https://loj.ac/problem/3156
[d1t3]: https://loj.ac/problem/3158
[d2t1]: https://loj.ac/problem/3159
[d2t2]: https://loj.ac/problem/3160
[d2t3]: https://loj.ac/problem/3161