【HDOJ7079】Pty loves lines（计算直线的交点方案数，打表）_zoj pty love line n条直线有多少个交点

Pty loves lines

题意：

• 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数，输出方案，n<=700

思路：

• 原题是HDOJ1466，不过数据只有20。
• 首先考虑原本简单情况下的做法是dp：
  • 我们知道，n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2。
  • 假设一共有n=a+b条直线（即n条直线分成2组，分别为a条和b条）则总的交点数= a内的交点数＋b内的交点数＋a，b之间的交点数
  • 我们将n条直线分为两部分,平行的直线数目r，和不平行的数目n-r；分析可以知道r的取值是0<=r<=n;
  • n条直线相交的方案数=(n-r）条平行线的交点方案（为0）+r条直线本身的交点方案+（n-r）条平行线与r条直线交叉的交点数方案= r条直线本身的交点方案 +（n-r）条平行线与r条直线交叉的交点数方案。=（m-r）*r+r条之间本身的交点方案数（0<=r<=n）
• 再考虑本题的做法，我们打表后可以发现，答案有一段连续的可行后缀，于是我们可以dp预处理出所有的后缀，存到数组里面，每次dp到可行后缀的开始就停止枚举，然后直接输出即可。
• 大佬也可以用bitset来优化转移，就不需要打表了。

#include<bits/stdc++.h>
using namespace std;
int ed[] = {0, 0,0,2,3,6,11,14,15,23,27,30,41,46,59,65,71,84,91,98,105,108,119,126,143,140,159,185,194,203,227,237,247,257,267,273,287,293,327,365,377,389,371,382,425,437,443,461,473,514,563,540,591,605,619,633,647,695,710,725,740,755,770,785,759,815,827,887,903,875,935,951,1019,980,1053,1070,1087,1104,1121,1138,1155,1172,1243,1206,1279,1297,1315,1333,1351,1369,1387,1405,1415,1433,1523,1542,1561,1580,1599,1549,1567,1656,1675,1694,1713,1732,1751,1770,1865,1885,1905,1925,1945,1965,1985,2005,2025,2045,2065,2085,2105,2125,2145,2165,2185,2292,2313,2334,2355,2375,2397,2418,2439,2460,2481,2502,2627,2649,2671,2693,2715,2733,2759,2781,2803,2825,2847,2869,2891,2913,2935,2957,3093,3116,3139,3162,3185,3208,3231,3383,3407,3431,3455,3479,3503,3527,3551,3438,3599,3623,3647,3671,3695,3719,3743,3767,3791,3815,3839,3863,3887,3911,3935,3959,3983,4007,4031,4190,4215,4240,4127,4290,4315,4340,4527,4721,4748,4775,4802,4829,4856,4883,4910,4937,4964,4991,5018,5045,5072,5099,5126,5153,5177,5207,5402,5430,5458,5486,5514,5542,5570,5598,5623,5654,5682,5710,5738,5766,5794,5822,5850,5878,5906,5934,6148,6177,6206,6235,6264,6293,6527,6557,6587,6617,6647,6677,6707,6737,6767,6797,6827,6857,6887,6917,6947,6977,7007,7022,7067,7097,7127,7367,7398,7429,7460,7491,7522,7553,7367,7615,7646,7677,7708,7739,7770,7801,7832,7863,7894,7925,7956,7987,8018,8279,8311,8343,8375,8407,8439,8471,8503,8535,8567,8599,8631,8663,8695,8727,8759,8791,8823,8855,8887,8919,8951,8983,9266,9299,9332,9365,9398,9431,9464,9497,9530,9563,9596,9629,9662,9695,9728,9761,9794,9559,9860,9893,9926,9959,9992,10025,10331,10365,10399,10433,10467,10497,10535,10569,10603,10637,10671,10705,10739,10773,10807,10841,10875,10909,10943,10977,11011,11045,11079,11113,11147,11181,11215,11249,11283,11613,11648,11683,11718,11753,11788,11823,11858,11893,11928,11963,11998,12033,12068,12103,12138,12173,12208,12243,12278,12313,12348,12707,12743,12779,12815,12851,12887,12923,12959,12995,13031,13067,13103,13139,13175,13211,13247,13283,13319,13355,13391,13427,13463,13499,13535,13571,13607,13643,13679,13715,13751,13787,14168,14205,14242,14279,14691,15107,15146,15185,15224,15263,15302,15341,15380,15419,15458,15497,15536,15575,15614,15653,15692,15731,15770,15809,15848,15887,15926,15965,16004,16043,16082,15717,16160,16577,16617,16657,16697,16737,16777,16817,16857,16897,16937,16977,17017,16667,17097,17137,17177,17217,17257,17297,17337,17377,17417,17457,17497,17537,17577,17617,17657,17697,18142,18183,18224,18265,18306,18347,18388,18429,18470,18511,18552,18593,18634,18675,18716,18757,18798,18839,18880,18921,18962,19003,19044,19085,19126,19167,19208,19249,19290,19331,19372,19413,19454,19495,19536,19577,19618,19659,19700,19741,19782,19823,19864,19905,19946,19987,20028,20069,20110,20151,20192,20233,20274,20315,20356,20397,20438,20479,20520,20561,21035,21077,21119,21161,21203,21245,21287,21329,21371,21413,21455,21497,21539,21581,21623,21665,21707,21749,21791,21833,21875,21917,21959,22001,22043,22085,22127,22169,22211,22253,22295,22337,22871,23437,23481,23525,23569,23613,23657,23701,23745,23789,23833,23877,23921,23965,24009,24053,24097,24141,24185,24229,24273,24317,24361,24405,24449,24493,24537,24581,24625,24669,24713,24757,24801,24845,25412,25457,25502,25547,25592,25637,25682,25727,25772,25817,25862,25907,25952,25997,26042,26087,26132,26177,26222,26267,26312,26357,26402,26447,26492,26537,26582,26627,26672,26717,26762,26807,26852,26897,26942,26987,27032,27077,27122,27167,27767,27813,27859,27905,27951,27997,28043,28089,28135,28181,28227,28273,28319,28365,28411,28457,28503,28549,28595,28641,28687,28733,28779,28825,28871,28917,28963,29009,29055,29695,29742,29789,29836,29883,29930,29977,30024,30071,30118,30165,30212,30259,30306,30353,30400,30447,30494,30541,30588,30635,30682,30729,30776,30823,30870,30917,30964,31011,31058,31105,31152};
int big[] = {0,1,2,3,5,7,9,13,18,21,27,34,39,46,54,61,72,83,92,106,118,130,145,162,176,193,209,226,246,265,284,308,330,352,375,402,426,453,480,508,538,570,598,631,661,694,730,765,800,835,872,911,951,992,1030,1071,1115,1158,1203,1251,1295,1343,1392,1440,1491,1541,1590,1642,1695,1750,1806,1861,1917,1977,2033,2092,2154,2216,2276,2340,2404,2467,2535,2605,2672,2741,2812,2882,2951,3024,3096,3170,3245,3319,3394,3474,3553,3634,3716,3798,3881,3963,4045,4131,4215,4302,4388,4479,4568,4659,4750,4843,4938,5034,5128,5225,5322,5419,5517,5616,5716,5818,5920,6023,6129,6234,6339,6450,6559,6668,6776,6888,6998,7110,7223,7337,7451,7567,7684,7803,7922,8042,8163,8288,8411,8536,8660,8786,8912,9040,9168,9296,9424,9555,9687,9820,9953,10089,10227,10364,10503,10643,10783,10925,11066,11209,11353,11497,11641,11785,11932,12079,12229,12378,12528,12682,12836,12989,13146,13303,13460,13619,13777,13936,14096,14257,14418,14580,14744,14908,15074,15240,15406,15575,15745,15915,16087,16261,16435,16610,16786,16963,17140,17318,17497,17676,17856,18038,18221,18404,18586,18772,18959,19145,19333,19523,19713,19906,20101,20295,20489,20686,20882,21078,21276,21474,21673,21874,22075,22277,22479,22682,22888,23094,23300,23509,23720,23929,24142,24356,24568,24783,24999,25215,25432,25650,25868,26089,26309,26530,26753,26974,27197,27422,27648,27874,28103,28332,28560,28791,29024,29258,29492,29728,29965,30202,30441,30680,30919,31159,31400,31642,31886,32128,32372,32618,32864,33112,33361,33610,33861,34112,34365,34620,34877,35134,35392,35652,35910,36170,36431,36692,36954,37218,37482,37747,38012,38278,38546,38816,39084,39355,39626,39897,40171,40446,40721,41000,41280,41560,41841,42124,42405,42688,42972,43256,43541,43828,44115,44403,44691,44980,45271,45563,45853,46146,46440,46734,47030,47328,47626,47926,48229,48532,48835,49141,49446,49752,50059,50367,50675,50984,51295,51606,51918,52230,52543,52858,53173,53488,53805,54122,54440,54760,55081,55404,55728,56053,56380,56707,57036,57366,57697,58028,58360,58693,59026,59360,59696,60032,60369,60706,61044,61384,61724,62064,62406,62748,63090,63435,63781,64128,64477,64827,65177,65529,65883,66237,66593,66950,67307,67665,68024,68383,68743,69105,69467,69830,70193,70557,70923,71289,71655,72023,72391,72759,73129,73502,73875,74249,74625,75001,75377,75757,76137,76518,76900,77283,77667,78052,78438,78824,79211,79600,79989,80379,80769,81160,81553,81946,82339,82734,83129,83524,83921,84319,84718,85119,85521,85924,86327,86732,87139,87548,87955,88365,88777,89189,89602,90016,90430,90845,91262,91679,92097,92515,92934,93356,93776,94197,94620,95043,95467,95892,96318,96744,97173,97603,98033,98464,98897,99330,99767,100205,100643,101083,101524,101965,102407,102850,103293,103737,104183,104629,105076,105523,105971,106421,106871,107321,107773,108225,108677,109131,109586,110041,110498,110957,111416,111875,112337,112799,113264,113731,114199,114668,115138,115609,116080,116552,117025,117498,117972,118448,118924,119401,119878,120356,120836,121316,121796,122278,122760,123242,123726,124211,124696,125183,125671,126160,126649,127140,127633,128127,128621,129119,129618,130117,130617,131119,131621,132124,132628,133132,133637,134144,134651,135159,135667,136176,136687,137198,137710,138223,138736,139249,139764,140280,140796,141314,141833,142352,142872,143394,143916,144441,144966,145492,146022,146552,147082,147615,148149,148683,149218,149754,150290,150827,151366,151905,152445,152985,153526,154069,154612,155155,155700,156245,156790,157337,157885,158433,158983,159534,160085,160637,161191,161745,162301,162858,163416,163976,164538,165100,165664,166229,166795,167362,167930,168499,169068,169638,170210,170782,171355,171928,172502,173078,173654,174230,174808,175386,175964,176544,177125,177706,178289,178873,179457,180041,180627,181214,181803,182392,182984,183577,184170,184765,185362,185959,186558,187159,187760,188362,188965,189568,190172,190778,191384,191991,192598,193206,193816,194426,195036,195648,196260,196872,197486,198101,198716,199333,199951,200569,201187,201807,202427,203050,203673,204297,204924,205551,206178,206809,207441,208073,208706,209342,209978,210615,211253,211891,212530,213171,213812,214454,215096,215739,216384,217029,217674,218321,218968,219615,220264,220914,221564,222216,222869,223522,224175};

int dp[705][705*705];//dp[i][j]=1表示存在i条直线交点方案数为j

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for(int i = 1; i <= 700; i++)dp[i][0] = 1;
    for(int i = 2; i <= 700; i++){
        for(int j = 0; j <= i; j++){
            //int mx = (i*(i-1))/2+1;
            for(int k = 0; (i-j)*j+k <= ed[i]; k++){
                if(dp[j][k]==1){
                    dp[i][(i-j)*j+k]=1;
                }
            }
        }
    }
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;

        int cnt = 0;
        int mx = n*(n-1)/2+1;
        for(int i = 0; i <= mx; i++){
            if(dp[n][i]==1){
                cout<<i<<" ";
                cnt++;
                if(i==ed[n]){
                    break;
                }
            }
        }
        int i = cnt+1,j=ed[n]+1;
        for( ; i < big[n]; i++,j++){
            cout<<j<<" ";
        }
        cout<<j;
        cout<<"\n";
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45