题解 P4956 【[COCI2017-2018#6] Davor】

· · 题解

这道题不暴力也是可以过的呢

思路

毕竟是红题，所以怎么做都行。不过我在这里写一个 O(1) 的做法，以解决更大的 n 和 x 的问题。

容易发现，那个 52 周在一开始就可以除掉了，反正这 52 周是完全一样的。

再来看每一周。把每天的数加起来，得到 7x+21k，化简得 7(x+3k)，于是 7 也可以开始除掉。

所以，只要在开始把 52\times 7=364 除掉，那么方程就变为：x+3k=n。

解这个不定方程时，也需要关注一些题目的条件。这道题的条件有：1≤x≤100，x 和 k 为正整数，且使得 x 最大，k 最小。

显然，如果没有第一个条件，k=1就是解，此时 x=n-3。

但是，当 n>103 时，x 取不到 n-3，就需要变小，而 k 就要变大。k 每变大 1，x 就要 -3，直到 x≤100 为止。

由此，可以分情况讨论。如果 n 是 3 的倍数，由 x=n-3k 得 x 为 3 的倍数，最大为 99。同理，n 模 3 余 1 则 x 也模 3 余 1，最大为 x=100，n 模 3 余 2 则最大为 x=98。k 也就是 (n-x)/3。

综上所述，先看是否 n≤103，如果是则直接输出，否则按照 n%3 讨论即可。

代码

毕竟是红题，没什么细节，直接上代码——

（我知道你们只看这里）

#include<cstdio>
using namespace std;
int read(){//没什么用的快读
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int main(){//主函数
    int n=read()/364;//读入，开始直接/364
    if(n<=103) printf("%d\n%d\n",n-3,1);//k可以取到1的情况
    else{//k不能取1
        if(n%3==0) printf("%d\n%d\n",99,(n-99)/3);//分类讨论，直接输出
        if(n%3==1) printf("%d\n%d\n",100,(n-100)/3);
        if(n%3==2) printf("%d\n%d\n",98,(n-98)/3);
    }
    return 0;//华丽结束
}

看我写了这么多推导过程，点个赞再走呗~