枚举/模拟

SUNNYDREAM · 2025-07-14 08:44:13 · 个人记录

2025.07.14

枚举

• 时间复杂度

  忽略系数和低次项

  理解: 系数介绍字母前的数 / 低次项是类似O(2n -1) 中-1就是低次项

  常见时间复杂度

  O( n ) O( n² ) ......

  例：求时间复杂度

  
  #include<bits/stdc++.h>
  using namespace std;
  int main()
  {
  for (int i=1;i<=n;i++)
  {
      for (int j=i+1;j<=n;j++)
      {
          cout<<"?";
      }
  }
  
  return 0;
  }

answer: O(n²)

 _如果一个数字是和数，那么他的因子一定是成对出现的，且较小的因子一定小于等于 sqrt($n$)_ 

  _对拍：数据生成器，使用对拍验证答案，OI赛制_

### 枚举的设计方法
- #### - 例题：[枚举例1](https://atcoder.jp/contests/abc414/tasks/abc414_c)

- ### - 题解：
```cpp
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define TRACE 1
#define tcout TRACE && cout

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define int long long

const int P = 998244353; 
const int INF = 0x3f3f3f3f3f3f3f3f; 

const int N = 1e6 + 10, M = 2e6 + 10; 

int a, n;
//读入进制和范围 n 10^12
int ans;

//m在a进制下是否是回文的
bool fun(int m)
{
    int t = m;
    string s;
    while(t)
    {
        char c = t % a + '0';
        s = c + s;
        t /= a;
    }
    //看s是否是回文的即可
    //对s进行反转, 字符串比较即可
    string ns = s;      //得到ns = s
    reverse(ns.begin(), ns.end());  //对ns进行反转
    return ns == s;
}

int check(int m)    //如果m合法, return m, 否则 return 0
{
//check(i)表示求i在10进制和a进制之下, 是否是回文的
    //首先判断m是否是回文的
    int t = m;
    int d = 0;
    while(t)
    {
        d = d * 10 + t % 10;
        t /= 10;
    }
    //得到m的反转数字d
    if(d != m)  //如果不是回文的, 直接返回0
    {
        return 0;
    }
    //再判断fun(m)是否为真, 再看一下m在a进制下是否回文
    if(fun(m))
    {
        return m;
    }
    return 0;
}

int p[N];   //p[i] = 10^i

signed main()
{
    fst; 
    p[0] = 1;
    for(int i=1; i<=14; i++)
    {
        p[i] = p[i-1] * 10;
    }
    cin >> a >> n;
    // for(int i=1; i<=n; i++)
    // {
        //方案失败! 为什么呢? 因为枚举的太多了
        //如何降低枚举次数???
        // ans += check(i);
    // }
    //考虑下回文数的特点!
    //左右对称
    //abc cba
    //1000000
    //123 321
    //12321
    //12521
    //[1, 9] 之间的数字 直接枚举即可
    //[123] -> [123321] ->[123k321]
    //构造成一个回文数!
    for(int i=1; i<=9; i++)
    {
        ans += check(i);
    }
    for(int i=1; i<=999999; i++)
    {
        int l = i;
        int r = rev(l);
        int t = l * p[c] + r;
        ans += check(t);
        for(int k=0; k<=9; k++)
        {
            int t = (l * 10 + k) * p[c] + r;
            ans += check(t);
        }
    }
    cout << ans;
    return 0;
}

例题2：题目

题解:

#include<bits/stdc++.h>
using namespace std;
bool d[300000008];
int n,m,l;
int a[110],b[110],c[110];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    cin>>l;
    for(int i=1;i<=l;i++)
    {
        cin>>c[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=1;k<=l;k++)
            {
                int s=a[i]+b[j]+c[k];
                d[s]=1;
            }
        }
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int x;
        cin>>x;
        if(d[x])
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}

模拟

例题1:亲爱的朋友

思路:我们只需到有朋友的地方即可

题解:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10;
long long n,k,p;
struct Pair
{
    long long first;
    long long second;
};
bool cmp(Pair x,Pair y)
{
    if (x.first==y.first)
    {
        return x.second<y.second;
    }
    return x.first<y.first;
}
pair<long long,long long> a[N];
int main()
{
    cin>>n>>k;
    for (long long i=1;i<=n;i++)
    {
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+n+1);
    for (long long i=1;i<=n;i++)
    {
        long long dis=a[i].first-p;
        if (k>=dis)
        {
            k-=dis;
            p=a[i].first;
            k+=a[i].second;
        }
        else
        {
            cout<<p+k<<endl;
            return 0;
        }
    }
    cout<<p+k<<endl;

    return 0;
}

• 例题2：超载的鸽子

• - 思路：模拟此过程，我们不要在2操作的时候去枚举所有鸽舍求解

• - 代码

• #include<bits/stdc++.h>
  using namespace std;
  const int N=1e6+10;
  int a[N],b[N];
  int n,q;
  int ans;
  int main()
  {
  cin>>n>>q;
  for (int i=1;i<=n;i++)
  {
      a[i]=1;
      b[i]=i;
  }
  while(q--)
  {
      int op;
      cin>>op;
      if(op==1)
      {
          int x,y;
          cin>>x>>y;
          a[b[x]]--;
          if (a[b[x]]==1)
          {
              ans--;
          }
          b[x]=y;
          a[y]++;
          if(a[y]==2)
          {
              ans++;
          }
      }
      else
      {
          cout<<ans<<endl;
      }
  }
  
  return 0;
  }

例题3

• 题目：格子

• 代码：