Bear and Colors题解

题目

Bear and Colors

描述

小熊利马克有n个彩色的球，排列在一长排。球的编号为1到n，从左到右。有n种可能的颜色，也编号为1到n。
对于一个固定的球的区间（连续元素的集合），我们可以定义一个主导颜色。这是一种在该区间内出现次数最多的颜色。如果一些颜色之间出现平局，则选择数字（指数）最小的颜色作为主导颜色。
这里总共有n*(n+1)/2多少个非空的区间。对于每种颜色，你的任务是计算这种颜色占主导地位的区间的数量。

输入

输入的第一行包含一个整数n（1≤n≤5000）–球的数量。
第二行包含n个整数t1,t2,…,tn（1≤ti≤n），ti是第i个球的颜色。

输出

打印n个整数。其中第i个应该等于第i个是主色的间隔数。

样例

输入

4
1 2 1 2

输出

7 3 0 0

输入

3
1 1 1

输出

6 0 0

提示

在第一个样本中，颜色2在三个区间中占优势。
一个区间[2,2]包含一个球。这个球的颜色是2，所以它显然是一个主导颜色。
一个区间[4,4]包含一个球，颜色还是2。
一个区间[2,4]包含两个颜色为2的球和一个颜色为1的球。
还有7个区间，颜色1在所有的区间中都是主导色。

补充

时间限制 2 秒
内存限制 256 MB
来源 FYOJ

题解

数论！数论！数论！！！！

#include <bits/stdc++.h>
using namespace std;
int a[5010][5010];
int sum[5010];
int chen_zhe[5010];
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> chen_zhe[i];
	}
	for (int i = 0; i < n; i++) {
		int maxn = 0;
		int kkksc03 = chen_zhe[i] - 1;
		for (int j = i; j < n; ++j){
			a[i][chen_zhe[j] - 1]++;
			if (a[i][chen_zhe[j] - 1] > maxn) {
				maxn = a[i][chen_zhe[j] - 1];
				kkksc03 = chen_zhe[j] - 1;
			} else if (a[i][chen_zhe[j] - 1] == maxn) {
				if (chen_zhe[j] - 1 < kkksc03) {
					kkksc03 = chen_zhe[j] - 1;
				}
			}
			sum[kkksc03]++;
		}
	}
	for (int i = 0; i < n; i++){
		cout << sum[i] << " ";
	}
	return 0;
}

测评结果 通过
分数 100
时间 1 MS
内存 1568 KB
语言 C++
代码长度 684