【ACM】—蓝桥杯大一暑期集训Day1

简介: 【ACM】—蓝桥杯大一暑期集训Day1

2ff49277181d4390b3cf6856746b9c7c.png

前言

因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备,所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟,便于复习巩固。辣么现在废话也不多说啦,直接往下看吧哈哈。

A - 查找

来源:洛谷P2249 【深基13.例1】查找

解题思路

本题用暴力搜索是过不了的,因为序列是有序的,所以在对每次需要进行查询的数用二分查找即可。

AC代码

#include<iostream>
using namespace std;
const int N=1000005;
int n,m,q,a[N];
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
  for(int i=1;i<=m;i++){
    int l=1,r=n;
    scanf("%d",&q);
    while(l<r){
      int mid=(l+r)/2;
      if(a[mid]>=q)
        r=mid;
      else
        l=mid+1;
    }
    if(a[l]==q)
      printf("%d ",l);
    else
      printf("-1 ");
  }
}

B - 地毯

来源:洛谷P3397 地毯

解题思路

这题数据不是很强,暴力也能过,所以我就暴力啦…

AC代码

#include<iostream>
using namespace std;
int n,m,x1,x2,y1,y2;
int s[1005][1005]={0};
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++){
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    for(int j=x1;j<=x2;j++)
      for(int k=y1;k<=y2;k++)
        s[j][k]++;
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++)
      printf("%d ",s[i][j]);
    cout<<endl;
  } 
}

C - 数楼梯

来源:洛谷P1255 数楼梯

解题思路

本题需要使用到高精度以及数学知识斐波那契(想必大家都知道哈,默认知道哈哈)。因为每次只能走一步或者两步,那么当前所在阶梯的方案数=上一阶梯方案数+上上一阶梯方案数,即s[i]=s[i−1]+s[i−2].。但是因为本题数据较大,所以直接一维数组的话不够用,这样用的是二维来储存。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,s[5005][5005],length;
void find(int x){
  for(int i=1;i<=length;i++)
    s[x][i]=s[x-1][i]+s[x-2][i];
  for(int i=1;i<=length;i++){
    if(s[x][i]>=10){
      s[x][i+1]+=s[x][i]/10;
      s[x][i]%=10;
      if(s[x][length+1]>0)
        length++;
    }
  }
}
int main(){
  cin>>n;
  length=1;
  s[1][1]=1;
  s[2][1]=2;
  for(int i=3;i<=n;i++)
    find(i);
  //注意逆序输出哈 
  for(int i=length;i>=1;i--)
    cout<<s[n][i];
} 

D - 宇宙总统

来源:洛谷P1781 宇宙总统

解题思路

本题也是道高精度的题,用字符串就好了

AC代码

#include<iostream>
using namespace std;
int n,win;
string s1,s2="";
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>s1;
    int t1=s1.size();
    int t2=s2.size();
    if(t1>t2||(t1==t2&&s1>s2)){
      s2=s1;
      win=i;
    }
  }
  cout<<win<<endl<<s2;
}

E - 高低位交换

来源:洛谷P1100 高低位交换

解题思路

本题主要运用到的位运算,直接左移16位和右移16位就OK

AC代码

#include<iostream>
using namespace std;
unsigned long long n;//无符号类型
int main(){
  scanf("%u",&n);
  printf("%u",(n>>16)+(n<<16));
}

F - Worms

来源:CodeForces-474B. Worms

翻译:

解题思路

本题用前缀和以及二分查找即可求解

AC代码:

#include<iostream>
using namespace std;
const int N=100005;
int n,a[N],b[N];
int m,label;
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>a[i];
  for(int i=2;i<=n;i++)//前缀和
    a[i]+=a[i-1];
  cin>>m;
  for(int i=1;i<=m;i++){
    cin>>label;
    int l=1,r=n,mid=(l+r)/2;//二分查找
    while(l<r){
      if(label<=a[mid]){
        r=mid-1;
      }else{
        l=mid;
        cout<<l<<endl;
      }   
    }
  }
}

总结

Day1的题主要考察的是一些基础的算法。

算法:二分查找、前缀和、数学、位运算、高精度、暴力搜索

感悟:这些算法算是比较基础的,只需多加练习就能熟练掌握

总结:算法的运用还是比较灵活的,能极大的减小时间复杂度

相关文章
|
6月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
106 0
|
6月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
82 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
82 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
88 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1007 印章
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1007 印章
62 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1006 拿金币
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1006 拿金币
65 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1004 无聊的逗
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1004 无聊的逗
87 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物
90 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1001 跳马
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1001 跳马
63 0
|
6月前
|
移动开发 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡
58 0