题解 P5425 【[USACO19OPEN]I Would Walk 500 Miles】

ix35 · 2019-06-12 22:11:28 · 题解

一道很搞笑的结论题。

唯一一篇题解中有提到图论的部分，但是我刚看到这玩意真不觉得是个图论。首先先拆式子吧。

设P=2019201997，则x<y产生的代价为((P-84)x+(P-48)y)\mod P，这个大数看着有点心烦，想办法把它拆去：

我们发现由于N\leq 7500，因此-84x-48y远远不到-P，所以内层的取模时可以去掉的，另外由于它总是个负数，因此加上P后不必再取模，外层的取模实际上也是可以去掉的，所以代价为：

下面让它的最小值取最大值。有一个很显然的结论，最小值一定由N和另一个数产生，假设不是这样，那么设最小值由r<s组成，那么其中必有一个数与N不在一组（否则r,s一组矛盾），于是将其中一个换成N得到结果更小。

那么当N确定时，这个式子的值尽量大，其实就是x尽量小，由于K组都非空，所以我们让1...K-1各自单独一组，最后K...N一组，那么(K-1,N)可以组成最大的最小值，即：

于是就...

注意这玩意看上去大，实际上超小，不会超int，所以随便过。

#include <bits/stdc++.h>
using namespace std;
int n,k;
int main () {
    scanf("%d%d",&n,&k);
    printf("%d\n",-12*(7*(k-1)+4*n)+2019201997);
    return 0;
}