首页 > 其他分享 >P1028 [NOIP2001 普及组] 数的计算

P1028 [NOIP2001 普及组] 数的计算

时间:2024-05-04 20:25:32浏览次数:30  
标签:普及 NOIP2001 int 数为 namespace long 后加 include P1028

题目链接:

观察样例。当输入 \(n=6\) 时,6 本身算一个。当 6 后加的数为 1 时只有一个。6 后加的数为 2 时有 6 2,6 2 1 两个。6 后加的数为 3 时有 6 3、6 3 1 两个。可以看到,我们往 \(n\) 后加的每一个不超过 \(\dfrac{n}{2}\) 的数都可以继续延伸。

考虑递推。\(f[i]\) 表示以 \(i\) 为起点的合法数列数量。有

f[1] = 1
f[2] = f[1] + 1 = 2
f[3] = f[1] + 1 = 2
f[4] = f[1] + f[2] + 1 = 4
f[5] = f[1] + f[2] + 1 = 4
......

因此可以得出以下代码:

#include <bits/stdc++.h>

using namespace std;

int f[1010];

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i / 2; j++) {
			f[i] += f[j];
		}
		f[i]++;//本身也算一个
	}
	cout << f[n];
	return 0;
}

其实本题也可以通过打表解决。
首先写出暴力搜索的程序,再枚举 \(1\sim1000\) 的答案并输出即可(实在没办法才这么做)

#include <bits/stdc++.h>

using namespace std;

long long dfs(int n) {
	long long cnt = 1;
    if (n == 1) return cnt;
    for (int i = 1; i <= n / 2; i++) {
        cnt += f(i);
    }
    return cnt;
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
    for (int i = 1; i <= 1000; i++) cout << dfs(i) << ",";
    return 0;
}

打表时几点注意事项

  1. 每行都要敲回车,不然会编译错误

  2. 数组开头补 \(0\)

