Educational Codeforces Round 133 (Rated for Div. 2)

A. 2-3 Moves

题目链接：Problem - A - Codeforces

样例输入:

4
1
3
4
12

样例输出：

2
1
2
4

题意： 给定一个n，问我们至少要经过多少次 *** 作可以从0号点到达n号点，每次 *** 作我们可以选择向左或者向右移动2步或者3步。

分析：由贪心策略知我们肯定是尽可能地选择每次移动3步的 *** 作，如果一直向右移动3步最后剩余2步那么我们最后就直接移动2步，而如果最后剩余1步，那么按道理来说我们应该向右移动3步再向左移动2步，但是这样会多一次 *** 作，不如我们上一次在离n点距离为4的时候直接选择两次向右移动2步的 *** 作，这样会节省一些时间，还有一种特殊情况需要我们特判一下，就是n=1的情况，这种情况我们没办法回退一次，所以只能是先向右移动3步再向左移动2步。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		n=abs(n);
		if(n%3==0) printf("%d\n",n/3);
		else printf("%d\n",n/3+1);
	}
	return 0;
} 

B. Permutation Chain

题目链接：Problem - B - Codeforces

样例输入： 

2
2
3

样例输出：

2
1 2
2 1
3
1 2 3
3 2 1
3 1 2

题意：每次给定一个n，给定一个1~n的排列数组a，f(a)等于,让我们构造一个最大的k，满足f(a1)>f(a2)>……>f(ak)且排列ai是由排列ai-1交换其中一对数对得到，输出a1~k。

分析：其实通过分析不难得到我们可以构造一个k=n的情况，而且由于排列ai是由排列ai-1交换其中一对数对得到,那么第一次交换至少要使得f值减2，所以一定有k<=n，下面介绍一种k==n的构造方法。一开始我们的数组肯定是ai=i的，然后我们从i=2开始，每次令a[i]与a[1]交换，这样就能够使得f值减1，而且满足所给规则。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) a[i]=i;
		printf("%d\n",n);
		for(int i=1;i<=n;i++) printf("%d ",a[i]);
		puts("");
		for(int i=2;i<=n;i++)
		{
			swap(a[1],a[i]);
			for(int j=1;j<=n;j++) printf("%d ",a[j]);
			puts("");
		}
	}
	return 0;
}

D. Chip Move

题目链接：Problem - D - Codeforces

 样例输入：

10 2

样例输出：

0 1 0 1 1 1 1 2 2 2 

题意：给定一个n，我们要求出从0移动到x的方案数（1<=x<=n），给定一个k，移动规则是第一次移动的距离能够被k整除，第2次移动的距离能够被（k+1）整除，……,第m次移动的距离能够被(k+m-1)整除，求解到达1，2，……，n的不同方案数，注意每次移动距离都是大于0的。

分析：我们先来看一下移动到x的最大 *** 作次数是多少，不妨设k是1，那么就有1+2+3+……m>n,不难得到m是小于700的，也就是说 *** 作轮次是不可能大于700的。

设f[i][j]表示j轮到达i点的方案数，然后容易想到f[i][j]=f[i-d][j]+f[i-d][j-1],d代表第j轮 *** 作的最小距离，其中f[i-d][j]代表到达i-d这个点是通过移动d的倍数得到的，那么我们完全可以把倍数+1移动至i，而f[i-d][j-1]是通过前j-1轮 *** 作到达的i-d，那么最少移动d到达i。

这样我们就写完了状态转移方程，如下：

for(int i=1;i<=n;i++)//枚举走到的位置 
	{
		for(int j=1;j<=700&&i>=(k+j-1);j++)//枚举当前跳的轮次
		{
			f[i][j]=(f[i-(k+j-1)][j]+f[i-(k+j-1)][j-1])%mod;
			sum[i]=(sum[i]+f[i][j]);
		}
		printf("%d ",sum[i]);
	}

但是这样显然有一个问题，就是空间复杂度有点高，也就是说700*n=1.4e8超过内存了，我们需要对其进行空间优化，通过观察状态转移方程我们不难发现，f[][j]只由f[][j]和f[][j-1]得到，于是根据以往空间优化的经验来说我们需要把内外层循环交换位置，并且使用滚动数组优化这个状态转移方程即可，代码如下：

for(int j=1;j<=700;j++)//枚举当前跳的轮次
	{
		for(int i=1;i<=n;i++)//枚举走到的位置 
		{
			if(1ll*(2*k+j-1)*j>1ll*2*i) continue;
			f[i][1]=(f[i-(k+j-1)][1]+f[i-(k+j-1)][0])%mod;
			sum[i]=(sum[i]+f[i][1])%mod;
		}
		for(int i=1;i<=n;i++)
			f[i][0]=f[i][1],f[i][1]=0;
	}

其中我们用if语句进行了剪枝，原理就是j轮 *** 作至少移动的位置是k+(k+1)+……+(k+j-1)=(2*k+j-1)*m/2,而这个位置是要小于等于i的，否则就不可能满足题意。空间优化的方法就是每次用f[][0]和f[][1]更新f[][1],最后再把值赋给f[][0],这个地方不要忘记把f[i][1]初始化为0，否则会出错。