当前位置: 首页 > news >正文

题解:P2662 牛场围栏

省流:同余最短路

本题是一道同余最短路算法的好题。接下来讲讲个人对这道题的理解。

首先,根据题意,我们知道,我们可以获得最多 \(m \times (m +1)\) 种木棍长度。我们设 \(t\) 为这个最大值,则木棍长度可表示为 \(a_1,a_2,…,a_t\)。设栅栏长度为 \(l\) ,若一个栅栏的长度是可表示的,则等同于 \(\exist k_1,k_2,…,k_t\in\Z^+,k_1a_1+k_2a_2+…+k_ta_t=l\)

根据数据范围可以看到,\(t\) 最大可以达到 \(9000000\),因此直接爆搜肯定不现实。但我们发现,单个木棍的长度最长只有 \(100\),我们又发现,当其中 \(t-1\) 个系数确定后,所有可表示的栅栏长度对剩下那个未被确定的系数对应的木棍长度取余的结果相同。因此,我们就可以使用同余的思想,选取长度最小的木棍来作为系数不确定的木棍,设其长度为 \(a_1\),同时设 \(d_i(i\in[0,a_1-1])\) 来表示当 \(l \bmod a_1=i\) 时,\(l\) 的最小值。此时,我们只需要建立从 $i(i\in[0,a_1-1]) $ 到 \((a_j+i)\bmod a_1(j\in[1,t])\),长度为 \(a_j\) 的有向边,并跑一遍 Dijkstra 求最短路即可。

在求出最短路后,若 \(d_i(i\in[0,a_1-1])\) 未被更新,就说明不存在最大值,输出 \(-1\)。否则,求出 \(ans=max\set{d_i-a_1(i\in[0,a_1-1])}\),输出即可。

上代码

#include<bits/stdc++.h>
using namespace std;#define int long longconst int N=3005;
const int M=6000005;int n,m;
int ans=-1,tot,maxn,minn=0x7ffffff;
int l[N],h[N];
int edge[M],ver[M],head[M],Next[M];
int d[M],vis[M];struct node{int id,step;bool operator <(const node b)const{return step>b.step;}
};priority_queue<node>q;inline int read(){int f=1,k=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}return f*k;
}void add(int x,int y,int z){edge[++tot]=z; ver[tot]=y; Next[tot]=head[x]; head[x]=tot;
}void dij(){d[0]=0;q.push(node{0,0});while(!q.empty()){int x=q.top().id; q.pop();if(vis[x]) continue;		vis[x]=true;for(int i=head[x];i;i=Next[i]){int y=ver[i];int z=edge[i];if(d[y]>d[x]+z){d[y]=d[x]+z;q.push(node{y,d[y]});}}}
}signed main(){n=read(),m=read();for(int i=1;i<=n;i++) l[i]=read();for(int i=1;i<=n;i++){for(int j=l[i]-m;j<=l[i];j++) h[j]=1;maxn=max(l[i],maxn);minn=min(l[i]-m,minn); //求出木棍长度、最小值和最大值}for(int i=0;i<minn;i++){for(int j=minn;j<=maxn;j++)if(h[j]==1) add(i,(i+j)%minn,j); //加边d[i]=(1ull<<63)-1;}dij();for(int i=0;i<minn;i++){if(d[i]==(1ull<<63)-1){cout<<-1<<endl;return 0;}ans=max(ans,d[i]-minn);}cout<<ans<<endl;return 0;
}
```1. 
http://www.hskmm.com/?act=detail&tid=17465

相关文章:

  • day11 课程(学员管理系统案例)
  • c语言初步学习
  • jmeter函数
  • 【网络编程】UDP 编程实战:从套接字到聊天室多场景计划构建
  • AC自动机在线版本(alert命中报警)
  • week1 homework
  • Windows 10 C盘占用释放 - tfel
  • 运算符
  • 科学计算方法--矩阵分析记录
  • window.addEventListener(message,()={})中的回调函数无故被一直触发的问题 - broky
  • python+pillow+Image实现图片压缩到指定大小
  • 页面卡顿问题分析与解决方案总结复盘
  • Say 题选记(9.21 - 9.27)
  • 9月25日
  • 3D 高斯训练速度和消耗 - MKT
  • 完整教程:【PyTorch实战:文本分类】23、BERT文本分类实战指南:从原理到PyTorch落地
  • 常见进制
  • 9.25总结
  • Day08-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\David\array-ArrayDemo01~07
  • yolov10_float16.tflite TO yolov10_int8.tflite
  • ansible注意的和错误代码分析
  • 用 Rust 和 Tesseract OCR 识别验证码
  • 基于寄存器地址amp;标准外设库的LED流水灯
  • 用 Swift 和 Tesseract OCR 实现验证码识别
  • Rust 和 Tesseract OCR 实现验证码识别
  • AI-Powered-ToDo-List
  • Netty:完成RPC服务(实战)
  • Python 在 Web 开发中的应用与趋势
  • LLM MOE的进化之路
  • 相交链表-leetcode