高效算法设计(八)

这篇博文的内容是接着《算法竞赛》第八章的习题
介绍了一些比较冷门的，也可能比较无聊，更多是考察抖机灵而非算法应用的题目

枚举组合分析

LA6286

int A[4];
int cur;

void init() {
    Set(A, 0);
    cur = 0;
}

void move(int step) {
    int id = abs(step);
    cur += step;
    printf(" %d", cur);
    A[id]--;
}

void move(int step, int cnt) {
    _for(i, 0, cnt) move(step);
}

void solve() {
    printf("0");

    int cnt3 = A[3] / 3;
    int n = A[3] % 3;

    if(n == 0) {
        move(3, cnt3);
        move(1);

        move(-3, cnt3);
        move(1);

        move(3, cnt3);
    }
    if(n == 1) {
        move(3, cnt3 + 1);
        move(-2);

        move(-3, cnt3);
        move(1);

        move(3, cnt3);
        move(2);
    }
    if(n == 2) {
        move(3, cnt3 + 1);
        move(-1);

        move(-3, cnt3);
        move(-1);

        move(3, cnt3 + 1);
    }


    move(1, A[1] - 1);

    int cnt2 = A[2] / 2, n2 = A[2] % 2;

    if(n2 == 0) {
        move(2, cnt2);
        move(1);
        move(-2, cnt2);
    }
    if(n2 == 1) {
        move(2, cnt2 + 1);
        move(-1);
        move(-2, cnt2);
    }

    puts("");
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    while(scanf("%d", &T) == 1) {
        while (T--) {
            init();
            scanf("%d%d%d", &A[1], &A[2], &A[3]);
            solve();
        }
    }
}

枚举的编程技巧

LA6401

const int maxn = 500 + 5;
const int inf = 0x3f;

int a, b, m, n;
int d[maxn][maxn];
int dep[maxn];
llong ans, v, s;

void init() {
    ans = 0;
}

void initdep() {
    Set(dep, inf);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d%d%d", &a, &b, &m, &n) == 4) {
        init();

        _for(x, 0, m) _for(y, 0, n) scanf("%d", &d[x][y]);

        if(b > a) swap(a, b);
        // always a >= b

        _for(x, 0, m) _rep(y, 0, n) {
            initdep();

            _for(xx, x, m) {
                int aa = xx - x + 1;
                if(aa > a) break;

                // dep[y] = min(dep[y], d[xx][y]);
                // debug(dep[y]);
                _for(yy, y, n) {
                    int bb = yy - y + 1;
                    if(bb > a || min(bb, aa) > b) break;

                    // then we solve the problem
                    dep[yy] = min(dep[yy], d[xx][yy]);
                    if(yy) dep[yy] = min(dep[yy - 1], dep[yy]);

                    s = aa * bb * 1LL;
                    v = aa * bb * dep[yy] * 1LL;

                    int rem = (v % (m * n - s) == 0) ? 1 : 0;
                    ans = max(ans, 1LL * (dep[yy] + (v / (m * n - s)) - rem) * s);
                }
            }
        }
        printf("%lld\n", ans);
    }
}

贪心算法处理阶段决策

思想: 舍弃的值最少

LA3660

llong solve(llong n, llong m, llong cntn, llong cnts, llong cntw, llong cnte) {
    llong ans = 0;
    if(cnts > cntn) swap(cnts, cntn);
    if(cnte > cntw) swap(cnte, cntw);

    if(cntn) {
        ans += n * m;
        n--;
        cntn -= cnts;

        if(cntn == 0) ans += n * m * (2 * cnts - 1);
        else {
            ans += n * m * 2 * cnts;
            cntn--;
        }

        cnts = 0;
    }

    if(cntw) {
        cntw -= cnte;
        if(cntw == 0) cnte = cnte * 2 - 1;
        else {
            cnte = cnte * 2;
            cntw--;
        }

        while (m + (m - 1) * cnte <= n && cntn) {
            ans += n * m;
            cntn--;
            n--;
        }

        ans += n * m;
        m--;

        ans += n * m * cnte;
        cnte = 0;
    }

    while (n * m > 0 && cntw + cntn > 0) {
        ans += n * m;
        if((n > m && cntn) || cntw == 0) {
            cntn--;
            n--;
        }
        else {
            cntw--;
            m--;
        }
    }
    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    llong n, m, cntn, cnts, cntw, cnte;
    int kase = 0;

    while (scanf("%lld%lld", &n, &m) && n && m) {
        scanf("%lld%lld%lld%lld", &cntn, &cnts, &cntw, &cnte);
        // then solve the problem

        llong res = max(solve(n, m, cntn, cnts, cntw, cnte), solve(m, n, cnte, cntw, cntn, cnts));
        printf("Case %d: %lld\n", ++kase, res);
    }
}

