我只是想记一下最近写的题目而已喵~
题解什么的才懒得写呢~
[poj 1625]Censored!
这题注意一个地方，就是输入数据中可能有 ASCII 大于 128 的情况，也就是说用 char 读入时，这个字符的值为负数，真是 RE 了好久……
可以像我一样 map 党，你也可以把每个 s[i] 都加上 128
#include <cstdio>
#include <cstring>
#include <map>
#define max(x, y) ((x)>(y) ? (x):(y))
const int digit=;
const int sizeOfLen=;
const int sizeOfMemory=;
const int sizeOfType=; struct bigint
{
int len;
int a[];
inline bigint():len() {memset(a, , sizeof(a));}
inline bigint & operator = (int x) {a[]=x; return *this;}
inline bigint & operator += (bigint x)
{
len=max(len, x.len);
for (int i=;i<len;i++)
{
a[i]+=x.a[i];
a[i+]+=a[i]/digit;
a[i]%=digit;
}
for ( ;a[len];len++) a[len+]=a[len]/digit, a[len]%=digit;
return *this;
}
inline void print()
{
printf("%d", a[len-]);
for (int i=len-;i>=;i--) printf("%08d", a[i]);
putchar('\n');
}
}; int N, M, P;
char str[sizeOfLen];
bigint f[sizeOfLen][sizeOfMemory];
std::map<char, int> ord;
inline void dynamicProgram(); namespace trieDfa
{
struct node
{
int order;
bool end;
node * fail;
node * ch[sizeOfType];
};
node memory[sizeOfMemory]; int port;
node * dfa=memory;
inline node * newnode()
{
node * ret=memory+port;
ret->order=port++;
ret->end=;
ret->fail=NULL;
memset(ret->ch, , sizeof(ret->ch));
return ret;
}
inline void clear() {port=; dfa=newnode();} inline void insert(char * s)
{
int len=strlen(s);
node * t=dfa;
for (int i=;i<len;i++)
{
if (!t->ch[ord[str[i]]]) t->ch[ord[str[i]]]=newnode();
t=t->ch[ord[str[i]]];
}
t->end=;
}
inline void buildDfa()
{
static node * queue[sizeOfMemory];
int l=, r=; dfa->fail=dfa;
for (int i=;i<N;i++)
if (!dfa->ch[i]) dfa->ch[i]=dfa;
else dfa->ch[i]->fail=dfa, queue[r++]=dfa->ch[i]; for ( ;l<r; )
{
node * u=queue[l++];
u->end|=u->fail->end;
for (int i=;i<N;i++)
if (u->ch[i])
{
u->ch[i]->fail=u->fail->ch[i];
queue[r++]=u->ch[i];
}
else
u->ch[i]=u->fail->ch[i];
}
}
} int main()
{
scanf("%d %d %d", &N, &M, &P);
scanf("%s", str);
for (int i=;i<N;i++) ord[str[i]]=i;
trieDfa::clear();
for (int i=;i<P;i++)
{
scanf("%s", str);
trieDfa::insert(str);
} dynamicProgram(); return ;
}
inline void dynamicProgram()
{
bigint ret; trieDfa::buildDfa(); f[][]=;
for (int i=;i<M;i++)
for (int j=;j<trieDfa::port;j++)
for (int k=;k<N;k++) if (!trieDfa::dfa[j].ch[k]->end)
f[i+][trieDfa::dfa[j].ch[k]->order]+=f[i][j];
ret=;
for (int i=;i<trieDfa::port;i++) if (!trieDfa::dfa[i].end)
ret+=f[M][i];
ret.print();
}
本傻装B系列1
[hdu 2896]病毒侵袭
这真是裸体，而且数据没有 poj 那道丧心病狂
#include <cstdio>
#include <cstring>
const int sizeOfVirus=;
const int sizeOfText=;
const int sizeOfType=;
const int sizeOfMemory=; int N, M;
char str[sizeOfText];
int virus[sizeOfMemory];
bool vis[sizeOfVirus]; namespace IOspace
{
inline int getint()
{
register int num=;
register char ch;
do ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline void putint(int num)
{
char stack[];
register int top=;
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
}
} namespace trieDfa
{
struct node
{
int order;
bool end;
node * fail, * last;
node * ch[sizeOfType];
};
node memory[sizeOfMemory]; int port;
node * dfa=memory;
inline node * newnode()
{
node * ret=memory+port;
ret->order=port++;
ret->end=false;
ret->fail=ret->last=NULL;
memset(ret->ch, , sizeof(ret->ch));
return ret;
}
inline void clear() {port=; dfa=newnode();} inline void insert(char * s, int k)
{
int len=strlen(s);
node * t=dfa;
for (int i=;i<len;i++)
{
if (!t->ch[s[i]]) t->ch[s[i]]=newnode();
t=t->ch[s[i]];
}
t->end=true;
virus[t->order]=k;
}
inline void buildDfa()
{
static node * queue[sizeOfMemory];
int l=, r=; dfa->fail=dfa;
for (int i=;i<sizeOfType;i++)
if (!dfa->ch[i]) dfa->ch[i]=dfa;
else dfa->ch[i]->fail=dfa, queue[r++]=dfa->ch[i]; for ( ;l<r; )
{
node * u=queue[l++];
for (int i=;i<sizeOfType;i++)
if (u->ch[i])
{
u->ch[i]->fail=u->fail->ch[i];
u->ch[i]->last=u->ch[i]->fail->end?u->ch[i]->fail:u->ch[i]->fail->last;
queue[r++]=u->ch[i];
}
else
u->ch[i]=u->fail->ch[i];
}
}
inline bool search(char * s)
{
bool flag=;
int len=strlen(s); node * t=dfa;
memset(vis, , sizeof(vis));
for (int i=;i<len;i++)
{
t=t->ch[s[i]];
if (t->end) vis[virus[t->order]]=flag=true;
for (node * j=t->last;j;j=j->last)
vis[virus[j->order]]=flag=true;
} return flag;
}
} int main()
{
int tot=; N=IOspace::getint();
trieDfa::clear();
for (int i=;i<=N;i++)
{
scanf("%s", str);
trieDfa::insert(str, i);
}
trieDfa::buildDfa(); M=IOspace::getint();
for (int i=;i<=M;i++)
{
scanf("%s", str);
bool flag=trieDfa::search(str);
tot+=flag; if (flag)
{
printf("web %d:", i);
for (int i=;i<=N;i++) if (vis[i])
putchar(' '), IOspace::putint(i);
putchar('\n');
}
}
printf("total: %d\n", tot); return ;
}
本傻装B系列2
