题解合集(2024年）

用于记录日常刷题练习的值得收藏的题,并给出题解

比赛等题目不在此贴记录,比赛题目另起一贴

模拟和高精度

函数与结构体

P2415 集合求和

给定一个集合 $s$（集合元素数量 $\le 30$），求出此集合所有子集元素之和。

子集为：$\varnothing, { 2 }, { 3 }, { 2, 3 }$，和为 $2 + 3 + 2 + 3 = 10$。

对于 $100 %$ 的数据，$1 \le \lvert s \rvert \le 30$，$1 \le s_i \le 1000$，$s$ 所有子集元素之和 $\le {10}^{18}$。

先选出指定的一个元素，加入子集；

首先，当子集里只有一个元素时，在其他剩余的元素中不能选出任何元素加入到子集中，所以对于每个元素来说，均有 $C_{n-1}^0$ 次被选中。

当子集里有 2 个元素时，在其他剩余的元素中选出 1 个元素加入到子集中，所以对于每个元素来说，均有 $C_{n-1}^1$ 次被选中。

当子集里有 3 个元素时，在其他剩余的元素中选出 2 个元素加入到子集中，所以对于每个元素来说，均有 $C_{n-1}^2$ 次被选中。

当子集里有 $i\ (i\leq n)$ 个元素时，在其他剩余的元素中选出 $i-1$ 个元素加入到子集中，所以对于每个元素来说，均有 $C_{n-1}^{i-1}$ 次被选中。

所以共有 $\sum_{i=1}^{n} {C_{n-1}^{i-1}}$ 次被选中，即 $2^{n-1}$ 次被选中。

也可以这样考虑：如果要选中 $x$，剩下的元素都可选可不选，所以总共有 $2^{n-1}$ 种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

int num[31],i=0,j;
long long s=0;

int main(){
	while(cin>>num[i++]);
	for(j=0;j<i;j++){
		s+=num[j];
	}
	s*=pow(2,i-2);
	cout<<s;
	return 0;
}

P1304 哥德巴赫猜想

输入一个偶数 $N$，验证 $4\sim N$ 所有偶数是否符合哥德巴赫猜想：任一大于 $2$ 的偶数都可写成两个质数之和。如果一个数不止一种分法，则输出第一个加数相比其他分法最小的方案。例如 $10$，$10=3+7=5+5$，则 $10=5+5$ 是错误答案。

输入格式

第一行输入一个正偶数 $N$

输出格式

输出 $\dfrac{N-2}{2}$ 行。对于第 $i$ 行：

首先先输出正偶数 $2i+2$，然后输出等号，再输出加和为 $2i+2$ 且第一个加数最小的两个质数，以加号隔开。

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
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

bool prime[10001];
//埃氏筛
void ai()
{
    for (int p = 2; p * p <= 10000; p++)
    {
        if (prime[p])
        {
            for (int i = p * p; i <= 10000; i += p)
            {
                prime[i] = 0;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    memset(prime, 1, sizeof(prime));
    //筛出10000以内的质数备用
    ai();
    //循环次数f，不知道为什么放在i<=后面不行
    int f=(n-2)/2;
    for (int i = 1; i <= f; i++)
    {
        //先输出开头数字和等号
        cout << i * 2 + 2 << "=";
        for (int k = 2; k <= 10000; k++)
        {
            int last=0;
            //从小到大，如果循环到的数字是质数
            if (prime[k])
            {
                //计算出另个一加数
                last = i * 2 + 2 - k;
                //如果另一个加数也是质数
                if (prime[last])
                {
                    cout << k << "+" << last << endl;
                    break;
                }
            }
        }
    }
    return 0;
}
//24.11.3 完全是自己写的，没有看题解，一开始备选的质数在5000以为够用了，但是第一个测试点错了，于是把备选该到了10000。最后AC，非常开心。

字符串

P1598 垂直柱状图

【本题知识点】：模拟、max_element指针

写一个程序从输入文件中去读取四行大写字母（全都是大写的，每行不超过 $100$ 个字符），然后用柱状图输出每个字符在输入文件中出现的次数。严格地按照输出样例来安排你的输出格式。

输入格式

四行字符，由大写字母组成，每行不超过 $100$ 个字符

输出格式

由若干行组成，前几行由空格和星号组成，最后一行则是由空格和字母组成的。在任何一行末尾不要打印不需要的多余空格。不要打印任何空行。

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
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

int main(){
    int num[26]={0};
    int* maxn;//maxn储存最大的字母
    string s;
    //循环4次整行输入
    for (int i = 0; i < 4; i++)
    {
        getline(cin,s);
        //遍历一行记录字母的次数
        for (auto i:s)
        {
            if(i>='A'&&i<='Z'){
            // cout<<i-'A'<<endl;
            num[i-'A']++;
            }
        }
    }
    //找到数组里最大的数
    //方法一，遍历数组
    // for (int i = 0; i < 26; i++)
    // {
    //     maxn=(maxn,num[i]);
    // }
    // 方法二，max_element函数
    maxn=max_element(num,num+26);
    // cout<<*maxn;
    
    //开始模拟输出
    //循环maxn行
    for (int i = *maxn; i >0 ; i--)
    {
        //循环26列
        for (int j = 0; j < 26; j++)
        {
            //如果出现的次数达到从maxn开始一行递减则输入*，否则输出空格
            if(num[j]>=i){
                cout<<"* ";
            }
            else{
                cout<<"  ";
            }
        }
        cout<<endl;
    }
    //输出字母
    for (int i = 0; i < 26; i++)
    {
        cout<<char(i+'A')<<" ";
    }
    
    return 0;
}

P1603 斯诺登的密码

【本题知识点】：map容器

2013 年 X 月 X 日，俄罗斯办理了斯诺登的护照，于是他混迹于一架开往委内瑞拉的飞机。但是，这件事情太不周密了，因为 FBI 的间谍早已获悉他的具体位置——但这不是最重要的——最重要的是如果要去委内瑞拉，那么就要经过古巴，而经过古巴的路在美国的掌控之中。

丧心病狂的奥巴马迫降斯诺登的飞机，搜查时却发现，斯诺登杳无踪迹。但是，在据说是斯诺登的座位上，发现了一张纸条。纸条由纯英文构成：Obama is a two five zero.（以 . 结束输出，只有 $6$ 个单词+一个句号，句子开头如没有大写亦为合法）这句话虽然有点无厘头，但是警官陈珺骛发现这是一条极其重要的线索。他在斯诺登截获的一台笔记本中找到了一个 C++ 程序，输入这条句子后立马给出了相对应的密码。陈珺鹜高兴得晕了过去，身为警官的你把字条和程序带上了飞机，准备飞往曼哈顿国际机场，但是在飞机上检查的时候发现——程序被粉碎了！飞机抵达华盛顿只剩 $5$ 分钟，你必须在这 $5$ 分钟内编写（杜撰）一个程序，免受上司的 $10000000000 \bmod 10$ 大板。破译密码的步骤如下：

（1）找出句子中所有用英文表示的数字 $(\leq 20)$，列举在下：

正规：one two three four five six seven eight nine ten eleven twelve
thirteen fourteen fifteen sixteen seventeen eighteen nineteen twenty

非正规：a both another first second third。为避免造成歧义，another 算作 $1$ 处理。

（2）将这些数字平方后对 $100$ 取模，如 $00,05,11,19,86,99$。

（3）把这些两位数按数位排成一行，组成一个新数，如果开头为 $0$，就去 $0$。

（4）找出所有排列方法中最小的一个数，即为密码。

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
#include <bits/stdc++.h>
using namespace std;
//map打表
map<string,int>q;
int cnt=0;//记录个数
int num[100];//数字存入数组
string s;

int main(){
    q["one"]=1;q["two"]=2;q["three"]=3;q["four"]=4;q["five"]=5;q["six"]=6;q["seven"]=7;q["eight"]=8;q["nine"]=9;q["ten"]=10;
    q["eleven"]=11;q["twelve"]=12;q["thirteen"]=13;q["fourteen"]=14;q["fifteen"]=15;q["sixteen"]=16;q["seventeen"]=17;q["eighteen"]=18;q["nineteen"]=19;q["twenty"]=20;
    q["a"]=1;q["both"]=2;q["another"]=1;q["first"]=1;q["second"]=2;q["third"]=3;
    //打表
    for (int i = 1; i <= 6; i++)
    {
        cin>>s;
        if(q[s])//如果输入的单词对应map里面的数字
        {
            int k=q[s]*q[s]%100;
            // cout<<k<<endl;
            if(k==0) continue;//如果计算出来为0则不存入
            num[++cnt]=k;
        }
    }
    sort(num+1,num+cnt+1);
    cout<<num[1];//输入第一位不是两个字符
    for (int i = 2; i <= cnt; i++)
    {
        //数字位数不足，则在前面补零
        printf("%02d",num[i]);
    }
    return 0;
}
24.11.2

P1553 数字反转（升级版）

【本题知识点】：**反转函数reverse、除去前导后导零 **

给定一个数，请将该数各个位上数字反转得到一个新数。

这次与 NOIp2011 普及组第一题不同的是：这个数可以是小数，分数，百分数，整数。

  • 整数反转是将所有数位对调。

  • 小数反转是把整数部分的数反转，再将小数部分的数反转，不交换整数部分与小数部分。

  • 分数反转是把分母的数反转，再把分子的数反转，不交换分子与分母。

  • 百分数的分子一定是整数，百分数只改变数字部分。

STL版

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
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

//反转函数并去掉前导0
string reverse(string s){
    int count=0;
    reverse(s.begin(),s.end());
    for (int i = 0; i < s.size(); i++)
    {
        if(s[i]=='0') count++;
        else break;
    }
    //清除前导0
    s.erase(s.begin(),s.begin()+count);
    //特判如果全是0则返回0
    return (s!="" ? s:"0");
}

string deleteTail(string s){
    int count=0;
    for (int i = s.size()-1; i >=0; i--)
    {
        if(s[i]=='0') count++;
        else break;
    }
    s.erase(s.end()-count,s.end());
    //特判如果全是0则返回0
    return (s!="" ? s:"0");
}

int main() {
    string s;
    cin>>s;
    //先判断第一种情况，最后是百分号的情况
    //back()函数返回字符串最后一个
    if(s.back()=='%'){
        // cout<<s.substr(0,s.size()-1);
        cout<<reverse(s.substr(0,s.size()-1))<<"%";
    }
    
    //找到符号旁边的left和right
    else if(s.find(".")<s.size()){
        string left,right;
        left=s.substr(0,s.find("."));
        right=s.substr(s.find(".")+1);
        cout<<reverse(left)<<"."<<deleteTail(reverse(right));
    }
    else if(s.find("/")<s.size()){
        string left,right;
        left=s.substr(0,s.find("/"));
        right=s.substr(s.find("/")+1);
        cout<<reverse(left)<<"/"<<reverse(right);
    }
    //整数
    else cout<<reverse(s);
    
    return 0;
}

P1308 NOIP2011 普及组] 统计单词数

【本题知识点】：find函数，转换大小写

一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例 1），如果给定单词仅是文章中某一单词的一部分则不算匹配。

【输入格式】

共 $2$ 行。

第 $1$ 行为一个字符串，其中只含字母，表示给定单词；

第 $2$ 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

【输出格式】

一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从 $0$ 开始）；如果单词在文章中没有出现，则直接输出一个整数 $-1$。

注意：空格占一个字母位

【样例输入】

1
2
To
to be or not to be is a question

【样例输出】

1
2 0

【提示】

数据范围

$1\leq $ 第一行单词长度 $\leq10$。

$1\leq $ 文章长度 $\leq10^6$。

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
#include <bits/stdc++.h>
using namespace std;

string a,b;

int main() {
    cin>>a;
    getchar();//处理回车
    //输入一行
    getline(cin,b);
    //转换为小写
    transform(a.begin(),a.end(),a.begin(),::tolower);
    transform(b.begin(),b.end(),b.begin(),::tolower);
    //前后加空格方便查找
    a=" "+a+" ";
    b=" "+b+" ";
    //如果没有找到
    if(b.find(a)==-1)
    {
        cout<<"-1";
    }
    else {
        //sum总个数，n查找第几个
        int sum=0,n=0;
        while(b.find(a,n)!=-1) {
            sum++;
            n=b.find(a,n)+1;
        }
        cout<<sum<<" "<<b.find(a);
    }
    return 0;
}

P5734 【深基6.例6】文字处理软件

【题目描述】

你需要开发一款文字处理软件。最开始时输入一个字符串作为初始文档。可以认为文档开头是第 $0$ 个字符。需要支持以下操作：

  • 1 str：后接插入，在文档后面插入字符串 $\texttt{str}$，并输出文档的字符串；
  • 2 a b：截取文档部分，只保留文档中从第 $a$ 个字符起 $b$ 个字符，并输出文档的字符串；
  • 3 a str：插入片段，在文档中第 $a$ 个字符前面插入字符串 $\texttt{str}$，并输出文档的字符串；
  • 4 str：查找子串，查找字符串 $\texttt{str}$ 在文档中最先的位置并输出；如果找不到输出 $-1$。

为了简化问题，规定初始的文档和每次操作中的 $\texttt{str}$ 都不含有空格或换行。最多会有 $q$ 次操作。

【输入格式】

第一行输入一个正整数 $q$，表示操作次数。

第二行输入一个字符串 $\texttt{str}$，表示最开始的字符串。

第三行开始，往下 $q$ 行，每行表示一个操作，操作如题目描述所示。

【输出格式】

一共输出 $q$ 行。

对于每个操作 $1,2,3$，根据操作的要求输出一个字符串。

对于操作 $4$，根据操作的要求输出一个整数。

【提示】

数据保证，$1 \leq q\le 100$，开始的字符串长度 $\leq 100$。

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
#include <bits/stdc++.h>
using namespace std;

int n,opt;//n操作次数，opt选择操作
string ans,a1;//ans原始字符串和最后的答案
int a,b;

int main() {
    cin>>n>>ans;
    for(int i = 0; i < n; i++) {
        cin>>opt;
        if(opt==1)
        {
            cin>>a1;
            //在后面增加字符串直接用+
            ans+=a1;
            cout<<ans<<endl;
        }
        else if(opt==2) {
            cin>>a>>b;
            //substr(a,b)对字符串从a截取到b
            a1=ans.substr(a,b);
            ans=a1;
            cout<<ans<<endl;
        }
        else if(opt==3) {
            cin>>a>>a1;
            //insert(a,a1)从字符串的a位置插入字符串a1
            ans.insert(a,a1);
            cout<<ans<<endl;
        }
        else if(opt==4) {
            cin>>a1;
            //find(a1)找到a1的位置，如果没有找到，find返回的数会大于size
            if(ans.find(a1)<ans.size())
                cout<<ans.find(a1)<<endl;
            else
                cout<<-1<<endl;
        }

    }
    return 0;
}

P1957 口算练习题

王老师正在教简单算术运算。细心的王老师收集了 $i$ 道学生经常做错的口算题，并且想整理编写成一份练习。 编排这些题目是一件繁琐的事情，为此他想用计算机程序来提高工作效率。王老师希望尽量减少输入的工作量，比如 $\texttt{5+8}$ 的算式最好只要输入 $\texttt 5$ 和 $\texttt 8$，输出的结果要尽量详细以方便后期排版的使用，比如对于上述输入进行处理后输出 $\texttt{5+8=13}$ 以及该算式的总长度 $6$。王老师把这个光荣的任务交给你，请你帮他编程实现以上功能。

【输入格式】

第一行一个整数 $i$。

接着的 $i$ 行为需要输入的算式，每行可能有三个数据或两个数据。

若该行为三个数据则第一个数据表示运算类型，$\texttt a$ 表示加法运算，$\texttt b$ 表示减法运算，$\texttt c$ 表示乘法运算，接着的两个数据表示参加运算的运算数。

若该行为两个数据，则表示本题的运算类型与上一题的运算类型相同，而这两个数据为运算数。

【输出格式】

输出 $2\times i$ 行。对于每个输入的算式，输出完整的运算式及结果，第二行输出该运算式的总长度。

1
2
3
4
5
4
a 64 46
275 125
c 11 99
b 46 64
1
2
3
4
5
6
7
8
64+46=110
9
275+125=400
11
11*99=1089
10
46-64=-18
9

【数据规模与约定】

对于 $50%$ 的数据，输入的算式都有三个数据，第一个算式一定有三个数据。

对于所有数据，$0<i\leq 50$，运算数为非负整数且小于 $10000$。

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
#include<bits/std++.h>
using namespace std;

char a,s[105]={0},b[10];//s数组储存全部字符，b数组储存第一个输入，a记录运算符
int c,d;

int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>b;
        //判断输入的是字母还是数字
        if(b[0]>='a'&&b[0]<='c'){
            a=b[0];
            cin>>c>>d;
        }else{
            sscanf(b,"%d",&c);
            cin>>d;
        }
        //格式化输出
        if(a=='a')
            sprintf(s,"%d+%d=%d",c,d,c+d);
        else if(a=='b')
            sprintf(s,"%d-%d=%d",c,d,c-d);
        else if(a=='c')
            sprintf(s,"%d*%d=%d",c,d,c*d);
        cout<<s<<endl<<strlen(s)<<endl;
    }
}

循环结构

P5725【深基4.习8】求三角形

模仿例题，打印出不同方向的正方形，然后打印三角形矩阵。中间有个空行。

1
2
3
4
5
6
7
8
9
01020304
05060708
09101112
13141516

      01
    0203
  040506
07080910
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
46
47
48
#include<bits/stdc++.h>
using namespace std;

int main() {
	int n;cin>>n;
	//当前的数字cnt
	int cnt=1;
	//打印正方形
	//行数
	for (int i = 0; i < n; i++)
	{
		//列数
		for (int j = 0; j < n; j++)
		{
			printf("%02d",cnt);
			cnt++;
		}
		cout<<endl;
	}
	cout<<endl;
	//打印三角形
	//当前的数字cnt
	cnt=1;
	//当前要打印的数字的个数num1
	int num1=1;
	for (int i = 0; i < n; i++)
	{
		//记录空格数，每个数字占两格，空格数为n*2-数字个数num1*2
		int kg=num1*2;
		//打印空格，j=kg除去了数字占用的位置
		for (int j = kg; j < n*2; j++)
		{
			cout<<" ";
		}
		//定义num用于while
		int num=num1;
		while (num--)
		{
			printf("%02d",cnt);
			cnt++;
		}
		//下次要打印的数字的个数加一
		num1++;
		cout<<endl;
	}
	return 0;
}
//24.10.24

P1720 月落乌啼算钱（斐波那契数列）

算完钱后，月落乌啼想着：“你坑我！”于是当爱与愁大神问多少钱时，月落乌啼说了一堆乱码。爱与愁大神说：“算了算了，我只问第 $n$ 样菜价格多少？”月落乌啼写出了：

$$F_n=\dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

由于爱与愁大神学过编程，于是就用 $1$ 分钟的时间求出了 $F_n$ 的结果。月落乌啼为此大吃一惊。你能学学爱与愁大神求出 $F_n$ 的值吗？

对于所有数据：$0 \leq n\leq 48$。

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
f1=1;
f2=1;
f3=2;
f4=3;
f5=5;
fn=f[n-1]+f[n-2]

//题解一
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin>>n;
    long long a=1,b=1,c=0;
    for(int i=3;i<=n;i++){
    c=a+b;
    a=b;
    b=c;
    }
    cout<<c<<".00";
    return 0;
}
//题解二
int main()
{
    double f[50];
    int n,i;
    f[0]=0;
    f[1]=1;
    f[2]=1;   //递归边界条件
    scanf("%d",&n);
    for(i=3;i<=n;i++)
    f[i]=f[i-1]+f[i-2];  //开始使用斐波那契数列
    printf("%0.2f",f[n]); //输出，保留两位小数
    return 0;
}

