题目
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
题解
数论！数论！数论！！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #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
