[jzoj 4722] [NOIP2016提高A组模拟8.21] 跳楼机 解题报告 (spfa+同余)
2024-10-01 14:07:40
题目链接:
http://172.16.0.132/senior/#main/show/4722
题目:
DJL为了避免成为一只咸鱼,来找srwudi学习压代码的技巧。
Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多,srwudi改造了一个跳楼机,使得访客可以更方便的上楼。
经过改造,srwudi的跳楼机可以采用以下四种方式移动:
1、向上移动x层;
2、向上移动y层;
3、向上移动z层;
4、回到第一层。
一个月黑风高的大中午,DJL来到了srwudi的家,现在他在srwudi家的第一层,碰巧跳楼机也在第一层。DJL想知道,他可以乘坐跳楼机前往的楼层数。
题解:
一开始$h--$,把第1层给减掉方便处理
40分的做法是直接bfs统计方案数,但是这样状态数太多太大了,考虑简化方案数
定义$d_i=c$,$c$表示最小的只由操作2,3得到的且满足$c \mod x = i$的数
那么答案$ans=\sum_{i=0}^{x-1} (\lfloor \frac{h-d_i}{x} \rfloor+1)$
为什么呢?我们考虑将合法的楼层按模x分类,显然余数是由操作2,3得到的。那么我们考虑得到了最小的楼层,比它大的所有的在这个剩余系里的楼层都可以得到,而比它小的绝对得不到
按模x分类做到了不重,取完后面所有的数做到了不漏
考虑$d_i$怎么计算,显然有
$$d_{k+y}=d_k+y$$
$$d_{k+z}=d_k+z$$
这是一个最短路模型,跑一次spfa就好了
时间复杂度怎么算呢?我也没太弄懂
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll; const int N=1e5+;
const ll inf=1e18;
ll h,x,y,z;
int vis[N];
ll d[N];
void spfa()
{
queue <int> q;
for (ll i=;i<x;i++) d[i]=inf;
d[]=;q.push();vis[]=;
while (!q.empty())
{
ll k=q.front();q.pop();vis[k]=;
if (d[(k+y)%x]>d[k]+y)
{
d[(k+y)%x]=d[k]+y;
if (!vis[(k+y)%x]) q.push((k+y)%x),vis[(k+y)%x]=;
}
if (d[(k+z)%x]>d[k]+z)
{
d[(k+z)%x]=d[k]+z;
if (!vis[(k+z)%x]) q.push((k+z)%x),vis[(k+z)%x]=;
}
}
}
int main()
{
scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
--h;
spfa();
ll ans=;
for (ll i=;i<x;i++) if (h>d[i]) ans+=(h-d[i])/x+;
printf("%lld\n",ans);
return ;
}
最新文章
- CSS3 box-sizing
- C#基础系列——多线程的常见用法详解
- Mac OS X双系统变回虚拟机
- java 23 - 2 设计模式之单例模式
- treeiso
- Codeforces 653D Delivery Bears(最大流)
- MVC简单实例
- 分享我用Qt开发的应用程序【一】,附绿色版下载,以后会慢慢公布源码
- Java 操作Excel 之Poi(第一讲)
- Mayan游戏 (codevs 1136)题解
- V8::Arguments中This和Holder的区别
- new Image()的用途
- 【CF39E】【博弈论】What Has Dirichlet Got to Do with That?
- 自定义控件学习之菜鸟笔记一(Hello World)
- iwebshop中的增删改查
- javaEmail发邮件是问号乱码,已解决
- vsftpd 安装与配置
- 微信小程序 TOP100 榜单
- vue js校验金钱、数字
- Xamarin.Android 调用手机拍照功能