题解 P3403 【跳楼机】
currycodingg · · 题解
【最短路相关】
夜深人静 但心里有些烦躁 写点东西记录一下自己刚做的两道题的感悟
两道题：
跳楼机https://www.luogu.org/problemnew/show/P3403
墨墨的等式https://www.luogu.org/problemnew/show/P2371
这两道题看似与最短路无关，第一道题让人摸不到头脑，第二道题一看题面倒像是一道数学题，结果却可以利用最短路求解，真是奇妙啊。
T1：
从一楼开始，可以上升x, y, z层，楼高H，求能够到达的楼层数量。
第一次写了个深搜，得了40分：
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll h, ans;
int x, y, z;
bool vis[50000000 + 3];
void dfs(int n){
if(n + x > h && n + y > h && n + z > h) return ;
if(n + x <= h && !vis[n + x]){
vis[n + x] = true;
ans++;
dfs(n + x);
}
if(n + y <= h && !vis[n + y]){
vis[n + y] = true;
ans++;
dfs(n + y);
}
if(n + z <= h && !vis[n + z]){
vis[n + z] = true;
ans++;
dfs(n + z);
}
}
int main(){
scanf("%lld%d%d%d", &h, &x, &y, &z);
ans = 1;
dfs(1);
printf("%lld\n", ans);
return 0;
}然后看yyb大爷的题解:
“先只考虑只用y,z两种移动方式，它们一定能够到达一些楼层， 那么这些楼层再只用x拓展就能够计算答案。
那么我们这样子计算答案，设dis[i]表示可以到达mod x=i的楼层的最小值，显然这个玩意可以最短路求，那么直接建图跑SPFA（死不掉的），然后统计一下答案。”
其实一开始并不怎么懂......
(自以为的主要思想)
任选两种方式 (似乎是哪两个都行...这里是选的x和y)，作为边权去拓展楼层，拓展到一个楼层只需要记录此楼层 mod x 的(最小?)值就行，因为只要存在一个数i(i < x)，那么 i + kx <= H 的楼层都可以到达，这个东西就可以建图然后跑最短路求了，那么统计答案的时候就应当这样
for(int i = 0; i < x; i++){
//最后+1是加上此楼层！
if(dis[i] <= H) ans += (H - dis[i]) / x + 1;
}std
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;
const int INF = 0x3f3f3f3f;
ll H, x, y, z, dis[N], ans;
bool inq[N];
struct edge{
int to, w, nxt;
}e[N << 1];
int tot, hd[N];
void addedge(int from, int to, int w){
e[++tot] = (edge){to, w, hd[from]}; hd[from] = tot;
}
queue<int> Q;
void SPFA(){
memset(dis, INF, sizeof(dis));
//一楼能到的mod x最小楼层数就是1了...
dis[1 % x] = 1; Q.push(1 % x); inq[1 % x] = true;
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(dis[v] > dis[u] + e[i].w){
dis[v] = dis[u] + e[i].w;
if(!inq[v]) Q.push(v), inq[v] = true;
}
}
}
}
int main(){
scanf("%lld%lld%lld%lld", &H, &x, &y, &z);
for(int i = 0; i < x; i++){ //关键在此
addedge(i, (i + y) % x, y);
addedge(i, (i + z) % x, z);
}
SPFA();
for(int i = 0; i < x; i++){ //关键在此: i : 0 -> (x - 1)
if(dis[i] <= H) ans += (H - dis[i]) / x + 1;
}
printf("%lld\n", ans);
return 0;
}讲了这么一遍自己应该会了吧......
T2：
给定方程 a1 x1 + a2 x2 + ... + an * xn = B , 给定N, {an}, 以及B的取值范围，问这其中有多少个B使得方程存在非负整数解
yyb:“和跳楼机那题是一样的。 只不过走的方式从3种变成了n种而已，其他的根本没有区别了。”
我：懵逼
看一看这两道题的共同点：都是统计个数
我们可以在{an}中选择一个最小的ai，记为mn，然后用其他的系数去拓展这些符合条件的B的个数，像上一题一样，用dis[i]表示 mod mn = i 的(最小?)值，然后将各个系数ai作为边权去拓展符合条件的B的个数，最后统计个数也是差不多的，只是题目给定了一个区间，所以：
ans = enquiry(R) - enquiry(L - 1);
ll enquiry(ll m){
ll res = 0;
for(int i = 0; i < mn; i++)
if(dis[i] <= m) res += (m - dis[i]) / mn + 1;
return res;
}std
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 12 + 3;
const int MAXA = 5e5 + 500;
const int INF = 0x3f3f3f3f;
int read(){
int k = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') { if(c == '-')k = -1; c = getchar(); }
while(c >= '0' && c<= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * k;
}
int n, a[N], tot, mn;
ll L, R, dis[MAXA];
bool inq[MAXA];
queue<int> Q;
void SPFA(){
memset(dis, INF, sizeof(dis));
memset(inq, false, sizeof(inq));
Q.push(0); inq[0] = true; dis[0] = 0;//得到0的代价是0
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = 1; i <= n; i++) if(a[i] != mn){
int v = (u + a[i]) % mn;
if(dis[v] > dis[u] + a[i]){
dis[v] = dis[u] + a[i];
if(!inq[v]) Q.push(v), inq[v] = true;
}
}
}
}
ll enquiry(ll m){
ll ans = 0;
for(int i = 0; i < mn; i++)
if(dis[i] <= m) ans += (m - dis[i]) / mn + 1;
return ans;
}
int main(){
scanf("%d%lld%lld", &n, &L, &R);
mn = INF;
for(int i = 1; i <= n; i++){
if((a[i] = read())) a[++tot] = a[i];
mn = min(mn, a[i]);
}
n = tot;
SPFA();
printf("%lld\n", enquiry(R) - enquiry(L - 1));
return 0;
}