首页 > 其他分享 >题解:AT_abc352_d [ABC352D] Permutation Subsequence

题解:AT_abc352_d [ABC352D] Permutation Subsequence

时间:2024-07-17 16:51:11浏览次数:14  
标签:ch 题意 no int 题解 abc352 Subsequence getchar

虽然比赛没打,但是想来水估值发表思路。

题意

给你一个 \(1\sim n\) 的排列,让你从中找一段长为 \(k\) 的子序列,使得这个子序列中的元素排序后数值连续。

分析

题意转换一下,先用结构体存储每个元素的编号和数值,按照数值排序。

于是这道题就成了:一个序列,让你求所有长 \(k\) 的子段中每个段编号极差的最小值。

所以我们需要维护每个段编号最大最小值,我选择了 ST 表。

其他做法维护也有很多,这里就不讲了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int maxn=1e6+10;
int n,k;
struct no
{
	int d,id;
}a[maxn];
bool cmp(no x,no y)
{
	return x.d<y.d;
}
int ma[maxn][22],mi[maxn][22];
void pre()
{
	for(int j=1;j<=20;j++){
     	for(int i=1;i+(1<<j)-1<=n;i++)
			mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
	}
    for(int j=1;j<=20;j++){
     	for(int i=1;i+(1<<j)-1<=n;i++)
      		ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
	}
	
}
int askmax(int l,int r)
{
	int le=l,ri=r;
        int len=log2(ri-le+1);
        return max(ma[le][len],ma[ri-(1<<len)+1][len]);
}
int askmin(int l,int r)
{
	int le=l,ri=r;
        int len=log2(ri-le+1);
		return min(mi[le][len],mi[ri-(1<<len)+1][len]);
}
signed main()
{
//  freopen("xxx.in","r",stdin);
//	freopen("xxx.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		a[i].d=read();
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);	
	for(int i=1;i<=n;i++)swap(a[i].d,a[i].id);
	for(int i=1;i<=n;i++)mi[i][0]=ma[i][0]=a[i].d;
	pre();
	int ans=1e9+7;
	for(int l=1;l<=n-k+1;l++)
	{
		int r=l+k-1;
		ans=min(ans,askmax(l,r)-askmin(l,r));
	}
	cout<<ans;
	return 0;
}

标签:ch,题意,no,int,题解,abc352,Subsequence,getchar
From: https://www.cnblogs.com/fengyixuan2027/p/18307795

相关文章

  • 有较复杂限制条件的dp(CF366C,POJ1837,CF294B题解+总结)
    前言这篇文章将用三道精选的好题例题让你学会这种类型的题目。题型看起来是一个背包,但是多了一个条件,是一个等式或不等式,有时候式子还挺复杂的,该怎么办呢?例题1CF366CDimaandSalad题意原题有n......
  • 洛谷P1596 [USACO10OCT] Lake Counting S 题解
    看别的神犇用的都是并查集,我还是用暴搜吧(doge下面纯暴搜#include<bits/stdc++.h>usingnamespacestd;intn,m,ans;//N行M列和答案charc[105][105];//存储农田的二维向量voiddfs(intx,inty){//暴搜 if(c[x][y+1]=='W'){ c[x][y+1]='.';//将水坑改为......
  • CodeForces Round 898 (div 4) H题解析
     CodeForcesRound898(div4)H.Mad City                           大致思路   对于有n条边和n个点,说明这个图里面只有一个环并且两人同时开始和结束移动,所以可以得到当Valeriu进入到这个图里面的唯一......
  • 一道大「水题」 题解
    一道大水题时间限制:1000ms空间限制:256000kB题目描述[题目描述]有\(n\)个点,第\(i\)个点到第\(j\)个点有边当且仅当j是i的倍数且\(j/i\)为质数。(边是单向的)给出\(q\)组询问,每次询问从第\(1\)个点走到第\(x\)个点的方案数,对\(1e9+7\)取模。[输入格式]......
  • UNR #8 部分题题解
    由于博主水平有限,目前只有\(A,B,D\)题题解。A.最酷的排列题目描述\(T\)组数据,给定长为\(n\)的序列\(a\)和下标集合\(S\),你可以对序列进行任意次操作,每次选择一个区间并将其中元素升序排序。求\(\sum\limits_{i\inS}a_i\)的最小可能值。数据范围\(1\len,\sum......
  • 启动应用程序出现mfc80u.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个mfc80u.dll文件(挑选合适的版本文件)把它放......
  • 启动应用程序出现mfc90u.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个mfc90u.dll文件(挑选合适的版本文件)把它放......
  • 2024牛客暑期多校训练营1 I.Mirror Maze(题解)
    题意给一个\(n\timesm\)的二维char数组,由4种镜子组成,'\','/','-','|',镜面反射规则就是根据光线的方向和镜面的角度符合直觉的反射,然后有多组询问\(q\leq10^6\),每次给定起始位置和光线方向,求该光会经过多少面不同的镜子的反射。思路首先根据数据范围,发现肯定需要预处......
  • ARC_069 D - Menagerie 题解
    atcoder一道很有意思的模拟题啊。思路很重要。首先,我们只要知道连续两只动物的身份,就可以根据\(s\)推出所有动物的身份。不妨假设我们知道第一只和第二只动物的身份,一共有几种情况呢?用\(1\)代表羊,\(0\)代表狼。那么,共有\(2^2=4\)种情况,分别为:00011011然后我......
  • 题解|2024暑期牛客多校01
    【原文链接】太菜了就先挂4题,其他的写出来了再回来补QwQA.ABitCommon组合数学题目大意题目概括:给定两个整数nnn和m......