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

C

``It is guaranteed that, for any pair of rooms in the office, there exists exactly one route between the two rooms''

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define RST(A) memset(A, 0, sizeof(A))
#define FLC(A, x) memset(A, x, sizeof(A))

typedef long long LL;
const int MOD = int(1e9) + 7;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
const int N = int(50) + 9;

char G[N][N];
int a[N][N], b[N][N], c[N][N], vis[N][N], last[N][N];
int n, m, l, T, Z;

bool inGrid(int x, int y){
    return x >= 0 && y >= 0 && x < n && y < m;
}

bool dfs(int x, int y, int tx, int ty, int t, int tt){

    if (vis[x][y] == tt || G[x][y] == '#') return false;
    bool flag = false; vis[x][y] = tt;

    if (x == tx && y == ty){
        flag = true;
        T = t;
    }
    else{
        REP(i, 4){
            int xx = x + dx[i], yy = y + dy[i];
            if (!inGrid(xx, yy)) continue;
            flag |= dfs(xx, yy, tx, ty, t+1, tt);
        }
    }

    if (flag){
        if (last[x][y] == -1) Z += b[x][y] + c[x][y];
        else Z += min(b[x][y] + c[x][y], a[x][y] * (t - last[x][y]));
        last[x][y] = t;
    }
    return flag;
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d%d%d", &n, &m, &l)){
        REP(i, n) scanf("%s", G[i]);
        REP(i, n) REP(j, m) scanf("%d", &a[i][j]);
        REP(i, n) REP(j, m) scanf("%d", &b[i][j]);
        REP(i, n) REP(j, m) scanf("%d", &c[i][j]);

        int x, y; RST(vis); FLC(last, -1); Z = T = 0; REP(i, l){
            int xx, yy; scanf("%d %d", &xx, &yy);
            if (i) dfs(x, y, xx, yy, T, i);
            x = xx, y = yy;
        }
        printf("%d\n", Z);
    }
}

D

... 数据范围很小。。。并没有二分的必要。。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define RST(A) memset(A, 0, sizeof(A))
#define FLC(A, x) memset(A, x, sizeof(A))

typedef double DB;

const int N = int(1e2) + 9, M = int(5e1) + 9;
DB p[N][M], sp[N][M], t[N], t0[N];
int n, m, l;

DB f(int i, DB ti){
    DB z = 1; REP(j, n) if (i != j){
        if (t0[j] + m*t[j] <= ti) return 0;
        REP(k, m+1) if (t0[j] + k*t[j] > ti){
            z *= (1 - sp[j][k]);
            break;
        }
    }
    return z;
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d%d%d", &n, &m, &l)){

        RST(p); REP(i, n){
            int _p, v; scanf("%d%lf%d", &_p, &t[i], &v); t0[i] = (DB) l / v; DB pp = (DB) _p / 100;

            p[i][0] = 1; DO(m){
                DWN_1(j, m, 1) p[i][j] = p[i][j-1] * pp + p[i][j] * (1-pp);
                p[i][0] = p[i][0] * (1-pp);
            }

            REP_1(j, m) sp[i][j] = sp[i][j-1] + p[i][j-1];
        }

        REP(i, n){
            DB z = 0; REP(j, m+1) z += p[i][j] * f(i, t0[i] + t[i]*j);
            printf("%.9f\n", z);
        }
    }
}

I

... 因为数据都是整数。。可以尝试。。。小角度枚举。。。

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define REP(i, n) for (int i=0;i<n;++i)
#define MP make_pair
#define PB push_back

typedef double DB;
typedef long long LL;

const DB EPS = 1e-8;
const DB PI = acos(-1);
const DB gg = 9.8;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;


inline void checkMin(int &a, int b){
    if (b < a) a = b;
}

inline int sgn(double x){
    return x < -EPS ? -1 : x > EPS;
}

const int N = int(1e2) + 9;
int n, l[N], b[N], r[N], t[N];
int X, Y; DB V; int low;

inline DB y(DB a, DB x) {
    DB t = x/(V*cos(a));
    return V*sin(a)*t - 0.5*gg*t*t;
}

inline DB getM(DB a){
    DB t = V*sin(a)/gg;
    return V*cos(a)*t;
}

bool ck(DB a) {

    DB h = y(a, X); if (sgn(h-Y) < 0 || sgn(h-low) > 0 ) return false;
    DB mx = getM(a), my = y(a, mx);

    REP(i, n){

        DB h1 = y(a, l[i]), h2 = y(a, r[i]);

        if (l[i] <= mx && mx <= r[i]){
            if (!(h1 <= b[i] && h2 <= b[i] && my <= b[i] || h1 >= t[i] && h2 >= t[i] && my >= t[i])) return false;
        }
        else{
            if (!(h1 <= b[i] && h2 <= b[i] || h1 >= t[i] && h2 >= t[i])) return false;
        }
    }
    return true;
}

