POI - B
A. [POI 2005] Cash Dispenser (bank) （思维题）
题意
有一个 \(4\) 位 PIN 码，现在记录下用户输入 PIN 码时手指移动位置的序列，序列中每一位数可能不按，也可能按若干次。
对于同一个 PIN 码，给定记录下的 \(n\) 个序列（序列 \(i\) 长度为 \(t_i\)），求可能的序列个数。
\(1\le n\le1000\)，\(1\le t_i\le10000\)，\(\sum t_i\le10^6\)。
思路
首先解释一下题意：设一个数字密码串的「位置序列」为相邻相同数字去重后的序列，如 \(22333\) 的位置序列为 \(23\)。给定 \(n\) 个数字串，求可能的 \(4\) 位数字密码个数，使得密码的位置序列是这 \(n\) 个数字串的子序列（可能不连续）。如，给定 \(123\) 和 \(234\)，那么密码的位置序列是公共子序列 \(23\) 的子序列，所以可能的密码有 \(5\) 种：\(2222,2223,2233,2333,3333\)。
题目要求我们求满足「位置序列 是 所有 \(n\) 个数字串的子序列」的串的个数，那么我们不妨转化一下：
因为所求的串一定是四位数，一共只有 \(10^4\) 个，所以我们可以考虑标记出「对于某个 给出数字串，位置序列 不是 其子序列」的串，最后数出没有被标记的串的个数即可。
对于读入的每一个数字串，我们需要标记所有不合法的数字。枚举 \([0,10^4)\) 内的所有数字，判断其是否是所读入的数字串的子序列。
如何快速判断？记 \(p(i,j)\) 为第 \(i\) 位后面第一个 \(j\) 的位置，如果没有则设为 \(-1\)。我们选择用先进先出的队列处理。具体实现参考代码。
于是，由于只有四位数，我们可以在常数时间内判断一个数字是否合法。如果不合法则在值域数组中打上标记。
在处理完所有数字串后，我们枚举 \([0,10^4)\) 内的所有数字，记录没有被标记过的数的个数即为答案。
时间复杂度 \(O\left(w\sum t_i+nm\right)\)，其中 \(w=10\)，\(m=10^4\)。
代码
#include <iostream>
#include <string>
#include <queue>
#define g(x, y, z) for (int x = (y); x < (z); ++x)
using namespace std;
const int N = 5e5 + 10;
int n, t, p[N][10];
bool ok[10001];
string s;
queue<int> q[10];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
while (n--) {
cin >> t >> s;
int len = s.length();
g(i, 0, len) q[s[i] - '0'].push(i);
g(i, 0, len) {
g(k, 0, 10) {
if (q[k].empty()) p[i][k] = -1;
else p[i][k] = q[k].front();
}
q[s[i] - '0'].pop();
}
g(x, 0, 1e4) {
if (!ok[x]) {
int i = x/1000, j = x/100-i*10, k = x/10-i*100-j*10, l = x%10;
if (p[0][i] == -1 || p[p[0][i]][j] == -1 || p[p[p[0][i]][j]][k] == -1 || p[p[p[p[0][i]][j]][k]][l] == -1)
ok[x] = true;
}
}
}
int ans = 0;
g(x, 0, 1e4) ans += (!ok[x]);
cout << ans << '\n';
return 0;
}
B. [POI 2005] Toy Cars (sam) （贪心）
题意
两个正整数集 \(A\) 和 \(B\)，初始时 \(A\) 中有 \(1\) 到 \(n\) 共 \(n\) 个数，\(B\) 为空。数字只能在 \(A\) 和 \(B\) 之间来回移动。
现在有长度为 \(p\) 的序列 \(a\)，\(a_i\) 表示在时刻 \(i\) 需要满足 \(a_i\) 在 \(B\) 中。且在同一时刻 \(B\) 中最多只能有 \(k\) 个数。
如果 \(B\) 中已经有 \(k\) 个数，则必须先选择 \(B\) 中的一个数移动到 \(A\) 中，才可以将 \(A\) 中一个数移动到 \(B\) 中。
求最少需要将数字从 \(A\) 到 \(B\) 移动几次。
\(1\le k\le n\le10^5\)，\(1\le p\le5\times10^5\)，\(1\le a_i\le n\)。
思路
如果迫不得已选择一个数从 \(B\) 移动到 \(A\)，一定是选择当前 \(B\) 中下一次需要最晚的数 \(i\)。
感性理解：如果选择一个下一次需要比 \(i\) 早的数 \(j\) 拿走，那么后面把 \(j\) 拿回来之后还需要把 \(i\) 拿回来，这样一定不优。
于是用堆维护 \(B\) 中的数，以下一次需要的时间为关键词从大到小排序。并且记录每个数是否在堆里。每次需要放进新的数时，如果 \(B\) 满了就拿走堆顶。
现在有一个问题：如果需要的数已经在堆中，如何更新它的下一次被需要的时间？
观察到一个数被需要的时间一定是单调递增的，也就是说，只要堆中加入了新的时间，那么原来的时间必不可能作为堆顶，也就完全没用了。
为了避免将原来的时间拿出来，我们可以把原来的时间就留在堆中，同时将 \(k\) 加一。（妙啊！
答案直接记录即可。复杂度 \(O(p\log p)\)。
代码
#include <iostream>
#include <queue>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10, P = 5e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k, p, lst[N], nxt[P], a[P], ans;
priority_queue<pii> q;
bool in[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k >> p;
g(i, p, 1) {
cin >> a[i];
if (!lst[a[i]]) nxt[i] = INF; //永远不再需要
else nxt[i] = lst[a[i]];
lst[a[i]] = i;
}
f(i, 1, p) {
if (!in[a[i]]) {
if (q.size() == k) {
in[q.top().second] = false;
q.pop();
}
in[a[i]] = true;
++ans;
} else ++k; //重点！！！！
q.emplace(nxt[i], a[i]);
}
cout << ans << '\n';
return 0;
}
C. [POI 2005] Piggy Banks (ska) （并查集）
题意
有 \(n\) 个存钱罐，存钱罐中不仅有钱，还有若干存钱罐的钥匙，第 \(i\)（\(1\le i\le n\)）个存钱罐的钥匙在第 \(x_i\) 个存钱罐中。
求最少需要暴力砸开几个存钱罐，使得所有存钱罐都能被打开。
\(1\le n\le10^6\)，\(1\le x_i\le n\)。
思路
如果一个存钱罐被打开（不管是暴力砸开还是用钥匙），那么可能会引起一系列存钱罐都被打开。
于是我们用并查集维护，如果把根节点对应的存钱罐打开，那么同一个并查集中的存钱罐都可以被打开。
输入时直接合并，把 \(x_i\) 作为 \(i\) 的根。由于 \(\boldsymbol{x_i}\) 和 \(\boldsymbol{i}\) 是一一对应的，所以并不存在指向非根节点的情况，因此每次都是直接把一棵树形结构合并到另一棵上。
最后枚举所有节点，数出一共几个并查集即可。
复杂度 \(O(n\alpha(n))\)。
代码
#include <iostream>
#define f(x, y, z) for (int x = (y); (x) <= (z); ++(x))
using namespace std;
const int N = 1e6 + 10;
int n, ans;
bool vis[N];
int fa[N];
int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
f(i, 1, n) fa[i] = i;
f(i, 1, n) {
int j;
cin >> j;
int fi = getfa(i), fj = getfa(j);
if (fi != fj) fa[fi] = fj;
}
f(i, 1, n) {
int fi = getfa(i);
if (!vis[fi]) vis[fi] = true, ++ans;
}
cout << ans << '\n';
return 0;
}
D. [POI 2005] A Journey to Mars (lot) （单调队列）
题意
有 \(n\) 个空间站呈环形排列，从 \(1\) 到 \(n\) 编号。
有一个人在其中一个空间站登陆，他的目标是顺时针或逆时针绕一圈回到初始位置。
走 \(1\) 米需要消耗 \(1\) 升油。油箱没有容量限制。
第 \(i\) 号空间站的信息有两个：
- \(p_i\) 表示该空间站可以补给的油量，单位为升；
- \(d_i\) 表示 \(i\) 到 \(i+1\) 的距离（\(d_n\) 表示 \(n\) 到 \(1\) 的距离），单位为米。
对于每个空间站，请你判断在此登陆是否可以绕一圈（顺时针或逆时针）回到登陆位置。
\(3\le n\le10^6\)，\(p_i\ge0\)，\(d_i>0\)，\(\sum d_i\le2\times10^9\)。
思路
首先破环为链。顺时针和逆时针的区别只有向左还是向右，这里先说向右。
我们发现，如果一个位置 \(i\)（\(1\le i\le n\)）不合法，那么一定是有一个位置 \(j\in[i,i+n)\)，满足
从而使 \(j\) 到不了 \(j+1\)。也就是说，如果位置 \(i\) 可行，那么对于所有 \(j\in[i,i+n)\)，必须满足
于是设前缀和 \(s_i=\sum\limits_{j=1}^ip_j-d_j\)，则上式变为 \(s_j-s_{i-1}\ge0\;(\forall\,j\in[i,i+n-1])\)，即
于是问题就变成了单调队列维护固定区间最小值的问题。由于区间在所遍历的 \(i\) 的右侧，所以对于这种情况要 从右到左 遍历。
向左同理，\(\forall\,j\in[i-n+1,i]\) 满足 $ p_i+p_{i-1}+\dots+p_j\ge d_{i-1}+d_{i-2}+\dots+d_{j-1}$，
即 \(\sum\limits_{k=j}^i\,p_k-d_{k-1}\ge0\)。设 \(s_i=\sum\limits_{j=1}^ip_j-d_{j-1}\)。则上式变为
为了方便，我们将 \(i\) 替换为 \(i+1\)，将 \(j\) 替换为 \(j+1\)，上式变为
其中 \(0\le i\le2n-1\)。于是就可以愉快地用单调队列维护了。别忘了是 从左到右 遍历。
答案可以用布尔数组来存，只要有一个方向合法即可，所以是或运算。
时间复杂度 \(O(n)\)。
代码
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
const int N = 1e6 + 10;
int n, p[N], d[N], s[N << 1];
int q[N << 1], h, t;
bool ans[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
f(i, 1, n) cin >> p[i] >> d[i];
f(i, 1, n) s[i] = s[i + n] = p[i] - d[i];
f(i, 1, n << 1) s[i] += s[i - 1];
h = t = 1;
q[h] = n << 1 | 1;
g(i, n << 1, 1) {
while (h <= t && q[h] > i + n - 1) ++h;
if (i < n) ans[i] |= (s[q[h]] - s[i - 1] >= 0);
while (h <= t && s[q[t]] >= s[i - 1]) --t;
q[++t] = i - 1;
}
d[0] = d[n];
f(i, 1, n) s[i] = s[i + n] = p[i] - d[i - 1];
f(i, 1, n << 1) s[i] += s[i - 1];
h = t = 1;
q[h] = 0;
f(i, 0, (n << 1) - 1) {
while (h <= t && q[h] < i - n + 1) ++h;
if (i + 1 > n) ans[i + 1 - n] |= (s[i + 1] - s[q[h]] >= 0);
while (h <= t && s[q[t]] <= s[i + 1]) --t;
q[++t] = i + 1;
}
f(i, 1, n) cout << (ans[i] ? "TAK\n" : "NIE\n");
return 0;
}
E. [POI 2005] Bank Notes (ban) （多重背包优化）
题意
一共有 \(n\) 种面值的硬币，第 \(i\)（\(1\le i\le n\)）种硬币的面值为 \(b_i\)，数量为 \(c_i\)，现在我们想要凑出面值 \(k\)，求最少要用多少个硬币。要求输出一种选硬币的方案。
\(1 \le n \le 200\)，\(1 \le b_1 < b_2 < \cdots < b_n \le 2 \times 10^4\)，\(1 \le c_i \le 2 \times 10^4\)，\(1 \le k \le 2 \times 10^4\)。
思路
多重背包模板题，但是输出方案（（
我们采用二进制优化。把 \(c_i\) 分成 \(2^0+2^1+2^2+\dots+2^p+m\)，其中 \(2^p-1\le c_i\)，\(2^{p+1}-1>c_i\)，\(0\le m<2^{p+1}\)（也就是令 \(p\) 极大）。
这样分组的目的是能凑出 \([0,c_i]\) 内的所有数字。接下来就是普通的 0/1 背包了，设 \(f(j)\) 表示凑出面值 \(j\) 最少需要多少个硬币。
但是这道毒瘤题还让我们记录转移点，于是新开一个数组 \(r\)（record）记录。
最后回去找方案可以用 DFS。时间复杂度 \(O(k\sum\log c_i)\)。
代码
#include <cstdlib>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
const int N = 210, M = 3e3 + 10, V = 2e4 + 10;
int n, b[N], c, k, cnt, w[M], v[M], f[V], r[M], ans[N];
bool vis[M];
void dfs(int x) {
if (!x) {
f(i, 1, n) cout << ans[i] << ' ';
cout << '\n';
exit(0); //结束程序
}
g(i, cnt, 1) {
if (vis[i] || w[i] > x) continue;
if (f[x] != f[x - w[i]] + v[i]) continue;
vis[i] = true;
ans[r[i]] += v[i];
dfs(x - w[i]);
ans[r[i]] -= v[i];
vis[i] = false;
}
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
f(i, 1, n) cin >> b[i];
f(i, 1, n) {
cin >> c;
int p = 1;
while (c - p > 0) {
c -= p;
w[++cnt] = b[i] * p, v[cnt] = p;
r[cnt] = i;
p <<= 1;
}
if (c) w[++cnt] = b[i] * c, v[cnt] = c, r[cnt] = i;
}
cin >> k;
memset(f, 0x3f, sizeof f);
f[0] = 0;
f(i, 1, cnt) g(j, k, w[i])
f[j] = min(f[j], f[j - w[i]] + v[i]);
cout << f[k] << '\n';
dfs(k);
return 0;
}