Overview
| SHA1 Hash: | 28a087506a86c52194a7f41da7b221e01638c92b |
|---|---|
| Date: | 2011-09-21 09:12:45 |
| 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
Deleted 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 <
Deleted 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 <
Name change from from SRM/519-U/1A.cpp to SRM/519/1A.cpp.
Name change from from SRM/519-U/1B.cpp to SRM/519/1B.cpp.
Added SRM/519/1C.java version [7e698666b34915d4]
> 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 VerySmoothDecompositions { public: > 23 int solve(vector <string> digits) > 24 { > 25 } > 26 }; > 27 > 28 > 29 > 30 // Powered by FileEdit > 31 // Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom > 32 // Powered by CodeProcessor