资源名称：
&&&&① 下载链接在本页上面广告牌的中间，红色字的右边！为此对各位造成不便请原谅。如实在不知道如何下载的，可
&&&&② 本站的资源一般都是上传到一些较多人使用的网盘，然后大家再从网盘上下载的。所以大家的下载速度或能否连接得上，本站都无法控制，这是由大家各自的网络状况与网盘的连接线路所决定。
&&&&③ 关于一些网盘的说明：
&&&&&&&&115网盘、迅雷快传、360网盘和QQ旋风都是本站早前使用较多的网盘，但现在都已经关闭了分享功能，里面的资源不能下载了（115网盘还可以让上传者自己下载），所以这只能建议大家使用其它网盘下载了。如上面无其它网盘，可见下面第④条方法通知管理员
&&&&&&&&百度网盘：目前市面上最多人使用的网盘了，如果不是会员的话，下载大文件的速度可能会慢点。要是下载大文件建议使用百度网盘的专用工具下载，如果有VIP会员的话是最好的，没有的话也可使用破解版工具（）达到会员效果（大家低调点使用，万一被封了就只能悲剧！）
&&&&④ 如果上面的地址有不能下载的，可联系留言（注意此Q不解答安装问题的），只负责检查资源是否存在！或到本站论坛（）里注册ID后发帖提出，谢谢合作!!
&&&&⑤ 本站提供的一些商业软件与游戏是供学习研究之用，如用于商业用途，请购买正版。
最后欢迎加入本站各游戏的千人超级Q群：(注意:有新人加入且群内满人时,会清除潜水者!
&&&&&实况①群：；　实况②群：；　实况③群:（可加2000人）
&&&&&FIFA①群：；　FIFA②群：；
&&&&&FM①群:；　FM②群:；　FM③群:；
&&&&&FM联机群:；
抵制不良游戏
注意自我保护
谨防受骗上当
适度游戏益脑
沉迷游戏伤身
合理安排时间
享受健康生活
声明:本站资源部分来自互联网，版权归原作者所有。如有侵犯您的权益，请联系我们，本站将在第一时间删除。站内网友所发表所有评论不代表本站立场。:Resource Archiver
:Resource Archiver
时间限制:10000MS &&
内存限制:100000KByte&&
64位IO格式:%I64d & %I64u
Great! Your new software is almost finished! The only thing left to do is archiving all your n resource files into a big one.Wait a minute… you realized that it isn’t as easy as you thought. Think about the virus killers. They’ll find your software suspicious, if your software contains one of the m predefined virus codes. You absolutely don’t want this to happen.Technically, resource files and virus codes are merely 01 strings. You’ve already convinced yourself that none of the resource strings contain a virus code, but if you make the archive arbitrarily, virus codes can still be found somewhere.Here comes your task (formally): design a 01 string that contains all your resources (their occurrences can overlap), but none of the virus codes. To make your software smaller in size, the string should be as short as possible.&
There will be at most 10 test cases, each begins with two integers in a single line: n and m (2 &= n &= 10, 1 &= m &= 1000). The next n lines contain the resources, one in each line. The next m lines contain the virus codes, one in each line. The resources and virus codes are all non-empty 01 strings without spaces inside. Each resource is at most 1000 characters long. The total length of all virus codes is at most 50000. The input ends with n = m = 0.&
For each test case, print the length of shortest string.&
2009 “NIT Cup” National Invitational Contest
Copyright @ , 台州学院软件理论与技术科研（教学）团队. All Rights Reserved.AC自动机【Trie图】（21）
Resource Archiver
Time Limit: 10 Seconds &&&&
Memory Limit: 32768 KB
Great! Your new software is almost finished! The only thing left to do is archiving all your n resource files into a big one.
Wait a minute. you realized that it isn't as easy as you thought. Think about the virus killers. They'll find your software suspicious, if your software contains one of the
m predefined virus codes. You absolutely don't want this to happen.
Technically, resource files and virus codes are merely 01 strings. You've already convinced yourself that none of the resource strings contain a virus code, but if you make the archive arbitrarily, virus codes can still be found
somewhere.
Here comes your task (formally): design a 01 string that contains all your resources (their occurrences can overlap), but none of the virus codes. To make your software smaller in size, the string should be as short as possible.
There will be at most 10 test cases, each begins with two integers in a single line:
n and m (2 &= n &= 10, 1 &= m &= 1000). The next
n lines contain the resources, one in each line. The next m lines contain the virus codes, one in each line. The resources and virus codes are all non-empty 01 strings without spaces inside. Each resource is at most 1000 characters long. The
total length of all virus codes is at most 50000. The input ends with n =
For each test case, print the length of shortest string.
Sample Input
Sample Output
Author: LIU, Rujia
Source: The 34th ACM-ICPC Asia Regional 2009 Ningbo Site NIT Cup National Invitation Contest
题目大意：给你n个资源串，m个病毒串，你的目的是构造一个尽量短的串使得包含所有的资源串并且不包含任意一个病毒串。&(2 &= n &= 10, 1 &= m &= 1000)，所有串都是非空的01序列,且每个资源串长度不大于1000，病毒串总长小于50000。
题目分析：
真是伤。。过了好久才想出这题该怎么写。ＴＵＴ
一开始先将资源串和病毒串都插入到AC自动机中。
分别记录病毒串的结尾和资源串的结尾。
然后在自动机上跑BFS，得到从一个资源串 j 的结尾到另外其他资源串 k 的结尾的最短移动步长dist[ j ][ k ]。
然后以dp[ i ][ j ]表示在状态 i 下以资源串 j 为结尾的合法串的最短长度。
则dp[ i | ( 1 && k )][ k ] = min ( dp[ i | ( 1 && k )][ k ] , dp[ i ][ j ] + dist[ j ][ k ] )。
然后就解出来了= =||真是伤。
PS：HDU数据满弱的样子，然后又去ZOJ交了，不知道ZOJ数据够不够强，希望自己写的没什么漏洞
代码如下：
#include &cstdio&
#include &cstring&
#include &algorithm&
#define clear( a , x ) memset ( a , x , sizeof a )
#define REP( i , n ) for ( int i = 0 ; i & ++ i )
#define REPF( i , a , b ) for ( int i = i &= ++ i )
#define CHAR( i ) for ( int i = 0 ; buf[i] ; ++ i )
const int MAXN = 60005 ;
const int MAXW = 2 ;
const int MAXQ = 1000000 ;
const int INF = 0x3f3f3f3
const int NUM = 10 ;
struct Trie {
int next[MAXN][MAXW] ;
int fail[MAXN] ;
int word[MAXN] ;
int virus[MAXN] ;
int Q[MAXQ] ;
int head ,
int d[MAXN] ;
int dist[NUM][NUM] ;
bool vis[MAXN] ;
int len[NUM] ;
int dp[1 && NUM][NUM] ;
int newnode () {
REP ( i , MAXW )
next[P][i] = -1 ;
word[P] = 0 ;
virus[P] = 0 ;
return P ++ ;
void init () {
clear ( dist , INF ) ;
clear ( len , 0 ) ;
root = newnode () ;
int get ( char c ) {
return c - '0' ;
int insert ( char buf[] , int idx ) {
CHAR ( i ) {
int x = get ( buf[i] ) ;
if ( next[now][x] == -1 )
next[now][x] = newnode () ;
now = next[now][x] ;
++ len[idx] ;
if ( idx == -1 )
virus[now] = 1 ;
word[now] = ( 1 && idx ) ;
void build () {
head = tail = 0 ;
fail[root] =
REP ( i , MAXW ) {
if ( next[root][i] == -1 )
next[root][i] =
fail[next[root][i]] =
Q[tail ++] = next[root][i] ;
while ( head != tail ) {
int now = Q[head ++] ;
REP ( i , MAXW ) {
if ( next[now][i] == -1 )
next[now][i] = next[fail[now]][i] ;
fail[next[now][i]] = next[fail[now]][i] ;
word[next[now][i]] |= word[fail[next[now][i]]] ;
virus[next[now][i]] |= virus[fail[next[now][i]]] ;
Q[tail ++] = next[now][i] ;
void bfs ( int x , int idx , int n ) {
clear ( vis , 0 ) ;
head = tail = 0 ;
Q[tail ++] =
d[x] = 0 ;
vis[x] = 1 ;
if ( word[x] )
REP ( i , n )
if ( word[x] & ( 1 && i ) )
dist[idx][i] = 0 ;
while ( head != tail ) {
int now = Q[head ++] ;
REP ( i , MAXW ) {
int nxt = next[now][i] ;
if ( !virus[nxt] && !vis[nxt] ) {
vis[nxt] = 1 ;
d[nxt] = d[now] + 1 ;
Q[tail ++] =
if ( word[nxt] )
REP ( j , n )
if ( word[nxt] & ( 1 && j ) )
if ( dist[idx][j] & d[nxt] )
dist[idx][j] = d[nxt] ;
void solve ( int n ) {
clear ( dp , INF ) ;
int o = 1 &&
REP ( i , n )
dp[1 && i][i] = len[i] ;
REP ( i , o )
REP ( j , n )
REP ( k , n )
dp[i | ( 1 && k )][k] = min ( dp[i | ( 1 && k )][k] , dp[i][j] + dist[j][k] ) ;
int ans = INF ;
REP ( i , n )
if ( ans & dp[o - 1][i] )
ans = dp[o - 1][i] ;
printf ( &%d\n& , ans ) ;
char buf[MAXN] ;
int idx[NUM] ;
void work () {
while ( ~scanf ( &%d%d& , &n , &m ) && ( n || m ) ) {
ac.init () ;
REP ( i , n ) {
scanf ( &%s& , buf ) ;
idx[i] = ac.insert ( buf , i ) ;
REP ( i , m ) {
scanf ( &%s& , buf ) ;
ac.insert ( buf , -1 ) ;
ac.build () ;
REP ( i , n )
ac.bfs ( idx[i] , i , n ) ;
ac.solve ( n ) ;
int main () {
return 0 ;
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：485056次
积分：12046
积分：12046
排名：第1194名
原创：717篇
评论：245条
(4)(20)(39)(1)(1)(1)(2)(5)(1)(9)(21)(5)(18)(18)(1)(4)(33)(51)(41)(107)(118)(132)(81)(4)