{"id":961,"date":"2014-09-03T18:43:24","date_gmt":"2014-09-03T10:43:24","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=961"},"modified":"2014-09-14T01:39:55","modified_gmt":"2014-09-13T17:39:55","slug":"srm-631","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-631\/","title":{"rendered":"SRM 631"},"content":{"rendered":"

<\/p>\n

250. TaroJiroGrid\uff1a<\/h2>\n

Brief description: <\/h3>\n

\u4e00\u4e2a n*n \u7684 0\/1 \u65b9\u9635\u3002\u3002\u88ab\u79f0\u4e3a good \u3002\u3002\u5982\u679c\u5bf9\u4e8e\u4efb\u610f\u4e00\u5217\u3002\u3002\u90fd\u4e0d\u5b58\u5728 > n\/2 \u4e2a\u8fde\u7eed\u76f8\u540c\u7684\u683c\u5b50\u3002\u3002
\n\u3002\u3002\u3002\u4f60\u53ef\u4ee5\u5bf9\u67d0\u884c\u8fdb\u884c\u67d3\u8272\u64cd\u4f5c\uff08\u5168\u90e8\u67d3\u6210\u767d\u8272\u6216\u9ed1\u8272\uff09\u3002\u3002\u3002
\n\u95ee\u81f3\u5c11\u51e0\u6b21\u67d3\u8272\u64cd\u4f5c\u53ef\u4ee5\u8ba9\u7ed9\u5b9a\u7684 0\/1 \u65b9\u9635 good\u3002\u3002\u3002<\/p>\n

Analysis: <\/h3>\n

\u6ce8\u610f\u5230\u6700\u591a\u53ea\u9700\u8981\u4e24\u6b21\uff08\u5728\u5bf9\u4e2d\u95f4\u4e24\u884c\u67d3\u8272\u3002\u3002\uff09\u4e00\u5b9a\u5408\u6cd5\u3002\u3002
\n……..
\n0000
\n1111
\n……..
\n\u56e0\u6b64\u53ea\u9700\u8981\u5224\u65ad 0 \u6b21\u548c 1 \u6b21\u662f\u5426\u5408\u6cd5\u3002\u3002\u3002\u66b4\u529b\u679a\u4e3e\u6240\u8981\u67d3\u8272\u7684\u884c\u548c\u67d3\u7684\u989c\u8272\u5373\u53ef\u3002<\/p>\n

\r\n#define REP(i, n) for (int i=0;i<n;++i)\r\n#define FOR(i, a, b) for (int i=a;i<b;++i)\r\n#define REP_2(i, j, n, m) REP(i, n) REP(j, m)\r\n#define CPY(A, B) memcpy(A, B, sizeof(A))\r\n\r\nconst int N = int(1e2) + 9;\r\nint A[N][N], _A[N];\r\nint n;\r\n\r\nbool ck(){\r\n\r\n    REP(j, n){\r\n        int c = 1; FOR(i, 1, n) if (A[i][j] != A[i-1][j]) c = 1;\r\n        else if (++c > n\/2) return 0;\r\n    }\r\n\r\n    return 1;\r\n}\r\n\r\nclass TaroJiroGrid {\r\npublic:\r\nint getNumber(vector <string> grid) {\r\n\r\n   n = grid.size(); REP_2(i, j, n, n) A[i][j] = grid[i][j] == 'B';\r\n   if (ck()) return 0;\r\n\r\nint z = 2; REP(i, n) REP(b, 2){\r\n   CPY(_A, A[i]); REP(j, n) A[i][j] = b;\r\n            if (ck()) return 1;\r\n            CPY(A[i], _A);\r\n}\r\n\r\nreturn 2;\r\n}\r\n};\r\n<\/pre>\n
500. CatsOnTheLineDiv1: <\/h2>\n
Brief description: <\/h3>\n
x-\u8f74\u4e0a\u5206\u5e03\u7740 n \u5806\u732b\uff0c\u6bcf\u5806\u732b\u7684\u4f4d\u7f6e\u662f p[i]\uff0c\u6570\u91cf\u662f c[i]\u3002\u3002\u3002\u6bcf\u4e2a\u5355\u4f4d\u65f6\u95f4\u6bcf\u53ea\u732b\u53ef\u4ee5\u5411\u4e24\u8fb9\u79fb\u52a8\u4e00\u683c\u3002
\n\u95ee t \u65f6\u95f4\u540e\uff0c\u6709\u4e24\u53ea\u53ca\u4ee5\u4e0a\u732b\u7684\u4f4d\u7f6e\u6700\u5c0f\u65f6\u591a\u5c11<\/p>\n
Analysis: <\/h3>\n
\u6392\u5e8f\uff0c\u8d2a\u5fc3\u3002 <\/p>\n
.\u3002\u3002\u8ba1\u7b97\u51fa\u6bcf\u5806\u732b\uff0ct \u65f6\u95f4\u540e\u53ef\u4ee5\u5230\u8fbe\u7684\u6700\u5de6\u8fb9\u548c\u6700\u53f3\u8fb9\u7684\u4f4d\u7f6e (l, r)\u3002\u3002\u3002\u663e\u7136\u5982\u679c c[i] > r-l+1\u3002\u3002\u90a3\u4e48\u81f3\u5c11 res++\u3002
\n\u3002\u6211\u4eec\u53ef\u4ee5\u628a\u8fd9\u4e2a \u201c\u6c47\u805a\u201d (sink) \u70b9\u653e\u5230\u6700\u53f3\u4fa7 r\u3002\u3002\u3002\u8fd9\u6837\u4e0b\u6b21\u8fd8\u9047\u5230\u8fd9\u7c7b\u533a\u95f4\u65f6\u3002\u3002\u5982\u679c l <= r \u90a3\u4e48\u5c31\u53ef\u4ee5\u4e0d\u7528 res++ \u4e86\u3002\u3002\n\n[cpp]\n#define REP(i, n) for (int i=0;i<n;++i)\n#define FOR(i, a, b) for (int i=a;i<b;++i)\n#define fi first\n#define se second\ntemplate<class T> inline T& checkMax(T &a,const T b){if (a<b) a=b;return a;}\nconst int INF = 0x3f3f3f3f;\n\nclass CatsOnTheLineDiv1 {\npublic:\nint getNumber(vector <int> position, vector <int> count, int time) {\n\n   int n = position.size(); vector<pair<int, int> > I;\n   REP(i, n) I.push_back({position[i]-time, count[i]}); sort(I.begin(), I.end());\n\nint res=0,l=-INF,sink=-INF; REP(i, n){\n\n   int ll = I[i].fi, r = I[i].fi+2*time;\n   if (ll <= sink) continue;\n            checkMax(l, ll);\n\n   if (r-l+1 >= I[i].se) l += I[i].se;\n   else ++res, sink = r;\n}\n\nreturn res;\n}\n};\n[\/cpp]\n\n\n\n\n\n
1000 TaroTreeRequests: <\/h2>\n
\u88f8\u52a8\u6001\u6811\u3002<\/p>\n
HDU 4010. Query on The Trees
\n<\/a><\/p>\n
SPOJ.com – Problem DYNALCA<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[17],"tags":[],"class_list":["post-961","post","type-post","status-publish","format-standard","hentry","category-topcoder"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fv","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/961","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=961"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/961\/revisions"}],"predecessor-version":[{"id":962,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/961\/revisions\/962"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=961"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=961"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=961"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}