蓝桥云课-第4场小白赛理解

网址：第 4 场 小白入门赛 - 蓝桥云课 (lanqiao.cn)

第一题：美丽的2024

思路：

2024 -直接用变成二进制的函数或者模拟二进制的过程，找到有几个1就行

第二题：自助餐

 题目：

思路：就是用字符串代表相对应的值，题目给你一堆字符串，然后累加他们所代表的值

          1.map键值对存储

         

#include <iostream>
#include<map>
using namespace std;
int main()
{
  map<string,int>hash;
  hash["yuanxing"]=1;
  hash["zhengfangxing"]=2;
  hash["changfangxing"]=3;
  hash["sanjiaoxing"]=4;
  hash["tuoyuanxing"]=5;
  hash["liubianxing"]=6;
  int n,cnt=0;;
  cin>>n;
  string str;
  while(n--){
     cin>>str;
     cnt+=hash[str];
  }
  cout<<cnt;
  // 请在此输入您的代码
  return 0;
}

          2.用到特殊的pair<string,int>结构,后面基本上和第一种思路一致

        

pair<string,int>h;
vector<pair<string,int>>hash;

第三题：玩游戏

题目：

思路：其实这道题是属于博弈论的一个问题，关键是找到什么条件下A，B那个人赢

首先B可以先分堆，这时需要想的极限一点，都分成每个堆唯一个的数量，说以这时的以得出结论，n为偶数的时候 ，为B，否则 ，为A；

#include <iostream>
using namespace std;
int main()
{
 
  int n;
  cin>>n;
  if(n%2==0) cout<<"B";
  else       cout<<"A";
  // 请在此输入您的代码
  return 0;
}

第4题：乘飞机

      这道题思路简单前提是你得掌握时间复杂度，不要超时

     首先咱们从最基础的来说：

     最耗时间的：当然是双重遍历在L-R区间内 O(n*n)

   代码：

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
 
  int n,q;
  cin>>n>>q;
  int l,r;
  int a[n+1],i;
  a[0]=0;
  for(i=1;i<=n;i++){
      cin>>a[i];
  }
  
  while(q--){
    cin>>l>>r;
    int cnt=0;
    for(i=l;i<=r-1;i++){
      for(int j=i+1;j<=r;j++){
        if(abs(a[j]-a[i])<=365) cnt++;
      }
    }
    if(cnt==0) cout<<"NO"<<endl;
    else       cout<<"YES"<<endl;
  }
  
  // 请在此输入您的代码
  return 0;
}

  或者可以用二维数组储存一下就可以

 

while(q--){
    cin>>l>>r;
    int cnt=0;
    int b[n+1][n+1];
    for(i=l;i<=r;i++){
      for(int j=l;j<=r;j++){
        b[i][j]=a[i]-a[j];
      }
    }
    for(i=l;i<=r;i++){
    for(int j=l;j<=r;j++){
      if(abs(b[i][j])<=365 && i!=j) cnt=1;
       
    }
  }

’  当然这个也是不行的，最简单的方法就是重新设一个容器vector去放在L-R内的元素，进行一个快速排序，再一次for循环遍历去找，这样下来时间复杂度，为O（n*logn）为最省时间，但是还是超时的百分之二十，

所以重新再看一遍题，两者之差小于365，数的范围为到36500内，如果区间的长度大于等于100，那么必然会满足上述的条件

代码：最终版

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
 
  int n,q;
  cin>>n>>q;
  int l,r;
  int a[n+1],i;
  a[0]=0;
  for(i=1;i<=n;i++){
      cin>>a[i];
  }
 
  while(q--){
    cin>>l>>r;
     if(r-l>=100) cout<<"YES"<<endl;
     else{
         int cnt=0;
    vector<int>ll;
    for(i=l;i<=r;i++){
      ll.push_back(a[i]);
    }
    sort(ll.begin(),ll.end());
    for(i=0;i<ll.size()-1;i++){
      if(ll[i+1]-ll[i]<=365) {
        cnt=1;
        break;
      }
    }
  if(cnt==1 ) cout<<"YES"<<endl;
  else       cout<<"NO"<<endl;
     }
    
  }
  
  // 请在此输入您的代码
  return 0;
}