当前位置：首页 > news >正文

蓝桥杯2024国赛--备赛刷题题单

news 来源：原创 2024/9/29 21:32:51

1.游戏（单调队列）

注意如果结果是分数，直接设置变量为double，最好不要使用把int类型乘1.0变成分数来计算。

#include <iostream>
#include <queue>
using namespace std;
const int N=1e5+10;
//滑动窗口大小为k,最大值为P,最小值为Q,K=P-Q
//窗口个数为cnt=n-k+1
//所有情况为all=cnt*cnt
//期望值为(K1+K2+...+Kall)/all
//由于熊大选框和熊二选框的情况是一样的，因此只需要
//(K1+K2+...+Kcnt)/cnt
int a[N];
int wd[N];
deque<int>q;//双端队列
int main()
{int n,k;scanf("%d %d\n",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}double sump=0;//窗口最大值加和for(int i=1;i<=n;i++){while(!q.empty()&&a[q.back()]<a[i])q.pop_back();q.push_back(i);//4 3 2 1...(从大到小的窗口)a[i]<=a[q.back()]才加入if(i>=k)//大于等于窗口大小才开始计算答案{ //不在窗口内的下标pop掉while(!q.empty()&&q.front()<=i-k)q.pop_front();sump+=a[q.front()];}}q.clear();//注意要把队列清空！double sumq=0;//窗口最小值加和for(int i=1;i<=n;i++){while(!q.empty()&&a[q.back()]>a[i])q.pop_back();q.push_back(i);//1 2 3 4...(从小到大的窗口)a[i]>=a[q.back()]才加入if(i>=k)//大于等于窗口大小才开始计算答案{ //不在窗口内的下标pop掉while(!q.empty()&&q.front()<=i-k)q.pop_front();sumq+=a[q.front()];}}printf("%.2lf\n",(sump-sumq)/(n-k+1));return 0;
}

2.01游戏（DFS剪枝）

#include<iostream>
using namespace std;
char a[15][15];
bool flag=0;
int n;
bool check()
{//判断行for(int i=0;i<n;i++){int cnt0=0,cnt1=0;//记录连续出现int sum0=0,sum1=0;for(int j=0;j<n;j++){if(a[i][j]=='_')cnt1=0,cnt0=0;//连续中断else if(a[i][j]=='1'){cnt1++;sum1++;cnt0=0;}else if(a[i][j]=='0'){cnt0++;sum0++;cnt1=0;}if(cnt1>2||cnt0>2)return 0;if(sum1>n/2||sum0>n/2) return false;//超过一半就无法保证数量相等}}//判断列for(int i=0;i<n;i++){int cnt0=0,cnt1=0;//记录连续出现int sum0=0,sum1=0;for(int j=0;j<n;j++){if(a[j][i]=='_')cnt1=0,cnt0=0;//连续中断else if(a[j][i]=='1'){cnt1++;sum1++;cnt0=0;}else if(a[j][i]=='0'){cnt0++;sum0++;cnt1=0;}if(cnt1>2||cnt0>2)return 0;if(sum1>n/2||sum0>n/2) return false;//超过一半就无法保证数量相等}}return 1;
}
void dfs(int x,int y)//默认是先向右走再向下走
{if(flag)return;if(y==n){x++;//再向下y=0;//再从左边起始开始}if(x==n){//到达右下角了可以输出答案flag=1;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cout<<a[i][j];}cout<<endl;}return;}if(a[x][y]=='_'){a[x][y]='1';if(check())dfs(x,y+1);//合法才继续往下搜if(flag)return;a[x][y]='0';if(check())dfs(x,y+1);//合法才继续往下搜if(flag)return;a[x][y]='_';//复原}else dfs(x,y+1);
}
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}dfs(0,0);return 0;
}

3.子2023（动态规划）

#include <iostream>
#include <string>
using namespace std;
long long dp[4];//注意开longlong!!
//dp[0]:以2结尾的序列数量
//dp[1]:以20结尾的序列数量
//dp[2]:以202结尾的序列数量
//dp[3]:以2023结尾的序列数量
int main()
{string s;for(int i=1;i<=2023;i++){string str=to_string(i);s+=str;}for(int i=0;i<s.size();i++){if(s[i]=='2'){dp[0]++;dp[2]=dp[2]+dp[1];}else if(s[i]=='0'){dp[1]=dp[1]+dp[0];}else if(s[i]=='3'){dp[3]=dp[3]+dp[2];}}cout<<dp[3];return 0;
}

4.双子数（质因数分解，线性筛）