set优化贪心

LA4977

const int maxn = 1000000 + 5;
int last[maxn], ans[maxn];
int rain[maxn];
int n, m;

void init() {
    Set(last, 0);
    Set(ans, 0);
    Set(rain, 0);
}

bool solve() {
    set<int> noRain;
    bool ok = true;

    _rep(i, 1, m) {
        if(rain[i] == 0) {
            noRain.insert(i);
            continue;
        }

        ans[i] = -1;
        auto day = noRain.lower_bound(last[rain[i]]);

        if(day == noRain.end()) {
            ok = false;
            break;
        }

        ans[*day] = rain[i];
        last[rain[i]] = i;
        noRain.erase(*day);
    }
    return ok;
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        init();
        scanf("%d%d", &n, &m);
        _rep(i, 1, m) scanf("%d", &rain[i]);

        // then solve the problem
        bool ok = solve();
        if(!ok) printf("NO\n");
        else {
            printf("YES\n");
            bool first = 1;

            _rep(i, 1, m) {
                if(ans[i] == -1) continue;

                if(first) first = 0;
                else printf(" ");

                printf("%d", ans[i]);
            }
            puts("");
        }
    }
}

扫描法

一般的思路, 按照一定的条件往前走, 看最远能走到哪里

POJ2364

const int maxn = 1000 + 5;
int lh, rh, lhi, rhi;
int l, r;
int lx[maxn], rx[maxn];

int leftx, rightx;

void init() {
    Set(lx, 0);
    Set(rx, 0);
    lh = rh = 0;
}

int solve() {
    if(lh == rh) {
        int lt = 0, rt = 0;
        for(int i = l, h = lx[l]; i > lhi; i--) {
            lt += h;
            h = max(h, lx[i - 1]);
        }

        for(int i = r, h = rx[r]; i > rhi; i--) {
            rt += h;
            h = max(h, rx[i - 1]);
        }

        return (lhi + rhi + 1) * lh * 2 + min(lt, rt) * 2 * 2;
    }

    int M = min(lh, rh), lgi = 0, rgi = 0;
    // water can reach at most x = lgi or rgi
    // the first higher than M
    // [lgi, rgi] is the rectangle area

    while (lgi < l && lx[lgi] < M) lgi++;
    while (rgi < r && rx[rgi] < M) rgi++;
    // [lhi, rgi] is the rectangle area
    // [lgi, rhi] is the rectangle area

    int lt = 0, rt = 0;
    int t = 0;
    if(lh < rh) {
        for(int i = l, h = lx[l]; i > lhi; i--)  {
            lt += h;
            h = max(h, lx[i - 1]);
        }
        // right we may not reach rhi, just fill at rgi

        for(int i = rgi, h = M; rx[i] <= M; i++) {
            rt += h;
            h = max(h, rx[i + 1]);
        }

        t = lt > rt ? (lt + rt) : 2 * lt;
    }

    if(lh > rh) {
        for(int i = r, h = rx[r]; i > rhi; i--) {
            rt += h;
            h = max(h, rx[i - 1]);
        }

        for(int i = lgi, h = M; lx[i] <= M; i++) {
            lt += h;
            h = max(h, lx[i + 1]);
        }

        t = rt > lt ? (lt + rt) : 2 * rt;
    }

    return t * 2 + (lgi + rgi + 1) * 2 * M;
}

int main() {
    freopen("input.txt", "r", stdin);

    while (cin >> leftx >> rightx && leftx && rightx) {
        init();

        l = (-leftx) / 2, r = rightx / 2;

        for(int i = leftx; i < 0; i += 2) {
            int ii = (-i) / 2;
            cin >> lx[ii];

            if(lx[ii] >= lh) lh = lx[ii], lhi = ii;
        }

        for(int i = 1; i <= rightx; i += 2) {
            int ii = i / 2;
            cin >> rx[ii];

            if(rx[ii] > rh) rh = rx[ii], rhi = ii;
        }

        // then solve the problem
        printf("%d\n", solve());
    }
}

反向图

UVA11175

const int maxn = 300 + 5;
int n = -1, k = -1;
int T;

vector<int> G[maxn], invG[maxn];
int indeg[maxn];