P1075 [NOIP2012 普及组] 质因数分解

已知正整数 $n$ 是两个不同的质数的乘积，试求出两者中较大的那个质数。

$1 \le n\le 2\times 10^9$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    //满足要求的数有且只有一组质数相乘等于这个数，找出一个质数，就可以知道另一个质数
    //找到第一个小的质数，那么另一个大的质数就是n/这个质数了
    for(int i=2;i<=n;i++){
    if(n%i==0)
    {
    cout<<n/i;
    return 0;
    }
    }
    return 0;
}
//24.10.24

P2669 [NOIP2015 普及组] 金币

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 $n$ 天每天收到 $n$ 枚金币后，骑士会在之后的连续 $n+1$ 天里，每天收到 $n+1$ 枚金币。

请计算在前 $k$ 天里，骑士一共获得了多少金币。

1
2
3
4
## 输入格式
一个正整数 $k$，表示发放金币的天数。
## 输出格式
一个正整数，即骑士收到的金币数。

骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 $1+2+2+3+3+3=14$ 枚金币。

对于 $100%$ 的数据，$1\le k\le 10^4$。

1
2
3
4
5
6
7
8
9
10
11
12
13
//题解一
#include<iostream>
using namespace std;
int main()
{
	int a,b=0,c=1,i;//a为天数，b为金币，c为每天比原来每天多获得的金币数 
	cin>>a;
	for(i=1;i<=a;i++)
		a-=i,b+=c*c,c++;//金币每天加上c的2次方，天数当然要减i了
	cout<<b+a*c;//最后算上剩余的a乘加的最多一次的c
	return 0;
}
//24.10.22 没看懂
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
//题解二
#include<bits/stdc++.h>
using namespace std;

