蓝桥杯真题——洛谷 Day10 并查集（枚举）

目录

P8651 [蓝桥杯 2017 省 B] 日期问题

P8635 [蓝桥杯 2016 省 AB] 四平方和

---

P8651 [蓝桥杯 2017 省 B] 日期问题

思路：
使用scanf读入，枚举从1960到2059，若符合题目形式，加入答案，
从小到大输出：存入结构体，通过自定义排序后输出

知识点：结构体排序+sort()

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;struct Node
{int year,mou,day;//结构体重构，结构体排序，类似与sort函数中的cmp bool operator < (const Node &tmp) const{if(year!=tmp.year)return year<tmp.year;else if(mou!=tmp.mou)return mou<tmp.mou;elsereturn day<tmp.day;} 
};//结构体，统一保存数据 
//上面的结构体排序类似于以下：一般在主函数中加入sort(st,st.size(),cmp)
//bool cmp(Node a,Node b)
//{
//    if(a.year!=b.year)
//    return a.year<b.year;
//    ……………… 
// } 
int main()
{int x,y,z;scanf("%d/%d/%d",&x,&y,&z);//读入数据int mouth[]={0,31,28,31,30,31,30,31,31,30,31,30,31};//每个月的日期//对于2月，先假设为平年 set<Node> st;//使用set结构体存放数据，便于去重 for(int i=1960;i<=2059;i++)//枚举每一年{for(int j=1;j<=12;j++)//枚举每个月{if(i%400==0||(i%4==0&&i%100!=0))//判断是否为闰年mouth[2]=29; for(int k=1;k<=mouth[j];k++)//枚举对应月下的日 {if(i%100==x&&j==y&&k==z)//年/月/日st.insert({i,j,k});//存入合法日期if(j==x&&k==y&&i%100==z)//月/日/年st.insert({i,j,k});if(x==k&&y==j&&i%100==z)//日/月/年 st.insert({i,j,k});}mouth[2]=28;//恢复现场 } } //    sort(st,cmp);for(auto i:st){printf("%d-%02d-%02d\n",i.year,i.mou,i.day);} //%02d是为了补全前导0 return 0;} 

P8635 [蓝桥杯 2016 省 AB] 四平方和

 思路：
进行枚举
N<5x10^6，枚举每个数时开方，遍历一遍时间复杂度为：根号n
小优化：可以只用枚举前三个，不用枚举第四个，即将目标数减去枚举的前三个就可得出最后一个数

#include<iostream>
#include<cmath>
using namespace std;int main()
{int n;cin>>n;for(int i=0;i*i<=n;i++)//枚举第一个数，通过i*i<=n来实现开方枚举 {for(int j=0;i*i+j*j<=n;j++)//枚举第二个数 {for(int k=0;i*i+j*j+k*k<=n;k++)//枚举第三个数{int tmp=n-(i*i+j*j+k*k);int t=sqrt(tmp);if(t*t==tmp)//判断是否为平方数{cout<<i<<' '<<j<<' '<<k<<' '<<t<<endl;return 0;} } }}
}