POI XIX(2012) Stage I

POI XIX(2012) Stage II

zimpha posted @ Fri, 06 Mar 2015 18:32:02 +0800 in POI , 913 readers

昨晚把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$组成,问是否能够选出某些物品使得:

  1. 对于每个选的物品$i$, 满足$a_i \le m$并且$b_i > m + s$;
  2. 所有选出物品的$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

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter