第十四届蓝桥杯 2023 C/C++组 日期统计

发布于:2025-04-23 ⋅ 阅读:(10) ⋅ 点赞:(0)

目录

题目:

题目描述:

题目链接:

思路:

核心思路:

思路详解:

set容器去重的原理:

代码:

代码详解:


题目:

题目描述:

题目链接:

日期统计

思路:

核心思路:

暴力优化+set去重

思路详解:

第一想法是暴力枚举,但是如果纯暴力枚举的话8个for循环嵌套还是很吓人的。由题找到的日期前四位都是2023,所以优化我们可以对前四位的每一位进行提前剪枝优化。再观察题目,题目特地把“不同”这两个字标黑,说明从前往后遍历可能存在相同的日期。为了达到相同的日期只统计一次,我们可以利用set容器去重

set容器去重的原理:

自动去重是set容器的特性,使用insert向容器set插入元素,insert会返回一个pair对象,其中first是一个迭代器,指向插入的元素(已经插入成功)或者已经存在的相同元素,second是一个布尔值,表示插入是否成功  eg:第一次插入"20230101"时insert会成功插入并返回true,第二次插入相同元素时,由于set中不允许有重复元素,插入会失败,返回false

代码:

代码详解:

#include<bits/stdc++.h> //这题给我一个教训就是暴力枚举也不是无脑暴力,像这题8个for循环,如果像我一 
using namespace std;    //开始那样把if全放到最内层的for里,运行时间过长看不到输出结果很搞心态
//因为肯定希望看到输出结果再来debug,一直看不到输出结果也不知道是还没运行完还是哪里语法出了错误
//这题是填空题,所以没有时间限制,能跑出答案就行,正确地在暴力过程中优化才能快速的输出结果
//一开始我把全部的if都放到了最内层的for中,由于没有提前终止条件,嵌套循环会尝试所有可能的组合,这可
//能会导致程序运行时间过长甚至看起来像是没有输出,实际上可能是由于计算量过大程序仍在运行中 
//通过多次设置提前终止条件,实际上235的输出结果的运行时间为1.1s左右,一开始甚至很久跑不出结果 

int ans;                                                   //显然2023年不是闰年 
int daysofmonth[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; //month从1开始,所以dayofmonth[0]=0 
set<string> valid_dates;  //使用set容器来存储合法的日期字符串,利用set的特性自动去重 

int main()
{
	string s="5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533";
	for(int a=0;a<100;a++)
	{
		if(s[a]!='2')  //设置提前终止条件 
		{
			continue;  //如果第一个字符不是'2'就结束当前循环,a++进入下一个循环 
		}
		for(int b=a+1;b<100;b++)
		{
			if(s[b]!='0')  //同理 
			{
				continue;
			}
			for(int c=b+1;c<100;c++)
			{
				if(s[c]!='2')  //同理 
				{
					continue;
				}
				for(int d=c+1;d<100;d++)
				{
					if(s[d]!='3')  //同理 
					{
						continue;
					}
					for(int e=d+1;e<100;e++)
					{
						for(int f=e+1;f<100;f++)
						{
							int month=(s[e]-'0')*10+(s[f]-'0'); //定义month,用s[e]和s[f]来计算 
							if(month<1||month>12) //上面定义month就是为了这里更简洁 
							{
								continue;
							}
							for(int g=f+1;g<100;g++)
							{
								for(int h=g+1;h<100;h++)
								{
									int day=(s[g]-'0')*10+(s[h]-'0'); //定义day,用s[g]和s[e]来计算 
									if(day>=1&&day<=daysofmonth[month]) //定义day更简洁 
									{
										string date="2023"+string(1,s[e])+string(1,s[f])+string(1,s[g])+string(1,s[h]);
										valid_dates.insert(date);
//使用insert向容器set插入元素,insert会返回一个pair对象,其中first是一个迭代器,指向插入的元素(已经
//插入成功)或者已经存在的相同元素,second是一个布尔值,表示插入是否成功  eg:第一次插入"20230101"时
//insert会成功插入并返回true,第二次插入相同元素时,由于set中不允许有重复元素,插入会失败,返回false 
									}
								}
							}
						}
					}
				}
			}
		}
	}
	cout<<valid_dates.size()<<endl;  //使用size方法获取set中元素的数量 
	return 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到