P2167 [SDOI2009]Bill的挑戰(zhàn)

題意：

有n個(gè)長(zhǎng)度一樣的字符串，字符串的每一位是？或者確定的字母，，求與這 N 個(gè)串中的剛好 K 個(gè)串匹配的字符串 T 的個(gè)數(shù)
1<=N<=15,1<=|S|<=50

題解：

很明顯狀態(tài)dp
我們可以先預(yù)處理一個(gè)match[1…len][a…z]:表示第i位取ch的狀態(tài)，比如match[1]['a]=10101就表示第一個(gè)，第三個(gè)，第五個(gè)字符串的第一位可以取’a‘。預(yù)處理出match
f[i][j]表示第i位的匹配上了j這個(gè)狀態(tài)的方案數(shù)
轉(zhuǎn)移方程：
j=1010(二進(jìn)制)就表示：選了第2行和第四行的字符串的狀態(tài)
選在第i+1行時(shí)，要與第i行的狀態(tài)取&

int now= (match[i][ch - 'a'] & j); f[i + 1][now]= (f[i + 1][now] + f[i][j]) % mod;

最后枚舉答案時(shí)，因?yàn)轭}目有說(shuō)時(shí)選取k行，所以枚舉所有狀態(tài)，只有狀態(tài)中帶有k個(gè)1的是我們要的狀態(tài)

代碼：

// Problem: P2167 [SDOI2009]Bill的挑戰(zhàn) // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P2167 // Memory Limit: 125 MB // Time Limit: 1000 ms // Data:2021-08-11 21:21:14 // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; template <typename T> inline void read(T& x) {T f= 1;x= 0;char ch= getchar();while (0 == isdigit(ch)) {if (ch == '-')f= -1;ch= getchar();}while (0 != isdigit(ch))x= (x << 1) + (x << 3) + ch - '0', ch= getchar();x*= f; } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 100; char s[maxn][maxn]; const int mod= 1e6 + 3; int f[60][1 << 15]; int match[60][60]; int main() {//rd_test();int t;read(t);while (t--) {memset(f, 0, sizeof(f));memset(match, 0, sizeof match);int tot= 0;int n, k;cin >> n >> k;for (int i= 1; i <= n; i++)scanf("%s", s[i]);int len= strlen(s[1]);for (int i= 0; i < len; i++) { //對(duì)于每一位for (char ch= 'a'; ch <= 'z'; ch++) {for (int k= 1; k <= n; k++) { //對(duì)于每個(gè)字符串//第k個(gè)字符串的第i個(gè)位置if (s[k][i] == '?' || s[k][i] == ch) {match[i][ch - 'a']|= (1 << (k - 1));//第i位取ch的狀態(tài)}}}}int cnt= (1 << n) - 1;f[0][cnt]= 1; //初始狀態(tài)for (int i= 0; i < len; i++) {for (int j= 0; j <= cnt; j++) {if (f[i][j]) { //如果f第i個(gè)位置的j狀態(tài)有方案for (char ch= 'a'; ch <= 'z'; ch++) {//得到新?tīng)顟B(tài)int now= (match[i][ch - 'a'] & j);f[i + 1][now]= (f[i + 1][now] + f[i][j]) % mod;}}}}for (int i= 0; i <= cnt; i++) { //枚舉取字符串的所有狀態(tài)int ans= 0;for (int j= 1; j <= cnt; j<<=1)ans+= (bool)(i&j);if (ans == k) //如果取了k個(gè)字符串(i中有k個(gè)1)tot= (tot + f[len][i]) % mod;}printf("%d\n", tot);}//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的P2167 [SDOI2009]Bill的挑战的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。