E.Partial Sorting
算法本质
分类讨论思维、容斥（一点点）
题目大意
给出n、mod，列出长度为3n的所有排列，每个排列都有自己的价值x——最少经过x次操作后使得排列为[1~3n]的形式。
下面是可以对排列进行的2种操作：
- 前排：递增sort前
2n个元素 - 后排：递增sort后
2n个元素
求所有排列价值之和（取余mod）。
思路推演-1
首先可以拿出的一个结论是，任何排列经过3次操作可以恢复。
既然只有3次操作，显然是一个分类讨论+组合数的题目。
分类讨论的重点就在于，该如何分类讨论，这里通常有2个方法：
- 贴近答案分类讨论
每个排列只有4种价值，则按照不同价值分类 - 贴近数据本身的结构分类讨论
可以看到，每个排列分为了3个大区间，思考排列的特殊结构
不论哪种分类方法，最后都疏通同归，但是思考的难易程度会有所不同。
同时注意，这题给的复杂度宽裕，支持在分类讨论中O(n)的暴力。
固定思维想着组合数问题需要O(1)解决，是没做出来的原因之一。
思路推演-2
这里选择贴近答案分类讨论，同时在分类的时候，发现先用小于等于处理较好。
价值==0
只有一种可能。
价值<=1
意味着只需要一次前排or后排就可以搞定，这分别对应2种情况：
[2n+1, 3n]的数字已就位且[1, 2n]数字任意排序[1, n]的数字已就位且[n+1, 3n]的数字任意排序
同时这两种情况有交叉的地方
fac[2n] + fac[2n] - fac[n]价值<=2
这里可以反向思考一下，价值为3的情况是什么——存在最小的
n个数在[2n+1, 3n]且存在最大的n个数在[1, n]思索片刻可知，操作必然是
前排+后排或者后排+前排，这里也对应2种情况：- 最小的
n个数只在[1, 2n] - 最大的
n个数只在[n+1, 3n]
这里注意理解一下
同时这两种情况也存在交叉的地方。
思考最小的
n个数只在[1, 2n]有多少种情况：[1,2n]选择n个位置，然后全排列：C(2n, n)*fac[n]- 剩下位置全排列：
fac[2n]
思考交叉部分的情况：
细细一琢磨，发现情况有点多，但是我们可以接受O(n)的暴力。
于是设最小的n个数，在[1,n]中有n-x个数，在[n+1,2n]中有x个数。[1,n]中选n-x个位置给最小的n个数：C(n, n-x)[n+1,2n]中选x个位置给最小的n个数：C(n, x)[n+1,3n]中剩下2n-x个位置留给最大的n个数选择：C(2n-x, n)- 最小、中、大的
n个数分别自我全排列：fac[n] * fac[n] * fac[n]
枚举
x ~ [0,n]- 最小的
价值<=3
全排列：
fac[3n]
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
组合数板子未给出
inline void solve()
{
//init
cin>>n>>mod;
init_c();
//cal
vector <int> v(4, 0); //v[x]表示价值<=x的方案数
v[0] = 1;
v[1] = fac[2*n] + fac[2*n] - fac[n];
v[1] %= mod;
v[2] = C(2*n, n) * fac[n] %mod * fac[2*n] * 2 %mod;
int n3 = fac[n] * fac[n] %mod * fac[n] %mod;
for (int x=0; x<=n; x++) //减去容斥
{
v[2] -= C(n, n-x) * C(n, x) %mod * C(2*n-x, n) %mod * n3 %mod;
v[2] = (v[2]%mod + mod) %mod;
}
v[3] = fac[3*n];
//cal
v[3] -= v[2];
v[3] = (v[3]%mod + mod) %mod;
v[2] -= v[1];
v[2] = (v[2]%mod + mod) %mod;
v[1] -= v[0];
v[1] = (v[1]%mod + mod) %mod;
ans = 0;
for (int i=0; i<=3; i++)
{
ans += i*v[i];
ans %= mod;
}
//out
cout<<ans<<endl;
return;
}F.Wonderful Jump
算法本质
思维、dp
思路推演-1
整个题目看上去，很明显的线性dp，同时也很明显的发现复杂度不够，作为2900的题目，肯定是需要在某些地方做出改进的。
然后观察不同寻常的地方：
- 元素范围
[1,n] - 成本公式：min*(j-i)^2^
目标非常明确，通过这2个不同寻常的条件，改进dp方式，从而满足复杂度。
同时注意有平方，复杂度可能为n^1.5^，或者nlog~2~n。
元素范围暂时看不出什么花样来，那就算看成本公式。
通过成本公式可以推出2个性质：
性质1：对于
i --> j，如果存在i<k<j && a[k]<a[i] && a[k]<a[j]，则i-->k-->j 优于 i-->k
这个性质相当不错，这意味我们简化了模型，只用讨论最小值在两端的情况当前的性质1作为定性讨论的，其实可以深挖定量，但是定量出来的公式未知数多，没有明确的关系。
- 性质2： 成本公式是抛物线上升的，如果每次走一格，则成本是线性上升的，当
i j相差过大时，每次走一格的成本较低
对于性质1来说，可以简化我们讨论的情况，但是对于最小值在两端的情况，依然没有什么好的方法去解决。
对于性质2来说，就比较有用了，因为在最朴素的n^2^算法中，我们需要对前面所有的元素都遍历一次。但性质2给我们提供了一个新的思路，或许我们可以找到i j相差过大的阈值，然后减少遍历的次数。
对于i-->j (i<=k<=j)，设a[k]为其最小值，设A为a[i~j]的平均值i-->j（直达）的成本是：a[k]*(j-i)*(j-i)i-->j（步步走）的成本是：A*(j-i)
发现当j-i > A/a[k]时，则直达的成本>步步走的成本，这并不意味我们会选择步步走，而是说，那部分i j的直达可以不用讨论了，肯定不是最优解。
但是同时，我们并不确定A a[k]的范围，没有一个较大的意义，所以我们在这里必须强制规定，假设a[k]>=根号n。
为什么这里假设的是根号n而非log~2~n之类的：
1.根号n的复杂度是ok的
2.后面可能会用到一些除法翻转，这里数设置小了，可能下一步的算法复杂度更大了
3.先随便假设一下，大了小了后面看着调整
当保证了a[k]>=根号n，考虑最坏的情况（A==n），则可以推出：当i j差超过了sqrt(n)时，则直达一定不是最优解。
这表明了，当a[k]>=根号n，算法复杂度被降低为了n^1.5^。
思路推演-2
随后我们需要考虑a[k]<根号n的情况。（a[k]是指是a[i~j]的最小值）
兜兜转转找了一会，并没有发现什么不错的公式，那没办法了，只有老实用性质1分类讨论一下。
- 如果最右边的元素是最小值（
a[j]是最小值 && a[j]<根号n）
那这就好办了，既然又要保证a[j]是最小值，又要保证a[j]<根号n。
我们让i从j-1遍历到1，暴力i j，但是因为上面2个条件的限制，我们的总体复杂度为n^1.5^。
这里理解逻辑的话可以配合代码一起看。
讲一下为什么复杂度为n^1.5^：
当a[j]>=根号n时不会处理
当a[j]<根号n时，对于多个同样的值（值指a[j]），其总体复杂度为n，一共最多有根号n个不同值，所以复杂度为n^1.5^
- 如果最左边的元素是最小值（
a[i]是最小值 && a[i]<根号n）
这里我们把这些最小值用一个栈存起来，并且保证是递增的。（单调栈）
代码思路
我们固定j，移动i，每次i j变化的时候，就只会存在上述3种情况：
a[k]>=根号n
让i从j-1开始向后暴力遍历根号n个数即可。
同时在这里，其实并不需要真的去判断a[k]>=根号n，可以直接计算，也不会增加复杂度的。a[j]是最小值 && a[j]<根号n
注：这里必须保证a[j]<根号n当固定好
j时，移动i时，前几个数可能会高于a[j]形成这种情况。不过一旦遇到某个元素<=a[j]则会打破这种情况，进入下一个情况- else
这个else情况，全部都可以转化为a[i]是最小值 && a[i]<根号n。
对于固定的j来说，只需要和单调栈中存放的下标一一暴力历遍即可。
这里也没有什么硬性要求，可以直接计算，不会增加复杂度。
ac核心代码-思路1
头文件、宏定义、快读模板、常见变量、常见变量等略。
int dp[maxn];
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>ar[i];
mem(dp, 0x3f);
m = sqrt(n); //根号n
vector <int> v; //单调栈
//cal
dp[1] = 0;
v.push_back(1); //第一位特殊处理
for (int j=2; j<=n; j++)
{
//case 1
//a[k]>=根号n
int mi = ar[j]; //mi表示区间[i, j]中的最小值
for (int i=j-1; i>=max((int)1, j-m); i--)
{
mi = min(mi, ar[i]);
dp[j] = min(dp[j], dp[i] + mi*(j-i)*(j-i));
}
//case 2
//a[j]是最小值 && a[j]<根号n
if (ar[j]<=m) //这里必须有条件，不然复杂度会炸
{
for (int i=j-1; i>=1 && ar[i]>ar[j]; i--)
dp[j] = min(dp[j], dp[i] + ar[j]*(j-i)*(j-i));
}
//case 3
//其他情况-->转化为`a[i]是最小值 && a[i]<根号n`
for (int i:v)
dp[j] = min(dp[j], dp[i] + ar[i]*(j-i)*(j-i));
//维护一下单调栈
if (ar[j]<=m)
{
while (!v.empty() && ar[v.back()]>=ar[j]) //当前点的值更小，就删去之前的
v.pop_back();
v.push_back(j);
}
}
//out
for (int i=1; i<=n; i++)
cout<<dp[i]<<" \n"[i==n];
return;
}
评论 (0)