[COCI2009-2010#2] PASIJANS

[COCI2009-2010#2] PASIJANS

题意

给出 \(n\) 个栈，每次可从任意一个栈取出栈顶放入答案队列。

求字典序最小的答案队列。

思路

考虑贪心。每次从字典序最小的栈中取出栈顶。

如何动态找出字典序最小的栈？

可以使用堆，单次 \(O(1)\) 查找最小值，\(O(\log n)\) 插入。

但比较两个栈的字典序是 \(O(n)\) 的，如何优化？

可以使用哈希优化至 \(O(\log n)\)。

根据字典序的定义，字典序取决于两个字符串第一个不等的位置的关系。

只需使用二分找出第一个不等的位置，判断前缀是否相等使用哈希 \(O(1)\)。

这样总复杂度 \(O((\sum L) \log (\sum L) \log n\)。

特别地，当一个字符串是另一个字符串的前缀时，认为长度长的字典序小。

这样保证去掉这个后，接下来的操作最优。

代码

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ui = unsigned int;
const int N = 2e3 + 5;

const ull Base = 10;
const ui Base2 = 4e9 + 7;
int n, a[N][N], L[N], top[N];
ull Hash[N][N], base[N];
ui Hash2[N][N], base2[N];

ull getHash(int id, int l, int len) {
	int r = l + len - 1;
	return Hash[id][r] - Hash[id][l - 1] * base[len];
}

ui getHash2(int id, int l, int len) {
	int r = l + len - 1;
	return Hash2[id][r] - Hash2[id][l - 1] * base2[len];
}

struct Int {
	int x;
};

bool cmp(int x, int y) {
	int lenX, lenY;
	lenX = L[x] - top[x] + 1;
	lenY = L[y] - top[y] + 1;
	int l = 1, r = min(lenX, lenY), mid, pos = -1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (getHash(x, top[x], mid) == getHash(y, top[y], mid)
		&& getHash2(x, top[x], mid) == getHash2(y, top[y], mid)) {
			l = mid + 1;
		} else {
			r = mid - 1;
			pos = mid;
		}
	}
	if (pos == -1) {
		return lenX > lenY;
	}
	return a[x][top[x] + pos - 1] < a[y][top[y] + pos - 1];
}

bool operator < (Int x, Int y) {
	return !cmp(x.x, y.x);
}

priority_queue <Int> Q; 

int main() {
	freopen("aaa.in", "r", stdin);
	freopen("aaa.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> L[i];
		for (int j = 1; j <= L[i]; j ++) {
			cin >> a[i][j];
		}
		top[i] = 1;
	}
	base[0] = 1;
	for (int i = 1; i <= 2e3; i ++) {
		base[i] = base[i - 1] * Base;
	}
	base2[0] = 1;
	for (int i = 1; i <= 2e3; i ++) {
		base2[i] = base2[i - 1] * Base2;
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= L[i]; j ++) {
			Hash[i][j] = Hash[i][j - 1] * Base + a[i][j]; 
		}
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= L[i]; j ++) {
			Hash2[i][j] = Hash2[i][j - 1] * Base2 + a[i][j]; 
		}
	}
	for (int i = 1; i <= n; i ++) {
		Q.push({i});
	}
	while (!Q.empty()) {
		int id = Q.top().x;
		Q.pop();
		cout << a[id][top[id]] << " ";
		top[id] ++;
		if (top[id] > L[id]) {
			continue;
		}
		Q.push({id});
	}
	return 0;
}