Permutation

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( ......

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

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

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

## 思路 这个题是一个简单的构造题。~~竟然比 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_ ......

## 题面 定义一个 $1 \sim n$ 的排列 $p$ 的「怪异度」为 $$\sum_{i=1}^n\left\lvert p_i-i\right\rvert$$ 求「怪异度」为 $k$ 的 $1 \sim n$ 的排列数，答案对 $10^9+7$ 取模。 ## 题解 考虑转化计算怪异度的过程， ......

### 题目大意 定义一个 $1 \sim n$ 的排列 $p$ 的「怪异度」为 $$\sum_{i=1}^n|p_i-i|$$ 求「怪异度」为 $m$ 的 $1 \sim n$ 的排列数，答案对 $10^9+7$ 取模。 ### 思路 考虑把 $p_i$ 和 $i$ 看作小球与盒子，方便题意理解。 ......

题意 给定一个长度为n的序列，计算有多少个子区间满足子区间第K小的数不在子区间第K位。 找出所有不满足条件的区间。枚举所有的ai和左端点al，找出满足ai是区间[l,r]中第r-l+1小的右端点r，则右端点r一定是一段区间。 例如 3 4 2 1 6 5 l i 则r=[3,6] 当l向左移动时，如 ......

# [ABC309G] - Ban Permutation 题解 ## 题目描述 求长为 $N(N\leq 100)$ 且满足以下条件的排列 $P=(P_1,P_2,...,P_N)$ 的个数，模 $998244353$： - $\forall 1\leq i\leq N$，$|P_i-i|\geq ......

# next_permutation的简单实现 ​ 首先需要从后往前找到第一对数字满足nums[i]& nums) { int n = nums.size(); int l = -1, r = -1; for (int i = n - 2; i >= 0; --i) { if (nums[i] = ......

Problem StatementFind the number, modulo $998244353$, of permutations $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$ such that: $|P_i - i| \ge X$ for all ......

很有趣的一道题。双倍经验：[P2757 [国家集训队] 等差子序列](https://www.luogu.com.cn/problem/P2757) 要找三个数构成等差序列，一个直接的想法就是枚举中间的数 $a_i$，然后看它左右两边是不是有 $a_i-k$ 和 $a_i+k$。这个枚举的过程已经不 ......

### [G - Ban Permutation](https://atcoder.jp/contests/abc309/tasks/abc309_g) 首先看到绝对值，很烦，考虑取掉绝对值得到$p_i\leq i-X$或$p_i\geq i+X$ 然后我们就自然而然有了一个暴力的想法，设$dp[i ......

[题面传送门](https://www.luogu.com.cn/problem/CF1844F2) 先不考虑字典序的问题，只考虑最小值怎么求。 先考虑一个特殊情况：$c=0$，也就是说我想要相邻两项之差的绝对值最小。那么将其从小到大排序以后就满足要求。 我们猜想实际上更一般的情况不会和这个差太多。 ......

显然分成 $k$ 段以后，最大化形成的排列的字典序的策略是将所有段按第一个元素的大小降序排列。 由于最终排列的字典序肯定 $\ge$ 原排列的字典序，因此我们考虑最大化最终排列与原排列的 LCP，这部分就考虑二分答案，记 $dp_i$ 表示以 $p_1$ 开始 $p_i$ 结尾的 LDS 的长度，那 ......

### Problem > 求有多少个 $1$ 至 $n$ 的排列 $P$，满足对于任意 $i$ 都有 $|i-p_i|\ge X$。 > $1\le n\le 100$，$1\le X\le 5$。 ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_abc309_g "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/abc309/tasks/abc309_g "AtCoder 传送门") 前置知识：[[AR ......

设 $s=\sum\limits_{i = 1}^n a_i$，考虑加上排列 $p$，那么 $s\leftarrow s + \frac{n\times (n + 1)}{2}$。 当有解时，因为 $a_i$ 相等，所以有 $s\bmod n = 0$。 考虑 $n \bmod 2 = 1$ 时，$ ......

# next_permutation 函数 next_permutation是全排列函数。 ## 一、基本用法 ```c++ int a[]; do{ }while(next_permutation(a,a+n)); ``` ## 二、例题 [P1088 [NOIP2004 普及组] 火星人]([P ......

吓人题。 一个显然的想法是对于 $k$, 将贡献分为 $3$ 类 ：$[1,k]$ 子区间的贡献，$[k+1,n]$ 子区间的贡献和跨过 $k$ 的贡献。 首先 $[1,k]$ 的贡献我们可以沿用 Pudding Monsters 的做法，从左往右枚举 $r$，统计 $r$ 作为右端点的贡献。发现一 ......

[原题](https://codeforces.com/problemset/problem/359/B) #### 解决思路 虽然题解思路里写着 $dp$，但是还是用最简单的 $math$ 方法写了 找规律题： 1. 如果结果为 $0$，只需要每个 $a_{2i-1}-a_{i}$ 同向即可，即都 ......

## 题意 给定一个 $1 \sim N$ 的排列，Alice 把它划分成 $k$ 段，Bob 把这 $k$ 段任意排列。Alice 想让字典序最小，Bob 想让字典序最大。请问最后的排列。 数据范围： $1\le k\le N\le 2 \times 10^5$。 ## 题解 首先 Bob 的排序 ......