ACM

题目链接 题意：有n扇门，n种钥匙，一一对应。每扇门打开后可能得到k把钥匙（k可能为0）。一扇门还可以用一颗炸弹炸开。现在问要开所有门，使用炸弹的期望个数。 思路：状态压缩。用一个二进制串表示每扇门能打开的门的信息，对应的位上为1表示能打开，为0表示不能打开。

题目链接 题意：给出一个数，问包含这个数三个数组成的勾股数，输出另外两个数。 思路： 所谓勾股数，就是当组成一个直角三角形的三边长都为正整数时，我们就称这一组数为勾股数. 那么，组成一组勾股数的三个正整数之间，是否具有一定的规律可寻呢？下面我们一起来观察几组勾股数： 规律一：在勾股数（3,4,5）、（5,12,13）、（7,24,25）（9,40,41）中，我们发现 由（3,4,5）有：32=9=4+5 由（5,12,13）有：52=25=12+13 由（7,24,25）有：72=49=24+25 由（9,40,41）有：92=81=40+41. 即在一组勾股数中，当最小边为奇数时，它的平方刚好等于另外两个连续的正整数之和.因此，我们把它推广到一般，从而可得出以下公式： ∵（2n+1)²=4n²+4n+1=（2n²+2n）+（2n²+2n+1） ∴（2n+1)²+（2n²+2n)²=（2n²+2n+1)²（n为正整数） 证明（略） 勾股数公式一：（2n+1,2n²+2n,2n²+2n+1）（n为正整数） 规律二：在勾股数（6,8,10）、（8,15,17）、（10,24,26）中，我们发现 由（6,8,10）有：62=36+2×（8+10） 由（8,15,17）有：82=64=2×（15+17） 由（10,24,26）有：102=100=2×（24+26） 即在一组勾股数中，当最小边为偶数时，它的平方刚好等于两个连续整数之和的二倍，推广到一般，从而可得出另一公式： ∵（2n）2=4n2=2[（n2-1）+（n2+1）] ∴（2n）2+（n2-1）2=（n2+1）2（n≥2且n为正整数） 证明（略） 勾股数公式二：（2n,n²-1,n²+1）（n≥2且n为正整数） 利用以上两个公式，我们可以快速写出各组勾股数.

题目链接 题意：把一个数n(n<1000)转化成二进制输出。。。 思路：。。。搜acm bitset 搜到这题。。。所以其实这并不是“bitset”优化的题。。。只是题目名字交这个了2333。

1.定义与初始化 在定义 bitset 时，要明确 bitset 有多少位，这个位数是整形常量 (tips：如果长度和输入的数m有关，在做翻转操作以后再统计时候会多算，一个可以的做法是设置一个长度为m，所有位上都是1的位串，然后翻转之后先与一下。类似的技巧还有很多。)

题目链接 题意：n个城市，m条双向路，要从k条中选择一个，使得到其他n-k个城市中的某个城市的距离最短。 思路：直接暴力 枚举。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月20日 星期六 21时02分14秒 4File Name :code/cf/#368/B.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <deque> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27using namespace std; 28const double eps = 1E-8; 29const int dx4[4]={1,0,0,-1}; 30const int dy4[4]={0,-1,1,0}; 31const int inf = 0x3f3f3f3f; 32const int N =1E5+7; 33int n,m,k; 34vector <pair <int,LL> >edge[N]; 35int b[N]; 36bool cangku[N]; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 ios::sync_with_stdio(false); 43 cin>>n>>m>>k; 44 ms(cangku,false); 45 for ( int i = 1 ; i <= m ; i++) 46 { 47 int u,v; 48 LL w; 49 cin>>u>>v>>w; 50 edge[u].push_back(make_pair(v,w)); 51 edge[v].push_back(make_pair(u,w)); 52 } 53 if (k==0) 54 { 55 cout<<-1<<endl; 56 return 0 ; 57 } 58 for ( int i = 1 ; i <= k ; i++) 59 { 60 cin>>b[i]; 61 cangku[b[i]] = true; 62 } 63 if (k==n) 64 { 65 cout<<-1<<endl; 66 return 0; 67 } 68 LL ans = inf; 69 for (int i = 1 ; i <= k ; i++) 70 { 71 int u = b[i]; 72 int siz = edge[u].size(); 73 for (int j = 0 ; j < siz ; j++) 74 { 75 int v = edge[u][j].fst; 76 if (cangku[v]) continue; 77 LL w = edge[u][j].sec; 78 ans = min(ans,w); 79 } 80 } 81 if (ans==inf) ans = -1; 82 cout<<ans<<endl; 83 #ifndef ONLINE_JUDGE 84 fclose(stdin); 85 #endif 86 return 0; 87}

