自动搬运

查看原文

来自洛谷，原作者为

	xxxaIq 一些压力，包括一些...就对于外界的否定吧

搬运于2025-08-24 22:46:48，当前版本为作者最后更新于2024-11-01 18:50:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

题意简述

要将一个区间长度为 $n$ 的区间划分为 $k$ 段，使得从每一段中任意选出一个数组成的长度为 $k$ 的子序列都不是严格上升的序列。输出划分方案，或报告无解。

特别地，长度为 $1$ 的序列是严格上升序列。

思路分析：

分类讨论。

$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$ 段即可。

代码：

//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;
}