ACM

题目链接 题意：有n扇门，n种钥匙，一一对应。每扇门打开后可能得到k把钥匙（k可能为0）。一扇门还可以用一颗炸弹炸开。现在问要开所有门，使用炸弹的期望个数。

题目链接 题意：给出一个数，问包含这个数三个数组成的勾股数，输出另外两个数。

题目链接 题意：把一个数n(n<1000)转化成二进制输出。。。

1.定义与初始化 在定义 bitset 时，要明确 bitset 有多少位，这个位数是整形常量

题目链接 题意：n个城市，m条双向路，要从k条中选择一个，使得到其他n-k个城市中的某个城市的距离最短。

题目链接 。。。这题也能成hack题。。。。有毒啊。。然后我room里所有人都写对了。。。是我看这道题看得太早了？

hdu 1754 题目链接 题意：单点更新，区间查询最大值。 思路：线段树。 一开始借鉴了clj的pointer写法。。wjmzbmr’s code 直接MLE。。。看来也许只能在cf上用。。。 下面是MLE的代码：

嘛，终于下定决心搞定线段树了。 之前几次都是被lazy标记卡住，这次大概不会了吧2333

题目链接 题意：给出n个病毒的模式串，问每个病毒串在文本串中出现了多少次。

hdu 2896 题目链接 题意：给出n个病毒，然后给出m个网站，然后问每个网站中有哪些病毒，以及有病毒的网站的个数。

orzorz 日常%学弟 华科的未来orz 1#include <cstdio> 2#include <cstring> 3 4using namespace std; 5 6struct tnode { 7 int s; 8 tnode *f, *w, *c[26]; 9} T[5000000], *Q[5000000]; 10int C; 11 12inline tnode *tnew() { 13 memset(T + C, 0, sizeof(tnode)); 14 return T + C++; 15} 16 17inline void AcaInsert(tnode *p, const char *s) { 18 while (*s) { 19 int u = *s - 'a'; 20 if (!p->c[u]) 21 p->c[u] = tnew(); 22 p = p->c[u]; 23 ++s; 24 } 25 ++p->s; 26} 27 28inline void AcaBuild(tnode *p) { 29 p->f = p->w = p; 30 int ql = 0; 31 for (int i = 0; i < 26; ++i) 32 if (p->c[i]) { 33 p->c[i]->f = p->c[i]->w = p; 34 Q[ql++] = p->c[i]; 35 } 36 for (int qf = 0; qf < ql; ++qf) 37 for (int i = 0; i < 26; ++i) 38 if (Q[qf]->c[i]) { 39 tnode *f = Q[qf]->f; 40 while (f != p && !f->c[i]) 41 f = f->f; 42 if (f->c[i]) { 43 Q[qf]->c[i]->f = f->c[i]; 44 Q[qf]->c[i]->w = f->c[i]->s ? f->c[i] : f->c[i]->w; 45 } 46 else 47 Q[qf]->c[i]->f = Q[qf]->c[i]->w = p; 48 Q[ql++] = Q[qf]->c[i]; 49 } 50} 51 52inline int AcaMatch(tnode *root, const char *s) { 53 int x = 0; 54 for (tnode *p = root; *s; ++s) { 55 while (p != root && !p->c[*s - 'a']) 56 p = p->f; 57 if (p->c[*s - 'a']) { 58 p = p->c[*s - 'a']; 59 for (tnode *q = p; q->s != -1; q = q->w) { 60 x += q->s; 61 q->s = -1; 62 } 63 } 64 } 65 return x; 66} 67 68char S[1000001]; 69 70int main() { 71 int tt; 72 scanf("%d", &tt); 73 while (tt--) { 74 C = 0; 75 tnode *root = tnew(); 76 root->s = -1; 77 int N; 78 scanf("%d", &N); 79 while (N--) { 80 scanf("%s", S); 81 AcaInsert(root, S); 82 } 83 AcaBuild(root); 84 scanf("%s", S); 85 printf("%d\n", AcaMatch(root, S)); 86 } 87 return 0; 88}

hdu 2222 题目链接 题意：给出n个模式串，一个文本串，问文本串中出现了多少各模式串。

老规矩，先放资料： 参考资料1 参考资料2 参考资料3 （其实这些资料我都没怎么看。。。。因为感觉。。。理解起来非常容易的样子orz）

poj 2001 题目链接 题意：给出n个字符串的表，问每个字符串的简化表示。简化表示的要求是，以该字符串的最短的而且不能产生歧义的前缀来表示。

poj 3630 题目链接 题意：给出n个字符串，问是否满足所有的字符串都不以其他的字符串为前缀。

hdu 1247 题目链接 题意：给出n个字符串的单词表，输出所有的字符串a，满足字符串a是由n中另外两个字符串拼接成的。

hdu 5536 题目链接 题意：给出n个数，然后问最大的(a[i]+a[j])^a[k] (i,j,k互不相同)

hdu 4825 题目链接 题意：给定n个数，然后给出m个询问，每组询问一个数x，问n中的数y使得x和y的异或和最大。

hdu 1251 题目链接 题意：先给一个单词表，然后给出若干查询，每个查询一个单词，问单词表中以这个单词为前缀的单词的个数。

hdu 5833 题目链接 题意：n个数，保证每个数的素因子不超过2000，从中取若干个，问乘积是完全平方数的方案数。