#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	/*以下为打表核心,可能要费力敲一下回车*/ 
    int a[1003]={0,1,2,2,4,4,6,6,10,10,14,14,20,20,26,26,36,36,46,46,60,60,74,74,94,94
    ,114,114,140,140,166,166,202,202,238,238,284,284,330,330,390,390,450,450,524,
    524
    ,598,598,692,692,786,786,900,900,1014,1014,1154,1154,1294,1294,1460,1460,1626,
    1626,1828,1828,2030,2030,2268,2268,2506,2506,2790,2790,3074,3074,3404,3404,3734,
    3734,4124,4124,4514,4514,4964,4964,5414,5414,5938,5938,6462,6462,7060,7060,7658,
    7658,8350,8350,9042,9042,9828,9828,10614,10614,11514,11514,12414,12414,13428,
    13428
    ,14442,14442,15596,15596,16750,16750,18044,18044,19338,19338,20798,20798,22258,
    22258,23884,23884,25510,25510,27338,27338,29166,29166,31196,31196,33226,33226,
    35494,35494,37762,37762,40268,40268,42774,42774,45564,45564,48354,48354,51428,
    51428
    ,54502,54502,57906,57906,61310,61310,65044,65044,68778,68778,72902,72902,77026,
    77026,81540,81540,86054,86054,91018,91018,95982,95982,101396,101396,106810,106810
    ,112748,112748,118686,118686,125148,125148,131610,131610,138670,138670,145730,
    145730,153388,153388,161046,161046,169396,169396,177746,177746,186788,186788,
    195830,195830,205658,205658,215486,215486,226100,226100,236714,236714,248228,248228,
    259742,259742,272156,272156,284570,284570,297998,297998,311426,311426,325868,
    325868,340310,340310,355906,355906,371502,371502,388252,388252,405002,405002,423046,
    423046,441090,441090,460428,460428,479766,479766,500564,500564,521362,521362,
    543620,543620,565878,565878,589762,589762,613646,613646,639156,639156,664666,664666
    ,692004,692004,719342,719342,748508,748508,777674,777674,808870,808870,840066,
    840066,873292,873292,906518,906518,942012,942012,977506,977506,1015268,1015268,
    1053030,1053030,1093298,1093298,1133566,1133566,1176340,1176340,1219114,1219114,
    1264678,1264678,1310242,1310242,1358596,1358596,1406950,1406950,1458378,1458378,
    1509806,1509806,1564308,1564308,1618810,1618810,1676716,1676716,1734622,1734622,
    1795932,1795932,1857242,1857242,1922286,1922286,1987330,1987330,2056108,2056108,
    2124886,2124886,2197788,2197788,2270690,2270690,2347716,2347716,2424742,2424742,
    2506282,2506282,2587822,2587822,2673876,2673876,2759930,2759930,2850948,2850948,
    2941966,2941966,3037948,3037948,3133930,3133930,3235326,3235326,3336722,3336722,
    3443532,3443532,3550342,3550342,3663090,3663090,3775838,3775838,3894524,3894524,
    4013210,4013210,4138358,4138358,4263506,4263506,4395116,4395116,4526726,4526726,
    4665396,4665396,4804066,4804066,4949796,4949796,5095526,5095526,5248914,5248914,
    5402302,5402302,5563348,5563348,5724394,5724394,5893790,5893790,6063186,6063186,
    6240932,6240932,6418678,6418678,6605466,6605466,6792254,6792254,6988084,6988084,
	7183914,7183914,7389572,7389572,7595230,7595230,7810716,7810716,8026202,8026202,
	8252302,8252302,8478402,8478402,8715116,8715116,8951830,8951830,9200058,9200058,
	9448286,9448286,9708028,9708028,9967770,9967770,10239926,10239926,10512082,10512082,
	10796652,10796652,11081222,11081222,11379220,11379220,11677218,11677218,
    11988644,11988644,12300070,12300070,12625938,12625938,12951806,12951806,13292116,
    13292116,13632426,13632426,13988332,13988332,14344238,14344238,14715740,14715740,
	15087242,15087242,15475494,15475494,15863746,15863746,16268748,16268748,16673750,
	16673750,17096796,17096796,17519842,17519842,17960932,17960932,18402022,18402022,
	18862450,18862450,19322878,19322878,19802644,19802644,20282410,20282410,20782974,
	20782974,21283538,21283538,21804900,21804900,22326262,22326262,22869882,22869882,
	23413502,23413502,23979380,23979380,24545258,24545258,25135020,25135020,25724782,
	25724782,26338428,26338428,26952074,26952074,27591230,27591230,28230386,28230386,
	28895052,28895052,29559718,29559718,30251722,30251722,30943726,30943726,31663068,
	31663068,32382410,32382410,33130918,33130918,33879426,33879426,34657100,
    34657100,35434774,35434774,36243644,36243644,37052514,37052514,37892580,37892580,
    38732646,38732646,39605938,39605938,40479230,40479230,41385748,41385748,42292266,
	42292266,43234278,43234278,44176290,44176290,45153796,45153796,46131302,46131302,
	7146570,47146570,48161838,48161838,49214868,49214868,50267898,50267898,51361196,
	51361196,52454494,52454494,53588060,53588060,54721626,54721626,55897966,55897966,
	57074306,57074306,58293420,58293420,59512534,59512534,60777212,60777212,62041890,
    62041890,63352132,63352132,64662374,64662374,66020970,66020970,67379566,67379566
    ,68786516,68786516,70193466,70193466,71651844,71651844,73110222,73110222,74620028,
	74620028,76129834,76129834,77694142,77694142,79258450,79258450,80877260,80877260,
	82496070,82496070,84172786,84172786,85849502,85849502,87584124,87584124,89318746,
	89318746,91114678,91114678,92910610,92910610,94767852,94767852,96625094,96625094,
	98547380,98547380,100469666,100469666,102456996,102456996,104444326,104444326,106500434,
	106500434,108556542,108556542,110681428,110681428,112806314,112806314,115004102,115004102,
	117201890,117201890,119472580,119472580,121743270,121743270,124090986,124090986,126438702,
	126438702,128863444,128863444,131288186,131288186,133794468,133794468,136300750,136300750,
	138888572,138888572,141476394,141476394,144150270,144150270,146824146,146824146,149584076,
	149584076,152344006,152344006,155194954,155194954,158045902,158045902,160987868,160987868,
	163929834,163929834,166967782,166967782,170005730,170005730,173139660,173139660,176273590,
	176273590,179508916,179508916,182744242,182744242,186080964,186080964,189417686,189417686,
	192861218,192861218,196304750,196304750,199855092,199855092,203405434,203405434,207068524,
	207068524,210731614,210731614,214507452,214507452,218283290,218283290,222177814,222177814,
	226072338,226072338,230085548,230085548,234098758,234098758,238237116,238237116,242375474,
	242375474,246638980,246638980,250902486,250902486,255297602,255297602,259692718,259692718,
	264219444,264219444,268746170,268746170,273411566,273411566,278076962,278076962,282881028,
	282881028,287685094,287685094,292634890,292634890,297584686,297584686,302680212,302680212,
	307775738,307775738,313024652,313024652,318273566,318273566,323675868,323675868,329078170,
	329078170,334641518,334641518,340204866,340204866,345929260,345929260,351653654,351653654,
	357547444,357547444,363441234,363441234,369504420,369504420,375567606,375567606,381808538,
	381808538,388049470,388049470,394468148,394468148,400886826,400886826,407492292,407492292,
	414097758,414097758,420890012,420890012,427682266,427682266,434670350,434670350,441658434,
	441658434,448842348,448842348,456026262,456026262,463415834,463415834,470805406,470805406,
	478400636,478400636,485995866,485995866,493806582,493806582,501617298,501617298,509643500,
	509643500,517669702,517669702,525922004,525922004,534174306,534174306,542652708,542652708,
	551131110,551131110,559846226,559846226,568561342,568561342,577513172,577513172,586465002,
	586465002,595665060,595665060,604865118,604865118,614313404,614313404,623761690,623761690,
	633469718,633469718,643177746,643177746,653145516,653145516,663113286,663113286,673353212,
	673353212,683593138,683593138,694105220,694105220,704617302,704617302,715413954,715413954,
	726210606,726210606,737291828,737291828,748373050,748373050,759752270,759752270,771131490,
	771131490,782808708,782808708,794485926,794485926,806474570,806474570,818463214,818463214,
	830763284,830763284,843063354,843063354,855689292,855689292,868315230,868315230,881267036,
	881267036,894218842,894218842,907510958,907510958,920803074,920803074,934435500,934435500,
	948067926,948067926,962056258,962056258,976044590,976044590,990388828,990388828,1004733066
	,1004733066,1019448806,1019448806,1034164546,1034164546,1049251788,1049251788,1064339030,
	1064339030,1079814524,1079814524,1095290018,1095290018,1111153764,1111153764,1127017510,
	1127017510,1143286258,1143286258,1159555006,1159555006,1176228756,1176228756,1192902506,
	1192902506,1209999302,1209999302,1227096098,1227096098,1244615940,1244615940,1262135782,
	1262135782,1280096714,1280096714,1298057646,1298057646,1316459668,1316459668,1334861690,
	1334861690,1353724140,1353724140,1372586590,1372586590,1391909468,1391909468,1411232346,
	1411232346,1431034990,1431034990,1450837634,1450837634,1471120044,1471120044,1491402454,
	1491402454,1512185428,1512185428,1532968402,1532968402,1554251940,1554251940,1575535478,
	1575535478,1597340378,1597340378,1619145278,1619145278,1641471540,1641471540,1663797802,
	1663797802,1686667684,1686667684,1709537566,1709537566,1732951068,1732951068,1756364570,
	1756364570,1780343950,1780343950,1804323330,1804323330,1828868588,1828868588,1853413846,
	1853413846,1878548866,1878548866,1903683886,1903683886,1929408668,1929408668,1955133450,
	1955133450,1981471878,1981471878,2007810306};
    cout<<a[n];    //直接输出 
    return 0;
}

