2023.7.15

news/2024/10/31 1:29:21/

同余最短路

 

P3403 跳楼机
题意:给定h高的楼层,起始位置在第一层,可以选择操作向上移动x层或y层或z层,回到第一层
求可以到达的楼层数
思路:转化题意为求ax+by+cz=k(k在[1,h],x,y,z为正整数,有多少k满足条件,
 简而言之就是选定一个数,用其他的凑出这个数的每个同余类的最小数,就凑出同余类中比最小数大的个数
 

#include<iostream>
#include<queue>
#include<cstring>
#define int long long
const int N = 2e5 + 10;
using namespace std;
int head[N];
int cnt;
int dis[N];
bool vis[N];
struct Edge {int v, w, next;
}e[N<<1];
void insert(int u, int v, int w) {e[++cnt] = Edge{ v,w,head[u] };head[u] = cnt;
}
void spfa(int s) {memset(vis, 0, sizeof(vis));vis[s] = 1;memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] = 1;queue <int>q;q.push(s);while (!q.empty()) {s = q.front();q.pop();vis[s] = 0;for (int i = head[s]; i; i = e[i].next) {int v = e[i].v;int w = e[i].w;if (dis[v] > dis[s] + w) {dis[v] = dis[s] + w;if (!vis[v]) {q.push(v);vis[v] = 1;}}}}
}
void solve(){int h,x,y,z;cin >> h;cin >> x >> y >> z;for (int i = 0; i < z; i++) {       insert(i, (i + x) % z, x);insert(i, (i + y) % z, y);}spfa(1);int ans = 0;for (int i = 0; i < z; i++) {if(h>=dis[i])ans += (h - dis[i]) / z + 1;}cout << ans << '\n';
}
signed main()
{int t = 1;//cin >> t;while (t--) {solve();}return 0;
}

arc084_b()
题意:给一个数 k ,问他的正整数倍数中,(十进制下)每一位的和最小是多少。
例子:41-》41*271=11111-》5
思路:设f(ans)=ans为各位数的和,ans=0(mod k),且f(ans)最小
 dis[i]表示模k为i的位数之和的最小值
 

#include<iostream>
#include<queue>
#include<cstring>
#define int long long
const int N = 1e5 + 10;
using namespace std;
int head[N];
int cnt;
int dis[N];
bool vis[N];
struct Edge {int v, w, next;
}e[N << 4];
void insert(int u, int v, int w) {e[++cnt] = Edge{ v,w,head[u] };head[u] = cnt;
}
void spfa(int s) {memset(vis, 0, sizeof(vis));vis[s] = 1;memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] = 0;queue <int>q;q.push(s);while (!q.empty()) {s = q.front();q.pop();vis[s] = 0;for (int i = head[s]; i; i = e[i].next) {int v = e[i].v;int w = e[i].w;if (dis[v] > dis[s] + w) {dis[v] = dis[s] + w;if (!vis[v]) {q.push(v);vis[v] = 1;}}}}
}
void solve() {int k;cin >> k;for ( int i = 0; i < k; ++i)for ( int j = 0; j < 10; ++j) {insert(i, (i * 10 + j) % k, j);}for ( int i = 1; i < 10; ++i)insert(k, i % k, i);//建虚点,第一位不能为0spfa(k);cout << dis[0] << '\n';
}
signed main()
{int t = 1;//cin >> t;while (t--) {solve();}return 0;
}


http://www.ppmy.cn/news/907143.html

相关文章

BaseDexClassLoader加载类流程源码阅读

安卓10 类图 双亲委派机制 Java层 BaseDexClassLoader 没有loadClass实现&#xff0c;继承的是 ClassLoader 实现 路径 libcore\ojluni\src\main\java\java\lang\ClassLoader.java protected Class<?> loadClass(String name, boolean resolve)throws ClassNotFound…

unity GUI按钮点击开关面板文本

gui一般格式 1画布canvas 2面板panel 3 按钮button 4文本text 2面板panel 3按钮button 4文本text 2面板panel 3文本text playmaker ugui插件 playmaker-addons-Ecosystem uGuiProxyFull

html 开关按钮 js代码,JavaScript实现开关等效果

废话不多说了&#xff0c;直接给大家贴代码了&#xff0c;具体代码如下所示&#xff1a;开关灯 html, body { margin: 0px; padding: 0px; width: 100%; height: 100%; cursor: pointer; background-color: white; } var oBody document.getElementById("bodyEle");…

手把手带你制作WIFI智能开关.走进物联网-ESP8266学习日记(三)

上一次我们初步认识了SDK编程和透传&#xff0c;给模组更新FW。 这一次我们直接用一个开源平台实现我们最终的目的&#xff0c;用一个APP远程控制模组开关。 我们使用的平台是机智云提供的开发平台。 开始之前我们先把硬件搭建起来&#xff0c;大概规划一下成品的样子 电路规划…

新发现Homekit智能触摸面板开关

一款Homekit直连的智能触摸面板开关&#xff0c;支持Homekit直连和绑定智能音箱使用&#xff0c;有美规和欧规款式&#xff0c;欧规可搭配86盒使用&#xff0c;可根据需要选择1/2/3键&#xff0c;绑定设备后轻松控制家里的电器设备&#xff0c;智能开关&#xff0c;当前外观上主…

开关电源PCB布局与EMC关系

一. 开关电源PCB设计之准备事项 1、外观结构尺寸&#xff0c;包括定位孔&#xff0c;风道流向&#xff0c;输入输出插座&#xff0c;需要与客户系统匹配&#xff0c;还需要与客户沟通装配上的问题&#xff0c;限高等。 2、安规认证&#xff0c;产品做哪种认证&#xff0c;哪些…

Bootstrap组件——折叠面板

折叠面板 一、折叠面板1.基础2.多个目标3.手风琴4.方法与事件 一、折叠面板 Bootstrap折叠板插件允许你在网页中用一点点JavaScript以及CSS类切换内容&#xff0c;控制内容的可见性。它是一个灵活的插件&#xff0c;使用少量的类&#xff08;来自必需的过渡插件&#xff09;&a…