【50.54%】【BZOJ 1879】[Sdoi2009]Bill的挑战
2024-09-06 16:02:32
Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 649 Solved: 328
[Submit][Status][Discuss]
Description
Input
本题包含多组数据。 第一行:一个整数T,表示数据的个数。 对于每组数据: 第一行:两个整数,N和K(含义如题目表述)。 接下来N行:每行一个字符串。
Output
1 2 1 a? ?b
Sample Input
50
Sample Output
对于30%的数据,T ≤ 5,M ≤ 5,字符串长度≤ 20;
对于70%的数据,T ≤ 5,M ≤ 13,字符串长度≤ 30;
对于100%的数据,T ≤ 5,M ≤ 15,字符串长度≤ 50。
对于70%的数据,T ≤ 5,M ≤ 13,字符串长度≤ 30;
对于100%的数据,T ≤ 5,M ≤ 15,字符串长度≤ 50。
HINT
Source
【题解】
感觉自己的智商不够用了。哎。这个方法太巧妙了。
g[i][j]第i个字符是j或'?'的字符串有哪一些(代表一个集合二进制的0表示不在这个集合中,1表示在)。
f[i][j],前i-1个字符已经全部匹配了,已经匹配了的字符串的集合为j的方案数;
这个集合j里面的字符串。前i-1个字符是一样的。
if (f[i][j]) f[i+1][j&g[i][k]]+=f[i][j]; (k∈[1..26]);
//一开始的时候f[0][(1<<n)-1]=1;
//然后&这个位运算。可以排除掉那些第i位不是字母k的字符串。保留第i位是字母k的字符串。
//然后想想i=i+1的时候。我们再次找到的f[i][j]实际上就是满足第i-1位是一样的了。然后再看看第i为是不是字母k。再把不是....
//每次都按照这个规律。那么最后保存的集合j中字符串就全部是一样的了(或者有些不一样,但是可以把?转换成某个字母让他们全都一样)。
好棒的方法。
看看代码吧
【代码】
#include <cstdio>
#include <cstring> const int MOD = 1000003; int t, n, k, len,ans = 0;
int g[55][30],f[55][32768]; struct data2
{
char s[55];
}; data2 a[17]; void input_data()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%s", a[i].s);
} void get_ans()
{
len = strlen(a[1].s);
for (int i = 0; i <= len - 1; i++)
for (int j = 1; j <= n; j++)
for (int l = 1; l <= 26; l++)
if (a[j].s[i] == '?' || a[j].s[i] == (l + 'a' - 1))//问号的话可以
g[i][l] |= (1 << (j-1));//替代成任何字符。
f[0][(1 << n) - 1] = 1;
for (int i = 0; i <= len - 1; i++)
for (int j = 1; j <= (1 << n) - 1; j++)
if (f[i][j])
for (int l = 1; l <= 26; l++)
f[i + 1][j&g[i][l]] = (f[i + 1][j&g[i][l]] + f[i][j]) % MOD;
for (int j = 0; j <= (1 << n) - 1;j++)
{
int num = 0;
for (int l = 1; l <= (1 << n) - 1; l = l << 1)//统计j这个"集合"有多少个字符串
if (j & l)
num++;
if (num == k)
ans = (ans + f[len][j]) % MOD;
}
} void output_ans()
{
printf("%d\n", ans);
} void init()
{
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
ans = 0;
} int main()
{
//freopen("F:\\rush.txt", "r", stdin);
int t;
scanf("%d", &t);
while (t--)
{
init();
input_data();
get_ans();
output_ans();
}
return 0;
}
最新文章
- codeforces 515A.Drazil and Date 解题报告
- VS2010/2012配置优化记录笔记
- Android开发(二十四)——数据存储SharePreference、SQLite、File、ContentProvider
- mysql performance_schema/information_schema授权问题
- java生成二维码图片
- POJ 2069 Super Star
- Angularjs 通过WebApi 下载excel
- Robotium 不能同时跑多个case
- Java jdk环境搭建
- oracle11g+ef+vs2013做的项目在部署的时候碰到的问题
- server配置学习 ---- 关闭防火墙
- avi格式详细介绍
- 决策树ID3算法
- java的Junit的用法(转发)
- 从线性模型(linear model)衍生出的机器学习分类器(classifier)
- SpringBoot读取yml中的配置,并分离配置文件
- vue 和 react 路由跳转和传参
- 3 快速创建SpringBoot项目
- 3. Longest Substring Without Repeating Characters (ASCII码128个,建立哈西表)
- First Date (hnoj12952)日期计算