POI XIX(2012) Stage II
昨晚把Stage II的最后一题搞定, 今天顺便写下题解备忘.
Tour de Byteotia
给出$n$个点$m$条边的无向图, 问最少删除多少条边才能使点$1,2,\dots,k$不在任何一个环内.
数据规模: $1 \le k \le n \le 10^6, 1 \le m \le 2\times 10^6$
对于一条边$(a,b)$, 如果$a \ge k, b \ge k$, 那么显然这条边保留下来也没有任何问题, 于是我们先把这些边保留下来. 接下来考虑其他边, 显然只要不形成环即可. 于是用并查集搞一下就好了.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1000000 + 10, MAXM = 2 * MAXN;
int dsu[MAXN], a[MAXM], b[MAXM];
int n, m, k, ret;
int get(int x) {
if (x != dsu[x]) dsu[x] = get(dsu[x]);
return dsu[x];
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++ i) dsu[i] = i;
for (int i = 0; i < m; ++ i) {
scanf("%d%d", a + i, b + i);
if (a[i] > b[i]) swap(a[i], b[i]);
if (a[i] > k && b[i] > k) {
dsu[get(a[i])] = get(b[i]);
a[i] = b[i] = 0;
}
}
for (int i = 0; i < m; ++ i) {
if (a[i] && b[i] && (a[i] <= k || b[i] <= k)) {
int x = get(a[i]), y = get(b[i]);
if (x == y) ++ ret;
else dsu[x] = y, a[i] = b[i] = 0;
}
}
printf("%d\n", ret);
for (int i = 0; i < m; ++ i) {
if (a[i] && b[i]) printf("%d %d\n", a[i], b[i]);
}
return 0;
}
Vouchers
考虑正整数集合, 现在有$n$组人依次来取数, 假设第$i$组来了$a_i$人, 他们每个取的数一定是$a_i$的倍数, 并且是还剩下的最小的$a-i$个. 正整数中有$m$个数$b_i$被标成了幸运数, 问有哪些人取到了幸运数.
数据规模: $1 \le n, m, b_i, a_i \le 10^6$
暴力记录当前$x$倍数取到哪个数了即可, 取数就暴力计算下一个位置取掉. 考虑$b_i \le 10^6$, 因此只要考虑$x$那些不超过$10^6$的倍数即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1000000 + 10;
bool mark[MAXN], bought[MAXN];
int st[MAXN], n, m;
vector<LL> ret;
int main() {
scanf("%d", &n); m = 0;
for (int _ = 0; _ < n; ++ _) {
int x; scanf("%d", &x);
m = max(m, x); mark[x] = true;
}
for (int i = 1; i <= m; ++ i) st[i] = i;
scanf("%d", &n); LL sum = 0;
for (int _ = 0; _ < n; ++ _) {
int x; scanf("%d", &x);
int now = st[x];
for (int i = 0; i < x; ++ i) {
while (bought[now] && now <= m) now += x;
st[x] = now;
if (now > m) break;
bought[now] = true;
if (mark[now]) ret.push_back(sum + i + 1);
}
sum += x;
}
printf("%d\n", (int)ret.size());
for (size_t i = 0; i < ret.size(); ++ i) printf("%lld\n", ret[i]);
return 0;
}
Cloakroom
有$n$件物品, 每件物品有三个属性$a_i,b_i,c_i (a_i<b_i)$. 再给出$q$个询问, 每个询问由非负整数$m,k,s$组成，问是否能够选出某些物品使得:
- 对于每个选的物品$i$, 满足$a_i \le m$并且$b_i > m + s$;
- 所有选出物品的$c_i$的和正好是$k$.
数据规模: $1 \le n, c_i \le 1000, 1 \le a_i < b_i \le 10^9, 1 \le q \le 10^6, 1\le k \le 10^5, 1 \le m, s \le 10^9$
显然这个题目不能在线, 那么考虑离线的做法.
将所有物品按照$a_i$从小到大排序, 所有询问按照$m$从小到大排序, 然后我们依次加入物品处理询问. 考虑朴素dp, 令$dp_{sum,lim}$表示用$b_i$大于$lim$的所有物品是否能组成$sum$. 由于$lim$太大, 根本无法存下. 那么倒着考虑, 令$dp_sum$表示组成和为$sum$的物品中$b_i$最小值的最大值, 然后这个可以用背包求出来. 对于询问, 我们只要考虑$dp_k$和$m+s$的相对大小即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
struct Item {
int a, b, c;
Item() {}
void read() {
scanf("%d%d%d", &c, &a, &b);
}
bool operator < (const Item &rhs) const {
return a < rhs.a || (a == rhs.a && b < rhs.b);
}
};
struct Query {
int m, k, s, id;
Query() {}
void read() {
static int sz = 0; id = sz ++;
scanf("%d%d%d", &m, &k, &s);
}
bool operator < (const Query &rhs) const {
return m < rhs.m;
}
};
const int MAXK = 100000 + 10, MAXN = 1000 + 10, MAXQ = 1000000 + 10;
Item it[MAXN];
Query ask[MAXQ];
int dp[MAXK], ret[MAXQ];
int n, q, mx;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++ i) it[i].read();
scanf("%d", &q); mx = 0;
for (int i = 0; i < q; ++ i) {
ask[i].read(); ret[i] = 0;
mx = max(mx, ask[i].k);
}
sort(it, it + n); sort(ask, ask + q);
for (int i = 0; i <= mx; ++ i) dp[i] = -1; dp[0] = 2e9 + 10;
for (int i = 0, cur = 0; i < q; ++ i) {
for (; cur < n && it[cur].a <= ask[i].m; ++ cur) {
for (int j = mx - it[cur].c; j >= 0; -- j) {
dp[j + it[cur].c] = max(dp[j + it[cur].c], min(dp[j], it[cur].b));
}
}
if (dp[ask[i].k] > ask[i].m + ask[i].s) ret[ask[i].id] = 1;
}
for (int i = 0; i < q; ++ i) puts(ret[i] ? "TAK" : "NIE");
return 0;
}
A Horrible Poem
给出一个由小写英文字母组成的字符串$S$, 再给出$q$个询问, 要求回答$S$某个子串的最短循环节. 如果字符串$B$是字符串$A$的循环节, 那么$A$可以由$B$重复若干次得到.
数据规模: $1 \le |S| \le 5 \times 10^5, 1 \le q \le 2 \times 10^6$
对于某个子串$S_{l..r}$和一个循环节$k$, 那么判断$k$是不是$S_{l..r}$只需要判断$S_{l..r-k+1}$和$S_{l+k..r}$是否相等即可, 用hash搞一下或者后缀数组预处理一下就可以$O(1)$判断了.
朴素做法是枚举$r-l+1$的所有约数, 依次判断可行性即可, 但是也有保证复杂度的做法.
假设长度为$x$, 那么考虑$x$的一个质因数$p$, 以及$p$在$x$中出现次数$c$. 那么我们只要依次检查$\frac{x}{p^c}, \frac{x}{p^{c-1}},\dots, x$就可以$p$在循环节中出现的次数.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
typedef pair<int, int> PII;
const int MAXN = 500000 + 10, MAGIC = 1e9 + 7;
LL pw[MAXN], hs[MAXN];
char s[MAXN];
int n, q;
vector<int> pl[MAXN];
void pre() {
pw[0] = 1;
for (int i = 1; i <= n; ++ i) pw[i] = pw[i - 1] * MAGIC;
for (int i = 2; i <= n; ++ i) {
if (pl[i].empty()) {
for (int j = i; j <= n; j += i) pl[j].push_back(i);
}
}
}
inline LL get(int l, int r) {
return hs[l] - hs[r] * pw[r - l];
}
bool check(int l, int r, int d) {
return get(l, r - d) == get(l + d, r);
}
int solve(int l, int r, int n) {
int ret = 1;
for (size_t i = 0; i < pl[n].size(); ++ i) {
int p = pl[n][i], x = n;
while (x % p == 0) x /= p;
while (!check(l, r, x)) {
ret *= p; x *= p;
}
}
return ret;
}
int main() {
scanf("%d%s%d", &n, s, &q); pre(); hs[n] = 0;
for (int i = n - 1; i >= 0; -- i) hs[i] = hs[i + 1] * MAGIC + s[i];
while (q --) {
int l, r; scanf("%d%d", &l, &r); -- l;
if (l + 1 == r) {puts("1"); continue;}
printf("%d\n", solve(l, r, r - l));
}
return 0;
}
Fibonacci Representation
给出一个正整数$x$, 问$x$最少能由多少个Fibonacci数加减算出.
数据规模: $1 \le x \le 4 \times 10^17$
之前碰到一道类似的二进制题目, 然后感觉可以用类似的方法贪心. 令$dp(n)$表示$n$的最小表示, 那么$dp(n) = min\{dp(n - fib_k), dp(fib_{k + 1} - n)\}+1$, 其中$fib_k$是小于等于$n$的最大Fibonacci数. 然后用map记忆化一下即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const LL inf = 1000000000000000000ll;
vector<LL> fib;
map<LL, int> mp;
int solve(LL n) {
//cout << n << endl;
if (n == 0) return 0;
if (n == 1) return 1;
if (mp.count(n)) return mp[n];
size_t i = upper_bound(fib.begin(), fib.end(), n) - fib.begin();
assert(i != fib.size());
return mp[n] = min(solve(fib[i] - n), solve(n - fib[i - 1])) + 1;
}
int main() {
fib.push_back(1); fib.push_back(1);
for (int i = 2; ; ++ i) {
LL x = fib[i - 1] + fib[i - 2];
if (x < inf) fib.push_back(x);
else break;
}
int T; scanf("%d", &T);
while (T --) {
LL n; scanf("%lld", &n);
cout << solve(n) << endl;
}
return 0;
}
- No match
Comments (0)
