P8909题解

· · 题解

楼上的大佬们已经介绍了暴力，\operatorname{map} 等解法，我就补充一下非正解的链表和 \operatorname{map}。

题目分析

  1. 首先看到这道题先想到暴力，枚举每个 a_i 的 k 倍，开个桶子计算出现几次。但是发现数太大了，桶开不下(1 \leq m \leq 10^9)。

  2. 先写个桶会发现中间有很多没有参与的数浪费很多空间，于是就可以把桶换成链表来模拟。

说白了就是将 a_i 的 k 倍这个数和出现次数压缩成一个结构体数组（链表）进行遍历。

但是要注意到链表中不需要删除元素，且只会在末尾添加，所以又变成了一个按下标遍历的链表。

code

struct list{
    int val, id;        //枚举出的a[i]的k倍的数， 出现过的次数 
}p[200000];         //这样就省下了中间很多根本不会用到的数
int n, m, a[2510], ans[2510], ln;
bool in[1000000010];
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= n;i++)
    {
        for(int j = a[i];j <= m;j += a[i])
        {
            if(!in[j])
            {
                in[j] = true;
                ln++;
                p[ln].val = j, p[ln].id = 1;
            }
            else
            {
                for(int k = 1;k <= ln;k++)
                {
                    if(p[k].val == j)
                    {
                        p[k].id++;
                        break;
                    }
                }
            }
        }
    }
    cout << m - ln;
    for(int i = 1;i <= ln;i++)
        ans[p[i].id]++;
    for(int i = 1;i <= n;i++)
        cout << " " << ans[i];
    return 0;
}

但是会发现总有一个点 MLE。

  1. 用 \operatorname{map} 代替桶。 这里讲一个关于 \operatorname{map} 的知识点，就是如何快速遍历 \operatorname{map}，这里用到了 \operatorname{map} 函数库的 $\operatorname{end()}$——返回指向 $\operatorname{map}$ 尾部的迭代器 等函数。 代码如下： ```cpp map<int,int>::iterator i = mp.begin();i != mp.end();i++ ```

最后附上本蒟蒻的代码

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
map <int, int> mp;
int n, m, a[3000], ans[3000];
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= n;i++)
        for(int j = a[i];j <= m;j += a[i])
            mp[j]++;
    cout << m - mp.size();
    for(map<int,int>::iterator i = mp.begin();i != mp.end();i++)
        ans[i->second]++;
    for(int i = 1;i <= n;i++)
        cout << " " << ans[i];
    return 0;
}

附件