素养大赛通关指南

nightwatch.ryan · 2024-04-05 11:15:17 · 个人记录

大纲

以下内容将围绕下图展开

算法处理

• 排序算法：使用 sort。

  用法

  #include<iostream>
  int main(){
  int a[]={5,4,3,2,1};
  std::sort(a,a+5);
  for(int i=0;i<5;i++){
  std::cout<<a[i]<<' ';
  }
  //输出 1 2 3 4 5
  }

• 查找:

  顺序查找：

  //在给定数组里寻找k第一次出现的位置，如没有出现，则输出-1
  #include<iostream>
  int a[105];
  int main(){
  int n,k;std::cin>>n>>k;
  for(int i=1;i<=n;i++){
  std::cin>>a[i];
  }
  //数组a具有单调性
  for(int i=1;i<=k;i++){
  if(a[i]==k){
  std::cout<<i;
  return 0;
  }
  }
  std::cout<<-1;
  }

  二分查找

  //在给定数组里寻找k第一次出现的位置，如没有出现，则输出-1
  #include<iostream>
  int a[105];
  int main(){
  int n,k;std::cin>>n>>k;
  for(int i=1;i<=n;i++){
  std::cin>>a[i];
  }
  //数组a具有单调性
  int pos=-1;
  int l=1,r=n;
  while(l<=r){
  int mid=(l+r)>>1;
  if(a[mid]==k){
  pos=mid;
  l=mid+1;
  }else if(a[mid]>k){
  r=mid-1;
  }else{
  l=mid+1;
  }
  }
  std::cout<<pos;
  }

• 简单的穷举

以这道题来举例。

我们可以用六重循环来做这道题。

#include<iostream>
int main(){
    int k;
    while(std::cin>>k&&k){
        int p[k+1]={0};
        for(int i=1;i<=k;i++){
            std::cin>>p[i];
        }
        for(int a=1;a<=k-5;a++){
            for(int b=a+1;b<=k-4;b++){
                for(int c=b+1;c<=k-3;c++){
                    for(int d=c+1;d<=k-2;d++){
                        for(int e=d+1;e<=k-1;e++){
                            for(int ex=e+1;ex<=k;ex++)
                            std::cout<<p[a]<<' '<<p[b]<<' '<<p[c]<<' '<<p[d]<<' '<<p[e]<<' '<<p[ex]<<'\n';
                        }
                    }
                }
            }
        }
        std::cout<<std::endl;
    }
}

• 递推算法

  下楼梯

