高效算法设计(七)

本节内容
对一些序列的问题进行归纳总结

中途相遇法

这种方法有点类似数学中的夹逼准则

typedef vector<int>::iterator vii;
const int maxn = 5000 + 10;

vector<int> H[maxn], L[maxn];
int N[maxn];
int n;

void init() {
    _for(i, 0, maxn) {
        H[i].clear();
        L[i].clear();
    }
    Set(N, 0);
}

bool find1(int p) {
    _for(i, 0, H[p].size()) {
        int q = H[p][i];

        vii rit = upper_bound(L[p].begin(), L[p].end(), q);
        if(rit == L[p].end()) continue;

        int r = *rit;

        vii sit = upper_bound(H[p].begin(), H[p].end(), r);
        while (sit != H[p].end()) {
            int s = *sit;

            if(binary_search(L[q].begin(), L[q].end(), s)) return true;

            sit++;
        }
    }
    return false;
}

bool find2(int p) {
    _for(i, 0, L[p].size()) {
        int q = L[p][i];

        vii rit = upper_bound(H[p].begin(), H[p].end(), q);
        if(rit == H[p].end()) continue;

        int r = *rit;

        vii sit = upper_bound(L[p].begin(), L[p].end(), r);
        while (sit != L[p].end()) {
            int s = *sit;

            if(binary_search(H[q].begin(), H[q].end(), s)) return true;

            sit++;
        }
    }
    return false;
}

bool solve() {
    _for(i, 0, n) if(find1(i) || find2(i)) return true;
    return false;
}

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

    while (T--) {
        init();
        scanf("%d", &n);
        _for(i, 0, n) scanf("%d", &N[i]);

        _for(i, 0, n) _for(j, i + 1, n) {
            if(N[j] > N[i]) H[i].push_back(j);
            else if(N[j] < N[i]) L[i].push_back(j);
        }

        if(solve()) printf("YES\n");
        else printf("NO\n");
    }
}

连续的几个数, 连续的子区间最小

这一系列的问题, 可以用滑动窗口解决
UVA11536

UVA11536

滑动窗口中可能会出现: 滑动窗口的长度不固定的情况，这时候注意

1) win在[L, ...]中向右滑动
win不一定会真正删除A[L]处的元素

2) 只有A[L]中的数在win中出现的次数为1的时候
窗口从L中滑走，win才算是彻底删除了A[L]

3) 我们需要用map<int, int>记录每个值在窗口中出现的次数

4) 滑动窗口和区间扩张相结合的模版

for(int L = 0, R = 0; L < N; L++) {
    if(R >= N) break;
    while (win中没有选够点) {
        ins(R, win);
        R++;
        if(R >= N) break;
    }

    [L, R]构成了新的滑动窗口
    滑动窗口是我们需要的值


    if(win选够点了)
        滑动窗口能否优化呢?
        滑动窗口最左边的A[L]元素有没有冗余？A[L]出现次数可能大于1
        或者是, 滑动窗口并不包含A[L], A[L]我们不需要

        ans = min(ans, R - L + 1);

    slide L, del(L, win)    
    R = max(L, R);
}

const int maxn = 1000000 + 10;
int n, m, k;
int x[maxn];

void cal() {
    _for(i, 0, n) {
        if(i < 3) x[i] = i + 1;
        else x[i] = (x[i - 3] + x[i - 2] + x[i - 1]) % m + 1;
    }
}

bool valid(int x) {
    return 1 <= x && x <= k;
}

void ins(int x, map<int, int>& win) {
    if(valid(x)) win[x] = win[x] + 1;
}

void del(int x, map<int, int>& win) {
    if(!win.count(x)) return;
    win[x] = win[x] - 1;
    if(win[x] < 1) win.erase(x);
}

int solve() {
    map<int, int> win;
    win.clear();

    int ans = 0;

    for(int L = 0, R = 0; L < n; L++) {
        while (win.size() < k) {
            ins(x[R], win);
            R++;
            if(R >= n) break;
        }

        if(R >= n) break;

        if(win.size() == k) {
            // enough points

            while (win[x[L]] > 1 || !win.count(x[L])) {
                del(x[L], win);
                L++;
            }

            if(!ans) ans = R - L + 1;
            else ans = min(ans, R - L + 1);
        }

        del(x[L], win);
    }

    return ans;
}

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

    _rep(t, 1, T) {
        scanf("%d%d%d", &n, &m, &k);

        // then we init cal() x[] and solve()

        cal();

        printf("Case %d: ", t);

        int ans = solve();
        if(!ans) printf("sequence nai\n");
        else printf("%d\n", ans - 1);
    }
}