标签:普及,NOIP2001,int,数为,namespace,long,后加,include,P1028
From: https://www.cnblogs.com/pangyou3s/p/18172624

相关文章

  • P1010 [NOIP1998 普及组] 幂次方
    题目:P1010[NOIP1998普及组]幂次方[NOIP1998普及组]幂次方题目描述任何一个正整数都可以用2的幂次方表示。例如137=27+23+2^0。同时约定次方用括号来表示,即a^b可表示为a(b)。由此可知,137可表示为2(7)+2(3)+2(0)进一步:$7=22+2+20(2^1用2表示),并且3=2+2^......
  • 【题解】[NOIP2001 普及组] 装箱问题
    [NOIP2001普及组]装箱问题这是一道动态规划题。那就先定义状态吧(这里用的是一维滚动数组)。$f[j]$代表当我有$j$这么多容量可以用时,能装的最大重量是多少。好,状态定义好了再想状态转移方程。$f[j]$可以从哪里转移过来呢?想一想,当我们循环到第$i$个物品时,我们面临两个......
  • 洛谷题单指南-动态规划1-P1077 [NOIP2012 普及组] 摆花
    原题链接:https://www.luogu.com.cn/problem/P1077题意解读:n种花选m个的选法,每种花数量为ai。解题思路:设dp[i][j]表示前i种花选j个的选法对于第i种花,可以选0,1,2...min(ai,j)个则有递推式:dp[i][j]=∑dp[i-1][j-k],k取0,1,2...min(ai,j)初始化dp[0][0]=1100分代码:#incl......
  • 洛谷题单指南-动态规划1-P1049 [NOIP2001 普及组] 装箱问题
    原题链接:https://www.luogu.com.cn/problem/P1049题意解读:装尽可能多的物品,使得总体积越大越好,即剩余空间最小,还是一个01背包问题,物品的体积就是其价值。解题思路:01背包模版题,物品体积、价值相同,直接采用一维dp。100分代码:#include<bits/stdc++.h>usingnamespacestd;co......
  • P10282
    思路首先想到一个\(n^{4}\)的dp,观察数据范围,发现这应该是一个\(n^{3}\)的算法,考虑如何优化。首先把转移方程写出来\(dp_{i,j}=\sum_{0\leii\lei-1,0\lejj\lej-1,\overline{a_{ii+1}...a{i}}\le\overline{b_{jj+1}...b{j}}}dp_{ii,jj}\),发现都不太好优化。首先枚举\(i\),\(......
  • P10288 [GESP样题 八级] 区间
    原题链接题解本题的优化真的很重要!!把所有元素出现的下标用map套vector存起来,然后二分查找code#include<bits/stdc++.h>usingnamespacestd;map<int,vector<int>>mp;intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//缺一不可intt;ci......
  • P10289 [GESP样题 八级] 小杨的旅游 题解
    题目简述给定一棵树,节点之间的距离为$1$,树上有$k$个传送门,可以从一个传送门瞬间传送到另一个传送门,有$q$此询问,问$u$和$v$之间的最短距离是多少。题目分析首先考虑没有传送门,我们可以直接求两个点的LCA,再用高度容斥计算即可。如果有传送门,那么有用与不用两种选择,如......
  • P3956 [NOIP2017 普及组] 棋盘
    /*这题本身不难,但是我写难了就是一个bfs,没了但是我的写法恰好犯了一个错误hark数据35110211311220330答案是4而我能输出30-1-110-11-10原因是我先走到了(2,2)这时候......
  • 洛谷题单指南-数学基础问题-P1069 [NOIP2009 普及组] 细胞分裂
    原题链接:https://www.luogu.com.cn/problem/P1069题意解读:一个数s代表细胞经过一天分裂的个数,则经过t天后个数为st,要计算经过几天后能整除m1m2,也就是st%m1m2==0,有多个s,要计算天数最少就可以满足条件的。解题思路:直接求st%m1m2显然不可取,会超出整数最大范围,高精度也不是好......
  • 洛谷题单指南-数学基础问题-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
    原题链接:https://www.luogu.com.cn/problem/P1029题意解读:已知x,y,求有多少对p、q,使得p、q的最大公约数为x,最小公倍数为y。解题思路:枚举法即可。枚举的对象:枚举p,且p必须是x的倍数,还有p<=yq的计算:q=x*y/p,q要存在,必须x*y%p==0,且gcd(p,q)==x100分代码:#include......