A5555.三数和题解

叫我杨同学

2023-11-06 19:34:09

发布于：四川

70阅读

0回复

0点赞

A5555.三数和题解

思路

这个题的话有四种方法。

方法1：

枚举 $a,b,c$ ，计算是否等于 $n$ 且 $0 \lt a \lt b \lt c \leq n$ ，时间复杂度 $O(n^{3})$ ，期望得分 $60pts$ ,加了一点点不算优化的优化实际得分 $100pts$ 。

方法2：

枚举 $a,b$ ，计算 $c$ ，判断是否 $b \lt c \leq n$ ，时间复杂度 $O(n^{2})$ ，期望得分 $100pts$ 。做到这里就算正解了。

方法3：

通过缩减 $b$ 的枚举范围，发现 $b$ 缩减到 $\lceil {\frac{n-a}{2}} \rceil - 1 - a$ 的时候一定有一个 $c$ 符合条件， $a$ 枚举到 $\frac{n}{3}$ 即可，因为 $a > \frac{n}{3}$ 的时候方案数会变成负数。

所以归根结底就是求

$\sum ^{\lfloor \frac{n}{3} \rfloor-1} _ {i=1}\lceil {\frac{n-i}{2}} \rceil - 1 - i$

是多少。

时间复杂度 $O(n)$ ，期望得分 $100pts$ 。

方法4:

这个方法不推荐，用正确代码打表就可以了。时间复杂度 $O(1)$ ，期望得分 $100pts$ 。

代码

方法 1 代码