• 递归算法/搜索

  P1028

  #include<iostream>
  #include<unordered_map>
  int ans,dp[1005];
  int dfs(int n){
  int ans=0;
  if(dp[n]!=0){
  return dp[n];
  }
  for(int i=1;i<=n/2;i++){
  ans=ans+1+dfs(i);
  }
  return dp[n]=ans;
  }
  int main(){
  int n;
  std::cin>>n;
  std::cout<<dfs(n)+1;
  }

  P1036

  
  #include<iostream>
  #define N 25 
  int a[N],result;
  bool isprime(int x){
  if(x<=1)return 0;
  for(int i=2;i*i<=x;i++)
  if(x%i==0)return 0;
  return 1;
  }
  int n,k;
  /*

• _k 当前选的数

• cur 选了几个数

• all 当前总和 */ void dfs(int _k,int cur,int all){ if(isprime(all)&&cur==k){ result++; return; } for(int i=_k;i<=n;i++){ dfs(i+1,cur+1,all+a[i]); } } int main(){ std::cin>>n>>k; for(int i=1;i<=n;i++)std::cin>>a[i]; dfs(1,0,0); std::cout<<result; }

  >P1331
  ```cpp
  #include<iostream>
  char map[1005][1005];
  int r,c,cnt;
  void dfs(int x,int y){
  cnt++,map[x][y]='.';
  if(x-1>=1 and map[x-1][y]=='#')dfs(x-1,y);
  if(x+1<=r and map[x+1][y]=='#')dfs(x+1,y);
  if(y+1<=c and map[x][y+1]=='#')dfs(x,y+1);
  if(y-1>=1 and map[x][y-1]=='#')dfs(x,y-1);
  }
  int main(){
  std::cin>>r>>c;
  for(int i=1;i<=r;i++){
      for(int j=1;j<=c;j++){
          std::cin>>map[i][j];
      }
  }
  int f=0,res=0;
  for(int i=1;i<=r;i++){
      for(int j=1;j<=c;j++){
          if(map[i][j]=='#'){
              cnt=0;
              int R,C;
              R=0,C=0;
              for(int nextX=i;nextX<=r;nextX++){
                  if(map[nextX][j]=='#'){
                      C++;
                  }else{
                      break;
                  }
              }
              for(int nextX=j;nextX<=c;nextX++){
                  if(map[i][nextX]=='#'){
                      R++;
                  }else{
                      break;
                  }
              }
              f=R*C;
              dfs(i,j);
              if(cnt!=f){
                  std::cout<<"Bad placement.";
                  return 0;
              }
              res++;
          }
      }
  }
  std::cout<<"There are "<<res<<" ships.";
  return 0;
  }

• 高精度

  加法

  #include<iostream>
  std::string a,b;
  int toNum(char ch){
  return int(ch-48);
  }
  void zero(){
  if(a.size()>b.size()){
  int temp=a.size()-b.size();
  for(int i=1;i<=temp;i++){
  b.insert(0,"0");
  } 
  }else if(a.size()<b.size()){
  int temp=b.size()-a.size();
  for(int i=1;i<=temp;i++){
  a.insert(0,"0");
  } 
  }
  }
  void calc(){
  std::string res;
  int last=0;
  for(int i=a.size()-1;i>=0;i--){
  int temp=toNum(a[i])+toNum(b[i]);
  temp+=last;
  int tar=temp-temp%10;
  res.insert(0,std::to_string(temp%10));
  tar/=10;
  last=tar;
  }
  if(last!=0){
  res.insert(0,std::to_string(last));
  }
  std::cout<<res;
  }
  int main(){
  std::cin>>a>>b;
  zero();
  calc();
  }

  乘法

  %:include<iostream>
  %:include<vector>
  std::string a,b;
  int toNum(char ch){
  return int(ch-48);
  }
  int zerocnt;
  void zero(){
  for(int i=a.size()-1;i>=0;i--){
  if(a[i]!='0'){
  break;
  }else{
  zerocnt++;
  }
  }
  for(int i=1;i<=zerocnt;i++){
  a.erase(a.end()-1);
  }
  int temp=zerocnt;
  for(int i=b.size()-1;i>=0;i--){
  if(b[i]!='0'){
  break;
  }else{
  zerocnt++;
  }
  }
  for(int i=1;i<=zerocnt-temp;i++){
  b.erase(b.end()-1);
  }
  }
  void calc(){
  std::vector<int>resTemp(a.size()+b.size(),0);
  for(int i=a.size()-1;i>=0;i--){
  for(int j=b.size()-1;j>=0;j--){
  int NumA=toNum(a[i]);
  int NumB=toNum(b[j]);
  int temp=NumA*NumB;
  int distA=i+j;
  int distB=i+j+1;
  int ans=temp+resTemp[distB];
  resTemp[distA]+=(ans/10);
  resTemp[distB]=(ans%10);
  }
  }
  std::string res;
  for(auto i:resTemp){
  //去除前导0 
  if(!res.size() and i==0){
  continue;
  }
  res+=std::to_string(i);
  }
  if(res.size()==0){
  std::cout<<"0";
  }else{
  for(int i=0;i<zerocnt;i++){
  res+="0";
  }
  std::cout<<res;
  }
  }
  int main(){
  std::cin>>a>>b;
  zero();
  calc();
  }

End

• 文件操作

  freopen("XXXX.in","r",stdin);
  freopen("XXXX.out","w",stdout);