首页 > 其他分享 >Yet Another Permutation Constructive

Yet Another Permutation Constructive

时间:2024-07-07 18:08:07浏览次数:13  
标签:构造方法 着想 题解 Yet 插入 Another 序列 Constructive 我们

这道题目不用写,因为必须要求用kotlin语言

讲一下我做这道题目的过程

我最开始正着想,如果\(k\)比较大的话,我们就想一次删的数少一点,所以考虑一次操作有哪些数被保留,于是我们发现,原序列的极大值点会被保留,于是一次操作被保留的数最多的情况就是如下的波浪形:

然后我们就发现正着想很难构造了,于是我们就倒着想:

最后一次删完了的序列是这样:$$[n]$$

我们考虑倒数第二次删完之后序列长成什么样,我们有个直觉就是越大的数越在后面被删除,于是我们考虑此时剩下的数是\(n-1\),也就是说序列此时是这样:$$[n-1,n]$$

那么对于倒数第三次,为了让上面两个数都不删除,我们必须要在中间插入\(n-2\),即$$[n-1,n-2,n]$$

这也就是正着想的时候,我们想要构造波浪形

同理第四次即$$[n-1,n-3,n-2,n-4,n]$$

在这样一直插入下去;如果说插入了\(1\)但是\(k\)次操作还没有用完,那么就是无解,否则的话,当\(k\)次操作用完的时候,我们将剩余的还没有插入的数,按照\([1,2,3,...]\)这样的顺序放在序列最前面即可

我们的构造方法与官方题解一样,但是官方题解的思路却跟我们完全不一样,但是是对我们的构造方法的严谨证明

标签:构造方法,着想,题解,Yet,插入,Another,序列,Constructive,我们
From: https://www.cnblogs.com/dingxingdi/p/18288766

相关文章

  • Nanami and the Constructive Problem
    线段树优化建图一般用动态开点线段树实现建立对称的入树和出树点击查看代码#include<bits/stdc++.h>usingnamespacestd;vector<int>a[600005];intc[100005],cnt,tot,sum,id[600005],dfn[600005],low[600005],val[100005],n,m;stack<int>s;boolv[600005],h[600005......
  • P9565 [SDCPC2023] Not Another Path Query Problem
    P9565[SDCPC2023]NotAnotherPathQueryProblem位运算+并查集从价值至少为\(V\)入手,枚举一段二进制上长为\(i\)的前缀,第\(i+1\)位取\(1\),并且比\(V\)要大,这样\(i+1\)之后的位就可以任意取了(不妨现在都先为\(0\)),设这样构成的二进制串为\(s\)。考虑按位与的性质......
  • Yet Another Sigma Problem
    题目传送门题目跳转看吧题解哈希,字典树对字符串的前缀进行哈希处理,转换为数字,用\(map\),然后为了避免重复,可以将每一种公共字符串前缀的权重都设置为1例如:\(a\),\(ab\),\(aba\)权重都为1,因为\(ab\)是2,但是有一种包含在\(a\)里面,同理,&aba&是3,但是被&ab&,&a&......
  • D. Yet Another Monster Fight
    cf链接洛谷链接方法一最大最小值问题我们很容易想到二分答案法。那么我们如何写出check函数呢?对于答案x,若x-i+1<a[i],则选定怪物一定不在i位置左侧,即L=i;若x-n+i<a[i],则选定怪物一定不在i位置右侧,R=min(R,i)。遍历数组,如果L<=R则答案符合题意;否则不符合。code #includ......
  • MySQL The instance is already part of another Replication Group
    MySQLInnoDBCluster(测试环境为MySQL8.0.35)将一个实例重新加入集群时,遇到了下面这个错误"Theinstance'dbu03:3306'isalreadypartofanotherReplicationGroup"MySQL  10.160.2.55:3306 ssl  JS > cluster.addInstance('[email protected]:3306')ERROR: Ru......
  • GD32学习中遇到 warning: #188-D: enumerated type mixed with another type 强迫症尽
    项目场景:今天往GD32的系统板里加入六个按键,在DEMO程序的基础上要做一些修改。在对时钟使能的时候,习惯的用STM32的方法。加|线隔开两个GPIO口,结果报出warning:#188-D:enumeratedtypemixedwithanothertype的警告。强迫症尽量不要有警告……rcu_periph_clock_enable(RC......
  • CF1234F Yet Another Substring Reverse
    CF1234FYetAnotherSubstringReverse状压dp+高维前缀和一个很显然的发现是最长子串长度不会超过字符集。那么如果没有这个操作,是很简单的,我们看看多了这个操作意味着什么。对于一个子串,考虑一次翻转对它的影响。在它内部的翻转肯定是没有意义的;我们一定有一个操作能将任意......
  • git 命令报错:Another git process seems to be running in this repository, e.g. an
    执行git命令时,报错:Anothergitprocessseemstoberunninginthisrepository,e.g.aneditoropenedby'gitcommit'.Pleasemakesureallprocessesareterminatedthentryagain.Ifitstillfails,agitprocessmayhavecrashedinthisrepository......
  • SystemC & TLM-2.0 - TLM-2.0 Interoperability in SyetemC
    TML-2.0Interoperabilityabouttellingtointeroperabilitylet'sabouttellingtointeroperabilitylet'sstartbydefiningsometermsuntilthemtoaninitiatorisacomponentthatinitiatesnewtransactionsatargetisacomponentbutactsast......
  • CF1228E Another Filling the Grid 题解
    tag:容斥原题+组合数设F[i]F[i]F[i]表示至少......