Codeforces Round #842 (Div. 2)（B，D，E）
B题实在是没想到
B
这个题大意是给你一个乱序的一到n的数，我们每次可以选择k个数，放到这个数组的最后面，问我们需要最少多少个操作可以把这个数组变成1到n的顺序
我在做这一道题的时候想了很多，其实没有我先前想的那么复杂，下面是我的小小的感觉（无法给出具体解释）
对于这样一段数
3 4 1 7 9 2 6 5 8
其中
3 4 （这两个必须放到后面，需要移动）
1（这个不需要动）
7 9 （这两个也需要移动到后面）
2（不需要动）
6 5 8（这三个也需要移动）
至于这些数的顺序，我们需要让较小的先移动，（先移动的在偏前面）
答案就是所有需要一定的数量除以k(向上取整)
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1e5+10;
int t,n,k;
void solve()
{
cin>>n>>k;
vector<int>a(n+1,0);
int last=1;
for (int i=1;i<=n;i++)
{
cin>>a[i];
if (a[i]==last)
{
last++;
}
}
int cnt=n-(last-1);
int ans=(cnt+k-1)/k;
cout<<ans<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C题我觉得就是模拟，很简单
D
这个题还是给我n个数（有可能是无序的）,还是把这个数组变成只有一个逆序对的顺序，但是我们每次只能交换ai和aj（i不等于j),问我们最少需要多少操作才可以完成
看到有一些题解里讲到了群论里的知识（我也没有深入，看不太懂），找了一个我觉得易懂的
只有一个逆序只能是这个逆序ai,aj（i,j一定是相邻的），比如1 3 2就是，3 1 2就不是，有两个
我们可以先找出要变成从小到大的操作数sum，如果在这个过程中出现过i和i+1需要交换位置，那我们可以不交换着一对,那么ans=sum-1，否则我们需要在完成这些操作后，再做一个操作，选择i和i+1，交换，ans=sum+1
那么我们怎么判断哪些数需要交换呢
这个用到了并查集
对于每一个位置的数，如果ai=i（那么这个位置不需要交换）
如果ai再j的位置，那么i，j一定需要交换（那么我们可以把i，j放到一个并查集里）
那我们如何通过并查集来求出需要变成从小到大的顺序，我举一个例子感受感受
| pos | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a[pos] | 3 | 1 | 2 | 4 |
这里最后1 2 3都会在一个集合里，需要进行2个操作才可以把这些变成有序的
3 1 2 变成 1 3 2（1的位置对了），变成 12 3 （2的位置对了，3是最后一个，不用管）
我们需要的并不是从小到大顺序，而是需要一对逆序，对于这一个案例，我们可以在变成1 3 2的时候就不需要了，最后变成了 13 2 4，ans=1
如果1 3 5在一个集合 （5 2 1 4 3）
最后会变成 1 2 5 4 3变成1 2 3 4 5 ，然后变成1 2 3 5 4（这个情况只能先变成有序，然后自己构造一个逆序对）ans=sum+1=2+1
一个集合的要变成有序的操作数是siz-1(最后一个一定是符号条件的，前面一个操作让1个变到它应该的位置)
#include <iostream>
using namespace std;
const int maxn=2e5+10;
int f[maxn],siz[maxn];
int t,n;
int find(int x)
{
if (x==f[x]) return x;
return f[x]=find(f[x]);
}
void merge(int x,int y)
{
int tx=find(x),ty=find(y);
if (tx==ty) return ;
f[ty]=tx;
siz[tx]+=siz[ty];
siz[ty]=0;
return ;
}
void solve()
{
cin>>n;
for (int i=1;i<=n;i++)
{
f[i]=i;
siz[i]=1;
}
int ans=0;
for (int i=1;i<=n;i++)
{
int tmp;
cin>>tmp;
int tx=find(i),ty=find(tmp);
if (tx==ty)
{
ans+=siz[tx]-1;
}
else
{
merge(tx,ty);
}
}
for (int i=1;i<n;i++)
{
int tx=find(i),ty=find(i+1);
if (tx==ty)
{
cout<<ans-1<<'\n';
return ;
}
}
cout<<ans+1<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
E
这个是一个排列组合的问题
问我们1到3n的所有不同排序变成从小到大的顺序需要的总次数模m的值
我们每一次可以选择下面两种操作中的一种，1，前2n个变成有序，2，后2n个变成有序
我们可以知道，不同的排列方式要变成从小到大最多需要3个排序（极端的情况3n在第一个位置，这种有3个）
需要0次排序的，原本就是1到3n的从小到大的排序，只有1种
需要1次排序的的，前n的是有序的，后2n个全排列减去有序的A(2n,2n),后n个是有序的，后2n个全排列减去有序的A(2n,2n)，还要注意前n个有序和后n个有序的交集（中间有序的和，但不包括1到3n有序的，这个两个情况都减去了）A(n,n)-1
cnt=2*(A(2n,2n)-1)-(A(n,n)-1)
需要排序两次的
总共需要
前2n个有1到n的，C（2n,n)*A(n,n)
后2n个有2n+1到3n的，C（2n,n)*A(n,n)
但是这样的情况还有交集
还有前面的排序的排列（也在这个大情况里）
减去交集
需要排序三次的我们通过反向求出
总共有A（3n,3n)减去上面的各种次数的数量，最后就是需要三次排序的排列数量
最后求和
我真的不太喜欢这个减去交集（很烦，老是理不清，我感觉我讲的也不是很好）
#include <iostream>
using namespace std;
const int maxn=3e6+30;
#define int long long
int mod;
int f[maxn],ipr[maxn];
int ksm(int x,int p)
{
int res=1;
while (p)
{
if (p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res;
}
void init(int x)
{
f[0]=f[1]=1;
for (int i=2;i<=x;i++)
{
f[i]=1ll*f[i-1]*i%mod;
}
ipr[x]=ksm(f[x],mod-2);
for (int i=x-1;i>=0;i--)
{
ipr[i]=1ll*ipr[i+1]*(i+1)%mod;
}
return ;
}
int C(int m,int n)//利用阶乘求组合数
{
int ans=f[n]*ipr[m]%mod*ipr[n-m]%mod;
return ans;
}
void solve()
{
int n;
cin>>n>>mod;
init(3*n+2);
int sum=f[3*n];
int sum1=f[2*n]*2ll-f[n]-1;
int sum2=2ll*f[2*n]%mod*f[n]%mod*C(n,2*n)%mod;
for (int i=0;i<=n;i++)
{
int a=C(i,n)*C(n-i,n)%mod*C(n,2*n-i)%mod*f[n]%mod*f[n]%mod*f[n]%mod;
sum2-=a;
sum2+=mod;
sum2%=mod;
}
sum2--;
sum2+=mod;
sum2%=mod;
sum2-=sum1;
sum2+=mod;
sum2%=mod;
sum=(sum-sum2+mod)%mod;
sum=(sum-sum1+mod)%mod;
sum--;
sum=(sum+mod)%mod;
int ans=(sum1+sum2*2)%mod;
ans=(ans+sum*3)%mod;
cout<<ans<<'\n';
return ;
}
signed main ()
{
int t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}