2020蓝桥杯省赛B组
1.回文日期
考点枚举+翻转
完整代码
#include<bits/stdc++.h> using namespace std; bool rn(int t){ if((t%4==0&&t%100!=0)||t%400==0)return true; return false; } 注意：是整体翻转不是年月日变成日月年！ bool f(int n,int y,int r){ int h=n*10000+y*100+r;//20100102 int p=h; int q=0; while(p){ q*=10; int j=p%10; p/=10; q+=j; } if(q==h)return true; return false; } int main() { int a;//起点 int b;//终点 cin>>a>>b; int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};考：每个月天数的表示 int c=a; int n=a/10000;//初始年 int y=(a/100)%100;//初始月 int r=a%100;//初始日 int ans=0; if(f(n,y,r))ans++; while(c!=b){ r++; if(rn(n)){ m[2]=29; } if(!rn(n)){ m[2]=28; } if(r>m[y]){ r=1; y++; } if(y>12){ y=1; n++; } if(f(n,y,r)){ ans++; } c=n*10000+y*100+r; } cout<<ans; // 请在此输入您的代码 return 0; }9.跑步锻炼
#include <iostream>
using namespace std;
bool rn(int t){
if((t%4==0&&t%100!=0)||t%400==0)return true;
return false;
}
int main()
{
int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//1.起点时间
int n1=2000;
int y1=1;
int r1=1;
//2.终点时间
int n2=2020;
int y2=10;
int r2=1;
int ans=2;//起点是一号
int w=6;
while(!(n1==n2&&y1==y2&&r1==r2)){
r1++;
w++;
if(w>7){
w=1;
}
if(rn(n1)){
m[2]=29;
}
if(!rn(n1)){
m[2]=28;
}
if(r1>m[y1]){
r1=1;
y1++;
}
if(y1>12){
y1=1;
n1++;
}
if(r1==1||w==1){
ans+=2;
}
else{
ans+=1;
}
}
cout<<ans;
// 请在此输入您的代码
return 0;
}
总结：T1,9考日期处理
3.成绩统计
完整代码：
#include<bits/stdc++.h> using namespace std; int n; int jg; int yx; int grade; int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>grade; if(grade>=60)jg++; if(grade>=85)yx++; } double a=100.0*jg/n; cout<<round(a)<<"%"<<endl; double c=100.0*yx/n; cout<<round(c)<<"%"<<endl; return 0; }本题考点总结：
与数字有关库函数
round()对小数进行四舍五入取整
floor对小数进行向下取整如：floor（99.8）为99
ceil对小数向上取整如：ceil(99.1)为100
5.门牌制作
#include <iostream> using namespace std; int main() { cout<<624; // 请在此输入您的代码 return 0; } /* 计算思路
#include <iostream> using namespace std; int main() { int ans=0; //数字分离 for(int i=1;i<=2020;i++){ int b=i; while(b) { if(b%10==2)ans++; b/=10; } } cout<<ans; // 请在此输入您的代码 return 0; }*/
6.既约分数
考点最大公因数算法gcd
7.蛇形数组
法一：直接手绘！
法二：编程
考察：分析
答案解析：
#include <iostream> using namespace std; int main() { int row=1,col=1,flag=1,num=1;//初始那个1在第一行第一列，并且现在是第一个数故num=1，flag做标记用来计算位移 while(true){ if(row==1){//到第一行，切实上升过程的第一行，那么列++，并且flag变成1因为等会要往左下走！并且将下个数算进去num++ col++;flag=1;num++; } if(col==1){//第一列且为下降列，那么行++，并且flag变为-1，接下来往右上走，将下一个数算入num++ row++;flag=-1;num++; } row+=flag;col-=flag;num++;//蛇形填数 if(row==20&&col==20) break;//找到第二十行第二十列那个数 } cout<<num; return 0; }完整代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int row=1,col=1,flag=1,num=1;
while(true){
if(row==1){
col++;
flag=1;
num++;
}
if(col==1){
row++;
flag=-1;
num++;
}
row+=flag;col-=flag;num++;//蛇形填数
if(row==20&&col==20)break;
}
cout<<num;
return 0;
}
8.七段码
是否连成一片：考察并查集算法-->连通性问题
并查集算法
并查集
用于解决合并集合以及判断两个元素是否位于同一集合。
p[x]表示x的父亲节点下标，find(x)表示x所在树的根节点下标。一个数的根节点若为y则p[y]=y;
合并集合 ：
p[find(i)]=find(j）；//将i和j所在集合合并，也就是i的树接在j树根节点下面，即i树根节点的父亲节点是j树根节点
找根节点find函数（并查集里面的压缩路径法）
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);//非根节点用递归思路
return p[x];
}
本题完整代码解析：
#include <iostream>
using namespace std;
const int N = 10;
int ans;
int p[N];//每个点的父亲
bool st[N];//记录是否点亮这个灯管
int e[N][N];//这两条边是否相邻
/*
七段码
| 序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 对应灯管 | a | b | c | d | e | f | g |
*/
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
//深搜，把七根搜一遍，第八回就判断
void dfs(int u)
{
//第八轮特判
if(u == 8)
{
for (int i = 1; i <= 7; i ++) p[i] = i;//初始化，七根棍七个集合
for (int i = 1; i <= 7; i ++)
for (int j = 1; j <= 7; j ++)
if(e[i][j] && st[i] && st[j])//相邻且都亮合并集合
p[find(i)] = find(j);
//统计两者的集合数
int cnt = 0;
for (int i = 1; i <= 7; i ++)
if(st[i] && p[i] == i)//亮着的且为根
cnt ++;
if(cnt == 1) ans ++;//连通亮着的集合只有一个才是满足条件的
return; //注意递归一定要有出口！
}
//当前管开，下一根
st[u] = 1; // 打开第 u 个二极管
dfs(u + 1);
//当前管关下一根
st[u] = 0; // 关闭第 u 个二极管
dfs(u + 1);
}
int main()
{
e[1][2] = e[1][6] = 1;//两边相邻
e[2][1] = e[2][7] = e[2][3] = 1;
e[3][2] = e[3][7] = e[3][4] = 1;
e[4][3] = e[4][5] = 1;
e[5][4] = e[5][7] = e[5][6] = 1;
e[6][1] = e[6][7] = e[6][5] = 1;
e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1;
dfs(1);
cout << ans << endl;
return 0;
}
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int p[N];//存父亲下标
int e[N][N];//是否相邻
int st[N];//是否亮
int ans;
//找祖宗
int find(int x){
if(p[x]!=x){
p[x]=find(p[x]);
}
return p[x];
}
void dfs(int u){
if(u==8){
//开始每一根棍子一个集合
for(int i=1;i<=7;i++){
p[i]=i;
}
int cnt=0;//亮着的连通集合数
//合并连通集合
for(int i=1;i<=7;i++){
for(int j=1;j<=7;j++){
if(st[i]&&st[j]&&e[i][j]){
p[find(i)]=find(j);
}
}
}
//计算亮着的连通集合数
for(int i=1;i<=7;i++){
if(st[i]&&p[i]==i){//自己是根
cnt++;
}
}
if(cnt==1){
//亮着的根仅有一个-->满足条件
ans++;
}
return;
}
st[u]=1;//点亮第u根
dfs(u+1);
st[u]=0;//熄灭第u根
dfs(u+1);
}
int main(){
e[1][2]=1;
e[1][6]=1;
e[2][3]=1;
e[2][7]=1;
e[3][4]=1;
e[3][7]=1;
e[4][5]=1;
e[5][6]=1;
e[5][7]=1;
e[6][7]=1;
dfs(1);
cout<<ans;//从第一根棍开始dfs
return 0;
}10.子串分值和
所以：
对于每次起点可选i-pre[t]种
对于终点有len-i+1种
子串一定是连续的。
pre存该元素最近一次出现的地方。
#include<bits/stdc++.h> using namespace std; int pre[30]; long long int ans; int main(){ /*总结对字符串的处理 string类型没有strlen要用.size( ) char 类型用strlen求字符串长度 从第一位开始输入字符串，cin>>a+1; 测量从第一位开始字符串长度strlen(a+1);*/ char a[100006]; cin>>a+1; int len=strlen(a+1);for(int i=1;i<=len;i++){ int t=a[i]-'a';//将字母用一个数字代替，从0~25 ans=ans+(long long int)(i-pre[t])*(len-i+1); pre[t]=i; } cout<<ans; }
4.平面切分
考：画图寻找规律+stl中set用法
易错点：交点可能是小数，所以用long double
核心代码：
void solve(){
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];//n条线的斜率截距俩个数组分开存
}
for(int i=1;i<=n;i++){//n条线依次算当前新增平面数
if(PII.count({a[i],b[i]}))continue;//线重复，在set里面count方法返回值为0或1,1表示已经有该元素，0表示没有
set<pair<db,db> >point;//存放当前线新增交点
for(pi j:PII){//遍历所以已经存在的线，分别计算他们与当前线的交点数
if(a[i]==j.first)continue;//平行无交点
db x=1.0*(j.second-b[i])/(a[i]-j.first);
db y=a[i]*x+b[i];
point.insert({x,y});
/*
交点计算：假设交点（x,y）
由y=aix+bi=ajx+bj 得
x=(bj-bi)/(ai-aj);
代入
-->y=aix+bi
*/
}
PII.insert({a[i],b[i]});//当前线放入线set
ans+=point.size()+1;//核心算式
}
}
完整代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1006;
int a[N];
int b[N];
int n;
long long int ans=1;//初始一条线没有交点但可以分成两个平面，所以默认从1开始一开始没有交点原来的1+0+1=2
//找规律可以知道划分平面时第i条线会使平面增加这条线与之前所有线交点数+1
typedef long double db;
typedef pair<int,int> pi;
set<pair<int,int> >PII;//存放线，因为要防止线重复所以用set
void solve(){
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++){
if(PII.count({a[i],b[i]}))continue;//线重复，在set里面count方法返回值为0或1,1表示已经有该元素，0表示没有
set<pair<db,db> >point;//存放当前线新增交点
for(pi j:PII){
if(a[i]==j.first)continue;//平行无交点
db x=1.0*(j.second-b[i])/(a[i]-j.first);
db y=a[i]*x+b[i];
point.insert({x,y});
}
PII.insert({a[i],b[i]});
ans+=point.size()+1;
}
}
int main (){
cin>>n;//n条直线
solve();
cout<<ans;
return 0;
}