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

· · 题解

打表找规律做法：

这道题，最重要的就是打表找规律！

这道题目简单来说就是三个岛屿之间不能全部架桥,如：

$B$、$C$有一座桥 $C$、$A$有一座桥 那么以上就是不成立的，但是请问你怎样能架桥最多。 打表得出： |1|2|3|4|5|6|···| | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | |0|1|2|4|6|9|···| 我们找到了一个规律： 设$f(n)$表示这串数列的第$n$项。 则： 当$n$是2的倍数时，$f(n)=(\dfrac{1}{2}n)^2

否则,f(n)=\lfloor \dfrac{1}{2}n \rfloor \times \lceil \dfrac{1}{2}n \rceil

(在这里的\lceil \dfrac{1}{2}n \rceil等同于\lfloor \dfrac{1}{2}n \rfloor +1)

所以代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    if(n%2==0)
        cout<<(n/2)*(n/2);
    else
        cout<<(n/2)*(n/2+1);
    return 0;
}