【POJ-1988】Cube Stacking【带权并查集】

【POJ-1988】Cube Stacking【带权并查集】

问题链接:https://vjudge.net/problem/POJ-1988

Solution:

叠箱子,一种想法是,使用双向链表,完全模拟这一过程,但是会超时,我们该用并查集解决。使用并查集的核心是,需要另外记录每个位置的高度,我们重新审视一下合并操作,将一个box A堆叠到另一个box B上,那么A的高度变成1,B的高度依旧是0;顺着这个思路,我们想尝试能否使用并查集记录某种值来解决,我们需要解决:

1.这个记录的值如何与查询的值联系起来

2.Union时如何更新这个值

3.find时如何更新(传播)这个值【通常Union后,合并前的某个根节点下的子结点的这个值没有更新,所以需要考虑如何在find时进行正确的更新】

首先,(1)可以被简单的设计出来,我们让一个点到其根节点的所有点上改值之和表示这个box下box的数量,这样显然也是可以通过路径压缩对路径上的这个值进行求和的,这样(3)find的更新细节也一并完成。

(2)如何Union,Union的时候,假设我们要将根A并到根B下方,显然需要将根A的这个值记录为根B下的结点数,对于根节点,我们可以使用负值表示根,那么这个负数具体是负几就可以用来记录这个树下有多少结点,这样合并的时候的值就正好可以设置成这个值的相反数。

代码:

#include <iostream>

using namespace std;

const int NIL = -1;
const int LIM = 30000;
struct Node {
    int parent, dist;
};
Node disSet[LIM];

inline char myGetChar() {
    char ret;
    while ((ret = getchar()) == ' ' || ret == '\n' || ret == '\t');
    return ret;
}

Node find(int x) {
    Node ret;
    if (disSet[x].parent < 0) {
        ret.parent = x;
        ret.dist = 0;
        return ret;
    }
    ret = find(disSet[x].parent);
    ret.dist += disSet[x].dist;
    disSet[x] = ret;
    return ret;
}

void Union(int x, int y) {
    x = find(x).parent;
    y = find(y).parent;
    if (x == y) return;
    disSet[x].dist = -disSet[y].parent;
    disSet[y].parent += disSet[x].parent;
    disSet[x].parent = y;
}

int main(void) {
    int p, x, y;
    char op;
    scanf("%d", &p);
    // init
    for (int i = 0; i < LIM; i++) {
        disSet[i].parent = NIL;
        disSet[i].dist = 0;
    }
    while (p--) {
        op = myGetChar();
        if (op == 'M') {
            scanf("%d%d", &x, &y);
            Union(x, y);
        } else {
            scanf("%d", &x);
            printf("%d\n", find(x).dist);
        }
    }
    return 0;
}

 

参考了:

https://www.youtube.com/watch?v=LfYiut7wYHI

【POJ-1007】DNA Sorting【树状数组求逆序对】

【POJ-1007】DNA Sorting【树状数组求逆序对】

问题链接:https://vjudge.net/problem/POJ-1007

Solution:

使用树状数组求解逆序对,倒序遍历序列,树状数组记录到遍历当前位置出现的所有元素各自的数量【我们将’A’通过’A’ – ‘A’ + 2映射到2,其余字符都是CH – ‘A’ + 2】,对于每个序列中的元素,我们先查询遍历到当前位置出现过多少比它小的元素,每一个计数将代表有一个逆序对,之后将树状数组中当前元素的计数加1.

这道题要求对所有字符串进行逆序对数量从小到大排序,之后输出,使用结构体存放string和计数,并使用计数来排序就好了。

时间复杂度\(O(mnlogn)\).

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int LIM = 30;
int bitree[LIM];

void update(int pos) {
    for (; pos < LIM; pos += pos & (-pos))
        bitree[pos]++;
}

int query(int pos) {
    int ret = 0;
    for (; pos > 0; pos -= pos & (-pos))
        ret += bitree[pos];
    return ret;
}

struct Node {
    string str;
    int cnt;
    bool operator < (const Node &n) const {
        return cnt < n.cnt;
    }
};
vector<Node> dat;

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int n, m;
    Node tmp;
    while (cin >> n >> m) {
        dat.clear();
        for (int i = 0; i < m; i++) {
            cin >> tmp.str;
            tmp.cnt = 0;
            memset(bitree, 0, sizeof bitree);
            for (int j = n - 1; j >= 0; j--) {
                tmp.cnt += query(tmp.str[j] - 'A' + 1);
                // cout << query(tmp.str[j] - 'A' + 1) << endl;
                update(tmp.str[j] - 'A' + 2);
            }
            dat.push_back(tmp);
        }
        sort(dat.begin(), dat.end());
        for (int i = 0; i < m; i++) {
            cout << dat[i].str << '\n';
            // cout << dat[i].cnt << '\n';
        }
    }
    return 0;
}