前言
因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备，所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟，便于复习巩固。辣么现在废话也不多说啦，直接往下看吧哈哈。
A - 查找
解题思路
本题用暴力搜索是过不了的，因为序列是有序的，所以在对每次需要进行查询的数用二分查找即可。
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 - 高低位交换
解题思路
本题主要运用到的位运算，直接左移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
翻译：
解题思路
本题用前缀和以及二分查找即可求解
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的题主要考察的是一些基础的算法。
算法：二分查找、前缀和、数学、位运算、高精度、暴力搜索
感悟：这些算法算是比较基础的，只需多加练习就能熟练掌握
总结：算法的运用还是比较灵活的，能极大的减小时间复杂度
