Page 6 of 29« First...2345678910...1827...Last »

BZOJ 1927. [Sdoi2010]星际竞速

http://www.lydsy.com/JudgeOnline/problem.php?id=1927
http://hi.baidu.com/lydrainbowcat/item/96ade2bf64c221f363388eb9

Brief description:

略。)

Analysis:

费用流,最小路径覆盖。)


//}/* .................................................................................................................................. */

int n, m;

namespace MinCostMaxFlow{

    const int N = 2048, M = 2*N*N + 9;
    const int NN = 2047; // cover_bit(N) - 1

    int D[N], hd[N], suc[M], to[M], cap[M], cst[M];
    int n, m, s, t; LL nesf, flow, cost;

    int new_node(){
        hd[n] = 0;
        return n++;
    }

    inline void add_edge(int x, int y, int c, int w = 0){
        suc[m] = hd[x], to[m] = y, cap[m] = c, cst[m] =  w, hd[x] = m++;
        suc[m] = hd[y], to[m] = x, cap[m] = 0, cst[m] = -w, hd[y] = m++;
        //nesf += w;
    }

    inline void add_edgee(int x, int y, int c, int w = 0){
        add_edge(x, y, c, w);
        add_edge(y, x, c, w);
    }

    int Q[NN+1], pre[N], cz, op; bool inQ[N];

#define v to[i]
#define c cap[i]
#define f cap[i^1]
#define w cst[i]

    bool spfa(){
        fill(inQ, inQ+n, 0), fill(D, D+n, INF);
        cz = 0, op = 1; D[Q[cz] = s] = 0; while (cz != op){
            int u = Q[cz++]; inQ[u] = 0; cz &= NN;
            REP_G(i, u) if (c && checkMin(D[v], D[u]+w)){
                pre[v] = i; if (!inQ[v]) Q[op++] = v, inQ[v] = 1, op &= NN;
            }
        }
        return D[t] != INF;
    }

#undef v

    void add_path(){
        int d = INF; int u, v = t; do{
            int i = pre[v]; checkMin(d, c);
            u = to[i^1], v = u;
        } while (u != s);

        flow += d; u, v = t; do{
            int i = pre[v]; f += d, c -= d; cost += d*w;
            u = to[i^1], v = u;
        } while (u != s);
    }

    pair<LL, LL> Run(){
        cost = 0, flow = 0; while (spfa()) add_path();
        return MP(cost, flow);
    }


#undef c
#undef f
#undef w

    void Init(){

        RST(hd); m = 2; RD(::n, ::m); s = 0, t = 2*::n+1; n = t+1;

        REP_1(i, ::n){
            add_edge(s, ::n+i, 1, RD());
            add_edge(s, i, 1, 0);
            add_edge(::n+i, t, 1, 0);
        }

        DO(::m){
            int x, y, w; RD(x, y, w); if (x > y) swap(x, y);
            add_edge(x, y+::n, 1, w);
        }
    }
} //using namespace MinCostMaxFlow;

int main(){

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


    MinCostMaxFlow::Init();
    cout << MinCostMaxFlow::Run().fi << endl;
}

2014 ACM/ICPC Asia Mudanjiang Regional Contest Onsite

Problem B. Domination

Brief description:

给定一棵无根树 T 。定义以 T 上一对点 (a, b) 为“复根”的树的高度 h(a, b) = max min(dist(x, a), dist(x, b)), for all x on T 。
现求 H(T) = min h(a, b), for all (a, b) | a != b。

Analysis:

结论:两个复根一定在树的直径上。

先求直径,并求出直径上每个点为根的树所到达的最远距离。
二分答案,每次先贪心的将复根尽可能向中间移动。。。然后在判断中间的那些点是否也合法。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2882177

Problem D. Domination

Brief description:

略。)

Analysis:

似乎是某场 CF 的 B。

f[i][j][k]: 表示当前有 i 行、j 列没有覆盖,且一共还有 k 个格子没填时的期望。
转移分四种情况讨论即可。(似乎这个状态表示不是特别好。。这样做必须要使用 long double。。)

//}/* .................................................................................................................................. */

const int N = 51;
long double f[N][N][N*N];
int n, m;

int main(){

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

    Rush{
        RD(n, m); RST(f);

#define u f[i][j][k]
        REP_2(i, j, n+1, m+1){
            if (!i && !j) continue;
            REP_1(k, n*m){
                u = (k-i*m-j*n+i*j) * f[i][j][k-1];
                if (i && j) u += i*j * f[i-1][j-1][k-1];
                if (i) u += i*(m-j) * f[i-1][j][k-1];
                if (j) u += j*(n-i) * f[i][j-1][k-1];
                u /= k, ++u;
            }
        }

        OT((DB)f[n][m][n*m]);
    }
}

Problem F. Fiber-optic Network

Brief description:

给定一颗 50 个结点的无向树,每个结点可以填 [Li, Ri] 之间的数。
要求相邻结点填的数 co-prime。问一共有多少种方案。(要求输出所有方案里每个结点所填的数字和)

Analysis:

树 DP,容斥原理转移。

f1[u][val]:表示 u 点填 val 时的方案数。。。
用容斥原理进行转移。。。

考虑 (u, v) 的转移,设 f2[v][val] 为 v 结点所有以 val 为倍数的答案。我们预处理出 mu 函数,以及 val 所有的 mu 值不为 0 的倍数。。
那么就是:

    ECH(it, adj[u]) if (v != p){
        FOR_1(i, ll[u], rr[u]){
            Int t = 0; ECH(d, dd[i]) t += Int(mu[*d])*f2[v][*d];            
            f1[u][i] *= t;
        }
    }

dfs 两次。。
第一次可以得到根结点的答案。。
为了得到其它结点的答案。。需要将父亲结点的结果除去以某个 v 作为孩子时的方案数作为一个新的孩子。。。参与转移。。
得用一些麻烦的方法避免除法。。。TLE...

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2844775

改进:
按照边进行 DP。。。
f1[i][val]:i 表示 (p, u) 这条边。。。
。。u 点填 val 时的方案数。。。可以避免除法。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2845448

Problem K.

Brief description:

...

Analysis:

贪心。。digit 总是越靠前越好。。
。先在前面补齐必要的 digit。。。然后贪心的将最前的非法 * 和最后的 digit 交换。

//}/* .................................................................................................................................. */

string s;
int n;

int main(){

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

    Rush{
        cin >> s; n = s.size();
        int a = 0; REP(i, n) if (s[i] == '*') ++a;
        int b = n - a, bb = 0, z = 0; z += max(0, a-(b-1)); bb = z;
        REP(i, n) if (s[i] == '*'){
            if (bb < 2) ++bb, ++z;
            else --bb;
        }
        else ++bb;
        cout << z << endl;
    }
}

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2845839

Page 6 of 29« First...2345678910...1827...Last »