{"id":1201,"date":"2015-08-24T11:31:31","date_gmt":"2015-08-24T03:31:31","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1201"},"modified":"2015-08-27T02:54:23","modified_gmt":"2015-08-26T18:54:23","slug":"%e5%bc%b1%e6%a0%a1%e8%81%94%e8%90%8c15-16%e7%ac%ac%e4%b8%80%e6%ac%a1%e8%ae%ad%e7%bb%83%e8%b5%9b","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/%e5%bc%b1%e6%a0%a1%e8%81%94%e8%90%8c15-16%e7%ac%ac%e4%b8%80%e6%ac%a1%e8%ae%ad%e7%bb%83%e8%b5%9b\/","title":{"rendered":"\u5f31\u6821\u8054\u840c15-16\u7b2c\u4e00\u6b21\u8bad\u7ec3\u8d5b"},"content":{"rendered":"

http:\/\/acm.bnu.edu.cn\/v3\/contest_show.php?cid=6626<\/a>
\nhttp:\/\/judge.u-aizu.ac.jp\/onlinejudge\/finder.jsp?volumeNo=23<\/a>
\nhttp:\/\/acm-icpc.aitea.net\/index.php?2011%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E8%AC%9B%E8%A9%95<\/a><\/p>\n

<\/p>\n

C<\/h2>\n
\n``It is guaranteed that, for any pair of rooms in the office, there exists exactly one route between the two rooms''\n<\/pre>\n
\r\n#include <iostream>\r\n#include <cstring>\r\n#include <cstdio>\r\nusing namespace std;\r\n\r\n#define DO(n) for ( int ____n = n; ____n-->0; )\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 DWN(i, b, a) for (int i=b-1;i>=a;--i)\r\n#define REP_1(i, n) for (int i=1;i<=n;++i)\r\n#define FOR_1(i, a, b) for (int i=a;i<=b;++i)\r\n#define DWN_1(i, b, a) for (int i=b;i>=a;--i)\r\n#define RST(A) memset(A, 0, sizeof(A))\r\n#define FLC(A, x) memset(A, x, sizeof(A))\r\n\r\ntypedef long long LL;\r\nconst int MOD = int(1e9) + 7;\r\nint dx[4] = {0,1,0,-1};\r\nint dy[4] = {1,0,-1,0};\r\nconst int N = int(50) + 9;\r\n\r\nchar G[N][N];\r\nint a[N][N], b[N][N], c[N][N], vis[N][N], last[N][N];\r\nint n, m, l, T, Z;\r\n\r\nbool inGrid(int x, int y){\r\n    return x >= 0 && y >= 0 && x < n && y < m;\r\n}\r\n\r\nbool dfs(int x, int y, int tx, int ty, int t, int tt){\r\n\r\n    if (vis[x][y] == tt || G[x][y] == '#') return false;\r\n    bool flag = false; vis[x][y] = tt;\r\n\r\n    if (x == tx && y == ty){\r\n        flag = true;\r\n        T = t;\r\n    }\r\n    else{\r\n        REP(i, 4){\r\n            int xx = x + dx[i], yy = y + dy[i];\r\n            if (!inGrid(xx, yy)) continue;\r\n            flag |= dfs(xx, yy, tx, ty, t+1, tt);\r\n        }\r\n    }\r\n\r\n    if (flag){\r\n        if (last[x][y] == -1) Z += b[x][y] + c[x][y];\r\n        else Z += min(b[x][y] + c[x][y], a[x][y] * (t - last[x][y]));\r\n        last[x][y] = t;\r\n    }\r\n    return flag;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    while (~scanf("%d%d%d", &n, &m, &l)){\r\n        REP(i, n) scanf("%s", G[i]);\r\n        REP(i, n) REP(j, m) scanf("%d", &a[i][j]);\r\n        REP(i, n) REP(j, m) scanf("%d", &b[i][j]);\r\n        REP(i, n) REP(j, m) scanf("%d", &c[i][j]);\r\n\r\n        int x, y; RST(vis); FLC(last, -1); Z = T = 0; REP(i, l){\r\n            int xx, yy; scanf("%d %d", &xx, &yy);\r\n            if (i) dfs(x, y, xx, yy, T, i);\r\n            x = xx, y = yy;\r\n        }\r\n        printf("%d\\n", Z);\r\n    }\r\n}\r\n<\/pre>\n
D<\/h2>\n
\n... \u6570\u636e\u8303\u56f4\u5f88\u5c0f\u3002\u3002\u3002\u5e76\u6ca1\u6709\u4e8c\u5206\u7684\u5fc5\u8981\u3002\u3002\n<\/pre>\n
\r\n#include <iostream>\r\n#include <cstring>\r\n#include <cstdio>\r\nusing namespace std;\r\n\r\n#define DO(n) for ( int ____n = n; ____n-->0; )\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 DWN(i, b, a) for (int i=b-1;i>=a;--i)\r\n#define REP_1(i, n) for (int i=1;i<=n;++i)\r\n#define FOR_1(i, a, b) for (int i=a;i<=b;++i)\r\n#define DWN_1(i, b, a) for (int i=b;i>=a;--i)\r\n#define RST(A) memset(A, 0, sizeof(A))\r\n#define FLC(A, x) memset(A, x, sizeof(A))\r\n\r\ntypedef double DB;\r\n\r\nconst int N = int(1e2) + 9, M = int(5e1) + 9;\r\nDB p[N][M], sp[N][M], t[N], t0[N];\r\nint n, m, l;\r\n\r\nDB f(int i, DB ti){\r\n    DB z = 1; REP(j, n) if (i != j){\r\n        if (t0[j] + m*t[j] <= ti) return 0;\r\n        REP(k, m+1) if (t0[j] + k*t[j] > ti){\r\n            z *= (1 - sp[j][k]);\r\n            break;\r\n        }\r\n    }\r\n    return z;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    while (~scanf("%d%d%d", &n, &m, &l)){\r\n\r\n        RST(p); REP(i, n){\r\n            int _p, v; scanf("%d%lf%d", &_p, &t[i], &v); t0[i] = (DB) l \/ v; DB pp = (DB) _p \/ 100;\r\n\r\n            p[i][0] = 1; DO(m){\r\n                DWN_1(j, m, 1) p[i][j] = p[i][j-1] * pp + p[i][j] * (1-pp);\r\n                p[i][0] = p[i][0] * (1-pp);\r\n            }\r\n\r\n            REP_1(j, m) sp[i][j] = sp[i][j-1] + p[i][j-1];\r\n        }\r\n\r\n        REP(i, n){\r\n            DB z = 0; REP(j, m+1) z += p[i][j] * f(i, t0[i] + t[i]*j);\r\n            printf("%.9f\\n", z);\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
I<\/h2>\n
\n... \u56e0\u4e3a\u6570\u636e\u90fd\u662f\u6574\u6570\u3002\u3002\u53ef\u4ee5\u5c1d\u8bd5\u3002\u3002\u3002\u5c0f\u89d2\u5ea6\u679a\u4e3e\u3002\u3002\u3002\n<\/pre>\n
\r\n#include <set>\r\n#include <map>\r\n#include <cmath>\r\n#include <queue>\r\n#include <stack>\r\n#include <cstdio>\r\n#include <string>\r\n#include <vector>\r\n#include <cstring>\r\n#include <iostream>\r\n#include <algorithm>\r\n\r\nusing namespace std;\r\n\r\n#define REP(i, n) for (int i=0;i<n;++i)\r\n#define MP make_pair\r\n#define PB push_back\r\n\r\ntypedef double DB;\r\ntypedef long long LL;\r\n\r\nconst DB EPS = 1e-8;\r\nconst DB PI = acos(-1);\r\nconst DB gg = 9.8;\r\nconst int INF = 0x3f3f3f3f;\r\nconst int MOD = 1e9 + 7;\r\n\r\n\r\ninline void checkMin(int &a, int b){\r\n    if (b < a) a = b;\r\n}\r\n\r\ninline int sgn(double x){\r\n    return x < -EPS ? -1 : x > EPS;\r\n}\r\n\r\nconst int N = int(1e2) + 9;\r\nint n, l[N], b[N], r[N], t[N];\r\nint X, Y; DB V; int low;\r\n\r\ninline DB y(DB a, DB x) {\r\n    DB t = x\/(V*cos(a));\r\n    return V*sin(a)*t - 0.5*gg*t*t;\r\n}\r\n\r\ninline DB getM(DB a){\r\n    DB t = V*sin(a)\/gg;\r\n    return V*cos(a)*t;\r\n}\r\n\r\nbool ck(DB a) {\r\n\r\n    DB h = y(a, X); if (sgn(h-Y) < 0 || sgn(h-low) > 0 ) return false;\r\n    DB mx = getM(a), my = y(a, mx);\r\n\r\n    REP(i, n){\r\n\r\n        DB h1 = y(a, l[i]), h2 = y(a, r[i]);\r\n\r\n        if (l[i] <= mx && mx <= r[i]){\r\n            if (!(h1 <= b[i] && h2 <= b[i] && my <= b[i] || h1 >= t[i] && h2 >= t[i] && my >= t[i])) return false;\r\n        }\r\n        else{\r\n            if (!(h1 <= b[i] && h2 <= b[i] || h1 >= t[i] && h2 >= t[i])) return false;\r\n        }\r\n    }\r\n    return true;\r\n}\r\n\r\nbool ck() {\r\n\r\n    REP(i, n){\r\n        if (l[i] == 0 && b[i] == 0) return false;\r\n        if (l[i] <= X && X <= r[i]  && b[i] <= Y && Y <= t[i]) return false;\r\n    }\r\n\r\n    DB d = PI\/2\/10000;\r\n    for (DB a=d;a<=PI\/2;a+=d) if (ck(a)) return true;\r\n    return false;\r\n}\r\n\r\nint main() {\r\n    \/\/freopen("in.txt", "r", stdin);\r\n    while (~scanf("%d%lf%d%d", &n, &V, &X, &Y)) {\r\n        low = INF; REP(i, n){\r\n            scanf("%d%d%d%d", &l[i], &b[i], &r[i], &t[i]);\r\n            if (l[i] > X){\r\n                --i; --n;\r\n                continue;\r\n            }\r\n            if (r[i] >= X){\r\n                if (b[i] >= Y) checkMin(low, b[i]);\r\n                r[i] = X;\r\n            }\r\n        }\r\n        puts(ck() ? "Yes" : "No");\r\n    }\r\n}\r\n<\/pre>\n
I<\/h2>\n
\nDAG DP\u3002\u3002\u3002\u3002\u3002\u4e0d\u9519\u54e6\u3002\u3002\u3002\ndp[][][]\u3002\u3002\u3002 \u4ece\u4e2d\u95f4\u5f00\u59cb\u5411\u4e24\u8fb9\u4e0d\u65ad\u6dfb\u52a0\u56de\u6587\u4e32\uff0c \u72b6\u6001\u65f6 (\u5de6\u8fb9 ID\uff0c\u53f3\u8fb9 ID\uff0c\u591a\u51fa\u6765\u7684\u957f\u5ea6)\u3002\u3002\u3002 \u6b63\u6570\u8868\u793a\u53f3\u8fb9\u591a\u3002\n\u7136\u540e\u7528\u8bb0\u5fc6\u5316\u641c\u7d22... \u5728\u8fd9\u4e2a DAG \u4e0a DP\u3002\u3002\u6709\u73af\u7684\u8bdd\u8fd4\u56de -1\u3002\u3002\n\u3001\u3001\u3001https:\/\/www.shuizilong.com\/house\/archives\/andrew-stankevichs-contest-2\/ \uff1f\n\u3001\u3001\u3001http:\/\/m.blog.csdn.net\/blog\/u010709592\/39025279\uff1f\n<\/pre>\n
\r\n#include <iostream>\r\n#include <vector>\r\n#include <cstring>\r\n#include <cstdio>\r\nusing namespace std;\r\n\r\n#define DO(n) for ( int ____n = n; ____n-->0; )\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 DWN(i, b, a) for (int i=b-1;i>=a;--i)\r\n#define REP_1(i, n) for (int i=1;i<=n;++i)\r\n#define FOR_1(i, a, b) for (int i=a;i<=b;++i)\r\n#define DWN_1(i, b, a) for (int i=b;i>=a;--i)\r\n#define ECH(it, A) for (__typeof(A.begin()) it = A.begin(); it != A.end(); ++it)\r\n#define RST(A) memset(A, 0, sizeof(A))\r\n#define FLC(A, x) memset(A, x, sizeof(A))\r\n#define PB push_back\r\n\r\ntemplate<class T> void checkMax(T &a, T b){\r\n    if (b > a) a = b;\r\n}\r\n\r\ntypedef double DB;\r\ntypedef vector<int> VI;\r\nconst int INF = 0x3f3f3f3f;\r\n\r\nconst int N = int(1e2) + 9, M = 20;\r\nchar str[N][M+1]; int slen[N]; VI adj[N], radj[N];\r\n\r\nint vis[N][N][M+M+1]; int dp[N][N][M+M+1];\r\nint n, m;\r\n\r\n\r\nint f(int i0, int i1, int j){\r\n\r\n    int &z = dp[i0][i1][j+M], &v = vis[i0][i1][j+M];\r\n\r\n    if (v == 3) return z;\r\n\r\n    if (v == 1){\r\n        v = 2;\r\n        return -INF;\r\n    }\r\n\r\n    v = 1; z = j ? -INF : 0;\r\n\r\n    if (j > 0){\r\n        ECH(it, radj[i0]){\r\n            int i00 = *it; bool ok = true;\r\n\r\n            int up = min(j, slen[i00]); REP(k, up){\r\n                if (str[i00][slen[i00]-1-k] != str[i1][slen[i1]-j+k]){\r\n                    ok = false;\r\n                    break;\r\n                }\r\n            }\r\n\r\n            if (!ok) continue;\r\n            checkMax(z, f(i00, i1, j-slen[i00]) + slen[i00]);\r\n        }\r\n    }\r\n    else{\r\n\r\n        j = -j;\r\n\r\n        ECH(it, adj[i1]){\r\n            int i11 = *it; bool ok = true;\r\n\r\n            int up = min(j, slen[i11]); REP(k, up){\r\n                if (str[i0][j-1-k] != str[i11][k]){\r\n                    ok = false;\r\n                    break;\r\n                }\r\n            }\r\n\r\n            if (!ok) continue;\r\n            checkMax(z, f(i0, i11, slen[i11]-j) + slen[i11]);\r\n        }\r\n    }\r\n\r\n    if (z >= 0 && v == 2) z = INF;\r\n    v = 3;\r\n\r\n\r\n    \/\/if (z >= 0)\r\n    \/\/cout << ")" << i0 << " " << i1 << " " << j << " " << v << " "<< z << endl;\r\n    \/\/cout << i0 << " " <<i1 << " " << j << ": " << z << " "<<v << endl;\r\n    return z;\r\n}\r\n\r\nbool isPalindrome(int i0, int l, int r){\r\n    int len = r-l;\r\n    REP(i, len\/2) if (str[i0][l+i] != str[i0][r-1-i]) return false;\r\n    return true;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    while (~scanf("%d%d", &n, &m)){\r\n\r\n        REP(i, n){\r\n            scanf("%s", str[i]); adj[i].clear(), radj[i].clear();\r\n            slen[i] = strlen(str[i]);\r\n        }\r\n\r\n        DO(m){\r\n            int a, b; scanf("%d%d", &a, &b); --a, --b;\r\n            adj[a].PB(b); radj[b].PB(a);\r\n        }\r\n\r\n        FLC(dp, -1); RST(vis); int z = 0; REP(i, n) REP(j, slen[i]+1){\r\n            if (isPalindrome(i, 0, slen[i]-j) && f(i, i, j) >= 0) checkMax(z, f(i, i, j) + slen[i]);\r\n            if (isPalindrome(i, j, slen[i]) && f(i, i, -j) >= 0) checkMax(z, f(i, i, -j) + slen[i]);\r\n        }\r\n\r\n        if (z >= INF) z = -1;\r\n        printf("%d\\n", z);\r\n    }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/acm.bnu.edu.cn\/v3\/contest_show.php?cid=6626 http:\/\/judge.u-aizu.ac.jp\/onlinejudge\/finder.jsp?volumeNo=23 http:\/\/acm-icpc.aitea.net\/index.php?2011%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E8%AC%9B%E8%A9%95<\/p>\n","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":[1],"tags":[],"class_list":["post-1201","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-jn","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1201","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=1201"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1201\/revisions"}],"predecessor-version":[{"id":1202,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1201\/revisions\/1202"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1201"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1201"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1201"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}