首页 > 其他分享 >[SDOI2009] Bill的挑战 (状压DP)

[SDOI2009] Bill的挑战 (状压DP)

时间:2024-04-09 10:22:05浏览次数:29  
标签:ch int Bill 枚举 le DP SDOI2009 dp define

[SDOI2009] Bill的挑战

题目描述

Sheng_bill 不仅有惊人的心算能力,还可以轻松地完成各种统计。在昨天的比赛中,你凭借优秀的程序与他打成了平局,这导致 Sheng_bill 极度的不满。于是他再次挑战你。这次你可不能输。

这次,比赛规则是这样的:

给出 \(N\) 个长度相同的字符串(由小写英文字母和 ? 组成),\(S_1,S_2,\dots,S_N\),求与这 \(N\) 个串中的刚好 \(K\) 个串匹配的字符串 \(T\) 的个数,答案对 \(1000003\) 取模。

若字符串 \(S_x(1\le x\le N)\) 和 \(T\) 匹配,满足以下条件:

  1. \(|S_x|=|T|\)。
  2. 对于任意的 \(1\le i\le|S_x|\),满足 \(S_x[i]= \texttt{?}\) 或者 \(S_x[i]=T[i]\)。

其中 \(T\) 只包含小写英文字母。

输入格式

本题包含多组数据

第一行一个整数 \(T\),表示数据组数。

对于每组数据,第一行两个整数,\(N\) 和 \(K\)。

接下来 \(N\) 行,每行一个字符串 \(S_i\)。

输出格式

每组数据输出一行一个整数,表示答案。

样例 #1

样例输入 #1

5

3 3

???r???

???????

???????

3 4

???????

?????a?

???????

3 3

???????

?a??j??

????aa?

3 2

a??????

???????

???????

3 2

???????

???a???

????a??

样例输出 #1

914852

0

0

871234

67018

提示

数据规模与约定

  • 对于 \(30\%\) 的数据,\(N\le5\),\(|S_i|\le20\);
  • 对于 \(70\%\) 的数据,\(N\le13\),\(|S_i|\le30\);
  • 对于 \(100\%\) 的数据,\(1\le T\le 5\),\(1\le N \le15\),\(1\le|S_i|\le50\)。

分析

题目给的\(|S|\)其实就是\(S.lenth\)
不会有人和我一样一眼没看出来吧

看眼数据不难想到应该枚举位数,那么维护数组\(g[i][j]\)表示第\(i\)个位数放\(j\)的情况下该列的情况

定义\(dp[i][j]\)为\(T\)串已经匹配了\(i\)位,且与\(n\)个字符串是否匹配的集合为\(j\),状态边界为\((1<<n)\)

所以\(dp[0][(1<<n)-1]=1\)

首先枚举位数,然后枚举状态

如果\(dp[i][j]==0\)不需要进行操作

之后枚举字符,在下一状态下添加字符的种类数为本状态加上下一状态的原种类数

得到的状态转移方程即为

\[dp[i+1][j\&g[i][k]]=dp[i+1][j\&g[i][k]]+dp[i][j] \]

最后枚举不同状态,记录该状态与原数组的匹配情况

判断该状态是否包括某一行的位数(即该行匹配)

如果是则\(tot++\),如果\(tot=m\),叠加\(dp[len][当前状态]\),得到\(ans\)

最后别忘了要取mod

code

Elaina's code
#include<bits/stdc++.h>
using namespace std;
const int N=50100;
const double eps=1e-8;
#define int long long
#define inf 0x3f
#define INF 0x3f3f3f3f
#define mst(a,b) memset(a,b,sizeof(a))
#define re register
#define Elaina 0
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

int mod=1e6+3;
int dp[55][1<<15],g[55][30];
char s[16][55];
int T,n,m;

main(){
	T=read();
	while(T--){
		mst(dp,0);
		mst(g,0);
		n=read(),m=read();
		for(int i=0;i<n;i++){
			scanf("%s",s[i]);
		}
		int len=strlen(s[0]);
		for(int i=0;i<len;i++){//位数
			for(int j=0;j<26;j++){//字符
				for(int k=0;k<n;k++){//行数
					if(s[k][i]=='?'||s[k][i]==j+'a'){
						g[i][j]|=(1<<k);//匹配情况
					}
				}
			}
		}
		dp[0][(1<<n)-1]=1;
		for(int i=0;i<len;i++){//位数
			for(int j=0;j<(1<<n);j++){//状态
				if(dp[i][j]){
					for(int k=0;k<26;k++){//字符
						dp[i+1][j&g[i][k]]=(dp[i+1][j&g[i][k]]+dp[i][j])%mod;
					}
				}
			}
		}
		int ans=0;
		for(int i=0;i<(1<<n);i++){//状态
			int tot=0;
			for(int j=0;j<n;j++){
				if(i&(1<<j)){
					tot++;
				}
			}
			if(tot==m){
				ans=(ans+dp[len][i])%mod;
			}
		}
		printf("%lld\n",ans);
	}
	return Elaina;
}
/*
5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??
*/

