821B - Okabe and Banana Trees——数学公式

ゝ一世哀愁。 2022-06-13 03:52 136阅读 0赞

Think:  
1题意：沿着一条线段![这里写图片描述][SouthEast]，在这条线段下点可在线段上，找一个矩形，矩形的边分别与x轴，y轴平行，使得这个矩形的所有整数点的sum\_x + sum\_y，矩形可退化为一条线段或一个点  
2方法：线段数学式子转化＋等差数列前n项和（内在规律）  
3反思：  
1>数据输出结果保证不会超过10e18，自己一开始用int型，Wrong Answer，之后比赛快结束了，匆忙改为long long unsigned型，然后for循环结束条件变成一个long long unsigned变量大于等于0，减1后回到long long unsigned变量可储存的最大值，然后for循环一直无限循环…

[codeforces题目链接][codeforces]

以下为Time Limit Exceeded代码——未注意for循环结束条件为long long unsigned型变量大于等于零

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main(){
        long long unsigned y, x, m, b;
        long long unsigned ans, sum;
        while(~scanf("%llu %llu", &m, &b)){
            ans = 0;
            for(y = b; y >= 0; y--){
                x = b*m - m*y;
                sum = x*(x+1)*(y+1)/2 + y*(y+1)*(x+1)/2;
                ans = max(ans, sum);
            }
            printf("%llu\n", ans);
        }
        return 0;
    }

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main(){
        long long x, y, m, b, sum, ans;
        while(~scanf("%lld %lld", &m, &b)){
            ans = 0;
            for(y = b; y >= 0; y--){
                x = b*m - y*m;
                sum = x*(x+1)*(y+1)/2 + y*(y+1)*(x+1)/2;
                ans = max(ans, sum);
            }
            printf("%lld\n", ans);
        }
        return 0;
    }

[SouthEast]: /images/20220613/63faa96119a14e77bd958509d742a290.png
[codeforces]: http://codeforces.com/problemset/problem/821/B