算法进阶——枚举

枚举算法的介绍：

  基本的算法思想，穷举所有可能的情况。他的基本思想是将问题的解空间中每个可能都枚举出来，并进行验证和比较，找出满足问题条件的最优解或所有解。

适合问题规模较小的，解空间可穷举的情况。

直接上例题（lanqiao OJ 191）

特别数的和

题目描述

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 nn 中，所有这样的数的和是多少？

输入描述

输入格式：

输入一行包含两个整数 n（1≤n≤104）n（1≤n≤104）。

输出描述

输出一行，包含一个整数，表示满足条件的数的和。

输入输出样例

示例

输入

40

输出

574

#include<bits/stdc++.h>
using namespace std;
int n;
int sum;
bool fun(int x){
    while(x){
      int y=x%10;
      if(y==2||y==0||y==1||y==9){
        return true;
      }
      x/=10;
    }
    return false;
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
      if(fun(i))
        sum+=i;
  }
  cout<<sum<<endl;
  return 0;
}

例题二（lanqaio OJ 152）

反倍数

题目描述

给定三个整数 a,b,ca,b,c，如果一个整数既不是 aa 的整数倍也不是 bb 的整数倍还不是 cc 的整数倍，则这个数称为反倍数。

请问在 1 至 nn 中有多少个反倍数。

输入描述

输入的第一行包含一个整数 nn。

第二行包含三个整数 a,b,ca,b,c，相邻两个数之间用一个空格分隔。

其中，1≤n≤1000000，1≤a≤n，1≤b≤n，1≤c≤n1≤n≤1000000，1≤a≤n，1≤b≤n，1≤c≤n。

输出描述

输出一行包含一个整数，表示答案。

输入输出样例

示例

输入

30
2 3 6

输出

10

#include<bits/stdc++.h>
using namespace std;
int n;
int a,b,c;
int fun(int n){
  int num=0;
  for(int i=1;i<=n;i++){
    if(i%a!=0&&i%b!=0&&i%c!=0){
      num++;
    }
  }
  return num;
}
int main(){
  cin>>n;
  cin>>a>>b>>c;
  cout<<fun(n);
  return 0;
}

在一个 n×mn×m 的矩阵中，有一个数字出现了超过一半的次数，请设计一个高效算法找到这个数字。

输入格式

输入第一行包含两个整数 nn 和 mm，表示矩阵的大小 (1≤n,m≤103)(1≤n,m≤103)。

接下来 nn 行，每行包含 mm 个正整数，表示矩阵中的元素。

输出格式

输出一个整数，表示矩阵中出现次数超过一半的数字。

样例输入

3 3
1 2 3
2 2 2
1 2 2

样例输出

2

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
int main(){
  int m,n;
  cin>>m>>n;
  for(int i=1;i<=n*m;i++){
    int x;
    cin>>x;
    mp[x]++;
  }
  for(const auto&[x,y]:mp){
    if(y>n*m/2){
      cout<<x<<endl;      
    }
  }
  return 0;
}