同余最短路

 

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;
}