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

· · 题解

这道题，我有两个做法，一个找规律，一个打表（大雾

1. 找规律

首先看到这种题第一个反应就是手算找规律，这样可以先对题目有个大致的了解。

然后手算的结果是：

0,1,2,4,6,9,12,16,20,25\ldots

当然，如果你还没做出这道题来，我可以为你提供标算生成的接下来几项：

30,36,42,49,56,64,72,81,90\ldots

此时，我们可以想到，这个数列的规律到 oeis.org 上面寻找！

这时候，搜索的结果是：A002620。

我们看到一行字：

\operatorname{Quarter-squares\ :\ floor(}n\div 2)\times \text{ceiling(}n\div2). \text{Equivalently, floor(}n^2\div 4\text{).}

所以通项公式很明显，就是 \operatorname{floor(\dfrac{n^2}{4})}

此时带入代码即为：

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n;
    cout<<n*n/4<<endl;
    return 0;
}

于是成功AC：https://www.luogu.com.cn/record/32398036

2.打表

首先根据我们推出的正解，同时数据范围 0\le n\le 1000 可以写出一个 generater，如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i=1;i<1005;i++){
        cout<<i*i/4<<',';
    }
    return 0;
}

然后打出来的表稍作修理，可以变成 AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[1005]={0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90,100,110,121,132,144,156,169,182,196,210,225,240,256,272,289,306,324,342,361,380,400,420,441,462,484,506,529,552,576,600,625,650,676,702,729,756,784,812,841,870,900,930,961,992,1024,1056,1089,1122,1156,1190,1225,1260,1296,1332,1369,1406,1444,1482,1521,1560,1600,1640,1681,1722,1764,1806,1849,1892,1936,1980,2025,2070,2116,2162,2209,2256,2304,2352,2401,2450,2500,2550,2601,2652,2704,2756,2809,2862,2916,2970,3025,3080,3136,3192,3249,3306,3364,3422,3481,3540,3600,3660,3721,3782,3844,3906,3969,4032,4096,4160,4225,4290,4356,4422,4489,4556,4624,4692,4761,4830,4900,4970,5041,5112,5184,5256,5329,5402,5476,5550,5625,5700,5776,5852,5929,6006,6084,6162,6241,6320,6400,6480,6561,6642,6724,6806,6889,6972,7056,7140,7225,7310,7396,7482,7569,7656,7744,7832,7921,8010,8100,8190,8281,8372,8464,8556,8649,8742,8836,8930,9025,9120,9216,9312,9409,9506,9604,9702,9801,9900,10000,10100,10201,10302,10404,10506,10609,10712,10816,10920,11025,11130,11236,11342,11449,11556,11664,11772,11881,11990,12100,12210,12321,12432,12544,12656,12769,12882,12996,13110,13225,13340,13456,13572,13689,13806,13924,14042,14161,14280,14400,14520,14641,14762,14884,15006,15129,15252,15376,15500,15625,15750,15876,16002,16129,16256,16384,16512,16641,16770,16900,17030,17161,17292,17424,17556,17689,17822,17956,18090,18225,18360,18496,18632,18769,18906,19044,19182,19321,19460,19600,19740,19881,20022,20164,20306,20449,20592,20736,20880,21025,21170,21316,21462,21609,21756,21904,22052,22201,22350,22500,22650,22801,22952,23104,23256,23409,23562,23716,23870,24025,24180,24336,24492,24649,24806,24964,25122,25281,25440,25600,25760,25921,26082,26244,26406,26569,26732,26896,27060,27225,27390,27556,27722,27889,28056,28224,28392,28561,28730,28900,29070,29241,29412,29584,29756,29929,30102,30276,30450,30625,30800,30976,31152,31329,31506,31684,31862,32041,32220,32400,32580,32761,32942,33124,33306,33489,33672,33856,34040,34225,34410,34596,34782,34969,35156,35344,35532,35721,35910,36100,36290,36481,36672,36864,37056,37249,37442,37636,37830,38025,38220,38416,38612,38809,39006,39204,39402,39601,39800,40000,40200,40401,40602,40804,41006,41209,41412,41616,41820,42025,42230,42436,42642,42849,43056,43264,43472,43681,43890,44100,44310,44521,44732,44944,45156,45369,45582,45796,46010,46225,46440,46656,46872,47089,47306,47524,47742,47961,48180,48400,48620,48841,49062,49284,49506,49729,49952,50176,50400,50625,50850,51076,51302,51529,51756,51984,52212,52441,52670,52900,53130,53361,53592,53824,54056,54289,54522,54756,54990,55225,55460,55696,55932,56169,56406,56644,56882,57121,57360,57600,57840,58081,58322,58564,58806,59049,59292,59536,59780,60025,60270,60516,60762,61009,61256,61504,61752,62001,62250,62500,62750,63001,63252,63504,63756,64009,64262,64516,64770,65025,65280,65536,65792,66049,66306,66564,66822,67081,67340,67600,67860,68121,68382,68644,68906,69169,69432,69696,69960,70225,70490,70756,71022,71289,71556,71824,72092,72361,72630,72900,73170,73441,73712,73984,74256,74529,74802,75076,75350,75625,75900,76176,76452,76729,77006,77284,77562,77841,78120,78400,78680,78961,79242,79524,79806,80089,80372,80656,80940,81225,81510,81796,82082,82369,82656,82944,83232,83521,83810,84100,84390,84681,84972,85264,85556,85849,86142,86436,86730,87025,87320,87616,87912,88209,88506,88804,89102,89401,89700,90000,90300,90601,90902,91204,91506,91809,92112,92416,92720,93025,93330,93636,93942,94249,94556,94864,95172,95481,95790,96100,96410,96721,97032,97344,97656,97969,98282,98596,98910,99225,99540,99856,100172,100489,100806,101124,101442,101761,102080,102400,102720,103041,103362,103684,104006,104329,104652,104976,105300,105625,105950,106276,106602,106929,107256,107584,107912,108241,108570,108900,109230,109561,109892,110224,110556,110889,111222,111556,111890,112225,112560,112896,113232,113569,113906,114244,114582,114921,115260,115600,115940,116281,116622,116964,117306,117649,117992,118336,118680,119025,119370,119716,120062,120409,120756,121104,121452,121801,122150,122500,122850,123201,123552,123904,124256,124609,124962,125316,125670,126025,126380,126736,127092,127449,127806,128164,128522,128881,129240,129600,129960,130321,130682,131044,131406,131769,132132,132496,132860,133225,133590,133956,134322,134689,135056,135424,135792,136161,136530,136900,137270,137641,138012,138384,138756,139129,139502,139876,140250,140625,141000,141376,141752,142129,142506,142884,143262,143641,144020,144400,144780,145161,145542,145924,146306,146689,147072,147456,147840,148225,148610,148996,149382,149769,150156,150544,150932,151321,151710,152100,152490,152881,153272,153664,154056,154449,154842,155236,155630,156025,156420,156816,157212,157609,158006,158404,158802,159201,159600,160000,160400,160801,161202,161604,162006,162409,162812,163216,163620,164025,164430,164836,165242,165649,166056,166464,166872,167281,167690,168100,168510,168921,169332,169744,170156,170569,170982,171396,171810,172225,172640,173056,173472,173889,174306,174724,175142,175561,175980,176400,176820,177241,177662,178084,178506,178929,179352,179776,180200,180625,181050,181476,181902,182329,182756,183184,183612,184041,184470,184900,185330,185761,186192,186624,187056,187489,187922,188356,188790,189225,189660,190096,190532,190969,191406,191844,192282,192721,193160,193600,194040,194481,194922,195364,195806,196249,196692,197136,197580,198025,198470,198916,199362,199809,200256,200704,201152,201601,202050,202500,202950,203401,203852,204304,204756,205209,205662,206116,206570,207025,207480,207936,208392,208849,209306,209764,210222,210681,211140,211600,212060,212521,212982,213444,213906,214369,214832,215296,215760,216225,216690,217156,217622,218089,218556,219024,219492,219961,220430,220900,221370,221841,222312,222784,223256,223729,224202,224676,225150,225625,226100,226576,227052,227529,228006,228484,228962,229441,229920,230400,230880,231361,231842,232324,232806,233289,233772,234256,234740,235225,235710,236196,236682,237169,237656,238144,238632,239121,239610,240100,240590,241081,241572,242064,242556,243049,243542,244036,244530,245025,245520,246016,246512,247009,247506,248004,248502,249001,249500,250000,250500,251001,251502,252004};
int main(){
    cin>>n;
    cout<<a[n-1]<<endl;
    return 0;
}

AC结果：https://www.luogu.com.cn/record/32398752

3.其他内容

但是，我们一起来分析一下这个图：

所谓的对于城市中的任意三个岛，不能在其中的两两之间都架上桥，就是不允许任意三点出现三角形。

那么据此我们也可以知道，一个图，如果任意两个节点两两相连，那么这个图的边数就是 \dfrac{n^2-n}{2}。

由此继续推导，也许能够从比较严谨的角度说明，这里由于笔者水平原因，不详细推导。

最后，求点个赞好吗？qwq