多校A层冲刺NOIP2024模拟赛21
\(T1\) A. 送信卒 \(90pts/100pts\)
-
部分分
-
\(90pts\)
-
设最后的可能的最短路中左右共移动了 \(d\) 次，上下共移动了 \(x\) 次。
-
则等价于求 \(\min \{ x_{i}k+d_{i} \}=s\) 的解，观察到 \(d \in [0,\min(\left\lceil \frac{nm}{2} \right\rceil,s)]\) 。
-
将左右移动次数也扔进 \(Dijkstra\) 中转移即可，然后暴力进行 \(check\) ，时间复杂度为 \(O(n^{4}\log n)\) 。
-
因为需要 \(O(n^{4})\) 的辅助空间，所以需要开
short。点击查看代码
const double eps=1e-8; struct node { int nxt,to,x,d; }e[40010]; int head[10010],cnt=0,n,m,limit; short dis[10010][5010]; bitset<5010>vis[10010]; char c[110][110]; struct quality { short dis; int x,d; bool operator < (const quality &another) const { return dis>another.dis; } }; void add(int u,int v,int x,int d) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].x=x; e[cnt].d=d; head[u]=cnt; } int work(int x,int y) { return (x-1)*m+y; } void dijkstra(int s) { memset(dis,0x3f,sizeof(dis)); priority_queue<quality>q; dis[s][0]=0; q.push((quality){dis[s][0],s,0}); while(q.empty()==0) { int x=q.top().x,d=q.top().d; q.pop(); if(vis[x][d]==0) { vis[x][d]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(d+e[i].d<=limit&&dis[e[i].to][d+e[i].d]>dis[x][d]+e[i].x) { dis[e[i].to][d+e[i].d]=dis[x][d]+e[i].x; q.push((quality){dis[e[i].to][d+e[i].d],e[i].to,d+e[i].d}); } } } } } int main() { #define Issac #ifdef Issac freopen("msg.in","r",stdin); freopen("msg.out","w",stdout); #endif int sx,sy,tx,ty,t,i,j; double s,ans=0x7f7f7f7f,k,minn; scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty); t=work(tx,ty); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf(" %c",&c[i][j]); } } cin>>s; limit=min(ceil(n*m/2.0),ceil(s)-1); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(c[i][j]=='0') { if(i-1>=0&&c[i-1][j]=='0'){add(work(i,j),work(i-1,j),1,0);} if(i+1<=n&&c[i+1][j]=='0'){add(work(i,j),work(i+1,j),1,0);} if(j-1>=0&&c[i][j-1]=='0'){add(work(i,j),work(i,j-1),0,1);} if(j+1<=m&&c[i][j+1]=='0'){add(work(i,j),work(i,j+1),0,1);} } } } dijkstra(work(sx,sy)); if((int)s==s&&tx==sx&&abs(ty-sy)==(int)s) { ans=0; } else { for(i=0;i<=limit;i++) { if(dis[t][i]!=0x3f3f&&dis[t][i]!=0) { k=1.0*(s-i)/dis[t][i]; minn=0x7f7f7f7f; for(j=0;j<=limit;j++) { if(minn-(1.0*j+1.0*k*dis[t][j])>eps) { minn=1.0*j+1.0*k*dis[t][j]; } } if(fabs(minn-s)<=eps&&ans-k>eps) { ans=k; } } } } printf("%.3lf\n",ans); return 0; }
-
-
\(100pts\) ：将上述做法的 \(dijsktra\) 改成 \(01BFS\) 即可，时间复杂度为 \(O(n^{4})\) 。
点击查看代码
const double eps=1e-8; struct node { int nxt,to,x,d; }e[40010]; int head[10010],cnt=0,n,m,limit; short dis[10010][5010]; bitset<5010>vis[10010]; char c[110][110]; void add(int u,int v,int x,int d) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].x=x; e[cnt].d=d; head[u]=cnt; } int work(int x,int y) { return (x-1)*m+y; } void bfs(int s) { memset(dis,0x3f,sizeof(dis)); deque<pair<int,int> >q; dis[s][0]=0; q.push_back(make_pair(s,0)); while(q.empty()==0) { int x=q.front().first,d=q.front().second; q.pop_front(); if(vis[x][d]==0) { vis[x][d]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(d+e[i].d<=limit&&dis[e[i].to][d+e[i].d]>dis[x][d]+e[i].x) { dis[e[i].to][d+e[i].d]=dis[x][d]+e[i].x; if(e[i].x==1) { q.push_back(make_pair(e[i].to,d+e[i].d)); } else { q.push_front(make_pair(e[i].to,d+e[i].d)); } } } } } } int main() { #define Issac #ifdef Issac freopen("msg.in","r",stdin); freopen("msg.out","w",stdout); #endif int sx,sy,tx,ty,t,i,j; double s,ans=0x7f7f7f7f,k,minn; scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty); t=work(tx,ty); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf(" %c",&c[i][j]); } } cin>>s; limit=min(ceil(n*m/2.0),ceil(s)-1); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(c[i][j]=='0') { if(i-1>=0&&c[i-1][j]=='0'){add(work(i,j),work(i-1,j),1,0);} if(i+1<=n&&c[i+1][j]=='0'){add(work(i,j),work(i+1,j),1,0);} if(j-1>=0&&c[i][j-1]=='0'){add(work(i,j),work(i,j-1),0,1);} if(j+1<=m&&c[i][j+1]=='0'){add(work(i,j),work(i,j+1),0,1);} } } } bfs(work(sx,sy)); if((int)s==s&&tx==sx&&abs(ty-sy)==(int)s) { ans=0; } else { for(i=0;i<=limit;i++) { if(dis[t][i]!=0x3f3f&&dis[t][i]!=0) { k=1.0*(s-i)/dis[t][i]; minn=0x7f7f7f7f; for(j=0;j<=limit;j++) { if(minn-(1.0*j+1.0*k*dis[t][j])>eps) { minn=1.0*j+1.0*k*dis[t][j]; } } if(fabs(minn-s)<=eps&&ans-k>eps) { ans=k; } } } } printf("%.3lf\n",ans); return 0; }
-
-
正解
- 观察到 \(\min \{ x_{i}k+d_{i} \}\) 具有单调性，即随着 \(k\) 的增大最短路长度不降。
- 二分答案即可。
点击查看代码
const double eps=1e-8; double dis[110][110]; bool vis[110][110]; char c[110][110]; void dijkstra(int sx,int sy,double mid,int n,int m) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { vis[i][j]=0; dis[i][j]=0x3f3f3f3f; } } priority_queue<pair<int,pair<int,int>>>q; dis[sx][sy]=0; q.push(make_pair(-dis[sx][sy],make_pair(sx,sy))); while(q.empty()==0) { int x=q.top().second.first,y=q.top().second.second; q.pop(); if(vis[x][y]==0) { vis[x][y]=1; if(x-1>=1&&dis[x-1][y]>dis[x][y]+mid&&c[x-1][y]=='0') { dis[x-1][y]=dis[x][y]+mid; q.push(make_pair(-dis[x-1][y],make_pair(x-1,y))); } if(x+1<=n&&dis[x+1][y]>dis[x][y]+mid&&c[x+1][y]=='0') { dis[x+1][y]=dis[x][y]+mid; q.push(make_pair(-dis[x+1][y],make_pair(x+1,y))); } if(y-1>=1&&dis[x][y-1]>dis[x][y]+1&&c[x][y-1]=='0') { dis[x][y-1]=dis[x][y]+1; q.push(make_pair(-dis[x][y-1],make_pair(x,y-1))); } if(y+1<=m&&dis[x][y+1]>dis[x][y]+1&&c[x][y+1]=='0') { dis[x][y+1]=dis[x][y]+1; q.push(make_pair(-dis[x][y+1],make_pair(x,y+1))); } } } } int main() { #define Issac #ifdef Issac freopen("msg.in","r",stdin); freopen("msg.out","w",stdout); #endif int n,m,sx,sy,tx,ty,i,j; double s,l=0,r,mid,ans=-1; cin>>n>>m>>sx>>sy>>tx>>ty; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>c[i][j]; } } cin>>s; r=s; while(r-l>=eps) { mid=(l+r)/2; dijkstra(sx,sy,mid,n,m); if(dis[tx][ty]>=s) { ans=mid; r=mid; } else { l=mid; } } printf("%.3lf\n",ans); return 0; }
\(T2\) B. 共轭树图 \(0pts/0pts\)
-
不妨钦定 \(u>v\) ，那么在断开 \((u,v)\) 这条边后等价于将 \(u\) 的深度最浅的祖先和 \(v\) 连接。故最终得到的 \(G\) 也一定是棵树，且当以 \(n\) 为根时也满足父亲节点的编号一定大于自身的编号。
-
考虑这样的 \(G\) 是怎么构造出来的。当把 \(G\) 的边在原图上画出后，任意两条边之间只能不交和包含，因为如果相交的话下边的那条边的端点就可以连到上面的边上去。
-
定义根节点的深度为 \(1\) 。
-
设 \(f_{x,i}\) 表示 \(x\) 在 \(G\) 中只被允许与原图中它的 \(i \in [1,dep_{x}-1]\) 个祖先连边时（即 \(G\) 中的父亲节点）以 \(x\) 为根的子树中的方案数，状态转移方程为 \(f_{x,i}=\sum\limits_{j=2}^{i+1}\prod\limits_{y \in Son(x)}f_{y,j}\) ，边界为 \(f_{x,i}=i(i \in [1,dep_{x}-1] \land du_{x}=1)\) 。
-
此时时间复杂度为 \(O(n^{3})\) ，考虑进一步优化。
-
手摸展开后的式子，容易有 \(f_{x,i}=f_{x,i-1}+\prod\limits_{y \in Son(x)}f_{y,i+1}\) 。此时时间复杂度就优化成了 \(O(n^{2})\) 。
-
最终，有 \(\prod\limits_{x \in Son(n)}f_{x,1}\) 即为所求。
点击查看代码
const ll p=998244353; int dep[3010],f[3010][3010]; vector<int>e[3010]; void add(int u,int v) { e[u].push_back(v); } void dfs(int x,int fa) { dep[x]=dep[fa]+1; for(int i=0;i<e[x].size();i++) { dfs(e[x][i],x); } for(int k=1;k<=dep[x]-1;k++) { f[x][k]=1; for(int i=0;i<e[x].size();i++) { f[x][k]=1ll*f[x][k]*f[e[x][i]][k+1]%p; } f[x][k]=(f[x][k]+f[x][k-1])%p; } } int main() { #define Issac #ifdef Issac freopen("reflection.in","r",stdin); freopen("reflection.out","w",stdout); #endif int n,u,v,ans=1,i; cin>>n; for(i=1;i<=n-1;i++) { cin>>u>>v; if(u<v) { swap(u,v); } add(u,v); } dfs(n,0); for(i=0;i<e[n].size();i++) { ans=1ll*ans*f[e[n][i]][1]%p; } cout<<ans<<endl; return 0; }
\(T3\) C. 摸鱼军训 \(0pts/0pts\)
- 部分分
- \(20 \%\) ： \(O(n^{2})\) 预处理 \(O(1)\) 查询。
\(T4\) D. 神奇园艺师 \(0pts/0pts\)
- 部分分
- 子任务 \(1\) ：爆搜子集后就是货仓选址问题了，暴力分解质因数即可。
总结
- \(T1\) 赛时觉得因为 \(k\) 的变化会导致最短路路径的变化然后就不能确定最短路长度了，没搞清其内部的单调性。
- \(T2\) 始终没读懂题意。
- \(T3\) 忘了可以 \(O(n^{2})\) 预处理，最低档部分分只写了单组询问 \(O(n^{2})\) 的做法，挂了 \(20pts\) 。
- \(T4\) 质因数分解写的是预处理素数挨个分解的方法，导致无用素数极多，挂了 \(20pts\) 。