首页 > Drop Voicing
开通博客写题解
头像 bobby285271
发表于 2020-07-25 18:28:18
2020 多校第五场 D https://ac.nowcoder.com/acm/contest/5670/D 做法就是把题目给的序列头尾相接形成一个环状序列，枚举环状序列的起点，答案就是「序列长度减去 LIS（最大上升子序列）」的最小值。 环状序列应该不难想，LIS 是怎么来的跟着样例 1 走一 展开全文
去ta的博客 赞 (24) 回复(1) 收起
头像 TitanZhang
发表于 2020-07-25 19:54:16
题目大意 给定一个1~n(2<=n<=500)的排列，有两种操作： 1.将倒数第二个数放到开头； 2.将第一个数放到最后； 连续的操作1（包括1次）称为一段。现在要将排列变成1~n，要使得段数尽可能少，输出这个最小值。 解题思路 我们可以想象出一 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 horbivores
发表于 2020-07-25 18:30:41
题目大意：有两种操作，1.整个数组执行若干次循环移位，2.前n-1个元素执行若干个循环移位。问，把一个全排列排成升序最少要执行多少次第二种操作。 我们再把两种操作组合一下，按照1 2 1来组合，我们发现可以等价于把任意一个数放在任意的地方。 直觉证明：1 2 3 4 5我们通过三个操作把5放在3前面 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 zjnu_tjq
发表于 2020-08-25 08:44:57
链接：https://ac.nowcoder.com/acm/contest/5670/D来源：牛客网 题意： 给你一个长度为n的数列，有两种操作，1.Drop-2，把倒数第二个数往前移，其余整体后移，2.Invert，把最后一个数往前移，其余整体后移。两种操作，连续做某种操作，当作一次，问你最少要 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 梁家铭2020
发表于 2020-07-25 21:00:47
稍作思考，一次multi-drop操作可以将序列中任意一个数字转移到任意位置，自然可以想到要求需要转移的数字个数，即用原序列的长度减去最长上升子序列的长度，此处的代码复杂度为可以用二分优化为由于我巨弱就不打了 #include #include using namespace std; int a 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 11D_Beyonder
发表于 2020-08-21 04:20:12
题目描述   Inaka composes music. Today's arrangement includes a chord of notes that are pairwise distinct, represented by a permutation of integers from 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 _hw
发表于 2020-07-26 16:47:39
Inaka创作音乐。今天的排列包括n个音符***，用排列p_1,p_2,...p_n表示从低到高的音符。她的朋友Miyako并通过以下两个操作更改***：Drop-2：取出第二高音符并将其移至最低位置，即将排列更改为pn-1,p1,p2,...,pn-3,pn-2,pn。反转：取出最低音符并将其移至 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”