bool ck() {

    REP(i, n){
        if (l[i] == 0 && b[i] == 0) return false;
        if (l[i] <= X && X <= r[i]  && b[i] <= Y && Y <= t[i]) return false;
    }

    DB d = PI/2/10000;
    for (DB a=d;a<=PI/2;a+=d) if (ck(a)) return true;
    return false;
}

int main() {
    //freopen("in.txt", "r", stdin);
    while (~scanf("%d%lf%d%d", &n, &V, &X, &Y)) {
        low = INF; REP(i, n){
            scanf("%d%d%d%d", &l[i], &b[i], &r[i], &t[i]);
            if (l[i] > X){
                --i; --n;
                continue;
            }
            if (r[i] >= X){
                if (b[i] >= Y) checkMin(low, b[i]);
                r[i] = X;
            }
        }
        puts(ck() ? "Yes" : "No");
    }
}

I

DAG DP。。。。。不错哦。。。
dp[][][]。。。 从中间开始向两边不断添加回文串， 状态时 (左边 ID，右边 ID，多出来的长度)。。。 正数表示右边多。
然后用记忆化搜索... 在这个 DAG 上 DP。。有环的话返回 -1。。
、、、https://www.shuizilong.com/house/archives/andrew-stankevichs-contest-2/ ？
、、、http://m.blog.csdn.net/blog/u010709592/39025279？

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define ECH(it, A) for (__typeof(A.begin()) it = A.begin(); it != A.end(); ++it)
#define RST(A) memset(A, 0, sizeof(A))
#define FLC(A, x) memset(A, x, sizeof(A))
#define PB push_back

template<class T> void checkMax(T &a, T b){
    if (b > a) a = b;
}

typedef double DB;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;

const int N = int(1e2) + 9, M = 20;
char str[N][M+1]; int slen[N]; VI adj[N], radj[N];

int vis[N][N][M+M+1]; int dp[N][N][M+M+1];
int n, m;


int f(int i0, int i1, int j){

    int &z = dp[i0][i1][j+M], &v = vis[i0][i1][j+M];

    if (v == 3) return z;

    if (v == 1){
        v = 2;
        return -INF;
    }

    v = 1; z = j ? -INF : 0;

    if (j > 0){
        ECH(it, radj[i0]){
            int i00 = *it; bool ok = true;

            int up = min(j, slen[i00]); REP(k, up){
                if (str[i00][slen[i00]-1-k] != str[i1][slen[i1]-j+k]){
                    ok = false;
                    break;
                }
            }

            if (!ok) continue;
            checkMax(z, f(i00, i1, j-slen[i00]) + slen[i00]);
        }
    }
    else{

        j = -j;

        ECH(it, adj[i1]){
            int i11 = *it; bool ok = true;

            int up = min(j, slen[i11]); REP(k, up){
                if (str[i0][j-1-k] != str[i11][k]){
                    ok = false;
                    break;
                }
            }

            if (!ok) continue;
            checkMax(z, f(i0, i11, slen[i11]-j) + slen[i11]);
        }
    }

    if (z >= 0 && v == 2) z = INF;
    v = 3;


    //if (z >= 0)
    //cout << ")" << i0 << " " << i1 << " " << j << " " << v << " "<< z << endl;
    //cout << i0 << " " <<i1 << " " << j << ": " << z << " "<<v << endl;
    return z;
}

bool isPalindrome(int i0, int l, int r){
    int len = r-l;
    REP(i, len/2) if (str[i0][l+i] != str[i0][r-1-i]) return false;
    return true;
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d%d", &n, &m)){

        REP(i, n){
            scanf("%s", str[i]); adj[i].clear(), radj[i].clear();
            slen[i] = strlen(str[i]);
        }

        DO(m){
            int a, b; scanf("%d%d", &a, &b); --a, --b;
            adj[a].PB(b); radj[b].PB(a);
        }

        FLC(dp, -1); RST(vis); int z = 0; REP(i, n) REP(j, slen[i]+1){
            if (isPalindrome(i, 0, slen[i]-j) && f(i, i, j) >= 0) checkMax(z, f(i, i, j) + slen[i]);
            if (isPalindrome(i, j, slen[i]) && f(i, i, -j) >= 0) checkMax(z, f(i, i, -j) + slen[i]);
        }

        if (z >= INF) z = -1;
        printf("%d\n", z);
    }
}

Posted by xiaodao
Category: 日常