permutation

CF1542E2 首先时间复杂度肯定是 \(\mathcal{O}(n^3)\) 的。 容易想到先枚举最长公共前缀，然后枚举 \(p_{len+1}\) 和 \(q_{len+1}\)，再枚举逆序对数进行统计。 令 \(f_{i,j}\) 表示有 \(j\) 个逆序对的 \(i\) 阶排列的个数。 ......

有一个 \(gcd\) 游戏，按以下步骤进行： 选择一个 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\) 。 对于每个 \(i\) ，\(d_i = gcd(p_i, p_{i \% n + 1})\) 排列 \(p\) 的 \(score\) 为数组 \([d_1, d_2 ......

题意 对于一个长度为 \(N\) 的排列 \(Q\)，定义其为好的，当且仅当 对于任意整数 \(i \in \left[1, N\right]\)，在进行若干次操作 \(i \leftarrow Q_i\) 后可以得到 \(i = 1\)。 给定一个排列 \(P\)，定义一次操作为交换两个数。定义 ......

题意 给定一个长度为 \(N\) 的排列 \((P_1,P_2,\cdots,P_N)\)。称一个排列 \(P\) 为“好排列”当且仅当对于所有 \(1\leq x\leq N\)，都能通过不停地使 \(x\leftarrow P_x\) 将 \(x\) 变成 \(1\)。 通过最小次数操作将 \( ......

Permutation and Minimum 看到 300 的数据范围，再加上计数题，很容易就往计数 DP 方向去想。 为方便，我们将 \(n\) 乘二。 因为是两个位置取 \(\min\)，于是我们便想到从小往大把每个数填入序列。于是DP数组第一维的意义便出来了：当前已经填入了前 \(i\) 小 ......

CF882E1+CF1882E2 Two Permutations 题解-构造题 哇，人类智慧，太智慧了。。。 此题作为20231010联考的 T3。 感觉赛时根本没有去往这方面想。 CF1882E1 CF1882E2 E1 是简单版，就是没有要求操作数最小化。 E1-Easy Version 方法 ......

洛谷传送门 CF 传送门 考虑若是对一个排列进行操作，怎么做。 我们维护一个排列上的值域连续段 \([l, r]\)，满足 \(a_{l + 1} = a_l + 1, a_{l + 2} = a_{l + 1} + 1\)，以此类推。初始 \(l = r = 1\)。 那么我们每次可以选择往外扩充 ......

洛谷传送门 CF 传送门 如何评价，模拟赛搬了一道，前一天晚上代码写了一半的题。 考虑如何让操作次数最小。发现直接做太困难了。根本原因是，一次操作对序列的影响太大了。考虑做一些转化，减少一次操作对序列的影响。 仍然先考虑一个排列怎么做。 不知道为什么可以想到在排列前面添加特殊字符 \(0\) 变成 ......

给一个长为 \(n\) 的排列 \(a\)，你可以执行以下操作：选择一个子数组并且按任意顺序重排，但这个子数组不能是数组本身。 询问最少经过多少次操作可以使得排列 \(a\) 变为升序。 定义操作次数为 \(ans\) 。 若数组已经有序，\(ans = 0\) 。 若 \(a_1 = 1\) 或者 ......

pytorch permute permute(dims)将tensor的维度换位。参数：参数是一系列的整数，代表原来张量的维度。比如三维就有0，1，2这些dimension。例： import torch import numpy as np a=np.array([[[1,2,3],[4,5,6 ......

D. Prefix Permutation Sums 吐槽：读题不仔细，还以为原数组的取值是任意的，最后看题解的时候才发现取值在[1,n]，当时因为看不懂直接跳过了 题意：给你一个缺了一个的前缀和数组，让你判断是否存在原数组，取值[1,n]，每个数只存在一次 可以分类讨论 1 缺少最后一个前缀和 2 ......

我咕咕咕了这道题半年之久？ 好像洛谷好多题解都被 hack 了啊。 （本题解现有 hack 均通过） 题目链接 折叠题干 [POI2008] PER-Permutation 题目描述 Multiset is a mathematical object similar to a set, but ea ......

洛谷传送门 CF 传送门 最小交换次数等于 \(n - \text{环数}\)。所以题目要我们统计把 \(p, q\) 补全成排列，连边 \(p_i \to q_i\)，环数 \(= i\) 的方案数。 考虑把边根据 \(p_i, q_i\) 的是否已知状态分成四类： \(p \to q\) \(p ......

洛谷传送门 AtCoder 传送门 若 \(2\min\limits_{i = 1}^m a_i < \max\limits_{i = 1}^n a_i\) 就无解，因为根据排列的性质必然存在 \(yxxxy\) 或两端 \(xxyy\) 的情况，并且若这个条件不满足，就可以构造一组解。 考虑最小化 ......

好玩题。 对于一个排列 \(p\)，进行 \(k\) 轮冒泡，记 \(v_i = \sum_{j < i} [p_j < p_i]\)，给定 \(v_i\)，部分值不确定，求合法的 \(p\) 的个数。 \(p\) 由 \(v\) 唯一确定。 考虑一个个加数字进去，每次可以判断加入数字与前面数字的相 ......

CF1542E1 Abnormal Permutation Pairs (easy version) 题解 不会 Hard version 对于第一个限制字典序，我们可以考虑枚举前 \(i\) 位相同，然后考虑后 \(n-i\) 位。我们只需要保证 \(p_{i+1} < q_{i+1}\) 即可。 ......

给三个正整数数 \(n, a, b\) ，\(n\) 是偶数。写出 \(n\) 的任意一个排列满足左边一半的最小值等于 \(b\) 且右边一半的最大值等于 \(a\) 。 性质： 控制某个区间的最小值，需要让这个区间的数尽可能大 控制某个区间的最大值，需要让这个区间的数尽可能小 于是让排列左半的数尽 ......

好久没有单独开题目写了，主要是最近都是以补比赛为主，很少直接找题目做 但现在感觉只靠打比赛一来很难直接提升水平了，二来需要找一些知识点精进一下 所以就找了个codeforces 2100左右的graphs题，没事就刷一刷上面的题目 这题的话就比较典，首先考虑怎么判无解，如果对于\(x<y\)，满足\ ......

思路 很简单的一道题，洛谷大概都不会开放题解通道？（实际上貌似每场比赛的 A 都没开放？） 显然，对于原数组较小的数，我们尽量让大的数，取全排列的较小的数，这样可以保证差是逐渐变小的，也就让 \(c\) 数组差异变大。 所以直接拿个 struct 存，然后两边排序就好。 AC code #inclu ......

给一个长为 \(n\) 的排列 \(p\) ，需要构造一个长为 \(n\) 的排列 \(q\) ，满足 \(\forall i, p_i \neq q_i\) ，且 \(q\) 在所有合法排列中字典序最小。 观察一：\(n = 1\) 时无解，否则有解。 观察二：\(n > 1\) 时，\(1 \s ......

31. Next Permutation Medium 168634309Add to ListShare A permutation of an array of integers is an arrangement of its members into a sequence or linear ......

## 思路 又又又是一道 CF 诈骗题。 对于 $x$ 选出来的数，我们尽量放大的，对于 $y$ 选出来的数，我们尽量放小的，但是呢，存在同时被 $x$ 和 $y$ 选出来的数，就随便放。 但是可以发现按照题目给的数据范围，这么找选择的数，然后放最大或者是放最小，肯定是超时。 所以我们可以直接算出有 ......

给一个无序排列 $p_1, p_2, \cdots, p_n$ 。为了排序这个排列，选一个常数 $k(k \geq 1)$ 并且在排列上做一些操作。 * 一次操作可以选择 $i, j, (1 \leq j view ``` #include typedef long long ll; ll gcd( ......

Permute 3 Mac是一款万能格式转换工具，可以帮助用户将音频和视频文件从一种格式转换为另一种格式，以适应不同的播放设备和媒体需求。 →→↓↓载Permute 3 Mac 该软件具有以下特点： 批量转换：允许用户同时处理多个文件，并将它们批量转换为目标格式，这样可以大大提高转换速度并节省时间。 ......

[递推法解决博弈论问题。](https://codeforces.com/problemset/problem/1860/C "递推法解决博弈论问题。") 博弈论问题基本思路是先确定“状态”，即先手必胜或者先手必败。这里定义“必胜/必败”为**走到当前格子的人**的结局（赛时因为搞混了走入的人和走出 ......

## 思路 我们需要尽量让相邻两个数的和的最大值减最小值最小。 先思考如何让最大值最小。 对于 $n$，两侧最小也必须要放 $1$ 和 $2$。所以最大值至少也是 $n+2$。 同时，我们再思考 $1$ 周围能摆什么，因为不能让最小值太小，我们需要放比较大的，也就是 $n$ 和 $n-1$。 这样来 ......

题意：在一条数轴上，Alice可以跳到在你所在点前面且值比当前所在点小的点。每回合可以向任意符合要求的点跳一次。当轮到Alice的回合同时不存在符合要求的点，Alice就赢了。Alice可以选择一个点作为起始点，然后作为后手（赛时这里把我坑了）。问有多少个点是必胜的点。 $n\leq 3\times ......

[题目链接](https://www.luogu.com.cn/problem/SP8591) ## 题目大意 给出 $1$ 个数 $n$，求 $n$ 的各位拆分后重新排列组合得到新数是质数的个数。 ## 思路（欧拉筛，全排列） 对于求质数，与其每组数据运行 $1$ 次质数筛，不如在一开始就筛出 $ ......

## 思路 这个题是一个简单的构造题。~~竟然比 T2 简单，也是少见~~ 我们可以首先从 $1$ 开始不断乘以 $2$，像这样：$1, 2, 4, 8, 16\cdots,2^x$，直到什么时候超过 $n$ 就停止。 这样相邻两个数字就可以凑出 $1, 2, 4, 6, \cdots,2^{x- ......

## 杂言 赛时想到做法，结果调 code 把自己心态调炸了，所以来写一篇题解（恼）。 另：此题与 [P9345 夕阳西下几时回](https://www.luogu.com.cn/problem/P9345) 几乎相同，可以此练手。 另另：本题多测，多测不清空，爆零两行泪。 ## 题意翻译 $a_ ......