算法设计基础（二）

这部分内容对贪心策略，算法优化等方面
做了一些阐述

区间贪心：二分集合

贪心算法经常应用数学归纳法的思想
在处理类二分图问题的时候，也就是说如果有一个相邻二元组
$(i, i+1)$，它们必须满足某种约束条件，此时对集合进行划分是一种策略

比如 $n$ 个人围成一圈，相邻两人不能拥有同样的物品
物品数没有限制，不相邻的人可以拥有同样的物品，问物品要准备多少？

UVA1335

const int maxn = 100000 + 10;
int n, a[maxn];
int L[maxn], R[maxn];

bool check(int val) {
    int x = a[1], y = val - a[1];
    L[1] = x, R[1] = 0;

    _rep(i, 2, n) {
        if (i % 2 == 0) {
            L[i] = min(x - L[i-1], a[i]);
            R[i] = a[i] - L[i];
        }
        else {
            R[i] = min(y - R[i-1], a[i]);
            L[i] = a[i] - R[i];
        }
    }
    return L[n] == 0;
}

void solve() {
    int l = 0, r = 0;
    _rep(i, 1, n) chmax(l, a[i] + a[i+1]);

    if (n % 2) {
        _rep(i, 1, n) chmax(r, a[i]*3);

        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
    }
    printf("%d\n", l);
}

void init() {
    memset(L, 0, sizeof(L));
    memset(R, 0, sizeof(R));
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();
        _rep(i, 1, n) scanf("%d", &a[i]);

        // then solve
        if (n == 1) {
            printf("%d\n", a[1]);
            continue;
        }

        a[n+1] = a[1];
        // solve()
        solve();
    }
}

floyd判圈算法

UVA11549

const int maxn = 100 + 10;
int n, x;
int buf[maxn];

int Next(int n, int x) {
    if (!x) return 0;
    ll x2 = 1ll * x * x;

    int m = 0;
    while (x2 > 0) { buf[m++] = x2 % 10, x2 /= 10; }
    chmin(n, m);

    int ans = 0;
    _for(i, 0, n) ans = ans * 10 + buf[--m];
    return ans;
}

void solve() {
    int ans = x;
    int x1 = x, x2 = x;

    for(;;) {
        x1 = Next(n, x1);
        x2 = Next(n, x2); chmax(ans, x2);
        x2 = Next(n, x2); chmax(ans, x2);
        if (x1 == x2) break;
    }

    printf("%d\n", ans);
}

void init() {
    //
}

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

    while (kase--) {
        scanf("%d%d", &n, &x);
        init();

        // then solve
        solve();
    }
}

归并排序求逆序对

POJ2299

const int maxn = 500000 + 10;
int a[maxn], b[maxn], n;
ll ans;

void merge(int l, int mid, int r) {
    if (l == r) return;
    if (l + 1 == r) {
        if (a[l] > a[r]) {
            ans++;
            swap(a[l], a[r]);
        }
        return;
    }

    merge(l, (l+mid)>>1, mid);
    merge(mid+1, (mid+1+r)>>1, r);

    int i = l, j = mid + 1;
    _rep(k, l, r) {
        if (j > r || (i <= mid && a[i] <= a[j])) b[k] = a[i++];
        else {
            ans += 1ll * (mid - i + 1);
            b[k] = a[j++];
        }
    }
    _rep(k, l, r) a[k] = b[k];
}

void solve() {
    _rep(i, 1, n) scanf("%d", &a[i]);
    ans = 0;
    merge(1, (1+n)>>1, n);
    printf("%lld\n", ans);
}

void init() {
    //
    ans = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();
        solve();
    }
}

扫描线算法

UVA1398

const int maxn = 100000 + 10;
const int LCM = 2520;
const int inf = 1e9;
int n, w, h;

void update(int x, int a, int w, double &l, double &r) {
    if (a == 0) {
        if (x <= 0 || x >= w) r = l-1;
    }
    else if (a > 0) {
        chmax(l, -(double)x*LCM / a);
        chmin(r, (double)(w-x)*LCM / a);
    }
    else {
        chmax(l, (double)(w-x)*LCM / a);
        chmin(r, -(double)(x)*LCM / a);
    }
}

int m = 0;

class Eve {
public:
    double x;
    int tp;
    Eve() = default;
    Eve(double x, int tp) : x(x), tp(tp) {}

