比赛链接：https://codeforc.es/contest/1716

A了两道题 A和B，速度还可以，但是CD态度太大一个也没做出来。

A题：给出一个数n，从0点开始到n点，每次只能走2步或3步，也可以回退。求最少多少次可以走到n点。

很简单，我们优先考虑3，如果是3的倍数可以直接/3过去，否则我们需要回退一个3这一个操作我们并不需要浪费一次，然后用两个2到达终点。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int sum = 0;
		sum = n/3;
		if(sum*3<n)
		{
			sum++;
		}
		if(n==1)	sum=2;
		cout<<sum<<endl;
	}
}

B题：大意是给出一个n，输出一些长度为n的数据我们定义为ki，对于任意一个ki，我们可以交换任意两个位置的元素，如果元素被改变，我们令固定性=n--改变的数量。这k组数组，我们要求严格固定性ki>ki+1。输出最多可以组数，存在多个输出任意。

解决方法：我们每次交换两个，最多可以使得严格意义执行n次，即第一次固定性为n，然后n-2，n-3一直到0

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
vector<int>ve;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		ve.clear();
		int n;
		cin>>n;
		cout<<n<<endl;
		for(int i=1;i<=n;i++)
			ve.push_back(i);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<ve.size();j++)
				cout<<ve[j]<<' ';
			cout<<endl;
			swap(ve[i],ve[i+1]) ;
		}
	}
}

C题：大意是有2*m个格子，每个格子有个开放时间，只有在开放时间之后才能进入这个格子。机器人在0,0位置，需要求出最少多长时间可以走完所有格子 “每个格子只能走一遍” href="http://www.cxb520.cn/content/uploadfile/202208/71c01659771187.jpg" target="_blank">

通过观察我们可以发现，行走方式只有  波浪行 和 绕行。

我们首先可以求出每个位置所需的最短时间，  影响因子有   对应另一行的时间+1，波浪行和绕行，其中一个最大值。

我们枚举所有的列，对于列中的每一行中的位置，我们可以通过绕行到达或者之前我们计算的时间到达。这样在这个过程当中，我们可以更新波浪行，然后对于我们需要求的当前列中的元素，我们看看波浪行和存储的可达到时间哪个小。由此我们可以知道在哪个位置改为波浪行所有时间更少。总共计算m列，我们可以在一个最佳位置中选出最少时间。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
const int nn = 2e5+10;
int a[3][nn];
int dp[3][nn]; 
int m;
int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>m;
		for(int i=0;i<2;i++)
			for(int j=0;j<m;j++)
				cin>>a[i][j];
		a[0][0] = -1;
		dp[0][m] = 0,dp[1][m] = 0;
		for(int j=m-1;j>=0;j--)
			for(int i=0;i<2;i++)
				dp[i][j] = max(max(a[1-i][j]+1,a[i][j]+2*(m-j)),dp[i][j+1]+1);
		//a[1-i][j]+1  是从上进入下 或 从下进入上的时间
		//a[i][j]+2*(m-j) 是上下绕行
		//dp[i][j+1]+1 是由身后的位置转移过来	 
		int cur = 0;
		int ans = 0x3f3f3f3f;
		for(int i=0;i<m;i++)
		{
			int k = i&1;
			ans = min(ans,max(cur,dp[k][i]));//让ans更新至  当前走过的时间和走到ki位置所需的等待时间的最大值 
			cur = max(cur,a[k][i]+2*(m-i));//cur更新至两个绕行路径的最大时间 
			cur = max(cur,a[1-k][i]+2*(m-i)-1);
		}
		cout<<ans<<endl;			
	}
}

D题：大意是给出一个数n，给出一个初始间距k。询问0 - x（1<=x<=n），询问有多少种方式可以到达。对于当前数，它可以到达某个数-当前数的值是k的倍数的数，在到达一次后，k值会往上+1，最后我们需要正好到达  x。求出到达每一个x的方式数量。

我们定义f[i]为m到达当前i的数量，这个值等于之前m到达i的量的总和
s[i]为之前所有m到达i量的总和，上一个m可以通过i-m获取。
通过观察，我们可以试着列出所有的m 当累加<=n时。依次来更新所有f[i]，通过每一次的f[i]由此更新所有ans。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)

const int nn = 400005;
const int mod = 998244353;

int s[nn],f[nn],ans[nn];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,m;
	cin>>n>>m;
	f[0] = 1;
	int wc = 0;
	while(m<=n&&wc<=n){//当间隔依次是  1 2 3 ...  s总和<=n  时，能否到达某个i点 
		for(int i=0;i<=n;i++){
			int tmp;//上一个阶段前缀值的和 
			if(i-m>=0)	tmp = s[i-m];
			else tmp = 0;
			s[i] = (tmp+f[i])%mod;//这里的fi 是m-1阶段  到达目标i的可能性数  
			f[i] = tmp;//si的前缀和等于 si-m  +  本阶段m  ，所以能够到达 
			ans[i] = (ans[i]+f[i])%mod;
		}
		wc+=m++;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
}