Codeforces 1400F. x-prime Substrings 题解

题目链接:F. x-prime Substrings

题目大意:洛谷


题解:这次官方题解看懂了,但是想不到一个高效的构造方法,所以再一次放弃。(还是菜,虽然后来发现暴力就能过

翻了一下提交记录学到了另一个做法。

我们考虑 DP,设(f[i][mask])表示当前已经到了第(i)个位置,前缀和表示为(mask)时向后的最小删除个数。

这样的转移方法就是枚举当前位置选或不选,然后往把一个位置的 DP 值拿过来即可。

然后判断前缀和是否合法也很简单,先判断前缀和中有没有(x)(大于(x)的前缀和已经全部可以删掉了),如果有再判断有没有前缀和是(x)的约数的。

但是很明显这种方法会有反例,但是我们发现其实如果出现(x)的约数的话,那么前缀和中比这个约数大的(也就是在前缀和中构成这个约数之前的数)可以全部删掉了,这样的话正确性得到了保证,还减少了状态数。

但是这样的话粗略上界是(O(ncdot d))(其中(d)为有效的状态数)的,看起来很不能过的样子。

但是本题的性质保证(d)不会很大(更加准确一些的说,是不会超过(5000)),所以这种做法能够通过。

存储状态的话直接用 unordered_map 就可以了。

代码:

#include <cstdio>
#include <unordered_map>
using namespace std;
const int Maxn=1000;
int n,x;
char s[Maxn+5];
int a[Maxn+5];
unordered_map<int,int> f[Maxn+5];
int dmask;
bool check(int mask){
	if(((mask>>x)&1)==0){
		return 1;
	}
	if(mask&dmask){
		return 1;
	}
	return 0;
}
void calc(int& mask){
	mask&=((1<<x)-1);
	int tmp=mask&dmask;
	if(tmp==0){
		return;
	}
	tmp&=-tmp;
	mask&=(tmp-1);
}
int dfs(int u,int mask){
	if(u>n){
		return 0;
	}
	calc(mask);
	if(f[u].count(mask)>0){
		return f[u][mask];
	}
	int nmask=mask;
	int ans=dfs(u+1,mask)+1;
	mask=(mask<<a[u])|1;
	if(check(mask)){
		ans=min(ans,dfs(u+1,mask));
	}
	return f[u][nmask]=ans;
}
int main(){
	scanf("%s",s+1);
	while(s[++n]!='');
	n--;
	for(int i=1;i<=n;i++){
		a[i]=s[i]-'0';
	}
	scanf("%d",&x);
	for(int i=1;i<x;i++){
		if(x%i==0){
			dmask|=(1<<i);
		}
	}
	printf("%d
",dfs(1,1));
	return 0;
}
本博客欢迎转载,转载请注明文章出处作者
原文地址:https://www.cnblogs.com/withhope/p/13574978.html