    bool operator< (const Eve& rhs) const {
        return x < rhs.x || (x == rhs.x && tp > rhs.tp);
    }
} eve[maxn << 1];

void getdata() {
    _rep(i, 1, n) {
        int x, y, a, b;
        scanf("%d%d%d%d", &x, &y, &a, &b);

        // 0 < x+at < w, 0 < y+bt < h
        double l = 0, r = inf;
        update(x, a, w, l, r);
        update(y, b, h, l, r);

        if (r > l) {
            eve[++m] = Eve(l, 0);
            eve[++m] = Eve(r, 1);
        }
    }
}

void solve() {
    // eve [1, m]
    sort(eve+1, eve+1+m);
    int ans = 0, cnt = 0;
    _rep(i, 1, m) {
        if (eve[i].tp == 0) chmax(ans, ++cnt);
        else cnt--;
    }
    printf("%d\n", ans);
}

void init() {
    //
    m = 0;
}

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

    while (kase--) {
        init();

        // getdata
        scanf("%d%d%d", &w, &h, &n);
        getdata();
        solve();
    }
}

单调栈优化

• 单调队列（单调栈）问题三部曲
  • 判断队头元素是否合法，不合法，队头元素出队列
  • 如果队列不空，取队头元素，作为 $f(i-1)$ 阶段的决策
    并且用这个队头元素，来更新 $f(i)$ 阶段
  • 维护单调性，将 $i$ 入单调队列

HDU1505

const int maxn = 1000 + 10;
int mat[maxn][maxn], m, n;

int up[maxn][maxn];

void prework() {
    _rep(i, 1, m) _rep(j, 1, n) {
        if (mat[i][j] == 0) up[i][j] = up[i-1][j] + 1;
        else up[i][j] = 0;
    }
}

int stk[maxn], le[maxn], ri[maxn];
void dp(ll &ans) {
    _rep(i, 1, m) {
        memset(stk, 0, sizeof(stk));
        memset(le, 0, sizeof(le));
        memset(ri, 0, sizeof(ri));

        int top = 0;
        _rep(j, 1, n) {
            while (top && up[i][stk[top]] >= up[i][j]) top--;
            if (top == 0) le[j] = 1;
            else le[j] = stk[top] + 1;
            stk[++top] = j;
        }

        top = 0;
        _forDown(j, n, 1) {
            while (top && up[i][stk[top]] >= up[i][j]) top--;
            if (top == 0) ri[j] = n + 1;
            else ri[j] = stk[top];
            stk[++top] = j;
        }

        _rep(j, 1, n) chmax(ans, 1ll * up[i][j] * (ri[j] - le[j]));
    }
}

void init() {
    memset(up, 0, sizeof(up));
}

void dbg() {
    _rep(i, 1, m) {
        _rep(j, 1, n) printf("%d ", mat[i][j]);
        puts("");
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;
    while (kase--) {
        scanf("%d%d", &m, &n);
        _rep(i, 1, m) _rep(j, 1, n) {
            char ch = getchar();
            while (ch != 'F' && ch != 'R') ch = getchar();
            mat[i][j] = ch == 'F' ? 0 : 1;
        }
        // dbg()

        // prework
        prework();
        ll ans = 0;
        dp(ans);
        printf("%lld\n", 3*ans);
    }
}

二维问题中的集合思维

HDU3299

const int maxn = 100 + 10;
int n, y[maxn];
int m;

class A {
public:
    int x, y;
    A() = default;
    A(int x, int y) : x(x), y(y) {}

    bool operator< (const A& rhs) const {
        return x < rhs.x;
    }
} a[maxn];

int le[maxn], on[maxn], on2[maxn];

int solve() {
    sort(a, a+n);
    sort(y, y+n);
    m = unique(y, y+n) - y;

    if (m <= 2) return n;

    int ans = 0;

    _for(p, 0, m) _for(q, p+1, m) {
        int ymin = y[p], ymax = y[q];

        int k = 0;
        _for(i, 0, n) {
            if (i == 0 || a[i-1].x != a[i].x) {
                k++;
                on[k] = on2[k] = 0;
                le[k] = k == 0 ? 0 : le[k-1] + on2[k-1] - on[k-1];
            }
            if (ymin < a[i].y && a[i].y < ymax) on[k]++;
            if (ymin <= a[i].y && a[i].y <= ymax) on2[k]++;
        }

        if (k <= 2) return n;

        int maxv = 0;
        _rep(j, 1, k) {
            chmax(ans, le[j] + on2[j] + maxv);
            chmax(maxv, on[j] - le[j]);
        }
    }

    return ans;
}

void init() {
    //
    memset(on, 0, sizeof(on));
    memset(le, 0, sizeof(le));
    memset(on2, 0, sizeof(on2));
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d", &n) == 1 && n) {
        init();
        printf("Case %d: ", ++kase);
        // get data

        _for(i, 0, n) scanf("%d%d", &a[i].x, &a[i].y), y[i] = a[i].y;

        // then prework and solve
        int ans = solve();
        printf("%d\n", ans);
    }
}

