![[学习笔记]NOIp2017小凯的疑惑及其推广](/0.jpg)
小凯的疑惑题面 两个数a,b，求最大的不能被a、b表示的数 2017年我没参加提高组，所以没有体会到此题毒瘤程度，据说一堆大佬死在了这题上面 首先，结论题，猜结论十分简单：
a
∗
b
−
a
−
b
a*b-a-b
a∗b−a−b 那么怎么推出来呢 以样例3、7为例 建立一个n*7的矩阵 红色部分都是能表示的，显然，答案是11（最大的白色的数） 我们可以发现矩阵中的某些性质
上下相邻的两个数相差7每一列中第一个红色的数一定是第一个被3整除的数（除了最后一列）
因为上下相邻的两数相差7，所以一列中只要其中一个能被表示出来，那么正下方的数就一定可以被表示出来 那么一列中最小的能被表示出来的数一定是3k（最后一列不讨论，因为最后一列是7的倍数）
然后发现11下方18刚好是几列中最大的最小的能被表示出来的数 再来看一组好的数据：4、7 建立一个4*7的矩阵 发现规律了没？
21
=
3
∗
7
=
(
4
−
1
)
∗
7
21=3*7=(4-1)*7
21=3∗7=(4−1)∗7
17
=
21
−
4
=
(
4
−
1
)
∗
7
−
4
=
4
∗
7
−
4
−
7
17=21-4=(4-1)*7-4=4*7-4-7
17=21−4=(4−1)∗7−4=4∗7−4−7 感性理解一下就行了 题目样例也是如此，公式就这么推出来了（看图理解更便捷，我口头论述不清） 代码就不放了~~
----------------------------------------------------------------------
接下来是升级版 首先这道题可以非常容易得拿到30分小凯的疑惑结论输出；以及40分暴力完全背包，就不加阐述了 想想满分的怎么打
对上面的图加深理解
发现每一列分别对4取模为1、2、3、0 像一个说法来描述每一列中最小的那个能被表示出来的数 比如21是%4=1的数中最小的能被7表示出来的数 14是%4=2的数中最小的能被7表示出来的数，以此类推 然后，每一列中最大的不能被7表示出来的数是：最小的能被7表示出来的数-4 然后答案是对每一列中最大的不能被7表示出来的数再取个max 也就是
m
a
x
(
每
一
列
中
最
小
的
能
被
7
表
示
出
来
的
数
−
4
)
max(每一列中最小的能被7表示出来的数-4)
max(每一列中最小的能被7表示出来的数−4)
若输入a,b（不妨令a m a x ( 每 一 列 中 最 小 的 能 被 b 表 示 出 来 的 数 − a ) max(每一列中最小的能被b表示出来的数-a) max(每一列中最小的能被b表示出来的数−a) 若输入三个数呢，设输入a,b,c(不妨令a m a x ( 每 一 列 中 最 小 的 能 被 b ， c 表 示 出 来 的 数 − a ) max(每一列中最小的能被b，c表示出来的数-a) max(每一列中最小的能被b，c表示出来的数−a) 那么有n个数的话一样也可以搞 那么看看这道强化题，发现x1<=1e6，说明列数<=1e6 令dis[u]表示最小的能被x2,x3……xn表示的%x1=u的数 dis数组可以跑最短路求得（x1<=1e6，没毛病） 然后答案是max(dis[i]-x1) 是不是很简单？ 在这里放个官方题解，不过及其省略 很明显，题解把怎么做说的清清楚楚，但是为什么并没有解释，所以我就是来解释一下为什么~~ 我最短路用了堆优dijk，比spfa稳定 Code： #include #define maxn 1000010 #define LL long long using namespace std; const LL inf = 9999999999999999; struct node{ int num; LL len; bool operator < (const node &x) const{ return len > x.len; } }; priority_queue int n, p, vis[maxn]; LL dis[maxn], a[maxn]; inline LL read(){ LL s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int main(){ freopen("sequence.in", "r", stdin); freopen("sequence.out", "w", stdout); n = read(); if (n == 2){//n=2,小凯的疑惑特判，因为这个情况x1<=1e9，无法最短路 LL x = read(), y = read(); printf("%lld\n", x * y - x - y); fclose(stdin); fclose(stdout); return 0; } p = read(); for (int i = 1; i < n; ++i) a[i] = read(); q.push((node) {0, 0}); for (int i = 1; i < p; ++i) dis[i] = inf; while (!q.empty()){//最短路过程 node tmp = q.top(); q.pop(); if (vis[tmp.num]) continue; vis[tmp.num] = 1; for (int i = 1; i < p; ++i){ LL u = (tmp.num + a[i]) % p; if (dis[u] > tmp.len + a[i]){ dis[u] = tmp.len + a[i]; q.push((node) { u, dis[u] }); } } } LL ans = 0; for (int i = 1; i < p; ++i) ans = max(ans, dis[i] - p);//求得答案 printf("%lld\n", ans); fclose(stdin); fclose(stdout); return 0; }