int main()
{
   //k为发放金币的天数
   //day为往后数day天获得的金币为money个
   //sum获得金币的总数
   //money：每天能获得的金币数量
   int k,day,sum=0,money;
   cin>>k;
   day=money=1;
   for (int i = 1; i <= k; i++)//要发k天金币
   {
      sum+=money;
      day--;//已经发了一天金币
      if(day==0){
         money++;//进入下一个周期前，金币数加一
         day=money;//如果该周期发完了则进入下一个周期，每天发money个金币
      }
   }
   cout<<sum;
   return 0;
}
//24.10.22

【筛质数】 P5723 【深基4.例13】质数口袋

小 A 有一个质数口袋，里面可以装各个质数。他从 $2$ 开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。

口袋的负载量就是口袋里的所有数字之和。

但是口袋的承重量有限，装的质数的和不能超过 $L$。给出 $L$，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数的个数，数字之间用换行隔开。

数据保证，$1 \le L \le {10}^5$。

筛法合集

  • 枚举法（试除法）
  • 埃拉托斯特尼筛法（Sieve of Eratosthenes）
  • 线性筛法（Linear Sieve）
  • 奇数筛法
  • 欧拉筛法（Euler Sieve）

前置题：P3383 【模板】线性筛素数

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
#include<bits/stdc++.h>
using namespace std;
int n,x;
long long sum=0;
int pd(int y) {
	for(int i=2; i*i<=y; ++i) {
		if(y%i==0) return 0;
	}
	return 1;
}
int main() {
	scanf("%d",&n);
	if(n<2) {
		printf("0\n");
		return 0;
	} else if(n==2) {
		printf("2\n1\n");
		return 0;
	}
	for(int i=2; i<=n; ++i) {
		if(i%2==0&&i!=2) continue;
		if(sum+i>n) {
			printf("%d\n",x);
			return 0;
		}
		if(pd(i)) {
			printf("%d\n",i);
			sum+=i;
			x++;
		}
	}
	return 0;
}
//24.10.22 未看懂
  • 用埃氏筛筛出100000以内的质数以备用。
  • 输入完之后，从最小的质数开始，然后第2小，第3小……由小往大，只要是质数都取，一直取到和超过𝐿L为止。

时间复杂度$Θ(𝑛log⁡log⁡𝑛)$，当$n$取到最大的100000时，也就Θ(70000)左右，足以通过本题。

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
#include<bits/stdc++.h>
using namespace std;

bool prime[100000];
int cnt,L;

//埃氏筛
void ai(){
   for(int i=2;i<=100000;++i){
      if(prime[i])
         for(int j=i*2;j<=100000;j+=i)
            prime[j]=0;
   }
}


int main()
{
   cin>>L;
   memset(prime,1,sizeof(prime));//初始化数组
   ai();
   for (int i = 2; i <=L; ++i){
      if(prime[i]){
         cout<<i<<endl;
         cnt++;
         L -= i;//质数的总和小于L
      }
   }
   cout<<cnt;
   return 0;
}
//24.10.22