高维前缀和

UVA10755

const ll inf = 1ll<<60;
const int maxn = 20 + 10;
ll S[maxn][maxn][maxn];
int a, b, c;

inline void expand(int i, int &b0, int &b1, int &b2) {
    b0 = i&1; i >>= 1;
    b1 = i&1; i >>= 1;
    b2 = i&1;
}

inline int sgn(int b0, int b1, int b2) {
    return (b0 + b1 + b2) % 2 == 1 ? 1 : -1;
}

ll sum(int x1, int x2, int y1, int y2, int z1, int z2) {
    int dx = x2-x1+1, dy = y2-y1+1, dz = z2-z1+1;

    ll ans = 0;
    _rep(i, 0, 7) {
        int b0, b1, b2;
        expand(i, b0, b1, b2);
        ans -= S[x2-b0*dx][y2-b1*dy][z2-b2*dz] * sgn(b0, b1, b2);
    }
    return ans;
}

void prework() {
    _rep(x, 1, a) _rep(y, 1, b) _rep(z, 1, c) _rep(i, 1, 7) {
        int b0, b1, b2;
        expand(i, b0, b1, b2);
        S[x][y][z] += S[x-b0][y-b1][z-b2] * sgn(b0, b1, b2);
    }
}

void solve() {
    ll ans = -inf;
    _rep(x1, 1, a) _rep(x2, x1, a) _rep(y1, 1, b) _rep(y2, y1, b) {
        ll M = 0;
        _rep(z, 1, c) {
            ll s = sum(x1, x2, y1, y2, 1, z);
            chmax(ans, s - M);
            chmin(M, s);
        }
    }
    printf("%lld\n", ans);
}

void init() {
    memset(S, 0, sizeof(S));
}

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

    while (kase--) {
        scanf("%d%d%d", &a, &b, &c);
        init();

        // get data
        _rep(x, 1, a) _rep(y, 1, b) _rep(z, 1, c) scanf("%lld", &S[x][y][z]);

        // then prework and solve
        prework();
        solve();
        if (kase) printf("\n");
    }
}

中途相遇法

ZOJ2469

const int maxn = 24 + 1;
const int maxl = 1000 + 10;
int a[maxn], n;

map<int, int> tb;

inline int bitcnt(int x) {
    return x == 0 ? 0 : bitcnt(x>>1) + (x&1);
}

void solve() {
    int n1 = n >> 1, n2 = n - n1;
    // first set
    _for(i, 0, 1<<n1) {
        int x = 0;
        _for(j, 0, n1) if (i & (1<<j)) x ^= a[j];

        if (!tb.count(x) || bitcnt(tb[x]) < bitcnt(i)) tb[x] = i;
    }

    // check second set
    int ans = 0;
    _for(i, 0, 1<<n2) {
        int x = 0;
        _for(j, 0, n2) if (i & (1<<j)) x ^= a[n1+j];

        if (tb.count(x) && bitcnt(ans) < bitcnt(i) + bitcnt(tb[x])) ans = tb[x] ^ (i<<n1);
    }

    printf("%d\n", bitcnt(ans));
    _for(i, 0, n) if (ans & (1<<i)) printf("%d ", i+1);
    printf("\n");
}

void init() {
    memset(a, 0, sizeof(a));
    tb.clear();
}

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

    while (scanf("%d", &n) == 1 && n) {
        char str[maxl];
        init();

        // get data
        _for(i, 0, n) {
            scanf("%s", str);
            _for(j, 0, strlen(str)) a[i] ^= (1<<(str[j] - 'A'));
        }

        // then solve
        solve();
    }
}