数颜色

题目描述

MoveToEx找到了很多不同颜色的珠子,他把这些珠子排成了一列,每个珠子的颜色用1,2....表示.定义一个区间的美观度为区间中不同颜色的珠子个数现在MoveToEx想知道,在所有n \times ( n + 1 ) / 2n×(n+1)/2个区间中,所有区间的美观度之和是多少.

题目分析

由于这个题目的数据并不是很大，所以直接暴力求解，题目说的是给定的子区间中一共有多少美观度，区间的数量显然是组合数，那么我们可以两层for循环，第一层for循环枚举左端点，第二层for循环枚举右端点，我们依次遍历下去，如果当前区间这个数是第一次出现，也就是说第一次出现该颜色，那么我们就计数加一，并且标记该颜色，而且我们要及时的加上该区间的美观度值，因为下一次遍历就是另外一个区间了！！！

方法一：数组标记

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], sum[maxn];
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; ++i)
        {
            int ans = 0; //每一次循环都要重新计数
            memset(sum, 0, sizeof(sum));
            for (int j = i; j <= n; ++j)
            {
                if (sum[a[j]] == 0) //如果这个元素是第一次出现那么就加一次
                    ans++;
                sum[a[j]]++; //标记该元素已经出现过了
                cnt += ans;  //加上当前区间的ans值
            }
        }
        printf("%d\n", cnt);
    }
}

方法二：set去重

经过方法一之后我们可以很快的想到set，因为set中不能存储相同的东西，而在方法一中我们需要把出现过的元素标记删除掉，而用set就能很好的解决这个问题，直接加上set的大小就是该区间的美观度！！！

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], sum[maxn];
set<int> s;
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; ++i)
        {
            for (int j = i; j <= n; ++j)
            {
                s.insert(a[j]);
                cnt += s.size();
            }
            s.clear(); //清空容器，防止干扰后序遍历
        }
        printf("%d\n", cnt);
    }
}