求助RE
  • 板块灌水区
  • 楼主WZWZWZWY
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/2 19:08
  • 上次更新2024/4/2 20:56:53
查看原帖
求助RE
704668
WZWZWZWY楼主2024/4/2 19:08

除了几个TLE的,剩下的都是RE。

#include <bits/stdc++.h>
using namespace std;

map <int, int> mp, mp2;
int cnt_mp;
vector <int> v;

int sum[205][40005], zs[205][40005], a[40005], tong[40005];
// sum[i][j] 第i个块编号j的前缀和 zs[i][j] 第i个块到第j个块的众数 

int main() {
	//freopen("P4168_1.in", "r", stdin);
	//freopen("P4168_1.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (!mp[a[i]]) {
			mp[a[i]] = ++cnt_mp;
			mp2[cnt_mp] = a[i];
		}
		//v[mp[a[i]]].push_back(i);
	}
	for (int i = 1; i <= 200; i++) {
		for (int j = 1; j <= 40000; j++) sum[i][j] = sum[i - 1][j];
		for (int j = (i-1) * 200 + 1; j <= i * 200; j++) sum[i][mp[a[j]]] ++;
	}
	for (int i = 1; i <= 200; i++)
		for (int j = i + 1; j <= 200; j++) {
			int maxx = zs[i][j - 1];
			for (int k = (j-1)*200 + 1; k <= 200 * j; k++) 
				if ((sum[j][a[k]]-sum[i - 1][a[k]] > sum[j][maxx]-sum[i - 1][maxx]) || (sum[j][a[k]]-sum[i-1][a[k]] == sum[j][maxx]-sum[i-1][maxx] && a[k] < maxx)) 
					maxx = a[k];
			zs[i][j] = maxx;
		}
	for (int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		int kl = (l/200 + 1), kr = (r/200 + 1);
		if (kr - kl <= 1) {
			int maxx = 0;
			memset(tong, 0, sizeof(tong));
			for (int j = l; j <= r; j++) {
				if ((++tong[mp[a[j]]] > tong[maxx]) || (tong[mp[a[j]]] == tong[maxx] && a[j] < maxx)) maxx = j;
			}
			cout << a[maxx] << "\n";
		} else { 
			memset(tong, 0, sizeof(tong));
            v.clear();
			int maxx = 0;
            for (int i = l; i <= (kl + 1) * 200; i++) {
                if (!tong[mp[a[i]]]) v.push_back(mp[a[i]]);//
                tong[mp[a[i]]] ++;
            }
            for (int i = (kr - 1)*200+1; i <= r; i++) {
                if (!tong[mp[a[i]]]) v.push_back(mp[a[i]]);
                tong[mp[a[i]]] ++;
            }
            int zhs = zs[kl+1][kr-1];
            for (int i = 0; i < v.size(); i++) {
            	int pre = tong[v[i]] + sum[kr-1][v[i]] - sum[kl][v[i]], now = sum[kr-1][zhs] - sum[kl][zhs] + tong[zhs];
                if ((pre > now) || (pre == now && mp2[v[i]] < mp2[zhs]))
                    zhs = mp[v[i]];
            }
			cout << mp2[zhs] << "\n";
		}
	}
	return 0;
}

这个代码哪里可能会RE?QWQ?

https://www.luogu.com.cn/record/154035104

2024/4/2 19:08
加载中...