蓝桥31天|今天4道题Day4|C++

1.奇偶倍数

#include<iostream>usingnamespace std;boolcheck(int num){while(num){if(num%2==0)returnfalse;
    num/=10;}returntrue;}intmain(){for(int i=2019;i<150000;i+=2019){if(check(i)){printf("%d",i);break;}}return0;}

2.第几个幸运数字

#include<iostream>usingnamespace std;constlonglong N=59084709587505;intmain(){int ans=0;for(longlong i=1;i<=N;i*=3){for(longlong j=1;i*j<=N;j*=5){for(longlong k=1;i*j*k<=N;k*=7){
        ans++;}}}printf("%d",ans-1);return0;}

3.四平方和

a、b、c、d＜根号n
最多只能枚举2个数

法一：暴力法：
枚举a、b、c,d可通过计算得到，时间复杂度不符合要求

#include<iostream>#include<cmath>usingnamespace std;intmain(){int n;scanf("%d",&n);for(int a=0;a*a<=n;a++){for(int b=a;a*a+b*b<=n;b++){for(int c=b;a*a+b*b+c*c<=n;c++){int t=n-a*a-b*b-c*c;int d=sqrt(t);if(d*d==t){printf("%d %d %d %d",a,b,c,d);return0;}}}}return0;}

可以考虑用时间换空间，把b2 +d2 先存起来

for(int c=0;c*c<=N;c++){for(int d=c;c*c+d*d<=N*N;d++){
        存储c*c+d*d
    }}for(int a=0;a*a<=N;a++){for(int b=0;b*b<=N;b++){int t=n-a*a-b*b
        //如果t在前面出现过，且使结果的字典序最小->//1.哈希O(1) //当和相同时,只存字典序最小的解//2.二分O(logn)//排序不只是c^2+d^c,还要排序c、d,相当是一个结构体}}

法二：二分
时间复杂度：O(n2 logn)

#include<iostream>#include<cmath>#include<algorithm>usingnamespace std;constint N=5*1e6+10;bool g[N];struct Sum{int s,c,d;booloperator<(const Sum& t)const{if(s!=t.s)return s<t.s;if(c!=t.c)return c<t.c;return d<t.d;}}sum[N];intmain(){int n,len=0;scanf("%d",&n);for(int c=0;c*c<=n;c++){for(int d=c;c*c+d*d<=n;d++){
            sum[len++]={c*c+d*d,c,d};}}sort(sum,sum+len);for(int a=0;a*a<=n;a++){for(int b=0;b*b+a*a<=n;b++){int t=n-a*a-b*b;int l=0,r=len-1;while(l<r){int mid=(l+r)/2;if(sum[mid].s>=t)r=mid;else l=mid+1;}if(sum[l].s==t){printf("%d %d %d %d",a,b,sum[l].c,sum[l].d);return0;}}}return0;}

法三：哈希表

时间复杂度：O(n2 )#include<iostream>#include<cmath>#include<algorithm>usingnamespace std;#define x first#define y secondtypedef pair<int,int>PII;
unordered_map<int,PII>s;intmain(){int n,len=0;scanf("%d",&n);for(int c=0;c*c<=n;c++){for(int d=c;c*c+d*d<=n;d++){int t=c*c+d*d;if(s.count(t)==0)s[t]={c,d};}}for(int a=0;a*a<=n;a++){for(int b=a;b*b+a*a<=n;b++){int t=n-a*a-b*b;if(s.count(t)){printf("%d %d %d %d",a,b,s[t].x,s[t].y);return0;}}}return0;}

4.迷宫

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

#include<iostream>#include<vector>usingnamespace std;constint N=33,M=53;char g[N][M];typedef pair<int,int>PII;
vector<char>ans;
PII que[N*M];int hh=0,tt=-1;
PII pre[N][M];voidbfs(){int dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};
  que[++tt]={0,0};while(hh<=tt){auto t=que[hh++];for(int i=0;i<4;i++){int x=dx[i]+t.first;int y=dy[i]+t.second;if(g[x][y]=='0'&&x>=0&&x<30&&y>=0&&y<50){
     
        que[++tt]={x,y};
        pre[x][y]=t;
        g[x][y]='1';}}}int x=29,y=49;int prex,prey;while(x||y){auto t=pre[x][y];
    prex=t.first;
    prey=t.second;if(x-prex==1){
      ans.push_back('D');}elseif(x-prex==-1){
      ans.push_back('U');}elseif(y-prey==1){
      ans.push_back('R');}elseif(y-prey==-1){
      ans.push_back('L');}
    x=prex;
    y=prey;}intmain(){for(int i=0;i<30;i++){for(int j=0;j<50;j++){scanf("%c",&g[i][j]);}getchar();}bfs();for(int i=ans.size()-1;i>=0;i--){printf("%c",ans[i]);}return0;}