#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
const ll N=1e7+9;//N*N>23333333333333(2.3*10^13)
ll prime[N];
ll ans;
bool st[N];
//线性筛O(n)
ll getPrime()
{ll cnt=0;for(ll i=2;i<=N;i++){if(!st[i])prime[cnt++]=i;for(ll j=0;prime[j]*i<=N;j++){st[prime[j]*i]=1;if(i%prime[j]==0)break;}}return cnt;
}
int main()
{ll idx=getPrime();//预处理得到素数for(ll i=0;i<idx;i++)//遍历所有素数{ll p2=prime[i]*prime[i];//p^2if(p2*p2>23333333333333)break;for(ll j=i+1;j<idx;j++){ll q2=prime[j]*prime[j];//q^2if(p2*q2>23333333333333)break;if(p2*q2<2333)continue;ans++;//在区间内}}cout<<ans<<endl;return 0;
}

5.合并数列（双指针）

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int b[N];
int n,m;
int ans;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>b[i];int i=0,j=0;//从0开始//采用前缀和的思想int cnta=0,cntb=0;while(i<=n&&j<=m){if(cnta==cntb)//注意相等是等号!{cnta=a[++i];cntb=b[++j];}else if(cnta<cntb){cnta+=a[++i];ans++;}else if(cntb<cnta){cntb+=b[++j];ans++;}}cout<<ans<<endl;return 0;
}

6.数三角形（枚举，STL）

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
#define ll long long
#define pii pair<int,int>
int main()
{int n;cin>>n;vector<pii>a(n+2);map<pii,int>m;//表示坐标(x,y)点一共出现了几次for(int i=1;i<=n;i++){cin>>a[i].first>>a[i].second;m[{a[i].first,a[i].second}]++;}int ans=0;for(int i=1;i<=n;i++)//枚举每个点作为顶点{map<ll,vector<int>>st;//距离到达为ll时有多少个点for(int j=1;j<=n;j++){ll dist=(a[i].first-a[j].first)*(a[i].first-a[j].first)+(a[i].second-a[j].second)*(a[i].second-a[j].second);if(dist!=0)st[dist].push_back(j);//已经保证了i!=j}//计算合法数量for(auto &x:st)//st为map类型{vector<int>&v=x.second;int cnt=v.size();ans+=cnt*(cnt-1)/2;//两两组合可以作为答案//保证三点不共线int del=0;//不合法的点的数量for(int j=0;j<v.size();j++){int x1=a[i].first,y1=a[i].second;int x2=a[v[j]].first,y2=a[v[j]].second;int x3=2*x1-x2,y3=2*y1-y2;//三点共线，都在一个圆内//x1=(x3+x2)/2,y1=(y3+y2)/2del+=m[{x3,y3}];}ans-=(del/2);//三点共线 两点的情况多计算了一次}}cout<<ans<<endl;return 0;
}

7.AB路线（BFS）

#include <iostream>
#include <queue>
using namespace std;
#define ll long long
const int N=1000+500;
char a[N][N];
int n,m,k;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
ll vis[N][N][11],dis[N][N][11];
//因为一个位置可以重复走多次，
//再加一维（到这个位置是第几个字母）
struct node
{int x,y,cnt;//cnt为当前为第cnt个相同字母node(int x=0,int y=0,int cnt=0):x(x),y(y),cnt(cnt){}
};
queue<node>q;//用于bfs
int main()
{cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}q.push(node(1,1,1));//cnt=1,为第一个相同字母vis[1][1][1]=1;if(n==1&&m==1)//特判{cout<<0<<endl;return 0;} //开始BFSwhile(!q.empty()){node t=q.front();q.pop();for(int i=0;i<4;i++){int xx=t.x+dx[i];int yy=t.y+dy[i];int cc=t.cnt+1;if(xx<1||xx>n||yy<1||yy>m)continue;if(cc>k)//需要变{if(a[t.x][t.y]==a[xx][yy])continue;else cc=1;}else //不需要变{if(a[t.x][t.y]!=a[xx][yy])continue;}if(vis[xx][yy][cc]!=0)continue;vis[xx][yy][cc]++;dis[xx][yy][cc]=dis[t.x][t.y][t.cnt]+1;if(xx==n&&yy==m)//BFS先找到的一定是最小的，直接输出{cout<<dis[xx][yy][cc]<<endl;return 0;}q.push(node{xx,yy,cc});}}return 0;
}

8.跑步计划（日期问题）