题目链接 。。。这题也能成hack题。。。。有毒啊。。然后我room里所有人都写对了。。。是我看这道题看得太早了？ 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月20日 星期六 21时01分57秒 4File Name :code/cf/#368/A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <deque> 15#include <map> 16#include <string> 17#include <cmath> 18#include <cstdlib> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28 29using namespace std; 30const double eps = 1E-8; 31const int dx4[4]={1,0,0,-1}; 32const int dy4[4]={0,-1,1,0}; 33const int inf = 0x3f3f3f3f; 34const int N=105; 35int n,m; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 cin>>n>>m; 43 bool ok = false; 44 for ( int i = 1 ; i <= n ; i++) 45 for ( int j = 1 ; j <=m ; j++ ) 46 { 47 char col; 48 cin>>col; 49 if (col=='C'||col=='M'||col=='Y') ok = true; 50 } 51 if (ok) cout<<"#Color"<<endl; 52 else cout<<"#Black&White"<<endl; 53 54 #ifndef ONLINE_JUDGE 55 fclose(stdin); 56 #endif 57 return 0; 58}

hdu 1754 题目链接 题意：单点更新，区间查询最大值。 思路：线段树。 一开始借鉴了 clj 的 pointer 写法，wjmzbmr’s code 直接 MLE，看来也许只能在 cf 上用。 下面是 MLE 的代码： 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月18日 星期四 18时40分24秒 4File Name :code/hdu/1754.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27using namespace std; 28const double eps = 1E-8; 29const int dx4[4]={1,0,0,-1}; 30const int dy4[4]={0,-1,1,0}; 31const int inf = 0x3f3f3f3f; 32const int N=2E5+7; 33int a[N],n,m; 34int _max( int x,int y) 35{ 36 if (x==-1||y==-1) 37 return x==-1?y:x; 38 return a[x]>a[y]?x:y; 39} 40struct Tree 41{ 42 Tree *pl,*pr; 43 int l,r,mx; 44 void update() 45 { 46 mx = _max(pl->mx,pr->mx); 47 } 48 Tree(int l,int r) : 49 l(l),r(r) 50 { 51 if ( l + 1 == r) 52 { 53 mx = l ; 54 return ; 55 } 56 pl = new Tree(l,(l+r)>>1); 57 pr = new Tree((l+r)>>1,r); 58 update(); 59 } 60 void change(int p,int x) 61 { 62 if (p < l|| p>=r) return; 63 if (l+1==r) 64 { 65 a[l] = x; 66 return ; 67 } 68 pl->change(p,x); 69 pr->change(p,x); 70 update(); 71 } 72 int queryMax(int L,int R) 73 { 74 if (L <= l && r <= R) return mx; 75 if (L>=r || l >=R) 76 return -1; 77 return _max(pl->queryMax(L,R),pr->queryMax(L,R)); 78 } 79}*rt; 80int main() 81{ 82 #ifndef ONLINE_JUDGE 83 freopen("code/in.txt","r",stdin); 84 #endif 85 while (~scanf("%d%d",&n,&m)) 86 { 87 ms(a,0); 88 for ( int i = 0 ; i < n ; i++) scanf("%d",a+i); 89 rt = new Tree(0,n); 90 while (m--) 91 { 92 char opt[3]; 93 int x,y; 94 scanf("%s %d %d",opt,&x,&y); 95 x--; 96 if (opt[0]=='Q') 97 printf("%d\n",a[rt->queryMax(x,y)]); 98 else rt->change(x,y); 99 } 100 } 101 #ifndef ONLINE_JUDGE 102 fclose(stdin); 103 #endif 104 return 0; 105} 关于线段树的理解，见代码注释：

嘛，终于下定决心搞定线段树了。 之前几次都是被lazy标记卡住，这次大概不会了吧2333 放一些学习资料，最后比较zkw线段树和普通线段树的区别。 codeforces上非递归线段树讲解 （其实就是zkw吧） 线段树进阶（各种花式技巧） 找到了一篇非常赞的tutorial（含lazy标记） 链接

题目链接 题意：给出n个病毒的模式串，问每个病毒串在文本串中出现了多少次。 思路：ac自动机。模式串只由大写字母组成。文本串是所有可视字符。 如果动态128会MLE.做法是换成静态数组写法，或者对于每次Search的时候，出现非大写字母的字符特判一下。

hdu 2896 题目链接 题意：给出n个病毒，然后给出m个网站，然后问每个网站中有哪些病毒，以及有病毒的网站的个数。 需要注意病毒和网站都需要按从小到达排列输出。 思路：ac自动机，需要记录病毒id…然后。。因为病毒的id忘记排序wa了好多发。。智力减2.

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 个模式串，一个文本串，问文本串中出现了多少个模式串。 思路：AC 自动机裸题。代码风格来自 bin 神。静态数组的写法。 需要理解在 build fail 的时候，先单独处理 root 的必要性。

老规矩，先放资料： 参考资料1 参考资料2 参考资料3 （其实这些资料我都没怎么看。。。。因为感觉。。。理解起来非常容易的样子orz） 我的理解：感觉这东西如果明白了kmp和trie，理解起来就完全没难度。。。

poj 2001 题目链接 题意：给出n个字符串的表，问每个字符串的简化表示。简化表示的要求是，以该字符串的最短的而且不能产生歧义的前缀来表示。 思路：字典树，多一个cnt属性，每次insert的时候，路过的每个节点的cnt++

poj 3630 题目链接 题意：给出n个字符串，问是否满足所有的字符串都不以其他的字符串为前缀。 思路：字典树，先建树，然后每次查找的之前先删掉自己，找完以后再加回来。 以及这题动态建艹不过。。。学习了一下静态建树的写法。。。第一次写静态的写法。。。可以当做模板用。。。

hdu 1247 题目链接 题意：给出n个字符串的单词表，输出所有的字符串a，满足字符串a是由n中另外两个字符串拼接成的。 思路：字典树。。其实我一开始想出了正解。。。。就是分割一个单词然后分别在trie上查找。。。但是由于题目坑爹得没给单词的长度这个数据范围。。并不是很敢写2333。。。看了下题解发现就是这么做。。。然后写了下1A。。。

hdu 5536 题目链接 题意：给出 n 个数，然后问最大的 (a[i]+a[j])^a[k]（i,j,k 互不相同）。 思路：异或和最大很容易想到字典树，但是如何保证 i,j,k 互不相同这里没有想明白。我的想法是加一个标记代表之前的 id，但是我加的标记只有在叶子节点上才有，也就是会出现走到了最后一步才发现这个节点不能走的情况。

hdu 4825 题目链接 题意：给定n个数，然后给出m个询问，每组询问一个数x，问n中的数y使得x和y的异或和最大。 思路：字典树。。把每个数转化成二进制，注意补全前导0，使得所有数都有相同的位数。

hdu 1251 题目链接 题意：先给一个单词表，然后给出若干查询，每个查询一个单词，问单词表中以这个单词为前缀的单词的个数。 思路：trie树裸题。第一次写trie树。。感觉要注意的是trie树是一个比较耗费空间的数据结构。。？ 以及动态开辟内存记得free…？

hdu 5833 题目链接 题意：n个数，保证每个数的素因子不超过2000，从中取若干个，问乘积是完全平方数的方案数。 思路： 完全平方数就是要求每个质因子的指数是偶数次。 列方程组，a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子，建立异或方程组，要求因子个数为偶数，即异或为0