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 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 -
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