#include <iostream>
#include <string>
using namespace std;
int main()
{int ans=0;int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};if((2023%400==0)||(2023%4==0&&2023%100!=0))a[2]++;int days=0;for(int i=1;i<=12;i++){for(int j=1;j<=a[i];j++){days++;string s1=to_string(i);string s2=to_string(j);   //2023年1月1日是周日if(s1.find('1')!=-1||s2.find('1')!=-1||days%7==2)ans+=5;else ans++;}}cout<<ans<<endl;return 0;
}

9.火车运输（动态规划背包问题）

#include <iostream>
using namespace std;
const int N=1000+10;
int dp[N][N];
int w[N];
int n,a,b;
int main()
{cin>>n>>a>>b;for(int i=1;i<=n;i++)cin>>w[i];// 三种情况：不选，放A，放Bfor(int i=1;i<=n;i++){for(int j=a;j>=0;j--){for(int k=b;k>=0;k--){if(j-w[i]>=0)dp[j][k]=max(dp[j][k],dp[j-w[i]][k]+w[i]);if(k-w[i]>=0)dp[j][k]=max(dp[j][k],dp[j][k-w[i]]+w[i]); }}}cout<<dp[a][b]<<endl;return 0;
}

10.走方格（动态规划图论）

#include <iostream>
using namespace std;
const int N=1000+100;
int a[N][N];
int dp[N][N];
int n;
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}for(int i=0;i<n;i++){dp[i][0]=i;//表示走到此步需要的时间//因为连续的跳步只发生在水平方向}for(int i=0;i<n;i++){for(int j=1;j<n;j++){dp[i][j]=1e9;//初始为大值// 从上面下来if(i>0)dp[i][j]=min(dp[i][j],dp[i-1][j]+1);// 向左到达最远的地方(即最小的地方)// 因为是从上到下，从左到右枚举，所以是向左（因为左边已是更新好的值）int temp=j;//临时变量while(a[i][temp]<a[i][temp-1]&&temp>=1)//严格小于{dp[i][j]=min(dp[i][j],dp[i][temp-1]+1);temp--;}//从左边一个过来dp[i][j]=min(dp[i][j],dp[i][j-1]+1);}}cout<<dp[n-1][n-1]<<endl;return 0;
}

11.选段排序（堆，贪心）

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm> 
using namespace std;
const int N=2e5+10;
int a[N];
priority_queue<int,vector<int>>q1;//大顶堆
priority_queue<int,vector<int>,greater<int>>q2;//小顶堆 
int main()
{int n,p,q;cin>>n>>p>>q;for(int i=1;i<=n;i++)cin>>a[i];sort(a+p,a+1+q);//注意sort的区间！！for(int i=p;i<=q;i++){//区间[p,q]先放入 q1.push(a[i]);//大 q2.push(a[i]);//小 } int ans=a[q]-a[p];//先得到初始的答案 //拓展右区间由[p,q]到[p,n]int maxx=a[q];int minn=a[p];for(int i=q+1;i<=n;i++){int t=q1.top();//先取堆顶 if(a[i]<minn)minn=a[i];//小的肯定可以排序到p if(a[i]<t)//t是拓展时用的 {q1.pop();//保证队列元素在[p,q]中q1.push(a[i]);ans=max(ans,q1.top()-minn);}	} //拓展左区间由[p,q]到[1,q],向左减法 for(int i=p-1;i>=1;i--){int t=q2.top();//先取堆顶 if(a[i]>maxx)maxx=a[i];//大的肯定可以排序到qif(a[i]>t){q2.pop();//保证队列元素在[p,q]中 q2.push(a[i]);ans=max(ans,maxx-q2.top());	} } cout<<ans<<endl;return 0;
}

12.混乘数字（数学，枚举）

#include <iostream>
#include <string>
#include <map>
#include <set>
using namespace std;
#define ll long long
set<ll>ans;//自动去重
bool check(ll n,ll a,ll b)
{int num[10]={0};string sn=to_string(n);string sa=to_string(a);string sb=to_string(b);for(int i=0;i<sn.size();i++){num[sn[i]-'0']++;}for(int i=0;i<sa.size();i++){num[sa[i]-'0']--;}for(int i=0;i<sb.size();i++){num[sb[i]-'0']--;}for(int i=0;i<=9;i++){if(num[i])return false;//通过相减}return true;
}
int main()
{for(ll i=1;i<=1000000;i++){ll kk=i*i;if(kk>1000000)break;if(check(kk,i,i))ans.insert(kk);for(ll j=i+1;j<=1000000;j++){kk=i*j;if(kk>1000000)break;if(check(kk,i,j))ans.insert(kk);}}cout<<ans.size()<<endl;return 0;
}

13.X质数（线性筛，二进制）

#include <iostream>
#include <string>
using namespace std;
const int N=1e6;
int idx=0;
int prime[N];
int st[N];
int ans=0;
void get()
{st[0]=st[1]=1;for(int i=2;i<=N;i++){if(!st[i])prime[++idx]=i;for(int j=1;j<=idx&&i*prime[j]<=N;j++)//从1开始{st[i*prime[j]]=1;if(i%prime[j]==0)break;}}
}
bool check(int x) {string num = to_string(x);int n = num.size();// n个数字，每个数字算不算进去两种选择for (int i = 0; i < (1 << n); ++i) { //n位数，有2^n种情况int cur = 0;for (int j = 0; j < n; ++j) { // 每种情况为一个二进制值if ((i >> j) & 1) cur = cur * 10 + num[j] - '0';}if (!st[cur]) return true;}return false;
}
int main()
{get();for(int i=1;i<=N;i++){if(check(i))ans++;}cout<<ans<<endl;return 0;
}