题解：P9255 [PA 2022] Podwyżki
xxxaIq
·
·
题解
题目链接
题意简述
要将一个区间长度为 n 的区间划分为 k 段，使得从每一段中任意选出一个数组成的长度为 k 的子序列都不是严格上升的序列。输出划分方案，或报告无解。
特别地，长度为 1 的序列是严格上升序列。
思路分析：
分类讨论。
$k=2$ 时，枚举两个区间中间的断点，如果左区间的最小值大于等于右边的最大值，那么就有解。预处理出前缀最大值和后缀最小值。
$k=3$ 时，考虑中间的区间选那个数，直接枚举这个数作为中间的区间，比较左右区间，做法与 $k=2$ 时类似。
当 $k \ge 4$ 时，有一个很显然的构造方案，就是如果有一个 $i$ 满足 $a_i>=a_{i+1}$，就可以将它们单独划分开，这样一定会选到这两个数，从而让所选出的序列不严格上升。这样这两个数一共占了两段，剩下左边一段，右边一段正好满足 $k=4$ 的情况。对于 $k>4$ 的情况，将 $[1,i-1]$ 和 $[i+2,n]$ 任意划分够 $k=2$ 段即可。
# 代码：
```cpp
//code by xxxaIq
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500003;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch>57||ch<48){
if(ch==45){
f=-1;
}
ch=getchar();
}
while(ch>=48&&ch<=57){
x=(x<<1)+(x<<3)+(ch-48);
ch=getchar();
}
return x*f;
}
int n,k,a[maxn],p=0,ma[maxn],mi[maxn];
void out(int x){
int r=0,d;
cout<<"TAK\n";
d=(x!=n);
for(int i=1;i<x-2;i++){
if(k-d-4>=0){
k--;
r=i;
cout<<i<<" ";
}else{
break;
}
}
if(x>2){
cout<<x-2<<" ";
r=x-2;
k--;
}
cout<<x-1<<" ";
if(x!=n){
cout<<x<<" ";
}
k-=2;
r=x;
for(int i=x+1;i<n;i++){
if(k-2>=0){
k--;
r=i;
cout<<i<<" ";
}else{
break;
}
}
return;
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
if(k==1){
cout<<"NIE\n";
return 0;
}
mi[1]=a[1];
for(int i=2;i<=n;i++){
mi[i]=min(mi[i-1],a[i]);
}
for(int i=n;i>=1;i--){
ma[i]=max(ma[i+1],a[i]);
}
if(k==2){
for(int i=1;i<n;i++){
if(mi[i]>=ma[i+1]){
cout<<"TAK\n"<<i<<"\n";
return 0;
}
}
cout<<"NIE\n";
return 0;
}
if(k==3){
for(int i=2;i<n;i++){
if(mi[i-1]>=a[i]||a[i]>=ma[i+1]){
cout<<"TAK\n";
cout<<i-1<<" "<<i<<"\n";
return 0;
}
}
cout<<"NIE\n";
return 0;
}
for(int i=2;i<=n;i++){
if(a[i-1]>=a[i]){
out(i);
return 0;
}
}
cout<<"NIE\n";
return 0;
}
```