前几天在家里看cy1999写牛客的周赛题，链接在这里，当时cy啪的一下很快啊，就做出来了，直接ac，我问他好不好写，他斜眼一笑，说好写，我大意了啊，直接信了，然后就链接一开，开始写了。

1. 题目大意

自助餐厅里有5个盘子，里面装的都是面包。

第1个盘子里有无限个面包；

第2个盘子里只有1个面包；

第3个盘子里只有4个面包；

第4个盘子里也有无限个面包，但必须两个两个地拿；

第5个盘子里也有无限个面包，但必须5个5个地拿；

给定正整数n，求有多少种正好拿出n个面包的方案。

方案a和方案b不同，当且仅当方案a存在从某个盘子里拿出面包的数量与方案b中对应盘子拿出的数量不同。

2. 解题过程

Round 1

只看题的话，我们可以很快的写出来一个答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public long work(int n){
    long ans=0;
    for(int i=0;i<=1;i++){
        for(int j=0;j<=4;j++){
            int last=n-i-j;
            if(last<0) continue;
            for(int k=0;k<=last;k+=5){
                for(int m=0; m<=last-k; m += 2){
                    ans ++;
                }
            }
        }
    }
    return ans;
}

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为30.00%

Round 2

显然是超时了，我们可以试着把最里面的循环拆掉，可以发现，最里面的循环计算的是循环的次数，通过小学二年级的知识我们可以把最里面的循环拆成如下所示

1
ans += (last-k)/2+1;

完整答案如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public long work(int n){
    long ans=0;
    for(int i=0;i<=1;i++){
        for(int j=0;j<=4;j++){
            int last=n-i-j;
            if(last<0) continue;
            for(int k=0;k<=last;k+=5){
                ans += (last-k)/2+1; 
            }
        }
    }
    return ans;
}

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为90.00%

Round 3

可以发现，拆完之后，仍然超时，我们还需要拆掉下面的循环：

1
2
3
for(int k=0;k<=last;k+=5){
    ans += (last-k)/2+1; 
}
  1. 首先我们可以仿照第二步的方式把+1拆成(last/5)+1，即循环的次数，此时还有(last-k)/2没有被拆
  2. 我们先忽略/2，先把last-k拆出来，last可以拆成循环的次数乘以last，即last*(last/5+1)
  3. 对于k来说，因为k是变量，我们可以按照等比数列求和的原理(a0+an)*n/2把k拆出来，首先an不是last，而是last-last%5，所以我们可以把k的循环拆为((last/5+1)*(last - last%5))/2
  4. 这样就完了吗？当然不是，因为我们刚才忽略了/2这个东东，我们知道，在计算机中，如果不是整除，则余数会直接舍去，所以我们要考虑被舍去的那一部分，即last/2和k/2这两种情况。

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public long wwork (int n) {
    long ans=0;
    for(int i=0;i<=1;i++) {
        for(int j=0;j<=4;j++){
            long last=n-i-j;
            if(last<0) continue;
            long tans=0;
            ans+=(last/5)+1;
            tans+=(last*(last/5+1));
            tans-=((last/5+1)*(last - last%5))/2;
            if(last%2==1){
                tans-=last/10 + 1;
            }else{
                tans-=last/5-last/10;
            }
            tans/=2;
            ans+=tans;
        }
    }
    return ans;
}

答案正确:恭喜！您提交的程序通过了所有的测试用例

3. 后记

好吧，cy大佬用了几分钟就写出来的，我想了好久还是被cy大佬屡屡提示才搞懂，我大意了啊，暴露了我是垃圾的本质。