PermutationForces II
算法本质
思维
题目大意
给定长度为n排列a[] b[]，其中b[]的部分元素丢失，使用-1代替。
玩家将执行以下n个操作，希望将a[]修改成b[]的合法情况：
- 对于第
i次操作，选择a[]中两个元素的值x y，保证其i ≤ x ≤ y ≤ i+k，然后交换其位置
（特别注意，是值而非下标）
输出可以抵达b[]合法的种类数。（不是方法数！）
思路推演
规则看似复杂，上手模拟即可发现，大部分情况第i回合我们必须将a[]中值为i的元素放在合法位置，不然以后将无法移动。
那接着思考，如果这个值已经在合法位置，能否为其他事情做一些贡献。
当然我们希望其最好不能，不然情况会变得更加复杂
这里值的其他事件例如：
4 2
1 2 3 5 4
1 5 3 2 4在上面这个样例中，当2希望走到合法位置时，其需要与5交换，同时元素1已经直接在合法位置了，能否为2做一些贡献。
显然不可行，因为2无法走到合法位置，就是因为其距离太远，而1<2，距离会更远了。
接着思考-1带来的影响。
当x希望找到合法位置时，也许其会发现自己的合法位置是-1，而-1的位置并不唯一。
由于我们之前的操作，可以知道1~x-1都已经合法了——观察那些站立于-1位置上的值，其一定>=x，只要在可行范围内，皆可随意索取。
注意思考核心，操作仅与元素值有关、与元素位置无关。
我们的操作具备十足的方向性，在这个方向性下，元素位置完全无关紧要（对于-1情况还是存在一定影响的）
朴素的想，我们从小开始遍历值x，如果这个值在b[]中有具体的位置，则我们按照题目要求操作即可。
否则，我们遍历b[]中的-1，若其同下标的a[]的值>=x && <=x+k值，说明其对x来说是可选的，x可以随机选择一个（随机选择不会影响结果），然后按照题目要求操作即可。
这样就可以得到最终的结果了。
优化 - 虚拟修改
我们可以将上面的两种操作分类：
- 常规操作
x在b[]有具体的位置 - -1操作
x在b[]中没有具体的位置
其中常规操作来说，b[i]==-1的a[i]来说，常规操作只会使其的值增加。
所以我们完全没必要真实地进行操作，在-1操作时，只需要检查b[i]==-1且a[i]<=x+k的值即可。
同理，-1操作也并不需要实际操作，只需要记录之前进行的-1操作次数，即不可占领的点会对应的减少。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>k;
vector<int> a(n+5), b(n+5), posa(n+5), cod(n+5), v;
read(a, 1, n);
read(b, 1, n);
for (int p=1; p<=n; p++)
{
if (b[p]==-1) v.push_back(a[p]);
else posa[b[p]] = p;
}
sort(v.begin(), v.end());
int cnt=0; // cnt记录-1的占领次数
int ans=1;
for (int val=1; val<=n; val++)
{
if (posa[val]) // 普通情况
{
if (a[posa[val]] - val > k) // 距离不够
ans=0;
}
else
{
int w = upper_bound(v.begin(), v.end(), val+k) - v.begin() - cnt; // 这个二分可以预处理把log优化掉的
ans = ans*w%mod;
cnt++;
}
}
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)