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 pattern 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 suffix of "t"... 51 + while( !r->link[c] ) 52 + r = r->link[NC]; 53 + t->link[c]->link[NC] = r->link[c]; // then "rc" is suffix of "tc" 54 + t->link[c]->final.insert(r->link[c]->final.begin(), r->link[c]->final.end()); 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(); ++it) 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 pattern 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 suffix of "t"... 38 + while( !r->link[c] ) 39 + r = r->link[NC]; 40 + t->link[c]->link[NC] = r->link[c]; // then "rc" is suffix of "tc" 41 + t->link[c]->final.insert(r->link[c]->final.begin(), r->link[c]->final.end()); 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 +};