POI XIX(2012) Stage II

POI XIX(2012) Stage I

zimpha posted @ Fri, 06 Mar 2015 01:40:21 +0800 in POI , 749 readers

最近越做题越发现自己智商捉急,赶紧找一些POI的题目练下智商。

Festival

给出$n$个正整数$x_1,x_2,\dots,x_n$, 然后给出$m_1+m_2$个限制条件,限制分为两类:

  1. 给出$a,b(1 \le a,b \le n)$, 要求满足$x_a+1=x_b$
  2. 给出$a,b(1 \le a,b \le n)$, 要求满足$x_a \le x_b$

要求在满足条件的基础下,问$x_1,x_2,\dots,x_n$中最多可以有多少个不同的数.

数据规模: $2 \le n \le 600, 1 \le m_1 + m_2 \le 100000$

首先我们可以把这些关系化为一些小于关系, 然后就可以建立差分约束系统. 然后对于不同强联通分量里面的数, 我们可以认为它们互不相关. 那么我们只要关心同一个强联通分量里面的元素即可. 对于某个连通块, 假设点u是时间最小的数, 我们可以枚举$u$, 以$u$为源点做一次最短路, 找到最大的$dist_{u,v}$, 则该连通块的最大不同时间数是$dist_{u,v}+1$, 事实上搞一个floyd就好了.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 600 + 10, inf = 1e9;

int dfn[MAXN], low[MAXN], stk[MAXN], col[MAXN];
int dis[MAXN][MAXN], n, m1, m2, scc_cnt;
bool vis[MAXN];
vector<PII> G[MAXN];

void link(int u, int v, int w) {
  G[u].push_back(PII(v, w));
}

void dfs(int x) {
  static int sz = 0, top = 0;
  low[x] = dfn[x] = ++ sz; stk[++ top] = x;
  for (size_t i = 0, y; i < G[x].size(); ++ i) {
    if (!dfn[y = G[x][i].first]) {
      dfs(y); low[x] = min(low[x], low[y]);
    }
    else if (col[y] == -1) low[x] = min(low[x], dfn[y]);
  }
  if (dfn[x] == low[x]) {
    scc_cnt ++; do {
      col[stk[top]] = scc_cnt - 1;
    } while (stk[top --] != x);
  }
}

