Overview
| SHA1 Hash: | 724e2f81fdc596c2068127053f84302ded39a1cf |
|---|---|
| Date: | 2017-02-09 13:43:48 |
| User: | kinaba |
| Comment: | 708 |
| 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/708-U/1A.cpp version [07f849a6818c5faf]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class BalancedStrings { public: > 23 vector <string> findAny(int N) > 24 { > 25 return solve(N); > 26 } > 27 > 28 int sim(const vector<string>& S) { > 29 int cnt = 0; > 30 for (int i = 0; i < S.size(); ++i) > 31 for (int k = i + 1; k < S.size(); ++k) > 32 for (char c1 : S[i]) > 33 for (char c2 : S[k]) > 34 if (c1 == c2) > 35 ++cnt; > 36 return cnt; > 37 } > 38 > 39 vector<string> solve(int N) > 40 { > 41 if (N <= 26) { > 42 vector<string> ans; > 43 for (int i = 0; i < N; ++i) > 44 ans.push_back(string(1, 'a' + i)); > 45 return ans; > 46 } > 47 > 48 vector<string> ans; > 49 for (int i = 0; i < N-2; ++i) > 50 ans.push_back(string(1, 'e' + i%20)); > 51 int s = sim(ans); > 52 string a = "b"; > 53 string c = "d"; > 54 while (s && a.size() < 100) a += (a.back()=='a' ? 'b' : 'a'), -- > 55 while (s && c.size() < 100) c += (c.back()=='c' ? 'd' : 'c'), -- > 56 ans.push_back(a); > 57 ans.push_back(c); > 58 return ans; > 59 } > 60 }; > 61 > 62 // BEGIN CUT HERE > 63 #include <ctime> > 64 double start_time; string timer() > 65 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 66 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 67 { os << "{ "; > 68 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 69 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 70 void verify_case(const vector <string>& Expected, const vector <string>& Receive > 71 bool ok = (Expected == Received); > 72 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 73 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 74 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 75 #define END verify_case(_, BalancedStrings().findAny(N));} > 76 int main(){ > 77 > 78 CASE(0) > 79 int N = 3; > 80 string __[] = {"eertree", "topcoder", "arena" }; > 81 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 82 END > 83 CASE(1) > 84 int N = 4; > 85 string __[] = {"hello", "little", "polar", "bear" }; > 86 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 87 END > 88 CASE(2) > 89 int N = 5; > 90 string __[] = {"abbbbbbbbbbbbczaaaaaao", "c", "zz", "c", "xxxyyyzvvv" }; > 91 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 92 END > 93 CASE(3) > 94 int N = 1; > 95 string __[] = {"kkkkkkkkkkkkkkkkkkk" }; > 96 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 97 END > 98 CASE(4) > 99 int N = 10; > 100 string __[] = {"asdflkjhsdfsfffkdhjfdlshlfds", "pudelek", "xo", "xo", "m > 101 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 102 END > 103 CASE(5) > 104 int N = 100; > 105 string __[] = { "" }; > 106 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 107 END > 108 CASE(6) > 109 int N = 40; > 110 string __[] = { "" }; > 111 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 112 END > 113 } > 114 // END CUT HERE
Added SRM/708-U/1B-U.cpp version [435de136cbd3a80e]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint() :val(0) {} > 27 mint(int x) :val(x%MODVAL) {} > 28 mint(unsigned x) :val(x%MODVAL) {} > 29 mint(LL x) :val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val + y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val - y.val + MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x += y; } > 35 mint operator-(mint x, mint y) { return x -= y; } > 36 mint operator*(mint x, mint y) { return x *= y; } > 37 > 38 template<typename T> > 39 struct DP2 > 40 { > 41 const int N1, N2; > 42 vector<T> data; > 43 DP2(int N1, int N2, const T& t = T()) > 44 : N1(N1), N2(N2), data(N1*N2, t) { > 45 assert(data.size() * sizeof(T)<(1 << 28)); > 46 } > 47 T& operator()(int i1, int i2) > 48 { > 49 return data[(i1*N2) + i2]; > 50 } > 51 }; > 52 > 53 class PalindromicSubseq { public: > 54 int solve(string s) > 55 { > 56 const int N = s.size(); > 57 > 58 DP2<mint> outer(N, N), inner(N,N); > 59 for (int l = 0; l < N; ++l) > 60 for (int r = l; r < N; ++r) > 61 if (s[l] == s[r]) > 62 outer(l, r) = inner(l, r) = 1; > 63 > 64 for(int len=N; len>=1; --len) > 65 for (int l = 0; l+len-1 < N; ++l) { > 66 int r = l + len - 1; > 67 if (s[l] == s[r]) { > 68 for (int x = l - 1; x >= 0; --x) > 69 for (int y = r + 1; y < N; ++y) > 70 if (s[x] == s[y]) > 71 outer(l,r) += ou > 72 } > 73 } > 74 for (int len = 1; len <= N; ++len) > 75 for (int l = 0; l+len-1 < N; ++l) { > 76 int r = l + len - 1; > 77 if (s[l] == s[r]) { > 78 for (int x = l + 1; x < r; ++x) > 79 for (int y = r - 1; y >= x; --y) > 80 if (s[x] == s[y]) > 81 inner(l,r) += in > 82 } > 83 } > 84 vector<mint> X(N); > 85 for (int l = 0; l < N; ++l) > 86 for (int r = l; r < N; ++r) > 87 if (s[l] == s[r]) { > 88 mint total = inner(l, r) * outer(l, r); > 89 X[l] += total; > 90 if (l != r) X[r] += total; > 91 } > 92 > 93 int ans = 0; > 94 for (int i = 0; i < N; ++i) > 95 ans ^= ((i+1)*X[i]).val; > 96 return ans; > 97 } > 98 }; > 99 > 100 // BEGIN CUT HERE > 101 #include <ctime> > 102 double start_time; string timer() > 103 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 104 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 105 { os << "{ "; > 106 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 107 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 108 void verify_case(const int& Expected, const int& Received) { > 109 bool ok = (Expected == Received); > 110 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 111 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 112 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 113 #define END verify_case(_, PalindromicSubseq().solve(s));} > 114 int main(){ > 115 > 116 CASE(0) > 117 string s = "aaba"; > 118 int _ = 30; > 119 END > 120 CASE(1) > 121 string s = "abcd"; > 122 int _ = 4; > 123 END > 124 CASE(2) > 125 string s = "tcoct"; > 126 int _ = 60; > 127 END > 128 CASE(3) > 129 string s = "zyzyzzzzxzyz"; > 130 int _ = 717; > 131 END > 132 CASE(4) > 133 string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa > 134 int _ = 1025495382; > 135 END > 136 CASE(5) > 137 string s = "a"; > 138 int _ = 1; > 139 END > 140 CASE(6) > 141 string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa > 142 int _ = -1; > 143 END > 144 } > 145 // END CUT HERE