Overview
| SHA1 Hash: | 96b8b260e143219090fb2e8bbb3c5908bda89025 |
|---|---|
| Date: | 2011-09-20 15:23:58 |
| User: | kinaba |
| Comment: | 519 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/519-U/1A.cpp version [ab38c113cfe34364]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class BinaryCards { public: > 23 long long largestNumber(long long A_, long long B_) > 24 { > 25 unsigned long long A = A_; > 26 unsigned long long B = B_; > 27 string sa; > 28 for(int i=0; (1ULL<<i)<=A; ++i) > 29 sa = char('0' + ((A>>i)&1)) + sa; > 30 string sb; > 31 for(int i=0; (1ULL<<i)<=B; ++i) > 32 sb = char('0' + ((B>>i)&1)) + sb; > 33 sa = string(sb.size()-sa.size(), '0') + sa; > 34 > 35 string sc; > 36 for(int i=0; i<sb.size(); ++i) > 37 if( sa[i] == sb[i] ) > 38 sc += sa[i]; > 39 else { > 40 sc += string(sb.size()-i, '1'); > 41 break; > 42 } > 43 > 44 LL value = 0; > 45 for(int i=0; i<sc.size(); ++i) > 46 if( sc[sc.size()-i-1] == '1' ) > 47 value |= (1LL << i); > 48 return value; > 49 } > 50 }; > 51 > 52 > 53 > 54 // Powered by FileEdit > 55 // Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom > 56 // Powered by CodeProcessor
Added SRM/519-U/1B.cpp version [148e8147aebc92eb]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 template<int NC=26, char BC='a'> > 23 struct AhoCorasick > 24 { > 25 AhoCorasick( const vector<string>& p ) : link(NC+1) { > 26 // Create a trie > 27 for(int i=0; i<p.size(); ++i) { > 28 AhoCorasick* t = this; > 29 for(int k=0; k<p[i].size(); t=t->link[p[i][k++]-BC]) > 30 if(!t->link[p[i][k]-BC]) > 31 t->link[p[i][k]-BC]=new AhoCorasick; > 32 t->final.insert(i); > 33 } > 34 > 35 // Do BFS and draw failure links, and prepare for substring patt > 36 queue<AhoCorasick*> Q; > 37 for(int c=0; c<NC; ++c) > 38 if( link[c] ) { > 39 Q.push(link[c]); > 40 link[c]->link[NC] = this; // "c"'s suffix is "" > 41 link[c]->final.insert(final.begin(), final.end() > 42 } > 43 else > 44 link[c] = this; > 45 while( !Q.empty() ) { > 46 AhoCorasick* t=Q.front(); Q.pop(); > 47 for(int c=0; c<NC; ++c) > 48 if( t->link[c] ) { > 49 Q.push(t->link[c]); > 50 AhoCorasick* r = t->link[NC]; // "r" is > 51 while( !r->link[c] ) > 52 r = r->link[NC]; > 53 t->link[c]->link[NC] = r->link[c]; // th > 54 t->link[c]->final.insert(r->link[c]->fin > 55 } > 56 } > 57 } > 58 const AhoCorasick* start() const { return this; } > 59 const AhoCorasick* next(char c) const { > 60 const AhoCorasick* t = this; > 61 while( !t->link[c-BC] ) > 62 t = t->link[NC]; > 63 return t->link[c-BC]; > 64 } > 65 const set<int>& accept() const { return final; } > 66 ~AhoCorasick() { for(int i=0; i<NC; ++i) if(link[i]!=this) delete link[i > 67 private: > 68 AhoCorasick() : link(NC+1) {} > 69 vector<AhoCorasick*> link; > 70 set<int> final; > 71 }; > 72 > 73 static const int MODVAL = 1000000009; // must be prime for op/ > 74 struct mint > 75 { > 76 int val; > 77 mint():val(0){} > 78 mint(int x):val(x%MODVAL) {} > 79 }; > 80 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 81 > 82 int bitcnt(LL x) > 83 { > 84 int c = 0; > 85 for(; x; x>>=1) > 86 c += x&1; > 87 return c; > 88 } > 89 > 90 class RequiredSubstrings { public: > 91 int solve(vector <string> words, int C, int L) > 92 { > 93 AhoCorasick<> ac(words); > 94 return rec(L, C, 0, ac.start()).val; > 95 } > 96 > 97 map<pair<pair<int,int>,const AhoCorasick<>*>, mint> memo; > 98 mint rec(int rest, const int C, const int found, const AhoCorasick<>* ac) > 99 { > 100 if( rest == 0 ) > 101 return (bitcnt(found)==C ? 1 : 0); > 102 pair<pair<int,int>,const AhoCorasick*> key(make_pair(rest, found), ac); > 103 if( memo.count(key) ) > 104 return memo[key]; > 105 > 106 mint sum = 0; > 107 for(char c='a'; c<='z'; ++c) > 108 { > 109 const AhoCorasick<>* t = ac->next(c); > 110 int f = found; > 111 for(set<int>::const_iterator it=t->accept().begin(); it!=t->accept().end() > 112 f |= (1 << *it); > 113 sum += rec(rest-1, C, f, t); > 114 } > 115 return memo[key] = sum; > 116 } > 117 }; > 118 > 119 > 120 > 121 // Powered by FileEdit > 122 // Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom > 123 // Powered by CodeProcessor > 124
Added lib/dataStructure/AhoCorasick.cpp version [71f65eb207acadc5]
> 1 //------------------------------------------------------------- > 2 // Aho-Corasick multi pattern search > 3 // O(|size-of-patterns|) for construction. O(1) per step. > 4 // > 5 // Verified by > 6 // - SRM519 Div1 LV2 > 7 //------------------------------------------------------------- > 8 > 9 template<int NC=26, char BC='a'> > 10 struct AhoCorasick > 11 { > 12 AhoCorasick( const vector<string>& p ) : link(NC+1) { > 13 // Create a trie > 14 for(int i=0; i<p.size(); ++i) { > 15 AhoCorasick* t = this; > 16 for(int k=0; k<p[i].size(); t=t->link[p[i][k++]-BC]) > 17 if(!t->link[p[i][k]-BC]) > 18 t->link[p[i][k]-BC]=new AhoCorasick; > 19 t->final.insert(i); > 20 } > 21 > 22 // Do BFS and draw failure links, and prepare for substring patt > 23 queue<AhoCorasick*> Q; > 24 for(int c=0; c<NC; ++c) > 25 if( link[c] ) { > 26 Q.push(link[c]); > 27 link[c]->link[NC] = this; // "c"'s suffix is "" > 28 link[c]->final.insert(final.begin(), final.end() > 29 } > 30 else > 31 link[c] = this; > 32 while( !Q.empty() ) { > 33 AhoCorasick* t=Q.front(); Q.pop(); > 34 for(int c=0; c<NC; ++c) > 35 if( t->link[c] ) { > 36 Q.push(t->link[c]); > 37 AhoCorasick* r = t->link[NC]; // "r" is > 38 while( !r->link[c] ) > 39 r = r->link[NC]; > 40 t->link[c]->link[NC] = r->link[c]; // th > 41 t->link[c]->final.insert(r->link[c]->fin > 42 } > 43 } > 44 } > 45 const AhoCorasick* start() const { return this; } > 46 const AhoCorasick* next(char c) const { > 47 const AhoCorasick* t = this; > 48 while( !t->link[c-BC] ) > 49 t = t->link[NC]; > 50 return t->link[c-BC]; > 51 } > 52 const set<int>& accept() const { return final; } > 53 ~AhoCorasick() { for(int i=0; i<NC; ++i) if(link[i]!=this) delete link[i > 54 private: > 55 AhoCorasick() : link(NC+1) {} > 56 vector<AhoCorasick*> link; > 57 set<int> final; > 58 };