D. Rating Compression(双指针 + 思维)
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
10111 0001 00111 1111111111 000
题解:
首先特判一下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(); }
}