LuoguP2662 牛场围栏

前言

XY说要让我们多见识见识联赛各种考题类型。这个是真的挺少见的,估计很多人都不知道。不过了解了总比不了解好。

题意

给你一些数字A_i,满足1 \leq A_i \leq 3000,每个数字都有无限多个。你可以选择一些数相加,要求你找出最大的不能用这些数相加的数。
可能不存在这个数或者这个数无穷大的情况,则输出-1。

分析

规模较小,直接上可行解DP(比赛时好多人这么写A了,_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_it_i=s_0\ast p+i,显然p>0,否则与s_0的最小性矛盾。那么对每一个K_i,最大不能被表示出来的数就是s_0*(p-1)+i。这样,问题就转化为了求每一个这样的t_i,这时候,我们就引入这个被称为剩余系最短路的算法了。我们可以把每个剩余系K_i抽象为图中的点,那么连接它们的边就是A_i中的那些数。然后就用普通的最短路更新方式就可以了。我选择了用Dijkstra算法。

参考程序

#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 105;
const int ArSize = 3005;
const int INF = 0x7f7f7f7f;

int N, M, dist[ArSize], MOD;
bool flag[ArSize], used[ArSize];

inline void upd(int & res, int val) { res = std::min(res, val); }
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 i, j, gd = 0, Li;
    for (i = 0, MOD = INF; i < N; i++)
        for (scanf("%d", &Li), j = 0; j <= M && j < Li; j++) flag[Li - j] = true, gd = gcd(gd, Li - j), MOD = std::min(MOD, Li - j);
    if (flag[1] || gd > 1) { puts("-1"); return 0; }
    printf("%d\n", Dijkstra());
    return 0;
}

int Dijkstra() {
    memset(dist, 0x7f, sizeof dist);
    dist[0] = 0;    // 初始化K0
    int i, k;
    for (; ; ) {
        for (i = 0, k = -1; i < MOD; i++)
            if (!used[i] && (k == -1 || dist[i] < dist[k])) k = i;
        if (k == -1) break;
        used[k] = true;
        for (i = 1; i <= 3000; i++)
            if (flag[i]) upd(dist[(dist[k] + i) % MOD], dist[k] + i);   // 更新其他剩余系
    }
    int res = 0;
    for (i = 0; i < MOD; i++) res = std::max(res, dist[i] - MOD);
    return res;
}

总结

这道题属于非常新颖的类型,对数论水平的考验较高,并且将数论与最短路算法结合在一起的方式也很巧妙。总之,这道题第一次碰到,对于想象力的要求是要很高的。好题!只可惜下一次碰到它,却只成了个套路。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注