Link

ARC166 B Make Multiples

Question

给出 \(N\) 个整数， \(A_1...A_N\) ，还有三个数 \(a,b,c\)

我们可以给 \(A_i\) 加上 \(1\)

需要使得数组 \(A\) 满足，存在一个数是 \(a\) 的倍数，一个数是 \(b\) 的倍数，一个数是 \(c\) 的倍数

求最少的操作次数

Solution

考虑对于每个数的操作无非就这几种

• 不变
• 加成 \(a\) 的倍数
• 加成 \(b\) 的倍数
• 加成 \(c\) 的倍数
• 加成 \(lcm(a,b)\) 的倍数
• 加成 \(lcm(a,c)\) 的倍数
• 加成 \(lcm(b,c)\) 的倍数
• 加成 \(lcm(a,b,c)\) 的倍数

我们不知道每个数具体的操作，但发现操作数很少，就考虑状态压缩

用 \(a\) 表示二进制的第一位 ，用 \(b\) 表示二进制的第二位，用 \(c\) 表示二进制的第三位

我们可以用二进制表示状态和操作

那么上面的8种操作就可以用 1-7 来表示

定义 \(F[i][s]\) 表示前 \(i\) 个整数，此时的状态是 \(s\) 的最小的加的次数

转移方程：

答案 \(F[N][7]\)

Code

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int maxn= 200005;
inline int read(){
    int ret = 0, f = 1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f = -f;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+ch-48,ch=getchar();
    return ret;
}
inline void print(int x, int flag = 1)
{
    if (x < 0) putchar('-'), x = ~(x - 1);
    if (x > 9) print(x / 10, 0);
    putchar(x % 10 + 48);
    if (flag) putchar(flag & 1 ? ' ' : '\n');
}
inline int gcd(int x,int y) {return y?gcd(y,x%y):x;}
inline int lcm(int x,int y) {return x/gcd(x,y) *y;}
int N,x,y,z,F[maxn][8],tmp[8],w[8];
signed main(){
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    N=read();x=read();y=read();z=read();
    w[1]=x;w[2]=y;w[4]=z;w[3]=lcm(x,y);w[5]=lcm(x,z);w[6]=lcm(y,z);w[7]=lcm(x,lcm(y,z));
    memset(F,0x7f,sizeof F);F[0][0]=0;
    for(int i=1;i<=N;i++){
        int now=read();
        for(int j=1;j<8;j++)
            tmp[j]=(w[j]-(now%w[j]))%w[j];
        F[i][0]=0;
        for(int j=0;j<8;j++){
            F[i][j]=min(F[i][j],F[i-1][j]);
            for(int k=1;k<8;k++)
                F[i][j|k]=min(F[i][j|k],F[i-1][j]+tmp[k]);
        }
    }
    print(F[N][7]);
    return 0;
}

Summary