bool check(int n) {
    _for(u, 0, n) {
        fill_n(indeg, n, 0);

        for(auto s : invG[u]) {
            for(auto x : G[s]) indeg[x]++;
        }

        _for(v, 0, n) {
            if(v == u) continue;
            if(indeg[v] == 0 || indeg[v] == invG[u].size()) continue;
            return false;
        }
    }
    return true;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &T);

    _rep(kase, 1, T) {
        scanf("%d%d", &n, &k);
        assert(n != -1 && k != -1);
        _for(i, 0, n) G[i].clear(), invG[i].clear();

        _for(i, 0, k) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            invG[v].push_back(u);
        }

        // then solve the problem

        bool ok = check(n);

        printf("Case #%d: %s\n", kase, (ok ? "Yes" : "No"));
    }
}

随机算法优化枚举

UVA12559

const double pi = acos(-1);

class Circle {
public:
    int r, x, y;
    Circle(int _r = 0, int _x = 0, int _y = 0) : r(_r), x(_x), y(_y) {}

    bool operator< (const Circle& rhs) const {
        if(r != rhs.r) return r < rhs.r;
        if(x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
};

ostream& operator<< (ostream& os, const Circle& c) {
    char buf[128];
    sprintf(buf, " (%d,%d,%d)", c.r, c.x, c.y);
    return os << buf;
}

bool inRange(int x, int l, int r) {
    if(l > r) return inRange(x, r, l);
    return l <= x && x <= r;
}

vector<string> lines;
vector<Circle> ans;

void init() {
    lines.clear();
    ans.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    _rep(kase, 1, T) {
        init();

        int w, h;
        scanf("%d%d", &w, &h);

        lines.resize(h);
        _for(i, 0, h) cin >> lines[i];

        // then we solve the problem
        _rep(r, 5, 50) _rep(x, r, w - r) _rep(y, r, h - r) {
            int tot = 0, black = 0;

            // then enumerate
            _for(i, 0, 100) {
                double deg = 2 * pi * (rand() / (RAND_MAX + 1.0));
                int cx = (int)(x + r * cos(deg) + 0.5), cy = (int)(y + r * sin(deg) + 0.5);

                if(inRange(cx, 0, w - 1) && inRange(cy, 0, h - 1) && lines[cy][cx] == '1') black++;
                tot++;

                if(tot > 10 && black * 2 < tot) break;
            }

            if(black / (double) tot > 0.8) ans.push_back(Circle(r, x, y));
        }

        printf("Case %d: ", kase);
        cout << ans.size();
        _for(i, 0, ans.size()) cout << ans[i];
        cout << endl;
    }
}

杂题

LA6043

const int maxn = 1000000 + 5;
int L, P;

struct Node {
    int pre, nxt;
};
Node nodes[maxn];

int twist[maxn];
int level[maxn];

void del(int x) {
    level[x] = 0;
    nodes[nodes[x].pre].nxt = nodes[x].nxt;
    nodes[nodes[x].nxt].pre = nodes[x].pre;
}

void init() {
    Set(twist, 0);
    Set(level, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    _rep(kase, 1, T) {
        init();
        scanf("%d%d", &L, &P);

        _for(i, 0, L) {
            nodes[i].pre = i - 1;
            nodes[i].nxt = i + 1;
        }
        nodes[0].pre = L - 1;
        nodes[L - 1].nxt = 0;

        _rep(i, 1, P) {
            int u, v;
            scanf("%d%d", &u, &v);
            // (u, v)
            twist[u] = v;
            twist[v] = u;

            level[u] = 1;
            level[v] = -1;
        }

        // then we solve the problem
        _for(i, 0, L) if(level[i] == 0) del(i);

        int idx = 0;
        while (P) {
            bool untie = false;
            while (level[idx] == 0) idx++;

            for(int i = nodes[idx].nxt; i != idx && untie == false; i = nodes[i].nxt) {
                int u = i, v = nodes[i].nxt;

                if(level[u] == level[v] && (nodes[twist[u]].nxt == twist[v] || nodes[twist[v]].nxt == twist[u])) {
                    del(u); del(v);
                    del(twist[u]); del(twist[v]);

                    P -= 2;
                    untie = true;
                }
                else if(twist[u] == v || twist[v] == u) {
                    del(u);
                    del(v);

                    P -= 1;
                    untie = true;
                }
            }

            if(untie == false) break;
        }

        printf("Case #%d: ", kase);
        if(P) printf("NO\n");
        else printf("YES\n");
    }

}