#include <iostream>
using namespace std;
int main(){
	int ans=0;
	int n;
	cin >> n;
	for (int a=1;a<=n;++a){
		for (int b=a+1;b<=n;++b){
			for (int c=b+1;c<=n;++c){
				if (a+b+c==n){
					++ans;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

方法 2 代码

#include <iostream>
using namespace std;
int main(){
	int ans=0;
	int n;
	cin >> n;
	for (int a=1;a<=n;++a){
		for (int b=a+1;b<=n;++b){
			int c=n-a-b;
			if (b<c){
				++ans;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

方法 3 代码

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	int n;
	cin >> n;
	int ans=0;
	for (int a=1;a<n/3;++a){
		ans+=ceil((n-a)/2.0)-1-a;
	}
	cout<<ans<<endl;
	return 0;
}

方法 4 代码

#include <iostream>
using namespace std;
int ans[]={0,0,0,0,0,0,1,1,2,3,4,5,7,8,10,12,14,16,19,21,24,27,30,33,37,40,44,48,52,56,61,65,70,75,80,85,91,96,102,108,114,120,127,133,140,147,154,161,169,176,184,192,200,208,217,225,234,243,252,261,271,280,290,300,310,320,331,341,352,363,374,385,397,408,420,432,444,456,469,481,494,507,520,533,547,560,574,588,602,616,631,645,660,675,690,705,721,736,752,768,784,800,817,833,850,867,884,901,919,936,954,972,990,1008,1027,1045,1064,1083,1102,1121,1141,1160,1180,1200,1220,1240,1261,1281,1302,1323,1344,1365,1387,1408,1430,1452,1474,1496,1519,1541,1564,1587,1610,1633,1657,1680,1704,1728,1752,1776,1801,1825,1850,1875,1900,1925,1951,1976,2002,2028,2054,2080,2107,2133,2160,2187,2214,2241,2269,2296,2324,2352,2380,2408,2437,2465,2494,2523,2552,2581,2611,2640,2670,2700,2730,2760,2791,2821,2852,2883,2914,2945,2977,3008,3040,3072,3104,3136,3169,3201,3234,3267,3300,3333,3367,3400,3434,3468,3502,3536,3571,3605,3640,3675,3710,3745,3781,3816,3852,3888,3924,3960,3997,4033,4070,4107,4144,4181,4219,4256,4294,4332,4370,4408,4447,4485,4524,4563,4602,4641,4681,4720,4760,4800,4840,4880,4921,4961,5002,5043,5084,5125,5167,5208,5250,5292,5334,5376,5419,5461,5504,5547,5590,5633,5677,5720,5764,5808,5852,5896,5941,5985,6030,6075,6120,6165,6211,6256,6302,6348,6394,6440,6487,6533,6580,6627,6674,6721,6769,6816,6864,6912,6960,7008,7057,7105,7154,7203,7252,7301,7351,7400,7450,7500,7550,7600,7651,7701,7752,7803,7854,7905,7957,8008,8060,8112,8164,8216,8269,8321,8374,8427,8480,8533,8587,8640,8694,8748,8802,8856,8911,8965,9020,9075,9130,9185,9241,9296,9352,9408,9464,9520,9577,9633,9690,9747,9804,9861,9919,9976,10034,10092,10150,10208,10267,10325,10384,10443,10502,10561,10621,10680,10740,10800,10860,10920,10981,11041,11102,11163,11224,11285,11347,11408,11470,11532,11594,11656,11719,11781,11844,11907,11970,12033,12097,12160,12224,12288,12352,12416,12481,12545,12610,12675,12740,12805,12871,12936,13002,13068,13134,13200,13267,13333,13400,13467,13534,13601,13669,13736,13804,13872,13940,14008,14077,14145,14214,14283,14352,14421,14491,14560,14630,14700,14770,14840,14911,14981,15052,15123,15194,15265,15337,15408,15480,15552,15624,15696,15769,15841,15914,15987,16060,16133,16207,16280,16354,16428,16502,16576,16651,16725,16800,16875,16950,17025,17101,17176,17252,17328,17404,17480,17557,17633,17710,17787,17864,17941,18019,18096,18174,18252,18330,18408,18487,18565,18644,18723,18802,18881,18961,19040,19120,19200,19280,19360,19441,19521,19602,19683,19764,19845,19927,20008,20090,20172,20254,20336,20419,20501,20584,20667,20750,20833,20917,21000,21084,21168,21252,21336,21421,21505,21590,21675,21760,21845,21931,22016,22102,22188,22274,22360,22447,22533,22620,22707,22794,22881,22969,23056,23144,23232,23320,23408,23497,23585,23674,23763,23852,23941,24031,24120,24210,24300,24390,24480,24571,24661,24752,24843,24934,25025,25117,25208,25300,25392,25484,25576,25669,25761,25854,25947,26040,26133,26227,26320,26414,26508,26602,26696,26791,26885,26980,27075,27170,27265,27361,27456,27552,27648,27744,27840,27937,28033,28130,28227,28324,28421,28519,28616,28714,28812,28910,29008,29107,29205,29304,29403,29502,29601,29701,29800,29900,30000,30100,30200,30301,30401,30502,30603,30704,30805,30907,31008,31110,31212,31314,31416,31519,31621,31724,31827,31930,32033,32137,32240,32344,32448,32552,32656,32761,32865,32970,33075,33180,33285,33391,33496,33602,33708,33814,33920,34027,34133,34240,34347,34454,34561,34669,34776,34884,34992,35100,35208,35317,35425,35534,35643,35752,35861,35971,36080,36190,36300,36410,36520,36631,36741,36852,36963,37074,37185,37297,37408,37520,37632,37744,37856,37969,38081,38194,38307,38420,38533,38647,38760,38874,38988,39102,39216,39331,39445,39560,39675,39790,39905,40021,40136,40252,40368,40484,40600,40717,40833,40950,41067,41184,41301,41419,41536,41654,41772,41890,42008,42127,42245,42364,42483,42602,42721,42841,42960,43080,43200,43320,43440,43561,43681,43802,43923,44044,44165,44287,44408,44530,44652,44774,44896,45019,45141,45264,45387,45510,45633,45757,45880,46004,46128,46252,46376,46501,46625,46750,46875,47000,47125,47251,47376,47502,47628,47754,47880,48007,48133,48260,48387,48514,48641,48769,48896,49024,49152,49280,49408,49537,49665,49794,49923,50052,50181,50311,50440,50570,50700,50830,50960,51091,51221,51352,51483,51614,51745,51877,52008,52140,52272,52404,52536,52669,52801,52934,53067,53200,53333,53467,53600,53734,53868,54002,54136,54271,54405,54540,54675,54810,54945,55081,55216,55352,55488,55624,55760,55897,56033,56170,56307,56444,56581,56719,56856,56994,57132,57270,57408,57547,57685,57824,57963,58102,58241,58381,58520,58660,58800,58940,59080,59221,59361,59502,59643,59784,59925,60067,60208,60350,60492,60634,60776,60919,61061,61204,61347,61490,61633,61777,61920,62064,62208,62352,62496,62641,62785,62930,63075,63220,63365,63511,63656,63802,63948,64094,64240,64387,64533,64680,64827,64974,65121,65269,65416,65564,65712,65860,66008,66157,66305,66454,66603,66752,66901,67051,67200,67350,67500,67650,67800,67951,68101,68252,68403,68554,68705,68857,69008,69160,69312,69464,69616,69769,69921,70074,70227,70380,70533,70687,70840,70994,71148,71302,71456,71611,71765,71920,72075,72230,72385,72541,72696,72852,73008,73164,73320,73477,73633,73790,73947,74104,74261,74419,74576,74734,74892,75050,75208,75367,75525,75684,75843,76002,76161,76321,76480,76640,76800,76960,77120,77281,77441,77602,77763,77924,78085,78247,78408,78570,78732,78894,79056,79219,79381,79544,79707,79870,80033,80197,80360,80524,80688,80852,81016,81181,81345,81510,81675,81840,82005,82171,82336,82502,82668,82834,83000,83167,83333,83500,83667,83834,84001,84169,84336,84504,84672,84840,85008,85177,85345,85514,85683,85852,86021,86191,86360,86530,86700,86870,87040,87211,87381,87552,87723,87894,88065,88237,88408,88580,88752,88924,89096,89269,89441,89614,89787,89960,90133,90307,90480,90654,90828,91002,91176,91351,91525,91700,91875,92050,92225,92401,92576,92752,92928,93104,93280,93457,93633,93810,93987,94164,94341,94519,94696,94874,95052,95230,95408,95587,95765,95944,96123,96302,96481,96661,96840,97020,97200,97380,97560,97741,97921,98102,98283,98464,98645,98827,99008,99190,99372,99554,99736,99919,100101,100284,100467,100650,100833,101017,101200,101384,101568,101752,101936,102121,102305,102490,102675,102860,103045,103231,103416,103602,103788,103974,104160,104347,104533,104720,104907,105094,105281,105469,105656,105844,106032,106220,106408,106597,106785,106974,107163,107352,107541,107731,107920,108110,108300,108490,108680,108871,109061,109252,109443,109634,109825,110017,110208,110400,110592,110784,110976,111169,111361,111554,111747,111940,112133,112327,112520,112714,112908,113102,113296,113491,113685,113880,114075,114270,114465,114661,114856,115052,115248,115444,115640,115837,116033,116230,116427,116624,116821,117019,117216,117414,117612,117810,118008,118207,118405,118604,118803,119002,119201,119401};
int main(){
	int n;
	cin >> n;
	cout<<ans[n]<<endl;
	return 0;
}