某岛

… : "…アッカリ～ン . .. . " .. .
October 2, 2014

2013 ACM/ICPC Asia Regional Hangzhou Onsite

http://acmicpc.info/archives/1636

Problem A. Lights Against Dudely

Brief description:

There are at most fifteen vulnerable rooms in the bank.

Analysis:

枚举 + 状态压缩 DP。

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

const int dx[] = {-1, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

const int NN = 15, N = 209;
char Map[N][N]; int id[N][N]; int dp[1<<NN];
int n, m, nn;

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

struct rec{
    int x, y, s;
    rec(int x = 0, int y = 0):x(x),y(y){
    }
    void init(int o = 0){
        s = _1(id[x][y]);
        REP(d, 2){
            int xx = x + dx[o+d], yy = y + dy[o+d];
            if (!inGrid(xx, yy)) continue;
            if (Map[xx][yy] == '.') s |= _1(id[xx][yy]);
            else{
                s = 0;
                return;
            }
        }
    }
} A[NN];

int f(int id, int off){

    REP(i, nn){
        if (i == id) A[i].init(off);
        else A[i].init();
    }

    FLC(dp, 0x3f); dp[0] = 0;
    REP(s, _1(nn)){
        REP(i, nn) if (!_1(s, i)){
            int ss = s | A[i].s;
            checkMin(dp[ss], dp[s] + 1);
        }
    }
    return dp[_U(nn)];
}


int main(){

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

    while (RD(n, m)){
        REP(i, n) RS(Map[i]);
        nn = 0; REP_2(i, j, n, m) if (Map[i][j] == '.'){
            id[i][j] = nn;
            A[nn++] = rec(i, j);
        }

        if (!nn){
            OT(0);
            continue;
        }

        int res = INF; REP(i, nn) REP(d, 4){
            checkMin(res, f(i, d));
        }
        if (res == INF) res = -1;
        OT(res);
    }
}

Problem F. Infinite Go

Brief description:

题目意思就是给你下围棋的位置，黑子先下，黑白子交替的下，途中会出现棋子被吃掉的情况，让你输出最后黑色和白色的棋子各有多少个。
棋子被吃掉的条件是：上下左右四个方向相邻的同色的棋子所形成的的联通快的边缘没有空位（目）。空位只需要考虑上下左右四个方向。

Analysis:

并查集维护棋子所在的联通块，f[] 维护 “目”。
攘外必先安内，当加入新棋子时，应严格按照，先维护自身目数，再处理吃对面的情况，再处理合并，再考虑是否自身被吃四个步骤。。。
（先出基本装、Gank 一波，再和队友抱团。。）。。。


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

const int N = int(1e4) + 9;
map<PII, int> B; // Board
int x[N], y[N], f[N], p[N];
int n, n1, n2;

int Find(int x){
    return p[x] == x ? x : p[x] = Find(p[x]);
}

void Union(int x, int y){
    x = Find(x), y = Find(y); if (x == y) return;
    p[x] = y; f[y] += f[x];
}

void del(int n){
    if (n&1) --n2; else --n1; B.erase(MP(x[n], y[n]));
    REP(d, 4){
        int xx = x[n] + dx[d], yy = y[n] + dy[d];
        if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;
        int m = B[MP(xx, yy)];
        if ((n^m)&1) ++f[Find(m)]; else del(m);
    }
}

void print(){
    FOR_1(a, 1, 10){
        FOR_1(b, 1, 10){
            if (!CTN(B, MP(a, b))) putchar('.');
            else putchar(B[MP(a, b)]&1 ? '&' : '*');
        }
        puts("");
    }
    puts("");
}

int main(){

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

    Rush{
        CLR(B), n = n1 = n2 = 0; Rush{
            RD(x[n], y[n]); p[n] = B[MP(x[n], y[n])] = n; f[n] = 0;
            if (n&1) ++n2; else ++n1;

            REP(d, 4){
                int xx = x[n] + dx[d], yy = y[n] + dy[d];
                if (!xx || !yy || CTN(B, MP(xx, yy))) continue;
                ++f[n];
            }
            REP(d, 4){
                int xx = x[n] + dx[d], yy = y[n] + dy[d];
                if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;
                int m = Find(B[MP(xx, yy)]);
                --f[m]; if ((m^n)&1 && !f[m]) del(m);
            }
            REP(d, 4){
                int xx = x[n] + dx[d], yy = y[n] + dy[d];
                if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;
                int m = Find(B[MP(xx, yy)]);
                if (!((m^n)&1)) Union(m, n);
            }

            if (!f[Find(n)]) del(n);

            ++n;
        }
        printf("%d %d\n", n1, n2);
    }
}

Problem G. Ants

fork: https://www.shuizilong.com/house/archives/poj-3764-the-xor-longest-path/

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

Problem H. Rabbit Kingdom

Brief description:

给出 n 个数，有 m 个查询，每次查询询问区间 [L, R] 中最多有多少个数与区间中其他数都不互质。

Analysis:

离线 + 树状数组。（类似 Dquery）


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

const int N = int(2e5) + 9;
int n;

namespace BIT{
    typedef int intt;
    intt C[N], S;
    void Add(int x, int d){
        if (!x) return;
        for (;x<=n;x+=low_bit(x)) C[x] += d;
        S += d;
    }
    intt Sum(int x){
        intt res = 0; for (;x;x^=low_bit(x)) res += C[x];
        return res;
    }
    intt Sum(int l, int r){
        return Sum(r) - Sum(l-1);
    }
} using namespace BIT;

//最小素因子。。
const int PMAX = N;
VI P; bitset<PMAX> isC; int p[PMAX];
#define ii (i*P[j])
void sieve(){
    FOR(i, 2, PMAX){
        if (!isC[i]) P.PB(i),p[i]=i;
        for (int j=0;j<SZ(P)&&ii<PMAX;++j){
            isC[ii]=1; p[ii]=P[j]; if (!(i%P[j])) break;
        }
    }
}
#undef ii

int A[N], suc[N], prd[N], last[N];
VII qry[N], rls[N]; int res[N];

int main(){

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

    sieve();

    int q; while (RD(n, q)){

        RST(C); S = 0; REP_1(i, n) RD(A[i]), CLR(qry[i], rls[i]);

        REP(i, q){
            int l, r; RD(l, r);
            qry[r].PB(MP(l, i));
        }

        RST(last); REP_1(i, n){
            int x = A[i]; prd[i] = 0;
            while (x != 1){
                int px = p[x]; checkMax(prd[i], last[px]); last[px] = i;
                do x /= px; while (p[x] == px);
            }
        }

        FLC(last, 0x3f); DWN_1(i, n, 1){
            int x = A[i]; suc[i] = INF;
            while (x != 1){
                int px = p[x]; checkMin(suc[i], last[px]);
                last[px] = i;
                do x /= px; while (p[x] == px);
            }
        }

        REP_1(i, n) if (suc[i] == INF) suc[i] = 0;

        REP_1(i, n){

            Add(i, 1); A[i] = 1; int l = prd[i], r = suc[i];

            Add(l, -1);
            rls[r].PB(MP(i, -1));
            rls[r].PB(MP(l, 1));

            ECH(it, rls[i]){
                Add(it->fi, it->se);
            }

            ECH(it, qry[i]){
                int l = it->fi, id = it->se;
                res[id] = S - BIT::Sum(l-1);
            }

            //REP_1(i, n) cout << Sum(i, i) << " "; puts("");
        }
        //puts("");
        REP(i, q) OT(res[i]);
    }
}

Problem I. Gems Fight!

Brief description:

略。）

Analysis:

状态压缩 + 博弈 DP。

（主要是 The Gems collected are stored in a shared cooker.
如果没有这个条件。。状态将会有后效性。。只能搜？）


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

const int N = 21, M = 9;
int F[1<<N], S[1<<N], n, m, s0;

void init(){

    VVI I; REP(i, n){
        VI t; Rush t.PB(RD()-1);
        I.PB(t);
    }

    static int cnt[M]; REP(s, _1(n)){
        RST(cnt); REP(i, n) if (_1(s, i)) ECH(it, I[i]) ++cnt[*it];
        S[s] = 0; REP(i, m) S[s] += cnt[i] / s0;
    }

    FLC(F, -1);
}

int main(){

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

    while (RD(m,n,s0)){

        init(); FLC(F, 0x8f); F[_U(n)] = 0; DWN(s, _1(n), 1){
            REP(i, n) if (_1(s, i)){
                int ss = s ^ _1(i), d = S[s]-S[ss];
                if (d) checkMax(F[ss], F[s] + d);
                else checkMax(F[ss], -F[s]);
            }
        }

        OT(F[0]);
    }
}

Problem K. Candy Factory

Brief description:

略。）

Analysis:

网络流

建模 1：上下界最小费用流
S -> M -> C0 <-> C1 -> T
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2823256

建模 2：最小费用最大流
S -> M -> C0 -> C1 -> T
S ------> C2 -> C1 -> T
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2822981

Posted by xiaodao
Category: 线下比赛

« | »

  • Archives

    open all | close all