EOJ刷题记录&题解第三弹

Problem #3299 - ECNU Online Judge

这道题理解题意花了很长时间，靠着AI辅助才大致写完框架，测试debug了半个小时，发现是错在判断条件if (res[cur] == m_cnt && m_c > cur) m_c = cur。

题目意思是遍历所有的区间，一开始考虑$dp$但是

1. 这不是常见的求最值问题

2. 区间如果用$dp[i][j]$表示的话无法转化成子问题

因此考虑直接模拟遍历所有区间，时间复杂度$log(n^2)$满足条件

//
// Created by HUAWEI on 2025/3/8.
//
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5010;
int color[N];

int main()
{
    int n;
    while(cin >> n) {
        vector<int> ans(n + 10, 0);  // 每种颜色为主色调的区间个数

        memset(color, 0, sizeof color);
        for (int i = 1; i <= n; i++)
            cin >> color[i];

        for (int i = 1; i <= n; i++) {
            vector<int> res(n + 10, 0);
            int m_c = -1;   // 维护的最大值颜色
            int m_cnt = 0;    // 最大值出现的次数

            for (int j = i; j <= n; j++) {
                int cur = color[j];
                res[cur]++;

                if (res[cur] > m_cnt) {
                    m_cnt = res[cur];
                    m_c = cur;
                } else if (res[cur] == m_cnt && m_c > cur) {
                    m_c = cur;
                }

                if(m_c >= 1 && m_c <= n)
                    ans[m_c]++;
            }


        }

        for (int i = 1; i <= n; i++)
        {
            cout << ans[i];
            if(i != n)  cout << ' ';
            else cout << endl;
        }
    }

    return 0;
}