2013-04-13 16:54:59Morris
[NPSC][AC自動機DP] a640. A. 曉涵的紙牌遊戲
內容 ：
曉涵和朋友們最近流行玩一個遊戲：首先準備好一疊紙牌，每張紙牌都有一個編號，編號為1 到N 之間的正整數，假設現在共有P 位玩家(包含曉涵在內)，則每個編號都分別有P 張紙牌(故共有P × N 張紙牌)。之後，每個人分別寫下一些「禁忌序列(forbidden sequence)」，每個禁忌序列都是一串遞增的編號，長度和序列內的編號由每個玩家自行決定，但編號不可重複，並且在遊戲開始前都不能給其他人看到。
大家都寫完自己設計的禁忌序列之後，由一個人將這P × N 張紙牌拋起、使其散落在地板上，同時，大家都公布出自己設計的禁忌序列，此時遊戲正式開始！遊戲的目標在於，玩家要從散落的紙牌中找出一個比其他玩家都長的遞增序列以獲得勝利，其中不能存在超過一張同樣編號的紙牌，且遞增序列長度必須至少為2 (至少要選兩張紙牌) ，且其中不可以包含任何人(包括自己) 所設計的禁忌序列。假設有一個人的禁忌序列是「1, 2, 4」，則「1, 2, 4, 5」便是不合法的遞增序列，但「1, 2, 3, 4」則是合法的。當然，像「1, 1, 2, 2」由於有同樣編號的紙牌，所以也是不合法的。
對於這個紙牌遊戲，好奇的曉涵除了想要贏之外，她還想要知道在給定大家的禁忌序列的情況下，究竟有多少種不同的合法遞增序列呢？然而慢慢數真的太累了，請你寫一個程式來幫曉涵計算出總共有多少種不同的遞增序列。
輸入說明 ：
輸入檔的第一行有一個正整數T (T<=50)，代表總共有幾筆測試資料。
每筆測試資料第一行有一個整數N (2<=N<=10)，表示紙牌的最大編號。第二行有一個整數P (2<=P<=10) 代表共有多少位玩家(包含曉涵在內)。之後從第三行開始共有P 行，每一行包含一位玩家所設計的「禁忌序列」。首先有一個正整數Li (2<=Li<=N)，代表該玩家所設計的禁忌序列的長度，之後有Li 個正整數，依序代表該禁忌序列中的各個編號。所有人設計的禁忌序列都是遞增的且其中包含的編號都是在1 到N 之間。
由於玩家之間遊戲前是看不到其他人設計的禁忌序列的，所以可能會有多位玩家設計出相同的禁忌序列。
輸出說明 ：
對於每一組測試資料請輸出一行，該行包含一個正整數代表共有多少種不同的遞增序列。
如果沒有任何遞增序列是合法的話，請輸出一行“so sad” (不含引號)。
範例輸入 ：
4533 2 3 42 2 32 2 4722 1 22 6 7545 1 2 3 4 55 1 2 3 4 55 1 2 3 4 55 1 2 3 4 5342 1 22 2 32 1 33 1 2 3
範例輸出 ：
146425so sad
提示 ：
出處 ：
NPSC 2012 高中組決賽 (管理：xavier13540)
題目簡述：
所有嚴格遞增的序列中(全生成為2^N種)有多少符合條件的序列。
這個條件是，不存在 "任何一條給定的序列" 為子字串。(sub string)
題目分析：
//窮舉應該是可以過的。
AC自動機 DP。
將遞增序列忽略，先當成任意字串由給定的字母集構成的。
將輸入的限制當作一個字串，將這些限制建成一棵 Trie，
並且建成 AC自動機，其中要標記字串的前綴是否存在某一個字串的結尾。
而最後由遞迴公式 dp[len][node]去更新dp[len+1][Next[node]]
釐清一點：Next[node] 可能需要走失敗指針。
len 是走的步數(又或者當作字串長度)，node 是節點編號。
設定 dp[0][root] = 1，模擬 AC自動機匹配的方式進行，
為了要生成遞增序列，更新的時候試圖增加比當前結尾還大的字符，
但在 dp 表格中不想存放結尾字符，只有在 root 會發生問題，
其餘的節點都可以拿當前節點所代表的字符表示。
因此一開始增加所有字符插入 Trie 中，而這些字符不是限制。
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
Node *next[20], *fail, *prev;
int eos;//prefix has a string end
int dp[20];
int ASCII;
Node() {
fail = NULL, prev = NULL;
memset(next, 0, sizeof(next));
memset(dp, 0, sizeof(dp));
eos = 0;
ASCII = 0;
}
};
void insertTrie(const int str[], Node *root, int label) {
static Node *p;
static int i, idx, eos;
p = root, eos = 0;
for(i = 0; str[i] > 0; i++) {
idx = str[i];
if(p->next[idx] == NULL) {
p->next[idx] = new Node();
p->next[idx]->prev = p;
p->next[idx]->ASCII = idx;
}
eos |= p->eos;
p = p->next[idx];
p->eos |= eos;
}
p->eos |= label;
}
void freeTrie(Node *root) {
queue<Node*> Q;
Node *nd;
Q.push(root);
while(!Q.empty()) {
nd = Q.front(), Q.pop();
for(int i = 0; i < 20; i++) {
if(nd->next[i] != NULL)
Q.push(nd->next[i]);
}
delete nd;
}
}
void buildACautomation(Node *root) {
queue<Node*> Q;
Node *nd, *p;
root->fail = NULL;
Q.push(root);
while(!Q.empty()) {
nd = Q.front(), Q.pop();
for(int i = 0; i < 20; i++) {
if(nd->next[i] == NULL)
continue;
Q.push(nd->next[i]);
p = nd->fail;
while(p != NULL && p->next[i] == NULL)
p = p->fail;
if(p == NULL)
nd->next[i]->fail = root;
else {
nd->next[i]->fail = p->next[i];
nd->next[i]->eos |= p->next[i]->eos;//special for dp
}
}
}
}
void dp(Node *root, int len) {
queue<Node*> Q;
Node *nd, *p;
root->dp[0] = 1;
int k, i, j;
int ans = 0, tot = 0;
for(k = 0; k <= len; k++) {
Q.push(root);
ans = 0;
while(!Q.empty()) {
nd = Q.front(), Q.pop();
for(i = nd->ASCII+1; i <= len; i++) {
if(nd->next[i] != NULL) {
if(nd->next[i]->eos)
continue;//not safe
nd->next[i]->dp[k+1] = nd->next[i]->dp[k+1] + nd->dp[k];
Q.push(nd->next[i]);
} else {
p = nd;
while(p != root && p->next[i] == NULL)
p = p->fail;
p = p->next[i];
if(p == NULL)
puts("NULL");
if(p->eos)
continue;//not safe
p->dp[k+1] += nd->dp[k];
}
}
ans += nd->dp[k];
}
if(k >= 2)
tot += ans;
}
if(tot == 0)
puts("so sad");
else
printf("%d\n", tot);
}
int main() {
int t, n, p;
int x, A[20];
int i, j, k;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &p);
Node *root = new Node();
for(i = 0; i < p; i++) {
scanf("%d", &x);
for(j = 0; j < x; j++)
scanf("%d", &A[j]);
A[x] = -1;
insertTrie(A, root, 1);
}
for(i = 1; i <= n; i++) {
A[0] = i;
A[1] = -1;
insertTrie(A, root, 0);
}
buildACautomation(root);
dp(root, n);
freeTrie(root);
}
return 0;
}