本文主要是介绍Codeforces Round #804 (Div. 2)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

比赛链接

其实这场的题都没有特别难，但D因为奇怪的问题卡住了，于是...

D

又是后面的DP都想出来了，但是不会判断一个区间是否能被完全消去...
容易发现消去的部分由一些长度为偶数的区间组成，且每个区间都是回文不对称的。然后原本一直在想：枚举每一个中心，求出可以消去的最大长度，然后就是已知一些合法区间，判断每个区间能否由这些合法区间的一部分组成的问题。如果把区间看做有向边，就是一个有向图求每个点可达集合的问题。但这个问题应该是没有办法在\(O(n^2)\)内解决的。
这时候应该向猜结论的方向思考一下：先想一下什么情况是一定不行的，那么容易想到：由于每次都消去不同的两个数，那么一定不能有一个数出现超过n/2次。然后又发现：只要不出现这种情况，似乎都可以的样子；事实上，对于合法的序列，每次一定会有相邻的两个不同的数，消去之后剩下的序列还是合法的，于是就归纳证明了！

所以这个结论其实并不难想到，难的是要往结论的方向去思考，而不是直接形式化地转到图论问题上。其实就算一开始想到图论，发现不可做之后也应该退回去想性质了。以后应该多注意不要在一个方向上卡太死，尤其是这种转化完之后并不可做的情况，要舍得放下之前的思路！

至于DP，一开始也在\(O(n^3)\)的做法上卡了好久（就是枚举最后剩下的那个数，然后f[i]表示前i个的最优解，每次枚举最后删去的一断转移）。然后发现可以直接令最后一个数为要保留的数（考虑最后剩下的那些数，直接令最后一个位置为我们想要的状态，并且发现是可以枚举上一个保留的位置来转移的）！
这样想来其实也是比较经典的减少状态的做法，关键是要跳出枚举最后剩下的数的思路（因为一开始想的时候觉得要确定这个才好做），然后考虑最终的（即答案的）状态，思考如何更简洁地表示和转移！

#include<bits/stdc++.h>
using namespace std;
const int N=5005,M=5e6+5;
int n,a[N],c[N];
bool is[N][N];
bool chk(int l,int r){
	//cout<<l<<" "<<r<<" "<<(find(l-1)==find(r))<<endl;
	if(r<l) return 1;
	return is[l][r];
}
int f[N];
void work(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) c[j]=0;
		int mx=0;
		for(int j=i;j<=n;j++){
			c[a[j]]++;
			mx=max(mx,c[a[j]]);
			is[i][j]=((j-i)&1 && mx<=(j-i+1)/2);
		}
	}
	for(int i=1;i<=n;i++){
		if(chk(1,i-1)) f[i]=1;
		else f[i]=-1;
		for(int j=1;j<i;j++) if(a[j]==a[i] && ~f[j]){
			if(chk(j+1,i-1)) f[i]=max(f[j]+1,f[i]);//cout<<j<<endl;
		}
		//cout<<i<<" "<<f[i]<<endl;
	}
	int mx=0;
	for(int i=1;i<=n;i++) if(chk(i+1,n) && ~f[i]) mx=max(mx,f[i]);
	cout<<mx<<endl;
}
int main()
{
	//srand(time(0));
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int T; cin>>T; while(T--) work();
	return 0;
}

E

主要是要大胆一点：首先想到枚举min或者max，求出另一个的最值；虽然这看起来复杂度很堪忧，但不妨先想下去。
如果枚举了min，那么可以\(O(nlnn)\)DP算出每个数分解的因数的max的最小值（从小往大遍历，每个数枚举其倍数转移）;然后发现这个DP的过程其实是可以随着min的减少改变的，所以min从m到1扫一次，每次记录一下每个数当前的DP值，用set维护全局最大值即可。

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,m,f[N];
bool is[N];
multiset<int>st;
void work(){
	cin>>n>>m;
	for(int i=1;i<=m;i++) f[i]=is[i]=0;
	st.clear();
	int mn=m;
	for(int x,i=1;i<=n;i++) scanf("%d",&x),is[x]=1,mn=min(mn,x);
	int ans=m;
	//cout<<is[35]<<endl;
	for(int i=m;i;i--){
		//cout<<"i="<<i<<endl;
		f[i]=i;
		if(is[i]) st.insert(i);//cout<<"ins:"<<i<<endl;
		for(int j=i;j<=m/i;j++){
			int x=max(f[j],f[i]),k=i*j;
			if(x<f[k]){
				if(is[k]){
					st.erase(st.find(f[k]));
					//cout<<"erase:"<<f[k]<<endl;
					st.insert(x);
					//cout<<"ins:"<<x<<endl;
				}
				f[k]=x;
			}
		}
		if(i>mn) continue;
		multiset<int>:: iterator it=st.end();
		it--;
		ans=min(ans,*it-i);
		//cout<<i<<" "<<(*it)<<endl;
	}
	cout<<ans<<endl;
}
int main()
{
	//srand(time(0));
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int T; cin>>T;
	while(T--) work();
	return 0;
}

这篇关于Codeforces Round #804 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！