10月4日 CSP-S 模拟赛总结

2457

题目大意

给定一个长度为 \(n\) 的排列 \(A\)，问交换两数的位置，最多能使逆序对的数量减少多少

思路

50 pts（\(n^2\)）

开两个二维数组， f1[i][j] 表示 \(i\) 与 \(j\) 互换位置时对于 \(i\) 减少的逆序对数量（也可以是增加），f2[i][j] 与 f1[i][j] 同理，不过是对于 \(j\) 来说的。

接下来考虑转移，对于 f1[i][j]，如果 \(a[i]>[j]\)，那么 \(f1[i][j]=f1[i][j-1]+1\)，否则，\(f1[i][j]=f1[i][j-1]-1\)。f2 同理。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+1;
int n,ans;
bool flag;
int a[maxn];
int f1[1001][1001];//i减少的逆序对 
int f2[1001][1001];//j减少的逆序对 
signed main()
{
	//freopen("2457.in","r",stdin);
	//freopen("2457.out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		if(a[i]<a[i-1])flag=1;
	}
	if(!flag)
	{
		cout<<0<<endl;
		return 0;
	}
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)
		{
			if(a[i]>a[j])
				f1[i][j]=f1[i][j-1]+1;
			else
				f1[i][j]=f1[i][j-1]-1;
		}
	for(int i=n;i>=1;--i)
		for(int j=i+1;j<=n;++j)
		{
			if(a[i]>a[j])
				f2[i][j]=f2[i+1][j]+1;
			else
				f2[i][j]=f2[i+1][j]-1;
		}
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)
			ans=max(ans,f1[i][j]+f2[i][j]);
	cout<<ans-1<<endl;
	return  0;
}

100 pts

不会

2458

题目大意

给定一个长为 \(n\) 的序列 ，可以进行下述操作：选择一个下标 \(i\)，将 \((a_i,a_{i+1},a_{i+2})\) 替换成
\((a_{i+1},a_{i+2},a_i)\)。
构造一个长度不超过 \(n^2\) 的操作序列，使得操作完毕后，序列升序排列。

思路

先考虑原序列是一个排列的情况。

我们先将元素 \(1\) 换到最前面，再将元素 \(2\) 换到第二位……直到 \(n-2\) 也这样完成。于是，现在序列要么形如 \(1,2,...,n-2,n-1,n\)，要么形如 \(1,2,...,n-2,n,n-1\)。前一种已经完成了，那后一种怎么办呢？

其实可以证明，如果此时出现了后一种情况，那么是无解的。考虑对排列定义“排列的符号”：\((-1)^{逆序对的数量}\)。当交换了相邻两个数之后，因为逆序对数要么增加一，要么减少一，所以无论如何“排列的符号”都会变号。（事实上，我们可以拓展这个结论，在一个排列中交换任意两个数，排列的符号都会发生改变）

而题面中的操作就相当于做了两次相邻元素交换，于是在进行一次题面操作后，排列的符号保持不变。所以，如果出现了 \(1,2,...,n-2,n,n-1\) 这种情况，那说明初始排列的符号和目标排列的符号是不同的，于是无解。

那么如果原序列不是一个排列呢？我们不妨将其转化成一个排列。如果有相同的元素，我们不妨随便钦定一个它们之间的大小关系，然后再进行离散化，这样原序列就变成一个排列了（直接随机排列）。可要是这样变化后无解，不代表原序列就无解。但是，我们可以挑出一对相同的元素，反转它们被钦定的大小关系。下面是一个例子。

比如，原序列是 \(2,3,3,3\)，可能变化出来的序列是 \(1,2,4,3\)，这是无解的。但是，我们可以交换两个“大小相邻”的 3 的顺序，变成 \(1,2,3,4\)，这样就是有解的了。

因此，如果原序列没有相同元素，那么离散化后使用对于排列的算法即可。如果有相同元素，那么仍然可以把它转化成排列的情况，并且可以转化成两个符号不同的排列，而其中一个必定有解，也套用上述算法即可。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e3+1;
int n;
bool flag;
int a[maxn];
int b[maxn];
vector<int> ans;
inline void change(int x)
{
	ans.push_back(x);
	swap(b[x],b[x+1]);
	swap(b[x+1],b[x+2]);
}
inline bool solve()
{
	ans.clear();
	for(int i=1;i<=n;++i)
		b[i]=a[i];
	for(int i=1;i<=n-2;++i)
	{
		int maxx=b[1];
		vector<int> box;
		for(int j=1;j<=n-i+1;++j)
		{
			if(maxx<b[j])
			{
				maxx=b[j];
				box.clear();
				box.push_back(j);
			}
			else if(maxx==b[j])
				box.push_back(j);
		}
		srand(time(0));
		random_shuffle(box.begin(),box.end());
		int x=box[0];
		while(x<=n-i-1)
		{
			change(x);
			x+=2;
		}
		if(x==n-i)
		{
			change(x-1);
			change(x-1);
		}
	}
	if(b[1]>b[2])
		return false;
	return true;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	if(n<=2)
	{
		if(n==1)
			cout<<0<<endl;
		if(n==2)
		{
			if(a[1]<=a[2])
				cout<<0<<endl;
			else
				cout<<-1<<endl;
		}
		return 0;
	}
	for(int i=1;i<=10;++i)
	{
		flag=solve()?true:false;
		if(flag)break;
	}
	
	if(!flag)
	{
		cout<<-1<<endl;
		return 0;
	}
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();++i)
		cout<<ans[i]<<' ';
	return 0;
}

2459

鸽

2460

题目大意

给定 \(n\)，\(m\) 保证 \(m\le n\)，计算满足下面条件的排列个数：

长度为

不存在相邻两个数和为 \(m\) 或 \(m+1\)

对 \(10^9+7\) 取模。