[补题篇] Codeforce 1417C (伪DP)

题目链接：传送门~~

题目大意
给一个长度为 n 的序列a，并且每个数的范围为 1 <= a[i] <= n.
定义 k 值为：在序列 a 中所有长度为 k 的子串中都存在的最小数，如果没有这样的数，此时的 k = -1.
问：给出 1 到 n，所有 k 对应的取值。

思路
对于相同的数字 x，我们统计相邻两个 x 之间的最大的长度L，那么，x 可以是 L 到 n的所有K值。
同时，我们要统计第一次 x 到左边界的长度和最后一个x到右边界的长度。
现在问题就是如何快速的算出这个长度L (当时就是被卡到这里，好菜)
具体实现和细节看代码。

代码

#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define chushi(a, b) memset(a, b, sizeof(a))
const double eps = 1e-8;
const ll INF = 1e9;
const ll mod = 998244353;
const int maxn = 3e5+10;
using namespace std;

int last[maxn];	// 纪录上一个数 x 出现的地方
int f[maxn];	// 纪录对于 X 最大的 L
int a[maxn];	// 纪录序列
int ans[maxn];	// 纪录答案

void init(int n){		// 初始化
	for(int i = 0; i <= n; i++){
		last[i] = 0;	// 默认为 0 ， 则可以统计右边界到第一个 x  的长度
		ans[i] = -1;	// 默认为 -1， 没有被修改就是没有满足的数
		f[i] = 0;		// 默认最大值为 0
	}
}

int main(){
	
	ios::sync_with_stdio(false);
	
	int ncase;
	cin >> ncase;
	
	while(ncase--){
		
		int n;
		cin >> n;
		for(int i = 1; i <= n; i++)	cin >> a[i];
		
		init(n);	// 初始化
		
		for(int i = 1; i <= n; i++){
			int x = a[i];
			f[x] = max(f[x], i - last[x]);	// 这个就是类似DP的地方，上一个状态和当前状态比较取最优 f[x] 就是以前的最优解， i - last[x] 就是当前的长度，两者取最大
			last[x] = i;	// 更新 x 出现的最后一个位子
		}
		
		for(int x = 1; x <= n; x++){		// 从较小的数开始更新答案，就可以满足题目的最小值要求
			f[x] = max(f[x], n - last[x] + 1); 	// 这里更新左边界到 最后一个x出现的长度
			for(int i = f[x]; i <= n && ans[i] == -1; i++) ans[i] = x;
			// 对于 x ，它可以满足的区间为 f[x] 到 n
			// 并且容易得到，对于 x = 1 的最长长度为 5 时，它可以更新 5 到 n 的 k，
			// 这是，就不用 x = 2 去更新 5 到 n 的 k 值了（题目要求k要尽量小）
		}

		for(int i = 1; i <= n; i++) cout << ans[i] << " ";
		cout << endl;
		
	}
    
    return 0;
}

本文地址：https://blog.csdn.net/mldl_/article/details/108877129