大多来自CF

CF911E

比较简单的贪心题。考虑什么样的序列满足其可以单栈排序，显然是对于每个点除去它前面比他小的点，这一段前缀是单调递减的。

那么首先判原序列是否单调递减。假设弹完可以弹的元素之后栈中为x1 x2 ... xn(xn<xn-1<...<x1)

那么后面我们明显应该排

\(xn\) \(xn-1\) xn-2 ... 1

如果把1放到前面去字典序会变小。

然后再排

\(x_{n-1}\) \(x_{n-1}-1\) ... \(xn+1\)

最后是 n n-1 ... xn+1

---

CF1304F2

做dp题一定要先写出dp式子！！！

写出来之后发现可以线段树直接算 or 单调队列

---

CF813D

几种做法。

1：暴力dp但是不太容易优化。

我们需要设计一种dp，不能计算出不存在的方案，常规的dp很容易让两个序列选到同一个位置。

所以我们可以强制用f(i,j)推导出其它的f(k,j)和f(i,k)，其中k应该大于max(i,j)。由于两个序列是等价的，这样一定可以求出最优解。

但是初始化比较麻烦，这里我先dp出了一个序列的dp值然后初始化。

这玩意不太好优化。

2：暴力dp但是很容易优化

发现一转多不好优化，要变为f(i-k,j-k)推f(i,j)的形式。

我们依然强制让f(i,j)从f(i,k)区间\(k\in(i,j)\)的位置转移过来，直接令f(i,j)=f(j,i)以更新i。这样仍然可以保证能得到最优解。

可以发现这样很好优化，记录最后一个位置数为x和%7=y的最优值即可。

---

3、

还有一个题要求四个序列。

甚至多个序列也可以。

考虑网络流。

朴素的建边：首先拆成两倍点限流为1，如果a和b能相邻（a<b）就a出点连b入点，费用设为1跑最大费用最大流。

这样边是\(n^2\)级别的。

考虑优化建图。要利用题目性质。

如果10个点都同余，那么1要连23456...10，2要连345....10

总共要连45个点。

太垃圾了，明显可以1连2，2连3，3连4...(都是入点连入点)。

差一就权相同的连一条。

这样就是O(n)级别了。

---

SP5973 SELTEAM - Selecting Teams

哈哈哈。。。模数是2^21。

式子只计算1~21即可。

---

CF140E New Year Garland

不会，只能看题解。计数DP太烂了，多练练。

https://www.luogu.com.cn/problem/solution/CF140E

---

CF859E Desk Disorder

神题。

考虑每个人往想去的位置连一条边。

然后会形成 树 基环树 环 自环

各自讨论，互相不影响，乘法原理。

---

CF883D Packmen Strike Back

又是神题。发现只要有两个人一定可以吃完。左边的向右右边的向左即可。

但是什么时候可以吃完呢？

发现答案具有单调性！考虑二分答案。

check的时候可以dp。发现一个人变成了可以吃一段长度。

设前i个人可以吃到j的位置。那么对于一个人，如果前面一个吃到自己或者更前面，自己可以往前吃。或者自己往后吃补齐。如果补不齐那就返回0了。

但是还有一种情况：前面一个往左吃到自己后面。

哈哈哈。。。

---

CF1107G Vasya and Maximum Profit

考虑单调性！

对于一个r，i~r(\(i\in [1,n)\)) 这一堆区间的那一坨d一定是单调不上升的。

每一次多一个值，都会更新一段前缀的这一坨d。

暴力跑这一段前缀，然后把这一段前缀压成一个点，再记录前缀和的前缀最小值即可O(n)。

还有更加神奇的线段树做法。

对于每个点先求出这个d。扫出这个d在那一段内是最大的。单调栈即可。然后求这一段过当前点的最大值，线段树即可。

---

UVA1289

神题。

https://www.cnblogs.com/AWCXV/p/7626135.html

---

CF1527D MEX Tree

考虑容斥。记录经过了0~x这一堆点的路径有多少个。

所以我们要维护经过0~x的一条最短的链。

记录左端点和右端点。

大力分类讨论插入新点x后左右端点的变化。

---

CF314E Sereja and Squares

和T2很像啊。。。

考虑

没有大写字母。

然后设f(i,j)为前i个位置，还有j个左括号没匹配时的方案数。

4s，卡常可过。

优化看题解。

---