题解 P6269 【[SHOI2002]空中都市】

· · 题解

题解 P6269 【[SHOI2002]空中都市】

Solution:

谢谢可爱的 chen_zhe 让我找到了一道水题

首先，我们先手算出前几个数据：

1 2 3 4 5 6 7 8 9 10
0 1 2 4 6 9 12 16 20 25

没发现规律？我们把下面的数差分一下：

1 1 2 2 3 3 4 4 5

诶，怎么是个“类等差数列”啊？

于是，这道题就给我们做完了/cy

我们定义一个 cnt 来存储现在的差是多少，每次把 cnt 加到 ans 里，最后输出就行啦qwq

下面附上代码：

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>//四大头文件，好习惯
using namespace std;
int n, ans, cnt = 1; 
int main(){
    scanf("%d", &n);
    if(n == 0 || n == 1) return printf("0") & 0;//先特判一下
    for(int i = 1; i < n; ++i){
        ans += cnt;//每次加上去
        if(i & 1 ^ 1) cnt++;//i & 1 ^ 1 等同于 i % 2 == 0
    }
    printf("%d", ans);//完结撒花-v-
    return 0;
}

End