Posts

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

昨天终于搞定了ycm对c++11的支持…. 嘛，17都快出来了，我竟然连11都不会用。 不过突然把所有的11特性给我也没办法全部吸收。 所以在这里记录下用过的c++11的用法。

题目链接 题意：给出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

hdu 5835 题目链接 题意：n种礼物，每种a[i]个。现在有无穷个小朋友排成一排，分给每个人一个“普通”的礼物，一个“昂贵”的礼物（哪个普通哪个昂贵是自己定的，或者说，任意的） 要求是相邻的小朋友的普通的礼物不能是同一种。现在问最多能给多少小朋友分礼物。。。

hdu 5842题目链接 题意：给一个只由小写字母组成的字符串，每个字符映射到一个数字，问映射之后的最长上升子序列的长度。。 思路：上来写nlogn的LIS是我无脑了。。。wa了之后想了下。。其实只要统计不同的字母数就好了啊。。。set一下

hdu 3374 题目链接 题意：给出一个循环字符串，问最小表示出现的位置以及次数，最大表示出现的位置以及次数。 思路：之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[len]，1A

hdu 2609 题目链接 题意：给出n个循环字符串，问有多少种。 思路：将每个字符串换成最小表示，然后set存一下即可。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月13日 星期六 02时44分21秒 4File Name :code/hdu/2609.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#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 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4+7; 34int n; 35char s[N][105]; 36set<string>se; 37int minRep(char *s) 38{ 39 int n = strlen(s); 40 int i = 0 ; 41 int j = 1 ; 42 int k = 0 ; 43 while (i<n&&j<n&&k<n) 44 { 45 int t = s[(i+k)%n] - s[(j+k)%n]; 46 if (t==0) k++; 47 else 48 { 49 if (t>0) 50 i+=k+1; 51 else j+=k+1; 52 if (i==j) j++; 53 k = 0 ; 54 } 55 } 56 return i<j?i:j; 57} 58int main() 59{ 60 #ifndef ONLINE_JUDGE 61 freopen("code/in.txt","r",stdin); 62 #endif 63 while (~scanf("%d",&n)) 64 { 65 ms(s,0); 66 se.clear(); 67 // cout<<"n:"<<n<<endl; 68 char tmp[105]; 69 for ( int i = 0 ; i < n; i++) 70 { 71 scanf("%s",tmp); 72// cout<<"tmp:"<<tmp<<endl; 73 int k = minRep(tmp); 74// cout<<"k:"<<k<<endl; 75 int cnt = 1; 76 int len = strlen(tmp); 77 for ( int j = k ; cnt <= len ; j++,cnt++) 78 s[i][cnt-1] = tmp[j%len]; 79 se.insert(string(s[i])); 80 } 81// for ( int i = 0 ; i < n; i++) cout<<"s[i]:"<<s[i]<<endl; 82// 83 int ans = se.size(); 84 printf("%d\n",ans); 85 } 86 #ifndef ONLINE_JUDGE 87 fclose(stdin); 88 #endif 89 return 0; 90}

hdu 4162 题意：给出一串代表8个方向的数字，求这串序列的一阶差分（the first difference）的字典序最小的表示。 思路：先做个变换，按照题意，第i位的一阶差分 s[i] = ((s[i+1]-s[i])+8)%8; 然后求出最小表示开始的位置。。输出即可。

poj 1509 题目链接 题意&思路：同uva 1314 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 18时48分29秒 4File Name :code/uva/1314.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#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 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int n ; 35char s[N]; 36int minRep(char *s) 37{ 38 int n = strlen(s); 39 int i = 0; 40 int j = 1; 41 int k = 0; 42 while (i<n&&j<n&&k<n) 43 { 44 int t = s[(i+k)%n]-s[(j+k)%n]; 45 if (t==0) k++; 46 else 47 { 48 if (t>0) 49 i+=k+1; 50 else j+=k+1; 51 if (i==j) j++; 52 k = 0 ; 53 } 54 } 55 return i<j?i:j; 56} 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 int T; 63 cin>>T; 64 while (T--) 65 { 66 scanf("%s",s); 67 printf("%d\n",minRep(s)+1); 68 } 69 #ifndef ONLINE_JUDGE 70 fclose(stdin); 71 #endif 72 return 0; 73}