{"id":1198,"date":"2015-08-19T11:19:25","date_gmt":"2015-08-19T03:19:25","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1198"},"modified":"2015-08-24T11:29:45","modified_gmt":"2015-08-24T03:29:45","slug":"2015-multi-university-training-contest-9-%ef%bc%8d-host-by-xudyh","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/2015-multi-university-training-contest-9-%ef%bc%8d-host-by-xudyh\/","title":{"rendered":"2015 Multi-University Training Contest 9 \uff0d Host by xudyh"},"content":{"rendered":"

<\/p>\n

1001<\/h2>\n
\r\n#include <iostream>\r\n#include <cstring>\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\r\n\r\ntypedef long long LL;\r\nconst int MOD = int(1e9) + 7;\r\n\r\nstruct Int{\r\n    int val;\r\n    \r\n    operator int() const{return val;}\r\n    \r\n    Int(int t){\r\n        val = t;\r\n    }\r\n    Int& operator -=(const int& rhs){\r\n        val -= rhs; if (val < 0) val += MOD;\r\n        return *this;\r\n    }\r\n    Int& operator +=(const int& rhs){\r\n        val += rhs; if (val >= MOD) val -= MOD;\r\n        return *this;\r\n    }\r\n    Int operator *(const int& rhs) const{\r\n        LL z = (LL) val * rhs % MOD;\r\n        return z;\r\n    }\r\n};\r\n\r\n\r\nconst int N = int(1e2) + 9;\r\n\r\nint a[N]; char op[N];\r\nint Fact[N], Binom[N][N], dp[N][N];\r\nint n;\r\n\r\nint w(int l, int r){\r\n    return Fact[r-l];\r\n}\r\nint c(int l, int k, int r){\r\n    return Binom[r-l-1][k-l];\r\n}\r\n\r\nInt f(int l, int r){\r\n    int &z = dp[l][r]; if (z == -1){\r\n        Int zz = 0; FOR(k, l, r) if (op[k] == '*'){\r\n            zz += (Int) f(l, k) * f(k+1, r) * c(l, k, r);\r\n        }\r\n        else if (op[k] == '+'){\r\n            zz += (Int) f(l, k) * w(k+1, r) * c(l, k, r);\r\n            zz += (Int) w(l, k) * f(k+1, r) * c(l, k, r);\r\n        }\r\n        else{\r\n            zz += (Int) f(l, k) * w(k+1, r) * c(l, k, r);\r\n            zz -= (Int) w(l, k) * f(k+1, r) * c(l, k, r);\r\n        }\r\n        z = zz % MOD;\r\n        if (z < 0) z += MOD;\r\n    }\r\n    return z;\r\n}\r\n\r\n\/\/(3+5+7) + (2+4+7)\r\n\r\nint main(){\r\n    \r\n#ifndef ONLINE_JUDGE\r\n    freopen("\/users\/xiaodao\/desktop\/Exercise\/in.txt", "r", stdin);\r\n    \/\/freopen("\/users\/xiaodao\/desktop\/Exercise\/out.txt", "w", stdout);\r\n#endif\r\n    \r\n    Fact[0] = 1; FOR(i, 1, N) Fact[i] = Int(Fact[i-1]) * i;\r\n    \r\n    REP(i, N){\r\n        Binom[i][0] = 1;\r\n        REP_1(j, i) Binom[i][j] = (Binom[i-1][j-1] + Binom[i-1][j]) % MOD;\r\n    }\r\n    \r\n    \r\n    while (~scanf("%d", &n)){\r\n        REP(i, n) scanf("%d", &a[i]); scanf("%s", op); memset(dp, -1, sizeof(dp));\r\n        REP(i, n) dp[i][i] = a[i];\r\n        printf("%d\\n", f(0, n-1));\r\n    }\r\n}\r\n\r\n\r\n\r\n\r\n<\/pre>\n
1004<\/h2>\n
\r\n#include <iostream>\r\n#include <cstring>\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, a, b) for (int i=a-1;i>=b;--i)\r\n#define RST(A) memset(A, 0, sizeof(A))\r\n\r\ntypedef long long LL;\r\nconst int MOD = int(1e9) + 7;\r\n\r\nint pow(int a, int b){\r\n    int z = 1;\r\n    while (b){\r\n        if (b&1) z = (LL)z * a % MOD;\r\n        a = (LL)a * a % MOD; b >>= 1;\r\n    }\r\n    return z;\r\n}\r\n\r\nconst int N = int(1e2) + 9;\r\nint Fact[N], P[N][N], I[N], II[N]; bool vis[N];\r\nint n, m;\r\n\r\nint solve(){\r\n    bool bad = false; int d = 0; REP(i, m){\r\n        scanf("%d", &P[i][0]);\r\n        if (P[i][0] == -1) ++d;\r\n        else{\r\n            RST(vis); vis[P[i][0]] = true;\r\n            FOR(j, 1, n){\r\n                scanf("%d", &P[i][j]);\r\n                if (vis[P[i][j]]) bad = true;\r\n                vis[P[i][j]] = true;\r\n            }\r\n        }\r\n    }\r\n    \r\n    if (bad) return 0;\r\n    \r\n    if (d){\r\n        return pow(Fact[n], d-1);\r\n    }\r\n    else{\r\n        REP(i, n) I[i] = i; DWN(i, m, 0){\r\n            REP(j, n) II[j] = I[j];\r\n            REP(j, n) I[j] = P[i][II[j]] - 1;\r\n        }\r\n        \r\n        REP(i, n) if (I[i] != i) return 0;\r\n        return 1;\r\n    }\r\n}\r\n\r\n\r\nint main(){\r\n    \r\n#ifndef ONLINE_JUDGE\r\n    freopen("\/users\/xiaodao\/desktop\/Exercise\/in.txt", "r", stdin);\r\n    \/\/freopen("\/users\/xiaodao\/desktop\/Exercise\/out.txt", "w", stdout);\r\n#endif\r\n    \r\n    Fact[0] = 1; FOR(i, 1, N) Fact[i] = (LL) Fact[i-1] * i % MOD;\r\n    while (cin >> n >> m){\r\n        cout << solve() << endl;\r\n    }\r\n}\r\n<\/pre>\n
1005<\/h2>\n
\r\n#include <iostream>\r\n#include <cstring>\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\r\ntypedef long long LL;\r\n\r\nconst int N = int(1e5) + 9;\r\nint A[N], L[N], R[N], n, d1, d2;\r\n\r\n\r\nLL solve(){\r\n    LL z = 0;\r\n    \r\n    REP(i, n) scanf("%d", &A[i]);\r\n    \r\n    REP(i, n-1){\r\n        if (A[i+1] - A[i] == d1){\r\n            L[i+1] = L[i] + 1;\r\n        }\r\n        else{\r\n            L[i+1] = 0;\r\n        }\r\n    }\r\n    \r\n    R[n-1] = 0;\r\n    DWN(i, n-1, 0){\r\n        if (A[i+1] - A[i] == d2){\r\n            R[i] = R[i+1] + 1;\r\n        }\r\n        else{\r\n            R[i] = 0;\r\n        }\r\n    }\r\n    \r\n    \r\n    \r\n    if (d1 == d2){\r\n        \/*REP(i, n){\r\n            z += (LL)(R[i]+1)*(R[i]+2) \/ 2;\r\n            i += R[i];\r\n        }\r\n        return z;*\/\r\n        REP(i, n) L[i] = 0;\r\n    }\r\n    \r\n    \r\n    REP(i, n){\r\n        z += (LL) (L[i]+1)*(R[i]+1);\r\n    }\r\n    return z;\r\n}\r\n\r\n\r\nint main(){\r\n    \r\n#ifndef ONLINE_JUDGE\r\n    freopen("\/users\/xiaodao\/desktop\/Exercise\/in.txt", "r", stdin);\r\n    \/\/freopen("\/users\/xiaodao\/desktop\/Exercise\/out.txt", "w", stdout);\r\n#endif\r\n    \r\n    while (cin >> n >> d1 >> d2){\r\n        cout << solve() << endl;\r\n    }\r\n}\r\n<\/pre>\n
1007<\/h2>\n
\r\n#include <iostream>\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\r\nconst int N = int(1e2) + 9;\r\nint A[N][N];\r\nint n, m;\r\n\r\n\r\nconst int dx[] = {1, 0, -1, 0};\r\nconst int dy[] = {0, 1, 0, 1};\r\nconst char op[] = {'D', 'R', 'U', 'R'};\r\nconst int SZ = 4;\r\n\r\nvoid snake(int x, int y, int tx, int ty){\r\n    int p = 0; bool flag = true; DO(2*(m-1) - 1){\r\n        if (x+dx[p] == tx && y+dy[p] == ty){\r\n            flag = false; ++y;\r\n            putchar('R');\r\n        }\r\n        x += dx[p]; y += dy[p]; putchar(op[p]);\r\n        ++p; if (p == SZ) p = 0;\r\n    }\r\n    if (flag) putchar('R');\r\n}\r\n\r\n\r\nint main() {\r\n    \r\n#ifndef ONLINE_JUDGE\r\n    freopen("\/users\/xiaodao\/desktop\/Exercise\/in.txt", "r", stdin);\r\n    \/\/freopen("\/users\/xiaodao\/desktop\/Exercise\/out.txt", "w", stdout);\r\n    \r\n#endif\r\n    \r\n    while (cin >> n >> m){\r\n        \r\n        int z = 0; REP(i, n) REP(j, m){\r\n            scanf("%d", &A[i][j]);\r\n            z += A[i][j];\r\n        }\r\n            \r\n        if (n&1){\r\n            cout << z << endl;\r\n            REP(i, n){\r\n                DO(m-1) putchar( (i&1) ? 'L' : 'R');\r\n                if (i != n-1) putchar('D');\r\n            }\r\n        }\r\n        else if (m&1){\r\n            cout << z << endl;\r\n            REP(i, m){\r\n                DO(n-1) putchar( (i&1) ? 'U' : 'D');\r\n                if (i != m-1) putchar('R');\r\n            }\r\n        }\r\n        else{\r\n            int x = 0, y = 1;\r\n            REP(i, n) REP(j, m) if ((i+j)&1){\r\n                if (A[i][j] < A[x][y]){\r\n                    x = i, y = j;\r\n                }\r\n            }\r\n            z -= A[x][y];\r\n            cout << z << endl;\r\n\r\n            bool flag = true;\r\n            REP(i, n\/2){\r\n                \r\n                if (i) putchar('D');\r\n                \r\n                if (flag){\r\n                    \r\n                    if (x\/2 == i){\r\n                        snake(i*2, 0, x, y);\r\n                        flag = false;\r\n                        continue;\r\n                    }\r\n                    \r\n                    DO(m-1) putchar('R'); putchar('D');\r\n                    DO(m-1) putchar('L');\r\n                }\r\n                else{\r\n                    DO(m-1) putchar('L'); putchar('D');\r\n                    DO(m-1) putchar('R');\r\n                }\r\n                \r\n            }\r\n        }\r\n        \r\n        puts("");\r\n    }   \r\n}\r\n<\/pre>\n
\n4 2\n1 1\n1 1\n1 1\n1 1\n\n2 4\n1 1 1 1\n1 1 1 1\n<\/pre>\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":[104],"tags":[],"class_list":["post-1198","post","type-post","status-publish","format-standard","hentry","category-multi-university-training"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-jk","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1198","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=1198"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1198\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1198"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1198"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1198"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}