Overview
| SHA1 Hash: | 5f23464ec44b7c4c80c3928fc9b4603ee7952bd3 |
|---|---|
| Date: | 2014-06-28 12:57:44 |
| User: | kinaba |
| Comment: | 625 |
| 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/625-U/1A.cpp version [e6519d12c7580902]
> 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 PalindromePermutations { public: > 23 double palindromeProbability(string word) > 24 { > 25 map<char, int> cnt; > 26 for(char c: word) cnt[c]++; > 27 > 28 vector<int> ns; > 29 for(auto cn: cnt) ns.emplace_back(cn.second); > 30 > 31 return solve(ns); > 32 } > 33 > 34 double solve(vector<int> c) > 35 { > 36 if(count_if(c.begin(), c.end(), [&](int x){return x%2==1;}) >= 2 > 37 return 0.0; > 38 return rec(c); > 39 } > 40 > 41 double rec(vector<int> c) > 42 { > 43 if(c.size() <= 1) > 44 return 1.0; > 45 > 46 int n = accumulate(c.begin(), c.end(), 0); > 47 int n2 = n/2; > 48 int k = c.back(); > 49 int k2 = k/2; > 50 c.pop_back(); > 51 return C(n2,k2) / C(n,k) * rec(c); > 52 } > 53 > 54 double C(int n, int k) > 55 { > 56 double v = 1.0; > 57 for(int i=1; i<=k; ++i) > 58 v = v * (n+1-i) / i; > 59 return v; > 60 } > 61 }; > 62 > 63 // BEGIN CUT HERE > 64 #include <ctime> > 65 double start_time; string timer() > 66 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 67 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 68 { os << "{ "; > 69 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 70 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 71 void verify_case(const double& Expected, const double& Received) { > 72 bool ok = (abs(Expected - Received) < 1e-9); > 73 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 74 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 75 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 76 #define END verify_case(_, PalindromePermutations().palindromeProbability(w > 77 int main(){ > 78 > 79 CASE(0) > 80 string word = "haha"; > 81 double _ = 0.3333333333333333; > 82 END > 83 CASE(1) > 84 string word = "xxxxy"; > 85 double _ = 0.2; > 86 END > 87 CASE(2) > 88 string word = "xxxx"; > 89 double _ = 1.0; > 90 END > 91 CASE(3) > 92 string word = "abcde"; > 93 double _ = 0.0; > 94 END > 95 CASE(4) > 96 string word = "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhff"; > 97 double _ = 0.025641025641025637; > 98 END > 99 /* > 100 CASE(5) > 101 string word = ; > 102 double _ = ; > 103 END > 104 CASE(6) > 105 string word = ; > 106 double _ = ; > 107 END > 108 */ > 109 } > 110 // END CUT HERE
Added SRM/625-U/1B.cpp version [8c270447eda5e6fb]
> 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 template<typename Vert=int, typename Flow=int, int NV=2048> > 23 class MaxFlow > 24 { > 25 vector<int> G[NV]; > 26 Flow F[NV][NV]; > 27 > 28 public: > 29 void addEdge( Vert s, Vert t, Flow f ) > 30 { > 31 G[s].push_back(t); > 32 G[t].push_back(s); > 33 F[s][t] = f; > 34 F[t][s] = 0; > 35 } > 36 > 37 Flow calc( Vert S, Vert D ) > 38 { > 39 for( Flow total=0 ;; ) { > 40 // Do BFS and compute the level for each node. > 41 int LV[NV] = {0}; > 42 vector<int> Q(1, S); > 43 for(int lv=1; !Q.empty(); ++lv) { > 44 vector<int> Q2; > 45 for(size_t i=0; i!=Q.size(); ++i) { > 46 const vector<int>& ne = G[Q[i]]; > 47 for(size_t j=0; j!=ne.size(); ++j) > 48 if( F[Q[i]][ne[j]] && !LV[ne[j]] > 49 LV[ne[j]]=lv, Q2.push_ba > 50 } > 51 Q.swap(Q2); > 52 } > 53 > 54 // Destination is now unreachable. Done. > 55 if( !LV[D] ) > 56 return total; > 57 > 58 // Iterating DFS. > 59 bool blocked[NV] = {}; > 60 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); > 61 } > 62 } > 63 > 64 private: > 65 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) > 66 { > 67 Flow flow_out = 0; > 68 for(size_t i=0; i!=G[v].size(); ++i) { > 69 int u = G[v][i]; > 70 if( LV[v]+1==LV[u] && F[v][u] ) { > 71 Flow f = min(flow_in-flow_out, F[v][u]); > 72 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f > 73 F[v][u] -= f; > 74 F[u][v] += f; > 75 flow_out += f; > 76 if( flow_in == flow_out ) return flow_ou > 77 } > 78 } > 79 } > 80 blocked[v] = (flow_out==0); > 81 return flow_out; > 82 } > 83 }; > 84 > 85 class BlockTheBlockPuzzle { public: > 86 int minimumHoles(vector <string> board) > 87 { > 88 const int H = board.size(); > 89 const int W = board[0].size(); > 90 const int INF = 2500; > 91 for(int gy=0; gy<H; ++gy) > 92 for(int gx=0; gx<W; ++gx) if(board[gy][gx] == '$') > 93 { > 94 map<pair<int,int>, int> id; > 95 for(int y=gy%3; y<H; y+=3) > 96 for(int x=gx%3; x<W; x+=3) > 97 { > 98 int new_id = id.size(); > 99 id[make_pair(y,x)] = new_id; > 100 } > 101 > 102 int N = id.size(); > 103 MaxFlow<>* mf = new MaxFlow<>; > 104 enum {IN, OUT}; > 105 > 106 int Goal; > 107 vector<int> Start; > 108 for(int y=gy%3; y<H; y+=3) > 109 for(int x=gx%3; x<W; x+=3)if(board[y][x]!='H') > 110 { > 111 int v1 = id[make_pair(y,x)]; > 112 if(board[y][x]=='$') > 113 Goal = v1; > 114 if(board[y][x]=='b') > 115 Start.push_back(v1); > 116 > 117 int e = (board[y][x]=='.' ? 1 : INF); > 118 mf->addEdge(v1*2+IN, v1*2+OUT, e); > 119 //cerr << v1 << " -- " << e << " -- " << v1 << e > 120 > 121 const int dy[] = {+1,0}; > 122 const int dx[] = {0,+1}; > 123 for(int d=0; d<2; ++d) > 124 { > 125 int Y = y+dy[d]*3; > 126 int X = x+dx[d]*3; > 127 if(0<=Y&&Y<H&&0<=X&&X<W&&board[Y][X]!='H > 128 { > 129 int v2 = id[make_pair(Y,X)]; > 130 > 131 int y1=y+dy[d]*1; > 132 int x1=x+dx[d]*1; > 133 int y2=y+dy[d]*2; > 134 int x2=x+dx[d]*2; > 135 int e = INF; > 136 if(board[y1][x1]!='b'&&board[y2] > 137 e = (board[y1][x1]=='.') > 138 if(e) { > 139 mf->addEdge(v1*2+OUT, v2 > 140 mf->addEdge(v2*2+OUT, v1 > 141 //cerr << v1 << " -- " < > 142 } > 143 } > 144 } > 145 } > 146 > 147 for(int v: Start) { > 148 //cerr << "S: " << v << endl; > 149 mf->addEdge(v*2+OUT, N*2+IN, INF); > 150 } > 151 //cerr << "G: " << Goal << endl; > 152 int ans = mf->calc(Goal*2+OUT, N*2+IN); > 153 delete mf; > 154 return ans>=INF ? -1 : ans; > 155 } > 156 return -1; > 157 } > 158 }; > 159 > 160 // BEGIN CUT HERE > 161 #include <ctime> > 162 double start_time; string timer() > 163 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 164 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 165 { os << "{ "; > 166 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 167 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 168 void verify_case(const int& Expected, const int& Received) { > 169 bool ok = (Expected == Received); > 170 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 171 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 172 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 173 #define END verify_case(_, BlockTheBlockPuzzle().minimumHoles(board));} > 174 int main(){ > 175 > 176 CASE(0) > 177 string board_[] = {"b..$", > 178 "....", > 179 "HHHH", > 180 "HHHH"}; > 181 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 182 int _ = 2; > 183 END > 184 CASE(1) > 185 string board_[] = {"............H..", > 186 "...............", > 187 "...............", > 188 "HHH$HHH.....H..", > 189 "HHHHHHH........", > 190 "HHHHHHHH.......", > 191 "......b..H.....", > 192 "...............", > 193 "...............", > 194 "...H..H..H.....", > 195 "...............", > 196 "...............", > 197 "...............", > 198 "...............", > 199 "..............."}; > 200 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 201 int _ = 0; > 202 END > 203 CASE(2) > 204 string board_[] = {"............H..", > 205 "...............", > 206 "...............", > 207 "HHH$HHH........", > 208 "HHHHHHH........", > 209 "HHHHHHHH.......", > 210 "......b..H.....", > 211 "...............", > 212 "...............", > 213 "...H..H..H.....", > 214 "...............", > 215 "...............", > 216 "...............", > 217 "...............", > 218 "..............."}; > 219 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 220 int _ = 1; > 221 END > 222 CASE(3) > 223 string board_[] = {"b..$...", > 224 "...H...", > 225 ".......", > 226 "b..b..b", > 227 "...H...", > 228 ".......", > 229 "b..b..b"} > 230 > 231 ; > 232 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 233 int _ = 4; > 234 END > 235 CASE(4) > 236 string board_[] = {"b..b..b", > 237 "..b..b.", > 238 ".......", > 239 "b..$bbb", > 240 ".b.....", > 241 "....b..", > 242 "b..b..b"} > 243 ; > 244 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 245 int _ = -1; > 246 END > 247 /* > 248 CASE(5) > 249 string board_[] = ; > 250 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 251 int _ = ; > 252 END > 253 CASE(6) > 254 string board_[] = ; > 255 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 256 int _ = ; > 257 END > 258 */ > 259 } > 260 // END CUT HERE