数据结构与算法：同余最短路

前言这真的是我能学会的东西吗……一、内容在完全背包问题中当总体积极大单个物品体积较小时此时就需要用同余最短路解决。这类问题一般形如给定 n 个正数每种数可以无限取求能凑出多少种数、能凑出来的最小数以及不能拼凑出的最大数等问题。在求解时因为是最短路问题所以一般可以用 dijkstra 和 01bfs 解决。除此之外还可以使用两次转圈法求解。具体方法就直接在下面题目里讲述了。二、题目1.跳楼机#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define endl \n typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { ll h; cinh; h--; int x,y,z; cinxyz; vectorvectorpllg(x); for(int i0;ix;i) { g[i].push_back({(iy)%x,y}); g[i].push_back({(iz)%x,z}); } vectorlldis(x,INFLL); vectorintvis(x); auto dijkstra[](int s)-void { auto cmp[](arrayll,2x,arrayll,2y)-bool { return x[1]y[1]; }; priority_queuearrayll,2,vectorarrayll,2,decltype(cmp)heap(cmp); heap.push({0,0}); dis[0]0; while(!heap.empty()){ auto [u,_]heap.top(); heap.pop(); if(vis[u]){ continue; } vis[u]1; for(auto [v,w]:g[u]){ if(!vis[v]dis[u]wdis[v]){ dis[v]dis[u]w; heap.push({v,dis[v]}); } } } }; dijkstra(0); ll ans0; for(int i0;ix;i) { if(dis[i]h) { ans(h-dis[i])/x1; } } coutansendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }可以发现 h 是很大的所以肯定不能以 h 为 dp 表的一维。之后首先可以发现 1~h 范围其实可以转化成 0~h-1 范围。那么假如 a4,b11,c6如果从 0 位置出发可以发现所有模 4 余 0 的组都是可以到达的。那么更进一步想因为用 b 和 c 能凑出来的模 4 余 1 的最小值是 17那么从 17 开始到 99 所有模 4 余 1 的数就都可以到达了。这个可以通过 99-17 除以 4 再加 1 在 O(1) 的时间里算出来模 4 余 2 和 3 的情况类似。那么对于其他数能凑出来的模 4 余 1 的最小数就可以使用同余最短路求解。那么若选 a 作为基准数考虑将 0~3 所有模 4 状态空间里的数作为图上的点。那么对于 b11 来说因为 011 模 4 余 3所以其从 0 节点出发可以去往 3 节点所以就建立一条从 0 到 3 边权为 11 的有向边其余点也同理。而对于 c6 来说因为 06 模 4 余 2所以其从 0 节点出发可以去往 2 节点所以就建立一条从 0 到 2 边权为 6 的边其他点也同理。在建好这样的一张图之后就可以从 0 开始跑一遍 dijkstra。此时就可以发现到 1 节点的最短路为 17所以能凑出来的模 4 余 1 的最小数就是 17。复杂度方面由于需要根据基准数确定点的数量所以肯定是选最小数 v 作为基准数。那么因为 n-1 个数每个数都要连 v 条边所以时间复杂度就是 O(v*n*log(v*n))。2.牛场围栏#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define endl \n typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n,m; cinnm; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorintsorted(1); for(int i1;in;i) { for(int j0;jmja[i];j) { sorted.push_back(a[i]-j); } } sort(sorted.begin()1,sorted.end()); int len1; for(int i2;isorted.size();i) { if(sorted[i]!sorted[len]) { sorted[len]sorted[i]; } } int xsorted[1]; if(x1) { cout-1endl; return ; } vectorvectorpllg(x); for(int i0;ix;i) { for(int j2;jlen;j) { g[i].push_back({(isorted[j])%x,sorted[j]}); } } vectorlldis(x,INFLL); vectorintvis(x); auto dijkstra[](int s)-void { auto cmp[](arrayll,2x,arrayll,2y)-bool { return x[1]y[1]; }; priority_queuearrayll,2,vectorarrayll,2,decltype(cmp)heap(cmp); heap.push({s,0}); dis[s]0; while(!heap.empty()){ auto [u,_]heap.top(); heap.pop(); if(vis[u]){ continue; } vis[u]1; for(auto [v,w]:g[u]){ if(!vis[v]dis[u]wdis[v]){ dis[v]dis[u]w; heap.push({v,dis[v]}); } } } }; dijkstra(0); ll ans0; for(int i0;ix;i) { if(dis[i]INFLL) { cout-1endl; return ; } ansmax(ans,dis[i]-x); } coutansendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }首先因为 m 和每根木棍原始的长度都不大所以考虑先暴力找出所有可以用的木棍长度。之后首先可以发现若最小长度是 1那么就说明任何长度都能拼出来。否则那么就选最小长度作为基准然后去跑同余最短路即可。最后若存在一个模数状态无法到达就说明不能拼成的个数是无穷的。否则对于模 i 意义下能凑出来的最小数 dis[i]让其再减去 x 就是模 i 意义下不可能达到的最大数。那么就只需要考虑所有 dis[i]取最大值即可。3.D - Small Multiple#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define endl \n typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int k; cink; vectorintvis(k); dequearrayint,2q; q.push_back({1,1}); while(!q.empty()) { auto [u,cost]q.front(); q.pop_front(); if(!vis[u]) { vis[u]1; if(u0) { coutcostendl; return ; } q.push_front({(u*10)%k,cost}); q.push_back({(u1)%k,cost1}); } } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }首先对于数位和也可以转化成图上问题。方法就是规定当前数 v 经过权值为 0 的路表示乘以 10经过权值为 1 的路表示加 1。那么此时从 1 开始到达 v 的最短路就是 v 的数位和。举个例子35 这个数可以从 1 开始先经过三次权值为 1 的路变成 3再经过权值为 0 的路变成 30再经过五次权值为 1 的路变成 35。之后对于 k 的整数倍还是考虑转化成同余问题即模 k 余 0 来考虑。所以之后就是根据上述方式在这个模 k 余 u 的图上连边。因为在走的过程中累计的权值和就是数位和又因为要让数位和最小而且边权只有 0 和 1所以考虑从 1 开始跑 01bfs。那么就可以保证在第一次走到模 k 余 0 的点时即是 k 的正整数倍此时得到的从 1 到 0 的权值最小即最小数位和。4.墨墨的等式#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define endl \n typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; templatetypename T T gcd(T a,T b){ return b0?a:gcd(b,a%b); } void solve() { int n; ll l,r; cinnlr; l--; vectorinta(n1); for(int i1;in;i) { cina[i]; } sort(a.begin()1,a.end()); int m0; for(int i1;in;i) { if(a[i]!0) { a[m]a[i]; } } if(m0) { cout0endl; return ; } int xa[1]; vectorlldis(x,INFLL); dis[0]0; for(int i2;im;i) { int dgcd(a[i],x); for(int j0;jd;j) { for(int uj,round0;round2;round(uj)) { int v(ua[i])%x; if(dis[u]!INFLL) { dis[v]min(dis[v],dis[u]a[i]); } uv; } } } ll ans0; for(int i0;ix;i) { if(rdis[i]) { ans(r-dis[i])/x1; } if(ldis[i]) { ans-(l-dis[i])/x1; } } coutansendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }首先第一道题问的是 1 到 h 范围上有多少个数能被凑出来。那么这个题问的是 [l,r] 范围上所以直接用 1 到 r 范围上的个数减去 1 到 l-1 范围上的个数即可。现在介绍两次转圈法实现同余最短路。首先因为在确定基准数 x 后对于每个数 y要从每个余数往外连边。那么此时就有一个结论对于基准数 x 和当前数 y图上能形成的环的个数是 gcd(x,y)。举个例子若 x10y15此时图上能形成的环的个数就是 5。因为 0 到 5 会一条边5 到 0 也会有一条边。然后 1 到 6 有一条边6 到 1 也有一条边之后以此类推。所以又有一个结论所有环的起点为 0~gcd(x,y)-1。那么之后每次就可以以每个环为单位进行更新。举个例子若 x8y4那么环的个数就是 gcd(8,4)4所以就需要从 0~3 开始分别转一圈更新即可。那么由于点的个数是 O(x) 的又因为每个条边的权值是正的所以最短路最多就只会转一圈。需要注意的是环的起点可能不是点权最小的点所以在实现的时候需要转两圈。举个例子若 x14,y7那么此时从 0 开始就只能把 7 的点权更新成 7。之后若 y2那么当从 1 开始转时因为一开始 1 的点权是正无穷所以是没法更新的。但当转到 7 时此时由于 7 有点权 7所以之后就可以更新后续点了。那么此时就需要再转一圈把 1 的点权也更新到。那么在两次转圈法中时间复杂度为 O(n*x)极端情况下是比 spfa 和 dijkstra 要好的。同余最短路不需要最短路5.背包太变态了……#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define endl \n typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; templatetypename T T gcd(T a,T b){ return b0?a:gcd(b,a%b); } void solve() { int n,q; cinnq; vectorllv(n1); vectorllc(n1); double best0; ll x,y; for(int i1;in;i) { cinv[i]c[i]; double cur(double)c[i]/v[i]; if(curbest) { bestcur; xv[i]; yc[i]; } } vectorlldp(x,-INFLL); dp[0]0; for(int i1;in;i) { if(v[i]x) { continue; } int dgcd(v[i],x); for(int j0;jd;j) { for(int curj,round0;round2;round(curj)) { int to(curv[i])%x; if(dp[cur]!-INFLL) { dp[to]max(dp[to],dp[cur]-(curv[i])/x*yc[i]); } curto; } } } ll V; while(q--) { cinV; int rV%x; if(dp[r]-INFLL) { cout-1endl; continue; } coutV/x*ydp[r]endl; } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }首先考虑将价值除以体积即性价比最大的物品选出来作为基准物品。举个例子若这个基准物品的体积是 10那么之后若体积和是 10 的整数倍那么必然是只用这个基准物品的。因为基准物品是性价比最高的选其他的只会让价值和更小。那么有了这个基准物品考虑定义 dp[i] 为对于某个总体积先尽可能选择基准物品剩下的体积为 i。再通过去掉若干基准物品用其他物品凑够总体积此时相比全用基准物品的最大收益差。太抽象了所以这里举个例子。若基准物品的体积为 10价值为 100那么首先对于 40 的体积其必然可以全用基准物品所以收益差 dp[0] 就是 0即不需要用别的物品补。之后对于 55 的体积全用基准物品能凑出 50 的体积余下 5 的体积所以考虑的是 dp[5]。之后若有一个体积为 15价值为 140 的物品那么就可以通过去掉一个基准物品加入这个物品来产生 40 的收益差。那么对于体积 55只需要先全用基准物品达到 50 的体积再加上 dp[5] 就是答案。再举一个例子还是这两个物品不变。此时多了一个体积为 16价值为 6 的物品那么其必然可以在 dp[5] 的基础上更新出 dp[1]。那么就是在 dp[5] 的基础上再来一个体积为 16 的物品就可以得到模 x 余 1 的状态。此时还需要去掉之前选的基准物品那么就是当前物品 16 再加上余的 5 的体积得到的 21再除以基准物品的 10 体积。所以要在当前物品加 dp[5] 产生的 46 的价值的基础上扣掉 2 个基准物品的价值 200那么 dp[1] 就是 -154。换言之若基准物品的体积为 x那么这个就是转化成模 x 同余的问题。但存在一个问题若存在一个体积为 101价值为 1001 的物品那么是可以把 dp[1] 更新为 1 的。但此时如果再计算 51 的体积时是用不到当前这个 dp[1] 的。但观察每条查询的数据范围可以发现查询的体积是非常大的比每个物品的体积大得多所以是不会出现上述情况的。那么在更新时若基准物品的体积为 x价值为 y。那么对于当前体积为 v价值为 c 的物品其可以从每个余数 r 往 (rv[i])%x 转移。那么在转移时就是看能否把去往的状态更新得更大。所以就是初始化为负无穷然后跑一个最长路即可。此时就可以对之前说的数据范围进行证明了。对于每个状态其必然是由若干个其他状态更新过来的。那么首先可以证明更新的这条路径上必然不会经过重复的点。因为若经过重复的点若这个点的余数为 r那么转了一圈就说明通过选了其他若干个物品余数又回到了 r。那么也就说明这些物品的体积和是基准物品体积 x 的整数倍那么这样做必然是亏的。所以可以得出这是一个负环。那么因为不会经过重复点所以最多就是全走一遍即经过 x 条边。那么因为一条边代表选一个物品那么就最多额外选了 x 个物品。因为每个物品的体积最多是 1e5 的所以基准数 x 也是 1e5 的所以 dp 值的大小最多就是 1e10 的是不会超过查询体积 1e11 的。在实现时只需要注意只有当物品的体积不是 x 才去两次转圈。因为若体积等于 x要么是基准物品要么比基准物品还劣所以就没必要考虑了。总结图论建模太变态了……很难想象之后挺难阶段的图论是什么样子……END