题解 P1903 【[国家集训队]数颜色 / 维护队列】

ZHDX · 2019-08-06 12:10:16 · 题解

分享一下暴力破解法 , 非常简单易懂.

首先用一个通用的方法, 来避免总是使用map或者set来统计颜色个数. 在函数get_index_of_number的实现里, 强制把number 转换为0,1,2,3,4,.....

这样, 无论number的取值范围是什么, 都可以使用单个数组的统计方式来替代map统计了.

后面用 unsigned int indexarr[110000]; 来做统计, 因为N和M的最大值都是50000, 其中R指令数量不确定 所以提供的颜色数量是可以达到100000个的. 所以数组数量随便取个 110000

get_colors_of_range函数用于统计区域内的颜色数量. 这里首先要给indexarr清零. 直接根据_indexmap的数量来清, 要清多一位 , 因为0是不放进_indexmap内的.

另外一个细节是 if (indexarr[valuearr[i]]++ == 0)count++ 这种判断 是要比 if (indexarr[valuearr[i]] == 0) { count++; indexarr[valuearr[i]]=1; } 这种类型要快很多.

#include <cstring>
#include <unordered_map>
#include <iostream>
using namespace std;

unordered_map<int, int> _indexmap;
int get_index_of_number(int number)
{
    if (number == 0)return 0;
    int index = _indexmap[number];
    if (index == 0)
    {
        index = _indexmap.size();
        _indexmap[number] = index;
    }
    return index;
}

int valuearr[55000];

unsigned int indexarr[110000];

int get_colors_of_range(int start, int endnotinc)
{
    memset(indexarr, 0, _indexmap.size() * 4 + 4);

    int count = 0;
    for (int i = start; i < endnotinc; i++)
    {
        if (indexarr[valuearr[i]]++ == 0)
            count++;
    }

    return count;
}

int main()
{
    char c;
    int N, M, v1, v2;

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> valuearr[i];
        valuearr[i] = get_index_of_number(valuearr[i]);
    }

    for (int i = 0; i < M; i++)
    {
        cin >> c >> v1 >> v2;
        if (c == 'Q')
            cout << get_colors_of_range(v1 - 1, v2) << endl;
        if (c == 'R')
            valuearr[v1 - 1] = get_index_of_number(v2);
    }

    return 0;
}