文章目录
蓝桥杯日期统计特殊日期(位数之和)2023特殊日期(倍数)跑步锻炼
蓝桥杯
日期统计
日期统计
如果暴力枚举100个数的八次循环那就是1016次运算,时间复杂度太高了,好在前四次的2023是确定的,所以我们优化一下,前四次循环不等于2023的就直接进入下一个循环,现在只需要108次运算了,注意有不少日子是重复的,所以还需要我们使用set去重一下。
也可以不使用set,我们之间对2023年的365天遍历,如果数组中有满足2023年日期范围的数我们直接++,这样不仅减少了循环的次数(一共需要大概365*100=36500次循环),也避免了去重。
#include
using namespace std;
#if 0
int main()
{
int arr[100] = {
5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3
};
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
set
for(int i=0;i<100;i++)
{
if(arr[i]!=2) continue;
for(int j=i+1;j<100;j++)
{
if(arr[j]!=0) continue;
for(int k=j+1;k<100;k++)
{
if(arr[k]!=2) continue;
for(int l=k+1;l<100;l++)
{
if(arr[l]!=3) continue;
for(int a=l+1;a<100;a++)
{
for(int b=a+1;b<100;b++)
{
for(int c=b+1;c<100;c++)
{
for(int d=c+1;d<100;d++)
{
int date=arr[a]*1000+arr[b]*100+arr[c]*10+arr[d];
int month=arr[a]*10+arr[b];
int day=arr[c]*10+arr[d];
if(month>=1&&month<=12&&day>=1&&day<=months[month])
{
ret.insert(date);
//cout< } } } } } } } } } cout< return 0; } #endif #if 1 int main() { int arr[100] = { 5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3 }; int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int ret = 0; for (int month=1;month<=12;month++) { for(int day=1;day { int target[8]={2,0,2,3,month/10,month%10,day/10,day%10}; int count=0; for(int i=0;i<100;i++) { if(arr[i]==target[count]) { count++; } if(count==8) { ret++; break; } } } } cout< return 0; } #endif 特殊日期(位数之和) 特殊日期 我们根据题意直接暴力即可,注意一下闰年的判断year%400==0||(year%4==0&&year%100!=0) 继续将年份的数字之和和月份天数的日子和做比较。 #include using namespace std; int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; void is_gap_month(int year,int month) { if(month==2&&year%400==0||(year%4==0&&year%100!=0)) months[2]=29; else months[2]=28; } int is_target(int year,int month,int day) { int sum1=0,sum2=0; while(year) { int cnt=year%10; sum1+=cnt; year/=10; } sum2=month/10+month%10+day/10+day%10; return sum1==sum2?1:0; } int main() { int ret=0; for(int year=1900;year<=9999;year++) { for(int month=1;month<=12;month++) { is_gap_month(year,month); for(int day=1;day<=months[month];day++) { if(is_target(year,month,day)) { ret++; } } } } cout< return 0; } 2023 2023 将每一个数从后向前依次取下末尾的数字,依次和3 2 0 2进行比较,如果这个数中完全包含2023,ret++。最后将所有的数减去完全包含的数,剩下的就是完全不包含的数,注意这里 98765432 - 12345678 之后还要加一。 #include using namespace std; int is_target(int n) { while (n) { int tmp1 = n % 10; n /= 10; if (tmp1 == 3) { while (n) { int tmp2 = n % 10; n /= 10; if (tmp2 == 2) { while (n) { int tmp3 = n % 10; n /= 10; if (tmp3 == 0) { while (n) { int tmp4 = n % 10; n /= 10; if(tmp4 == 2) return 1; } } } } } } } return 0; } int main() { int ret = 0; for (int i = 12345678; i <= 98765432; i++) { if (is_target(i)) { //cout< ret++; } } cout << 98765432 - 12345678 - ret+1; //cout<<"85959030"; return 0; } 特殊日期(倍数) 特殊日期 #include using namespace std; int main() { int ret=0; int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; for(int year=2000;year<=2000000;year++) { for(int month=1;month<=12;month++) { if(year%month==0) { if(month==2&&(year%400==0||(year%4==0&&year%100!=0))) { months[2]=29; } else { months[2]=28; } for(int day=1;day<=months[month];day++) { if(year%day==0) { ret++; } if(year==2000000&&month==1&&day==1) { cout< } } } } } //cout<<"35813063"< return 0; } 跑步锻炼 跑步锻炼 #include using namespace std; int is_gap_year(int n) { if((n%400==0)||(n%4==0&&n%100!=0)) return 1; else return 0; } int main() { int ret=0; int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int year=0,month=0,day=0; int week=6; for(int i=2000;i<=2020;i++) { for(int j=1;j<=12;j++) { if(j==2&&is_gap_year(i)) months[2]=29;else months[2]=28; for(int k=1;k<=months[j];k++) { if(week==8) { week=1; } if(week==1||k==1) { ret+=2; } else { ret+=1; } week++; if(i==2020&&j==10&&k==1) cout< } } } return 0; } 参考文章
发表评论