连续子序列权值问题

LA3517

LA3517

const int maxn = 100000 + 10;
int n;

llong L[maxn], R[maxn], sum[maxn], A[maxn];
stack<int> stk;
// stk used to store index

void init() {
    Set(sum, 0);
    Set(A, 0);
    Set(L, 0);
    Set(R, 0);
}

void popGreater(int i) {
    while(!stk.empty() && A[stk.top()] >= A[i]) stk.pop();
}

void solve() {
    while (!stk.empty()) stk.pop();

    _rep(i, 1, n) {
        popGreater(i);
        L[i] = stk.empty() ? 0 : stk.top();
        stk.push(i);
    }

    while (!stk.empty()) stk.pop();

    _forDown(i, n, 1) {
        popGreater(i);
        R[i] = stk.empty() ? n + 1 : stk.top();
        stk.push(i);
    }

    llong ans = -1, ansl = -1, ansr = -1;
    _rep(i, 1, n) {
        // if A[i] is min value
        llong li = L[i], ri = R[i] - 1, tmp = (sum[ri] - sum[li]) * A[i];
        li++;

        bool update = false;
        if(tmp < ans) continue;
        if(tmp > ans) update = true;

        if(tmp == ans) {
            if(ansr - ansl > ri - li) update = true;
            else if(ansr - ansl == ri - li) update = li < ansl;
        }

        ans = max(tmp, ans);
        if(update) {
            ansl = li;
            ansr = ri;
        }
    }

    printf("%lld\n%lld %lld\n", ans, ansl, ansr);
}


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

    bool first = true;

    while (scanf("%d", &n) == 1) {
        init();

        if(first) first = false;
        else puts("");


        bool all0 = true;
        _rep(i, 1, n) {
            scanf("%lld", &A[i]);
            if(A[i]) all0 = false;
            sum[i] = A[i] + sum[i - 1];
        }


        if(all0) {
            printf("0\n1 1\n");
            continue;
        }

        // then solve the problem
        solve();
    }
}

坐标离散化

LA2689
LA2689

const int maxn = 100 + 4;

class Point {
public:
    int x, y;
    bool operator< (const Point& rhs) const {
        if(x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
};

Point P[maxn];
int dy[maxn];
int ans, ansX, ansY;

void init() {
    Set(dy, 0);
    ans = ansX = ansY = 0;
}

int N, W, H;

void solve() {
    int n = unique(dy, dy + N + 2) - dy;
    _for(i, 0, n) _for(j, i + 1, n) {
        int minY = dy[i], maxY = dy[j];
        int hh = maxY - minY, last = 0, ww = 0;

        _for(k, 0, N) {
            Point& cur = P[k];
            if(cur.y <= minY || cur.y >= maxY) continue;

            ww = cur.x - last;
            if(ans < min(ww, hh)) {
                ans = min(ww, hh);
                ansX = last, ansY = minY;
            }
            last = cur.x;
        }

        ww = W - last;
        if(ans < min(ww, hh)) {
            ans = min(ww, hh);
            ansX = last, ansY = minY;
        }
    }
    printf("%d %d %d\n", ansX, ansY, ans);
}

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

    while (T--) {
        init();
        scanf("%d%d%d", &N, &W, &H);

        _for(i, 0, N) {
            scanf("%d%d", &P[i].x, &P[i].y);
            dy[i] = P[i].y;
        }
        dy[N] = 0, dy[N + 1] = H;

        // discrete
        sort(dy, dy + N + 2);
        sort(P, P + N);

        solve();
        if(T) printf("\n");
    }
}

逆序对(找规律枚举)

LA4000
LA4000

const int maxn = 500 + 10;
int n;
int A[maxn];

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

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

    while (T--) {
        init();
        scanf("%d", &n);
        _for(i, 0, n) scanf("%d", &A[i]);

        int cnt = 0;
        _for(i, 0, n - 1) _for(j, i + 1, n) {
            if(A[i] > A[j]) cnt++;
        }

        if(n % 2 && cnt % 2) cout << "impossible" << endl;
        else cout << "possible" << endl;
    }
}