题解 P2662 【牛场围栏】

· · 题解

前言

我觉得这题挺好啊...为什么题解都写得这么草率...那就由我来系统地讲解讲解。 （顺带安利一发自己的博客，大家也可以去这里看）

分析

规模较小，直接上可行解DP（有个叫_DYT大佬搞了一波分析证明这个解若存在是小于9 \times 10^6） 当然我们要考虑更好的解法，如果是初中我也会写可行解DP，当然考场上实在写不出来我还是应该打个暴力骗骗满分的。

PART 1 无解？

问题确实可能无解，分两种情况：

  • 存在数字1

    • 如果有1这个数字，那么所有的数字都可以被表示出来，就不存在不能表示出的数了

  • 所有数的gcd大于1

    • 设这些数为A_1, A_2,...,A_n，设q=gcd(A_1, A_2,...,A_n)，则q|A_1x_1+A_2x_2+...+A_nx_n(x_1,x_2,...,x_n \in Z)。这是一个很显然的结论，学习整除的时候是必回讲到的。所以，由于q > 1，必然存在不能表示出来的数，即\forall q \nmid m，都是不符合条件的数，显然这个m是可以到无穷大的。

这两者情况我们可以先特判出来，而剩下的就是q=1的情况了，这样的话是肯定存在最大的不能表示出来的数的。 这个很显然。

PART 2 寻找

我们如何去寻找这个最大的不能被表示出来的数呢？ 我们考虑所有可以被表示出来的数构成的数集S，由最小数原理可知，S中一定存在最小的s_0。考虑模s_0的每一个剩余系，记为K_i=\lbrace x|x \equiv i\pmod{s_0}\rbrace,i=0,1,2,...,s_0-1。 显然s_0=min(A_i)。对\forall K_i，由最小数原理，存在最小的能被表示出来的t_i，t_i=s_0*p+i，显然p>0，否则与s_0的最小性矛盾。那么对每一个K_i，最大不能被表示出来的数就是s_0*(p-1)+i。这样，问题就转化为了求每一个这样的t_i，这时候，我们就引入这个被称为剩余系最短路的算法了。我们可以把每个剩余系K_i抽象为图中的点，那么连接它们的边就是A_i中的那些数。然后就用普通的最短路更新方式就可以了。我选择了用Dijkstra算法。

参考程序

// Luogu P2262
#include <cstdio>
#include <cstring>
#include <algorithm>
const int ARSIZE = 4005;
const int INF = 0x7f7f7f7f;

int N, M, L[ARSIZE], tot_l = 0, Q[ARSIZE];
bool exist[ARSIZE] = {0}, used[ARSIZE] = {0};

inline int gcd(int a, int b) {
    for (a < b ? std::swap(a, b) : (void)0; b; std::swap(a, b)) a %= b;
    return a;
}
int dijkstra();

int main() {
    scanf("%d%d", &N, &M);
    int j, li, gd = 0;
    for (int i = 0; i < N; i++) {
        scanf("%d", &li);
        gd = gcd(gd, li);
        for (j = 0; j <= M && j < li; j++) exist[li - j] = true, gd = gcd(li - j, gd);  // 很多人WA，半天查不出错，很可能就是只算了所有L[i]的gcd
    }
    if (exist[1] || gd > 1) puts("-1");
    else printf("%d\n", dijkstra());
    return 0;
}

int dijkstra() {
    memset(Q, 0x7f, sizeof(Q));
    int i, v, k;
    for (Q[0] = 0, i = 2; i <= 3000; i++)   // 初始化
        if (exist[i]) L[tot_l++] = i;
    int MOD = L[0];
    while (true) {
        for (i = 0, k = -1; i < MOD; i++)
            if (!used[i] && (k == -1 || Q[i] < Q[k])) k = i;
        if (k == -1) break;
        used[k] = true;
        for (i = 1; i < tot_l; i++)
            if (!used[v = (k + L[i]) % MOD]) Q[v] = std::min(Q[v], Q[k] + L[i]);    // 更新其他剩余系
    }
    int res = -1;
    for (i = 1; i < MOD; i++) res = std::max(res, Q[i] - MOD);
    return res;
}