目录
原文链接
0x00 算法介绍
0x01 基础做法
首先介绍基础做法。
从1到h中的所有数一共有多少个数可以被\(a_1,a_2...a_n\)表示？
考虑直接\(x\equiv a_i\pmod m\)，从中假设\(dis_{(i+y)\bmod x}=dis_i+y\)表示通过拓展\(y,z\)可以得到的最小的模x意义下的为i的数。看起来长得很像最短路，于是我们直接建边：
\[i\rightarrow(i+y)\bmod x
\]
\[i\rightarrow(i+z)\bmod x
\]
其边权分别为\(y,z\)。
由于图的形状比较固定，所以SPFA不会死。
时间复杂度：\(\Theta(na_1k)\)，但是跑不满。
0x02 不如转圈！
考虑最本源的思想：完全背包DP。对于没有以上的数学分析，我们基本上都会想到完全背包。考虑和之前一样的同余思想，将完全背包的体积设定为一个模基本物体上的体积，假设这个值为\(m\)。
类似完全背包，我们将会枚举背包体积。对于任意一个物品\(v_i\)，它将在整体的[1,m]区间中形成环，且环的个数为\(\gcd(v_i,m)\)（因为能使得\(v_i\times a \leqslant m\)的\(a\)的值有且最大为\(\gcd(v_i,m)\)）。
由于DAG上DP的经验，我们不能在DP的过程中产生环，所以这个“完全背包”最大只能容纳\(\frac{m}{\gcd(v_i,m)}-1\)个体积为\(v_i\)的物品。
对于每一个物品，如果我们在子环上转两圈，就可以考虑到所有状态（类似区间DP，感性理解）。时间复杂度\(\Theta(nm)\) 。
模板：
for(int i = 2;i <= n;++i)//枚举物品编号
for(int j = 0 ,lim = __gcd(v[i] , m);j < lim;++j){//枚举选取物品的件数
//j从0开始，相当于变相-1了
int c = 0 ;//转了几圈
for(int k = j;c < 2;c += (j == k)){//枚举当前的体积 只有i和j重合时才算转了一圈
int p = (k + v[i]) % m ;//计算加了之后的点位
f[p] = min(f[p] , f[k]+v[i]) ;//取最优值
k = p ;//跳到当前点位，表示多取了一件物品
}
}
下面“补充练习”部分也有详细的注释分析。
0x10 例题
0x11 P2371 [国家集训队] 墨墨的等式
模板题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
#define ll long long
const int MAXN = 5e5+10 ;
int n ,m ,a[MAXN] ;
ll f[MAXN] ,l ,r ,ans ;
int main(){
ios::sync_with_stdio(0) ;cin.tie(0) ;cout.tie(0) ;
cin >> n >> l >> r ;
for(int i = 1;i <= n;++i) cin >> a[i] ;
memset(f , 0x7f , sizeof f) ;f[0] = 0 ;
sort(a+1 , a+1+n) ;//从大到小排序：单调增保证后续的区间取值操作
m = a[1] ;//随便取，尽量小
for(int i = 2;i <= n;++i)//枚举第几件物品，1是mod数不算
for(int j = 0 ,lim = __gcd(a[i] , m);j < lim;++j){//枚举体积值
int c = 0 ;//转几圈
for(int k = j;c < 2;c += (j == k)){//取几个数
int p = (k + a[i]) % m ;
f[p] = min(f[p] , f[k]+a[i]) ;
k = p ;
}
}
for(int i = 0;i < m;++i){//枚举体积mod数
if(r >= f[i]) ans += max(0ll , (r - f[i]) / m + 1) ;//可能产生负贡献，此时选择不取
//最大能取的a[1]数量为r-模数，+1保证向上取证（因为一定有小数）
if(l > f[i]) ans -= max(0ll , (l - 1 - f[i]) / m + 1) ;
}
cout << ans ;
return 0 ;
}
0x12 P9140 [THUPC 2023 初赛] 背包
复习时见blog
0x20 和其他算法的对比
转圈技巧比最短路做法好写，且适用范围没有任何限制。(然而有时候SPFA更快)
0x30 总结
最短路 \(\rightarrow\) 完全背包 \(rightarrow\) 多重背包
0x40 补充练习
0x41 P3403 跳楼机
注释比较详细。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
#define ll long long
const int MAXN = 1e5+10 ;
ll n ,a[10] ,m ;
ll f[MAXN] ;
int main(){
ios::sync_with_stdio(0) ;cin.tie(0) ;cout.tie(0) ;
cin >> n >> a[1] >> a[2] >> a[3] ;
m = a[1] ;memset(f , 0x7f , sizeof f) ,f[1 % m] = 1 ;//初始化f[1]=1，因为从1开始，至少有一个数
for(int i = 2;i <= 3;++i){
for(int j = 0 ,lim = __gcd(m , a[i]);j < lim;++j){//最大子环个数。
//就像通分 两边的分母同乘以对方除以gcd 之后两个数相等。这个子环个数就是为了让m和a[i]相同计算的gcd
//这就解释了m/gcd*v_i 可以被替换的原因。这里j枚举的就是这之间的差（对方除以gcd后剩下的所有可能）
int c = 0 ;
for(int k = j;c < 2;c += (k == j)){
int p = (k + a[i]) % m ;
f[p] = min(f[p] , f[k] + a[i]) ;//是否选取这个物品（边权）
//这里选取这个边权就相当于加上这个数，使得差变小
k = p ;
}
}
}
ll ans = 0 ;
for(int i = 0;i < m;++i){//枚举体积mod数
if(n - f[i] >= 0) ans += max(0ll , 1ll * (n - f[i]) / m + 1) ;
//f[p]表示在容量大小为p时最小的余数
//n-f[i]表示首先要暂时性减去这部分，然后计算比它大的（因为v_1还没计算）有多少个数，最后加上自己
}
cout << ans ;
return 0 ;
}
0x42 AT_arc084_b [ABC077D] Small Multiple
这是01bfs的经典题型（混入其中）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std ;
const int MAXN = 1e5+10 ;
int k ,f[MAXN] ,vis[MAXN] ;
queue<int> q ;
int main(){
cin >> k ;
memset(f , 0x3f , sizeof f) ;
f[1] = 1 ;q.push(1) ;
while(!q.empty()){
int u = q.front() ;
q.pop() ;
vis[u] = 0 ;
int v = u * 10 % k ;
if(f[u] < f[v]){
f[v] = f[u] ;
if(!vis[v]) q.push(v) ,vis[v] = 1 ;
}
v = (u + 1) % k ;
if(f[u] < f[v]){
f[v] = f[u] + 1 ;
if(!vis[v]) q.push(v) ,vis[v] = 1 ;
}
}
cout << f[0] ;
return 0 ;
}
0x43 P2662 牛场围栏
我他妈怀疑这个东西用DP根本卡不过去。。。
只能用SPFA。
30pts代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
#define ll long long
const int MAXN = 600005 ;
ll n ,m ,cnt ,v ;
ll a[MAXN] ;
ll f[MAXN] ,ans ;
ll sum ;
int main(){
ios::sync_with_stdio(0) ;cin.tie(0) ;cout.tie(0) ;
cin >> n >> m ;
int gcdd = 0 ,flag = 0 ;
for(int i = 1;i <= n;++i){
cin >> a[++cnt] ;int lim = cnt ;
gcdd = __gcd(a[cnt] , 1ll*gcdd) ;
if(!flag && a[cnt] == 1) flag = 1 ;
for(int j = 1;j <= m && a[lim]-j;++j){
a[++cnt] = a[lim] - j ;
gcdd = __gcd(a[cnt] , 1ll*gcdd) ;
if(!flag && a[cnt] == 1) flag = 1 ;
}
}
if(flag || gcdd > 1){
cout << -1 ;
return 0 ;
}
for(int i = 1;i <= cnt;++i) sum += a[i] ;
memset(f , 0x7f , sizeof f) ;
m = a[1] ;f[0] = 0 ;
for(int i = 2;i <= cnt;++i){
for(int j = 0 ,lim = __gcd(a[i] , m);j < lim;++j){
int c = 0 ;
for(int t = j;c < 2;c += (j == t)){
int p = (t + a[i]) % m ;
f[p] = min(f[p] , f[t]+a[i]) ;
t = p ;
}
}
}
ll lans ,ans = 0 ;
for(int i = 100*3000;i;--i){
lans = ans ,ans = 0 ;
for(int j = 0;j < m;++j) if(i - f[j] >= 0) ans += (i - f[j]) / m + 1 ;
if(lans - ans == 0){
cout << i+1 ;
return 0 ;
}
}
return 0 ;
}
0x44 P4156 [WC2016] 论战捆竹竿
这道题主要考察KMP。