D. Rating Compression(双指针 + 思维)

news/2024/7/23 18:40:37

Problem - D - Codeforces

在竞争编程平台CodeCook上，每个人都有一个由长度为n的整数数组a描述的评分图。现在你正在更新基础设施，所以你已经创建了一个程序来压缩这些图。程序的工作原理如下。给定一个整数参数k，程序取in中每个长度为k的连续子数组中的最小值一个。更正式地说，对于长度为n和整数k的数组a，将a的k-压缩数组定义为长度为n - k + 1的数组b，这样b; =敏ai j <我< + k - 1例如，[1,3,4,5,2]的3-压缩数组为[min{1,3,4}， min{3,4,5}， min{4,5,2}] =[1,3,2]。长度为m的排列是由m个从1到m的不同整数以任意顺序组成的数组。例如，[2,3,1,5,4]是一个排列，但[1,2,2]不是一个排列(2在数组中出现两次)，[1,3,4]也不是一个排列(m = 3，但数组中有4个)。如果k-压缩数组是一种排列，CodeCook的用户会很高兴。给定一个数组a，确定对于所有1 < k≤n的数组，CodeCook用户在对该数组进行k-压缩后是否满意。输入第一行包含一个整数t (1 < t < 104)——测试用例的数量。每个测试用例描述的第一行包含一个整数n (1 < n < 3 - 105)——数组的长度。每个测试用例描述的第二行包含n个整数a1，。， an (1 < ai S n) -数组的元素。可以保证，所有测试用例的n的和不超过3 - 105。输出对于每个测试用例，打印一个长度为n的二进制字符串。如果CodeCook用户对数组a进行k-压缩后感到满意，则字符串的第k个字符应为1，否则为O。

Example

input

Copy

5
5
1 5 3 4 2
4
1 3 2 1
5
1 3 3 3 2
10
1 2 3 4 5 6 7 8 9 10
3
3 3 2

output

Copy

题解:

首先特判一下k = 1,k = n的情况(很简单)

由于取长度为k的子数组取最小,1肯定在首或尾,否则(除了特判)肯定都不不行

比如3 1 2,k = 2 [1,1]

假设1在首位,如果排列[1,2]成立

那么下标2~n的数组中肯定要有2,否则后面的肯定都不行

接着下标为2的数应该是2,否则会出现

这种情况,依次递推下去,发现数组应该是单调递增的

同理1在末尾,从右往左也是一样的

总结下来就是

当k = n − 1时，全排列就是 1和2 两个数，假设 1不在两端，而在中间，那么结果一定是 1 ,1 ，这就不可能为全排列，所以1 一定在数组两端。

接下来就是 k = n − 2 ,假设上面 1 在首部，那么剩下就是去考虑区间 ( 2 , n ) ,同理，此时2 也只能出现一次，那么2 也只能在区间( 2 , n ) 的两端。

根据上述规律一直递归求解，遇到不满足的直接退出即可。需要注意的是，要保证区间这个数只能出现一次，并且+ 1 这个数一定要存在

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
//#define int long long
map<int,int> f;
int ans[300050];
int a[300050];
int n;
void dfs(int l,int r,int val)
{
	if(l > r)
	return ;
	if(a[l] == val || a[r] == val)
	{
		if(f[val] == 1&&f.count(val + 1))
		{
			if(a[l] == val)
			{
				ans[n - val] = 1;
				dfs(l + 1,r,val + 1);
			}
			else 
			{
				ans[n - val] = 1;
				dfs(l,r - 1,val + 1);

			}
		}
	}
}
void solve()
{
	cin >> n;
	f.clear();
	int flag = 0;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i]; 
		ans[i] = 0;
		f[a[i]]++;
		if(f[a[i]] != 1)
		flag = 1;
	}
	if(!flag)
	ans[1] = 1;
	if(f.count(1))
	ans[n] = 1;
	dfs(1,n,1);
	for(int i = 1;i <= n;i++)
	cout << ans[i] ;
	cout << "\n"; 
}

signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve(); 
	}
}