int main() {
  scanf("%d%d%d", &n, &m1, &m2);
  for (int _ = 0; _ < m1; ++ _) {
    int a, b; scanf("%d%d", &a, &b); -- a; -- b;
    link(a, b, 1); link(b, a, -1);
  }
  for (int _ = 0; _ < m2; ++ _) {
    int a, b; scanf("%d%d", &a, &b); -- a; -- b;
    link(a, b, 0);
  }
  memset(col, -1, sizeof(col));
  for (int i = 0; i < n; ++ i) {
    if (!dfn[i]) dfs(i);
  }
  for (int i = 0; i < n; ++ i) {
    dis[i][i] = 0;
    for (int j = 0; j < i; ++ j) {
      dis[i][j] = dis[j][i] = -inf;
    }
  }
  for (int u = 0, v; u < n; ++ u) {
    for (size_t i = 0; i < G[u].size(); ++ i) {
      if (col[u] == col[v = G[u][i].first]) {
        dis[u][v] = max(dis[u][v], G[u][i].second);
      }
    }
  }
  for (int k = 0; k < n; ++ k) {
    for (int i = 0; i < n; ++ i) if (dis[i][k] != -inf) {
      for (int j = 0; j < n; ++ j) if (dis[k][j] != -inf) {
        dis[i][j] = max(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
  for (int i = 0; i < n; ++ i) {
    if (dis[i][i] > 0) {
      puts("NIE");
      return 0;
    }
  }
  int ret = 0;
  for (int i = 0; i < n; ++ i) if (!vis[i]) {
    vector<int> ls;
    for (int j = 0; j < n; ++ j) {
      if (col[i] == col[j]) vis[j] = true, ls.push_back(j);
    }
    int tmp = 0;
    for (size_t j = 0; j < ls.size(); ++ j) {
      for (size_t k = 0; k < ls.size(); ++ k) {
        tmp = max(tmp, abs(dis[ls[j]][ls[k]]) + 1);
      }
    }
    ret += tmp;
  }
  printf("%d\n", ret);
  return 0;
}

Letters

给出两个只包含大写字母的字符串$A$和$B$, 它们所含有的每个字母的个数是相同的. 每次可以将两个相邻的字符换位, 问$A$最少要经过多少步可以变成$B$.

数据规模: $1 \le |A|=|B| \le 10^6$

事实上$A$中的每个字符位置是固定的. 考虑$A$和$B$中的同一个字母, $A$中第$i$个出现的必定会到$B$中第$i$个位置. 然后我们可以得到一个排列, 然后把排列变成有序的最少次数就是逆序对的个数.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MAXN = 1000000 + 10;
char s[MAXN], t[MAXN];
vector<int> vs[26], vt[26];

int u[MAXN], a[MAXN], n;
void ins(int x) {
  for (; x <= n; x += ~x & x + 1) u[x] ++;
}
int get(int x) {
  int r = 0;
  for (; x >= 0; x -= ~x & x + 1) r += u[x];
  return r;
}

int main() {
  scanf("%d%s%s", &n, s, t);
  for (int i = 0; i < n; ++ i) {
    vs[s[i] - 'A'].push_back(i);
    vt[t[i] - 'A'].push_back(i);
  }
  for (int i = 0; i < 26; ++ i) {
    for (size_t j = 0; j < vs[i].size(); ++ j) {
      a[vs[i][j]] = vt[i][j];
    }
  }
  LL ret = 0;
  for (int i = n - 1; i >= 0; -- i) {
    ret += get(a[i] - 1); ins(a[i]);
  }
  cout << ret << endl;
  return 0;
}

Distance

对于两个正整数$a,b$, 这样定义函数$d(a,b)$: 每次操作可以选择一个质数$p$, 将$a$变成$a \times p$或$\frac{a}{p}$, 如果选择变成$\frac{a}{p}$就要保证$p | a$, $d(a,b)$表示将$a$变成$b$所需的最少操作次数.

现在给出$n$个数$a_1,a_2,\dots,a_n$, 对于每个$i(1 \le i \le n)$, 求出最小的$j(1\le j \le n, i \ne j)$使得$d(a_i,a_j)$最小.

数据规模: $1 \le n \le 10^5, 1 \le a_i \le 10^6$

 

记$cnt(x)$表示$x$中质因子(相同的重复计数)的个数, 那么$d(a,b)=cnt(\frac{ab}{\gcd^2(a,b)})$. 于是我们枚举每个$g=\gcd(a,b)$, 考虑$g$的所有倍数, 那么这些倍数两两之间的gcd都可能是$g$, 于是我们不妨认为就是$g$(如果不是$g$的话以后会被更优解更新掉). 那么在所有倍数中我们找出$cnt$最小的那个$gg$, 那么其他的数必定要和这个数$gg$匹配. 然后用$gg$更新答案即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1000000 + 10;

vector<int> np[MAXN];
int a[MAXN], dis[MAXN], ans[MAXN], cnt[MAXN];
int pl[MAXN], rep[MAXN], n, m, mx;

void sieve() {
  m = 0;
  for (int i = 2; i <= mx; ++ i) {
    if (!cnt[i]) pl[m ++] = i, cnt[i] = 1;
    for (int j = 0; j < m && pl[j] * i <= mx; ++ j) {
      cnt[i * pl[j]] = cnt[i] + 1;
      if (i % pl[j] == 0) break;
    }
  }
}

int main() {
  scanf("%d", &n); mx = 0;
  for (int i = 0; i < n; ++ i) {
    scanf("%d", a + i); mx = max(mx, a[i]);
    if (!rep[a[i]]) rep[a[i]] = i + 1;
    np[a[i]].push_back(i + 1);
  }
  sieve();
  for (int i = 1; i <= mx; ++ i) dis[i] = -1;
  for (int g = 1; g <= mx; ++ g) {
    vector<int> num;
    int gg = -1;
    for (int i = g; i <= mx; i += g) if (!np[i].empty()) {
      num.push_back(i);
      if (gg == -1 || (cnt[gg] > cnt[i]) || (cnt[gg] == cnt[i] && rep[gg] > rep[i])) gg = i;
    }
    if (gg == -1) continue;
    for (size_t i = 0; i < num.size(); ++ i) if (gg != num[i]) {
      int a = gg, b = num[i], cost = cnt[a] + cnt[b] - 2 * cnt[g];
      if (dis[a] == -1 || (dis[a] > cost) || (dis[a] == cost && ans[a] > rep[b])) {
        dis[a] = cost; ans[a] = rep[b];
      }
      if (dis[b] == -1 || (dis[b] > cost) || (dis[b] == cost && ans[b] > rep[a])) {
        dis[b] = cost; ans[b] = rep[a];
      }
    }
  }
  for (int i = 0; i < n; ++ i) {
    int ret = ans[a[i]];
    if (np[a[i]].size() > 1) {
      if (np[a[i]][0] == i + 1) ret = np[a[i]][1];
      else ret = np[a[i]][0];
    }
    printf("%d\n", ret);
  }
  return 0;
}

Rendezvous

给出一个有$n$个顶点的有向图, 每个点只有一条出边. 然后给出$q$组询问,每次给出两个顶点$a,b$, 要求输出满足以下条件的$x,y$:

  1. 从顶点$a$沿着出边走$x$步和从顶点$b$沿着出边走$y$步后到达的顶点相同
  2. 在满足条件1的情况下$\max(x,y)$最小
  3. 在满足条件1和2的情况下$\min(x,y)$最小
  4. 如果满足条件1,2和3的存在多组, 这时候选择$x \ge y$的那一组
  5. 如果不存在满足条件1的$x,y$,输出-1 -1

数据规模: $1 \le n,q \le 500000$

首先得到的图是环套内向树, 把边反向变成环套外向树. 找出所有环, 以环上每个点为根dfs, 搞个LCA就好了, 剩下的都是一些经典问题.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MAXN = 500000 + 10;

int dep[MAXN], rk[MAXN], rt[MAXN];
int len[MAXN], belong[MAXN], vis[MAXN];
int father[MAXN][20], nx[MAXN], n, q;
vector<int> G[MAXN];

namespace LCA {
  const int POW = 19;
  void build() {
    for (int i = 1; (1 << i) <= n; ++ i) {
      for (int j = 0; j < n; ++ j) {
        if (father[j][i - 1] == -1) continue;
        father[j][i] = father[father[j][i - 1]][i - 1];
      }
    }
  }
  int up(int u, int d) {
    for (int i = 0; d; ++ i, d >>= 1) {
      if (d & 1) u = father[u][i];
    }
    return u;
  }
  int ask(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = up(u, dep[u] - dep[v]);
    for (int i = POW; i >= 0; -- i) {
      if (father[u][i] == father[v][i]) continue;
      u = father[u][i]; v = father[v][i];
    }
    if (u != v) u = father[u][0];
    return u;
  }
}

int main() {
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; ++ i) {
    scanf("%d", nx + i); nx[i] --;
    G[nx[i]].push_back(i);
    memset(father[i], -1, sizeof(father[i]));
  }
  static int sz = 0;
  for (int i = 0, x, y; i < n; ++ i) if (!vis[i]) {
    for (x = i; !vis[x]; x = nx[x]) vis[x] = true;
    for (y = i; vis[y]; y = nx[y]) vis[y] = false;
    queue<int> Q;
    for (len[sz] = 0, y = x; !vis[y]; y = nx[y]) {
      rk[y] = len[sz] ++; Q.push(y); vis[y] = true;
      rt[y] = y; belong[y] = sz; dep[y] = 0;
    }
    while (!Q.empty()) {
      x = Q.front(); Q.pop();
      for (size_t i = 0; i < G[x].size(); ++ i) {
        y = G[x][i]; if (vis[y]) continue;
        rt[y] = rt[x]; belong[y] = sz;
        dep[y] = dep[x] + 1; father[y][0] = x;
        vis[y] = true; Q.push(y);
      }
    }
    sz ++;
  }
  LCA::build();
  while (q --) {
    int a, b; scanf("%d%d", &a, &b); -- a, -- b;
    if (belong[a] != belong[b]) {puts("-1 -1"); continue;}
    if (rt[a] == rt[b]) {
      int c = LCA::ask(a, b);
      printf("%d %d\n", dep[a] - dep[c], dep[b] - dep[c]);
    }
    else {
      int x = rt[a], y = rt[b];
      int x1, y1, x2, y2;
      if (rk[x] < rk[y]) {
        x1 = dep[a] + rk[y] - rk[x]; y1 = dep[b];
        x2 = dep[a]; y2 = dep[b] + len[belong[a]] - rk[y] + rk[x];
      }
      else {
        x1 = dep[a]; y1 = dep[b] + rk[x] - rk[y];
        x2 = dep[a] + len[belong[a]] - rk[x] + rk[y]; y2 = dep[b];
      }
      if ((max(x1, y1) > max(x2, y2)) ||
          (max(x1, y1) == max(x2, y2) && min(x1, y1) > min(x2, y2)) ||
          (max(x1, y1) == max(x2, y2) && min(x1, y1) == min(x2, y2) && x2 >= y2)) {
        swap(x1, x2); swap(y1, y2);
      }
      printf("%d %d\n", x1, y1);
    }
  }
  return 0;
}

Well

给出$n$个正整数$x_1,x_2,\dots,x_n$, 可以进行不超过$m$次操作, 每次操作选择一个非零的$x_i$, 并将它减一. 最终要求存在某个$k$满足$x_k=0$, 并且$z=\max{|x_i - X_{i+1}|}最小. 输出最小的$z$和此时最小的$k$.

数据规模: $1 \le n \le 10^6, 1 \le m \le 10^{18}, 1 \le x_i \le 10^9$

第一步就是二分$z$, 那么问题转化为给出一个序列, 求最少的操作次数使得相邻两个数之差不超过$z$, 并且其中某个数等于0. 

首先不考虑$x_k=0$这个条件, 如果要用最少体力, 只需要从左往右扫一遍令$x_{i+1}=min(x_{i+1}, x_i + z)$, 然后从右往左扫一遍, 令$x_{i-1}=min(x_{i-1}, x_i + z)$即可. 同时顺便搞出这次花费的操作次数.

现在我们考虑令$x_k=0$, 那么显然只要找到最大的$l(1 \le l \le k)$满足$x_l \le (k-l)z$, 最小的$r (k \le r \le n)$满足$x_r \le (k-l)z$即可. 然后把区间$(l,r)$之间的数改成相对应的等差数列即可. 然后我们也可以发现随着$k$的变化$l,r$的变化也是单调的, 于是就可以$O(n)$扫描求出代价.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MAXN = 1000000 + 10;
int x[MAXN], y[MAXN], n, mx;
LL m, cost[MAXN], sum[MAXN];

int check(LL z) {
  LL ret = 0;
  for (int i = 0; i < n; ++ i) y[i] = x[i];
  for (int i = 0; i + 1 < n; ++ i) if (y[i + 1] > y[i] + z) {
    ret += y[i + 1] - (y[i] + z);
    y[i + 1] = y[i] + z;
  }
  for (int i = n - 1; i > 0; -- i) if (y[i - 1] > y[i] + z) {
    ret += y[i - 1] - (y[i] + z);
    y[i - 1] = y[i] + z;
  }
  sum[n] = 0;
  for (int i = n - 1; i >= 0; -- i) sum[i] = sum[i + 1] + y[i];
  if (ret > m) return -1;
  for (int i = 0, l = i; i < n; ++ i) {
    while (l < i && y[l] <= LL(i - l) * z) ++ l;
    cost[i] = sum[l] - sum[i + 1] - (LL)(i - l) * LL(i - l + 1) * z / 2;
  }
  for (int i = n - 1, r = i; i >= 0; -- i) {
    while (r > i && y[r] <= LL(r - i) * z) -- r;
    cost[i] += sum[i] - sum[r + 1] - (LL)(r - i) * LL(r - i + 1) * z / 2;
  }
  for (int i = 0; i < n; ++ i) {
    if (cost[i] - y[i] + ret <= m) return i;
  }
  return -1;
}

int main() {
  scanf("%d%lld", &n, &m);
  for (int i = 0; i < n; ++ i) scanf("%d", x + i), mx = max(mx, x[i]);
  int left = 0, right = mx;
  while (left < right) {
    int mid = (left + right - 1) >> 1;
    if (check(mid) != -1) right = mid;
    else left = mid + 1;
  }
  printf("%d %d\n", check(left) + 1, left);
  return 0;
}
  • No match

Login *


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