欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-15 10:32:09
题目链接:传送门~~题目大意给一个长度为 n 的序列a,并且每个数的范围为 1 <= a[i] <= n.定义 k 值为:在序列 a 中所有长度为 k 的子串中都存在的最小数,如果没有这样的数,此时的 k = -1.问:给出 1 到 n,所有 k 对应的取值。思路对于相同的数字 x,我们统计相邻两个 x 之间的长度L,那么,x 可以是 L 到 n的所有K值。同时,我们要统计第一次 x 到左边界的长度和最后一个x到右边界的长度。现在问题就是如何快速的算出这个长度L (当时就是被卡到...

题目链接:传送门~~

题目大意
给一个长度为 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