标签:ch,int,Bill,枚举,le,DP,SDOI2009,dp,define
From: https://www.cnblogs.com/Elaina-0/p/18123226

相关文章

  • Bill的挑战
    看数据范围就知道应该要状压,也不难看出应该压缩位数的状态。所以设f[i][j]为前i位,相互匹配的字符串的状态。那么,就会有f[i+1][j&a[i][ch]]=(f[i+1][j&a[i][ch]+f[i][j])%mod。其中a[i][j]表示满足第i位为j所对应的字母的字符串的状态。所以只要枚举长度为l(其中一个字符串的......
  • 斜率优化 DP
    对于这样一类方程\(dp_i=\min\limits_{j=1}^{i-1}(dp_j-a_ic_j)\),其中\(a,c\)都为正整数且递增:如果直接计算,时间复杂度为\(\mathcal{O}(N^2)\)。使用斜率优化,可以将时间复杂度将为\(\mathcal{O}(N)\)。在学习本节之前,请先学会单调队列,还要知道在平面直角坐标系中,斜率越小......
  • 小红不想做完全背包 (hard)(DP)--牛客周赛 Round 39-D
    #include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'#defineinf1e18constintmod=1e9+7;constintN=2005;//typedef__int128lll;//typedefunsignedlonglongull;intn,p;inta[N],dp[N];voidsolve(){......
  • Linux命令之lldptool命令
    LLDP是一个数据链路层发现协议,LLDP协议使得接入网络的一台设备可以将其主要的能力,管理地址,设备标识,接口标识等信息发送给接入同一个局域网络的其它设备。lldptool工具采用的是LLDP协议,一般我们使用lldptool是为了得到设备的物理拓扑结构以及管理配置信息,比如说,和eth1网口相连的网......
  • 状态压缩dp——动物园
    题目描述新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上,包含一大圈围栏,每个围栏里有一种动物。如下图所示:你是动物园的公关主管。你要做的是,让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观,你希望能让他们在动物园度过一段美好的......
  • JUC:ThreadPoolExecutor线程池的使用方法
    文章目录ThreadPoolExecutor线程池状态构造方法Executors工厂方法newFixedThreadPoolnewCachedThreadPoolnewSingleThreadExecutor提交任务方法关闭任务方法ThreadPoolExecutor线程池状态线程池用高三位表示状态,第一位为符号位。TERMINATED>TIDYING>STOP>......
  • 如何避免WordPress中文乱码现象
    在使用WordPress网站的过程中,很多用户都会遇到中文乱码的问题。中文乱码会给用户阅读和浏览网站带来困扰,也可能影响网站的用户体验和搜索引擎优化。在本篇文章中,我们将介绍一些解决WordPress中文乱码问题的方法,并提供具体的代码示例。1、设置数据库字符集:首先,要确保数据库字符集......
  • WordPress访问不了?快速解决方法大揭秘!
    《WordPress访问不了?快速解决方法大揭秘!》WordPress作为一个流行的内容管理系统,被广泛应用于网站建设领域。然而,有时候我们可能会遇到WordPress网站无法访问的情况,这个问题如果不及时处理,会影响网站的正常运行,进而影响用户体验。本文将探讨常见的WordPress网站无法访问问题,并提供......
  • WordPress网站乱码怎么办?快速解决方案
    在使用WordPress建立网站的过程中,有时候会遇到网站页面出现乱码的情况,这会影响用户体验和网站的可读性。造成网站乱码的原因可能有很多,比如字符编码设置不正确、插件冲突、主题代码问题等。本文将为您介绍一些快速解决WordPress网站乱码问题的具体方法,并提供相应的代码示例。1.......
  • 解决WordPress页面错位问题的实用技巧
    解决WordPress页面错位问题的实用技巧WordPress作为世界上最流行的内容管理系统之一,提供了强大的功能和灵活的定制性,使得许多网站管理员和开发人员选择使用它来搭建自己的网站。然而,有时候在使用WordPress创建页面时,可能会遇到页面错位的问题,导致页面布局混乱,影响用户体验。那么,......