2014-2015 ACM-ICPC, NEERC, Western Subregional Contest

题目总体上挺简单的, 写个题解备忘.

题目链接: https://contest.yandex.ru/QF2014/contest/794

也有题解视频, 但是是毛子语, 能听懂的可以去看看. 

Problem A. Arithmetic Derivative

定义自然数的arithmetic derivative: 

• $p^\prime = 1$对于任意质数
• $(ab)^\prime=a^\prime b + a b^\prime$对于任意自然数$a,b$

现在给你一个数$x$, 求出$x$的arithmetic derivative.

数据规模: $1 \le x \le 10^9$

分解质因数搞搞就好了. 由于多组数据, 可能会超时, 记得小范围打表.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 100000 + 10;
int pl[MAXN], mp[MAXN], n, m;
LL cnt[MAXN];

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

int main() {
  sieve();
  int T; scanf("%d", &T);
  while (T --) {
    scanf("%d", &n);
    LL ret = 0;
    int x = n;
    for (int i = 0; pl[i] * pl[i] <= n && n >= MAXN; ++ i) {
      while (n % pl[i] == 0) n /= pl[i], ret += x / pl[i];
    }
    if (n < MAXN) ret += x / n * cnt[n];
    else ret += x / n;
    printf("%lld\n", ret);
  }
  return 0;
}

Problem B. Banner Rotation

有$N$个不同的广告, 一个网站的顶部每次会随机等概率的显示这$N$个广告之一. 用户每次有$P$的概率点击这个广告, 某个广告如果被点击了, 那么下次访问网站的时候不会在出现这个广告而是从剩下的没有点过的广告中随机等概率选择一个. 如果每个广告都被点过了, 那么之后网站上不会再显示任何广告.

现在一个用户每天访问网站的次数均匀分布在区间$[A,B]$之间, 问期望需要多少天这个用户才能看到过所有广告. 注意每天广告的点击都会重置, 也就是说天与天之间广告的点击是互不相关的.

数据规模: $1 \le N \le 50, 1 \le A \le B \le 50, 0 \le P \le 1$

看到这题我想到了2015年Facebook HackerCup的Round 2的一道题目, 然后感觉应该也可以这么做.

首先求出一天看到$i$个广告的概率$Q_i$. 为了算$Q_i$, 我们需要一个辅助的dp数组. 令$dp_{i,j,k}$表示在前$i$次浏览中, 共看到了$j$个不同的广告, 总共点击了$k$次的概率. 分成点击或者不点击就很容易写出dp方程. 需要注意的是$dp_{i,N,N}$需要特别转移.

然后我们就有$Q_i = \frac{\displaystyle\sum_{j=A}^{B}\displaystyle\sum_{k=0}^{N}dp_{j,i,k}}{B-A+1}$

然后令$f_{t,i}$表示前$t$天总共看了$i$个不同广告的概率, 考虑枚举$t+1$天新看到的广告数目$k$, 以及第$t+1$天看的广告数目$j$, 我们可以得到如下的递推:\[f_{t+1,i + k} \text{ += } f_{t,i}Q_j \frac{\binom{N-i}{k}\binom{i}{j-k}}{\binom{N}{j}}\]

然后我们就可以得到第$t$天看到$N$个广告的概率$g_t=f_{t,N}-f_{t-1,N}$

于是期望就等于$\displaystyle\sum_{t=0}^{\infty}{tg_t}$, 然后只要精度够了就好, 于是我们只要取$t$的上界为1000就好了.

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

flt dp[MAXN][MAXN][MAXN], p;
flt Q[MAXN], f[SIZE][MAXN];
flt fac[MAXN];
int A, B, N;

flt C(int n, int m) {
  return fac[n] - fac[m] - fac[n - m];
}

flt calc(int i, int j, int k) {
  if (i < j - k) return 0;
  else return exp(C(N - i, k) + C(i, j - k) - C(N, j));
}

int main() {
  fac[0] = fac[1] = 0;
  for (int i = 2; i < MAXN; ++ i) fac[i] = fac[i - 1] + log(1.0 * i);
  scanf("%d%d%d%lf", &N, &A, &B, &p);
  memset(dp, 0, sizeof(dp)); dp[0][0][0] = 1;
  for (int i = 0; i < B; ++ i) {
    for (int j = 0; j <= N && j <= i; ++ j) {
      for (int k = 0; k <= j && k < N; ++ k) {
        if (dp[i][j][k] == 0) continue;
        dp[i + 1][j][k + 1] += dp[i][j][k] * p * (j - k) / (N - k);
        dp[i + 1][j][k] += dp[i][j][k] * (1.0 - p) * (j - k) / (N - k);
        if (j < N) {
          dp[i + 1][j + 1][k + 1] += dp[i][j][k] * p * (N - j) / (N - k);
          dp[i + 1][j + 1][k] += dp[i][j][k] * (1.0 - p) * (N - j) / (N - k);
        }
      }
    }
    if (dp[i][N][N] != 0) dp[i + 1][N][N] += dp[i][N][N];
  }
  for (int i = A; i <= B; ++ i) {
    for (int j = 0; j <= N; ++ j) {
      for (int k = 0; k <= j; ++ k) {
        Q[j] += dp[i][j][k];
      }
    }
  }
  for (int j = 0; j <= N; ++ j) {
    Q[j] /= flt(B - A + 1);
  }
  int L = 1000; f[0][0] = 1;
  for (int t = 0; t < L; ++ t) {
    for (int i = 0; i <= N; ++ i) {
      if (f[t][i] == 0) continue;
      for (int k = 0; k <= N - i; ++ k) {
        for (int j = k; j <= N; ++ j) {
          f[t + 1][i + k] += f[t][i] * Q[j] * calc(i, j, k);
        }
      }
    }
  }
  flt ret = 0;
  for (int i = 1; i <= L; ++ i) {
    ret += i * (f[i][N] - f[i - 1][N]);
  }
  printf("%.10f\n", ret);
  return 0;
}

Problem C. Code of the Tree

给出一棵树, 问从每个点出发的最长路.

数据规模: $2 \le N \le 10^5$

经典两遍dfs水过.

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

struct Node {
  int len, idx;
  Node() {}
  Node(int a, int b): len(a), idx(b) {}
};

const int MAXN = 100000 + 10;
vector<int> G[MAXN];

Node down[MAXN][2], best[MAXN][2];
int n;

void dfs1(int u, int f = -1) {
  down[u][0] = Node(0, u);
  down[u][1] = Node(0, 0);
  for (auto &v : G[u]) if (v != f) {
    dfs1(v, u);
    if (down[v][0].len + 1 > down[u][1].len) {
      down[u][1] = down[v][0];
      ++ down[u][1].len;
      if (down[u][1].len > down[u][0].len) swap(down[u][0], down[u][1]);
    }
  }
}

void dfs2(int u, int f = 0) {
  best[u][0] = down[u][0]; best[u][1] = down[u][1];
  if (f != 0) {
    for (int i = 0; i < 2; ++ i) {
      if (best[f][i].idx != down[u][0].idx) {
        if (best[f][i].len + 1 > best[u][1].len) {
          best[u][1] = best[f][i];
          ++ best[u][1].len;
        }
        if (best[u][1].len > best[u][0].len) {
          swap(best[u][0], best[u][1]);
        }
        break;
      }
    }
  }
  for (auto &v : G[u]) if (v != f) {
    dfs2(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; ++ i) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs1(1); dfs2(1);
  for (int i = 1; i <= n; ++ i) {
    if (i > 1) putchar(' ');
    printf("%d", best[i][0].len);
  }
  puts("");
  return 0;
}

Problem D. Decoding Tree Code

上面一题的逆. 给出每个点出发的最长路的长度, 要求还原这棵树.

数据规模: $2 \le N \le 10^5$

只要找到树的直径, 每次都在直径上加点就好了.

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

int main() {
  scanf("%d", &n);
  vector<PII> p, ret;
  for (int i = 0; i < n; ++ i) {
    int x; scanf("%d", &x);
    p.push_back(PII(x, i));
  } 
  memset(c, -1, sizeof(c));
  sort(p.begin(), p.end(), greater<PII>());
  int len = p[0].first, flag = true;
  for (auto &v : p) {
    int d = v.first, u = v.second;
    if (c[d] == -1) {
      c[d] = u; v.first = -1;
      if (len - d > d) flag = false;
    }
    else if (c[len - d] == -1) {
      c[len - d] = u; v.first = -1;
      if (len - d > d) flag = false;
    }
  }
  for (int i = 0; i <= len; ++ i) {
    if (c[i] == -1) flag = false;
  }
  for (int i = 0; i < len; ++ i) ret.push_back(PII(c[i], c[i + 1]));
  for (auto &v : p) if (v.first != -1) {
    int d = v.first, u = v.second;
    -- d; ret.push_back(PII(c[d], u));
    if (len - d > d) flag = false;
  }
  if (flag) {
    puts("I got it");
    for (auto &v : ret) {
      printf("%d %d\n", v.first + 1, v.second + 1);
    }
  }
  else puts("Epic fail");
  return 0;
}

Problem E. Election

给出$N$个四舍五入之后的百分比(都是整数), 问这个是否合法. 即是否存在一些小数满足四舍五入之后是这$N$个数, 并且加起来等于100.

数据规模: $1 \le N \le 1000$

对于一个数$x$, 他对应的实数范围为$[x-0.5, x+0.5)$, 然后我们求出所有这些区间, 加起来, 看看100是否在区间内即可.

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

int main() {
  //freopen("election.in", "r", stdin);
  //freopen("election.out", "w", stdout);
  scanf("%d", &n);
  int l = 0, r = 0;
  for (int i = 0; i < n; ++ i) {
    int x; scanf("%d", &x);
    l += max(x * 2 - 1, 0), r += x * 2 + 1;
  }
  bool flag = 200 >= l && 200 < r;
  puts(flag ? "Yes" : "No");
  return 0;
}

Problem F. Factorial Number System

定义阶乘进制, 然后给出一个只有加减法的表达式, 求出表达式的值.

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

char s[SIZE], *p;
LL f[SIZE];

LL get(char c) {
  if (c >= '0' && c <= '9') return c - '0';
  else return c - 'A' + 10;
}
char tochar(int x) {
  if (x < 10) return '0' + x;
  else return 'A' + x - 10;
}

LL get(string s) {
  int l = s.size();
  LL ret = 0;
  for (size_t i = 0; i < s.size(); ++ i) {
    ret += get(s[i]) * f[l - i];
  }
  return ret;
}

string tostr(LL n) {
  string ret;
  for (int i = 20; i >= 1; -- i) {
    int c = 0;
    while (n >= f[i]) {
      n -= f[i];
      ++ c;
    }
    ret += tochar(c);
  }
  for (size_t i = 0; i < ret.size(); ++ i) {
    if (ret[i] != '0') return ret.substr(i);
  }
  return string(1, '0');
}

int main() {
  f[0] = 1;
  for (int i = 1; i < 36; ++ i) f[i] = f[i - 1] * i;
  scanf("%s", s);
  LL ret = 0;
  for (p = s; *p;) {
    int sgn = 1;
    if (*p == '+') ++ p;
    else if (*p == '-') sgn = -1, ++ p;
    string num;
    while (*p != '+' && *p != '-' && *p) {
      num += string(1, *p); ++ p;
    }
    ret += get(num) * sgn;
  }
  printf("%s\n", tostr(ret).c_str());
  return 0;
}

Problem G. Graphs. How Many of Them?

求最多有$B$座桥的$N$个点的带标号无向连通图的数目.

数据规模: $1 \le N \le 50, 0 \le B \le N(N-1)/2$

对于一个无向连通图, 我们双连通分量缩点之后就得到了一颗树, 然后我们可以沿着这个思路开始做这道题目.

为了说明方便, 下面的树或者图都是带标号的, 树均指缩点之后得到的树, $n$指缩点之前图中点的总数.

令$f_{n,b}$表示有$n$个点恰好有$b$座桥的树的数目. $g_{n,b,k}$表示有$n$个点,恰好有$b$座桥,有$k$棵树的森林数目, $k$棵树的每个树根都需要往外连一条边. $h_{n,b}$表示有$n$个点恰好有$b$座桥的树的数目, 但是树根上有个点需要往外连边.

然后我们可以得到以下的一些递推式子:

$$f_{n,b}=\sum_{i=1}^{n-1}\sum_{j=1}^{b}\binom{n-1}{i-1}i^j\frac{g_{n-i,b-j,j}}{j!}f_{i,0}$$

$$g_{n,b,k}=\sum_{i=1}^{n}\sum_{j=0}^{b}\binom{n}{i}h_{i,j}g_{n-i,b-j,k-1}$$

$$h_{n,b}=\sum_{i=1}^{n-1}\sum_{j=1}^{b}\binom{n}{i}i^{j+1}\frac{g_{n-i,b-j,j}}{j!}f_{i,0}$$

$$f_{n,0}=C_n - \sum_{b=1}^{n-1}f_{n,b}, h_{n,0}=nf_{n,0}$$

其中$C_n$表示联通带标号无向图个数, 也很容易知道:$$C_n=2^{\binom{n}{2}}-\sum_{i=1}^{n-1}\binom{n-1}{i-1}C_i2^{\binom{n-i}{2}}$$

然后答案就是$\sum_{i=0}^{B}f_{N,i}$.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 60, MOD = 1e9 + 7;
int dp1[MAXN][MAXN];
int dp3[MAXN][MAXN];
int dp2[MAXN][MAXN][MAXN];
int f[MAXN], g[MAXN], C[MAXN][MAXN];
int fac[MAXN], inv[MAXN];

LL calc1(int N, int B);
LL calc2(int N, int B, int K);
LL calc3(int N, int B);

LL pm(LL a, LL n) {
  LL r = 1;
  for (; n; n >>= 1) {
    if (n & 1) r = r * a % MOD;
    a = a * a % MOD;
  }
  return r;
}

LL calc1(int N, int B) {
  if (B >= N && N) return 0;
  int &ret = dp1[N][B];
  if (ret != -1) return ret;
  if (B == 0) {
    ret = g[N];
    for (int b = 1; b < N; ++ b) {
      ret -= calc1(N, b);
      ret = (ret + MOD) % MOD;
    }
    return ret;
  }
  ret = 0;
  for (int i = 1; i < N; ++ i) {
    for (int k = 1; k <= B; ++ k) {
      LL tmp = calc2(N - i, B - k, k) * inv[k] % MOD;
      tmp = tmp * calc1(i, 0) % MOD;
      tmp = tmp * C[N - 1][i - 1] % MOD;
      tmp = tmp * pm(i, k) % MOD;
      ret = (ret + tmp) % MOD;
    }
  }
  return ret;
}

LL calc2(int N, int B, int K) {
  if (B >= N && N) return 0;
  int &ret = dp2[N][B][K];
  if (ret != -1) return ret;
  if (K == 0) return ret = (N == 0 && B == 0);
  ret = 0;
  for (int i = 1; i <= N; ++ i) {
    for (int b = 0; b <= B; ++ b) {
      LL tmp = calc3(i, b) * C[N][i] % MOD;
      tmp = tmp * calc2(N - i, B - b, K - 1) % MOD;
      ret = (ret + tmp) % MOD;
    }
  }
  return ret;
}

LL calc3(int N, int B) {
  if (B >= N && N) return 0;
  int &ret = dp3[N][B];
  if (ret != -1) return ret;
  if (B == 0) return ret = calc1(N, 0) * N % MOD;
  ret = 0;
  for (int i = 1; i < N; ++ i) {
    for (int k = 1; k <= B; ++ k) {
      LL tmp = calc2(N - i, B - k, k) * inv[k] % MOD;
      tmp = tmp * calc1(i, 0) % MOD * i % MOD;
      tmp = tmp * C[N][i] % MOD * pm(i, k) % MOD;
      ret = (ret + tmp) % MOD;
    }
  }
  return ret;
}

void init() {
  fac[0] = inv[0] = 1;
  for (int i = 1; i < MAXN; ++ i) {
    fac[i] = (LL)i * fac[i - 1] % MOD;
    inv[i] = pm(fac[i], MOD - 2);
  }
  for (int i = 0; i < MAXN; ++ i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++ j) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
  }
  g[0] = g[1] = 1; f[0] = f[1] = 1;
  for (int n = 2; n < MAXN; ++ n) {
    f[n] = g[n] = pm(2, n * (n - 1) / 2);
    for (int k = 1; k < n; ++ k) {
      g[n] -= (LL)C[n - 1][k - 1] * g[k] % MOD * f[n - k] % MOD;
      g[n] = (g[n] + MOD) % MOD;
    }
  }  
}

int main() {
  memset(dp1, -1, sizeof(dp1));
  memset(dp2, -1, sizeof(dp2));
  memset(dp3, -1, sizeof(dp3));
  int N, B; scanf("%d%d", &N, &B);
  int ret = 0; init();
  for (int b = 0; b <= B; ++ b) {
    ret = (ret + calc1(N, b)) % MOD;
  }
  printf("%d\n", ret);
  return 0;
}

Problem H. Halloween

给出两个数组$\{a_1,a_2,\dots,a_n\}$和$\{b_1,b_2,\dots,b_m\}$

求$\sum_{i=1}^{m}\sum_{j=1}^{n}[b_i | a_j]\frac{a_j}{b_i}$

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

水水的.

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

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++ i) {
    int x; scanf("%d", &x); ca[x] ++;
  }
  for (int i = 0; i < m; ++ i) {
    int x; scanf("%d", &x); cb[x] ++;
  }
  LL ret = 0;
  for (int i = 1; i < MAXN; ++ i) if (cb[i]) {
    for (int j = i; j < MAXN; j += i) {
      ret += (LL)cb[i] * ca[j] * j / i;
    }
  }
  printf("%lld\n", ret);
  return 0;
}

Problem I. Intelligent System

有$k$条生产线, 每条生产线上都有$n$个机器人, 每个机器人的工作效率可能不一样. 有一件物品需要依次经过$n$到工序. 现在可以降低某个机器人的工作效率, 问最坏情况下的最小时间.

数据规模: $1 \le k, n \le 1000$

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

PII mx[MAXN];
int K, N;

int main() {
  scanf("%d%d", &K, &N);
  fill(mx, mx + N, PII(inf, inf));
  for (int i = 0; i < K; ++ i) {
    for (int j = 0; j < N; ++ j) {
      int x; scanf("%d", &x);
      mx[j].second = min(mx[j].second, x);
      if (mx[j].second < mx[j].first) {
        swap(mx[j].first, mx[j].second);
      }
    }
  }
  int sum = 0, ret = 0;
  for (int i = 0; i < N; ++ i) sum += mx[i].first;
  for (int i = 0; i < N; ++ i) {
    if (mx[i].first * 2 < mx[i].second) {
      ret = max(ret, sum + mx[i].first);
    }
    else {
      ret = max(ret, sum + mx[i].second - mx[i].first);
    }
  }
  printf("%d\n", ret);
  return 0;
}

Problem J. Joining Transformation

给出一个字符串$s$, 定义一个函数$f$: 删除字符串中的若干个字符, 返回可以得到的字典序最大的字符串.

现在有$Q$个操作, 要么询问$s$某个区间作用$f$的结果, 要么改变某个位置的字符.

数据规模: $1 \le |s|, Q \le 10^5$

作用$f$的字符串最后肯定是一连串z接着一连串y...接着一连串a, 然后我们发现这个东西是可加的, 用线段树维护即可.

#include <bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 100000 + 10;
struct Node {
  int cnt[26];
} mx[MAXN << 2];
char s[MAXN];
int n, q;

void upd(Node &x, Node y) {
  int a = 25, b = 25;
  for (; a >= 0 && !x.cnt[a]; -- a);
  for (; b >= 0 && !y.cnt[b]; -- b);
  if (a == -1 || a < b) x = y;
  else if (a == b) y.cnt[a] += x.cnt[a], x = y;
  else {
    if (b >= 0) x.cnt[b] += y.cnt[b];
    for (int i = b - 1; i >= 0; -- i) x.cnt[i] = y.cnt[i];
  }
}

void build(int rt = 1, int l = 0, int r = n) {
  if (l + 1 == r) {
    mx[rt].cnt[s[l] - 'a'] = 1;
    return;
  }
  build(lson, l, mid); build(rson, mid, r);
  mx[rt] = mx[lson]; upd(mx[rt], mx[rson]);
}

void modify(int p, int v, int rt = 1, int l = 0, int r = n) {
  if (l + 1 == r) {
    memset(mx[rt].cnt, 0, sizeof(mx[rt].cnt));
    mx[rt].cnt[v] = 1; return;
  }
  if (p < mid) modify(p, v, lson, l, mid);
  else modify(p, v, rson, mid, r);
  mx[rt] = mx[lson]; upd(mx[rt], mx[rson]);
}

Node ret;
void ask(int L, int R, int rt = 1, int l = 0, int r = n) {
  if (L <= l && R >= r) {
    upd(ret, mx[rt]);
    return;
  }
  if (L < mid) ask(L, R, lson, l, mid);
  if (R > mid) ask(L, R, rson, mid, r);
}

int main() {
  scanf("%s", s); n = strlen(s);
  build();
  scanf("%d", &q);
  for (int _ = 0; _ < q; ++ _) {
    int op; scanf("%d", &op);
    if (op == 1) {
      int l, r, k; scanf("%d%d%d", &l, &r, &k);
      memset(ret.cnt, 0, sizeof(ret.cnt));
      ask(l - 1, r);
      char ans = '-';
      for (int i = 25, s = 0; i >= 0; -- i) {
        s += ret.cnt[i];
        if (s >= k) {ans = 'a' + i; break;}
      }
      printf("%c\n", ans);
    }
    else {
      scanf("%d%s", &op, s);
      modify(op - 1, s[0] - 'a');
    }
  }
  return 0;
}

Problem K. King of Byteland

给出一棵$n$个点的树和$q$个询问, 每次询问距离某个点$c$距离恰好为$d$的所有点中标号第$k$小的节点的标号(保证存在).

数据规模: $2 \le n \le 50000, 1 \le q \le 10^5, 1 \le c \le n, 1 \le d \le 30$

树分治大法好. 二分答案, 然后树分治判断即可. 复杂度$O(q\log^3n)$

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

const int MAXN = 50000 + 10;
vector<int> G[MAXN];
int n, m;

struct Entry {
  int anc, dis, idx;
  Entry() {}
  Entry(int a, int b, int c): anc(a), dis(b), idx(c) {}
};

struct BIT {
  vector<int> u, s, c;
  int n;
  void add(int v) {s.push_back(v);}
  void build() {
    c = s; sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    n = c.size(); u.assign(n + 1, 0);
    for (size_t i = 0; i < s.size(); ++ i) ins(s[i]);
  }
  void ins(int x) {
    int i = lower_bound(c.begin(), c.end(), x) - c.begin();
    for (; i <= n; i += ~i & i + 1) u[i] ++;
  }
  int get(int x) {// <=x
    int r = 0, i = upper_bound(c.begin(), c.end(), x) - c.begin() - 1;
    for (; i >= 0; i -= ~i & i + 1) r += u[i];
    return r;
  }
};

struct Item {
  vector<BIT> lev;
  void add(int d, int v) {
    while ((int)lev.size() <= d) lev.push_back(BIT());
    lev[d].add(v);
  }
  void build() {
    for (auto &x : lev) x.build();
  }
  int get(int d, int v) {
    if (d >= (int)lev.size()) return 0;
    else return lev[d].get(v);
  }
} pool[MAXN << 4];

vector<Entry> entry[MAXN];

namespace TreeSplit {
  bool vis[MAXN];
  int rt, mx, total;
  int sz[MAXN], item_cnt;
  void getCenter(int u, int f = -1) {
    sz[u] = 1; int tmp = 0;
    for (auto &v : G[u]) if (v != f && !vis[v]) {
      getCenter(v, u); sz[u] += sz[v];
      tmp = max(tmp, sz[v]);
    }
    tmp = max(tmp, total - sz[u]);
    if (tmp < mx) mx = tmp, rt = u;
  }
  int anc;
  void calc(int u, int f = -1, int d = 0) {
    sz[u] = 1; pool[item_cnt].add(d, u);
    //cout << u << ": " << anc << " " << d << " " << item_cnt << endl;
    entry[u].push_back(Entry(anc, d, item_cnt));
    for (auto &v : G[u]) if (v != f && !vis[v]) {
      calc(v, u, d + 1); sz[u] += sz[v];
    }
  }
  void build(int u, int tot) {
    total = tot; rt = -1; mx = tot * 2;
    getCenter(u); u = rt; vis[u] = true;
    //cout << rt << " " << tot << endl;
    anc = rt;
    calc(u); pool[item_cnt ++].build();
    anc = -1;
    for (auto &v : G[u]) if (!vis[v]) {
      calc(v, u, 1); pool[item_cnt ++].build();
    }
    for (auto &v : G[u]) if (!vis[v]) {
      build(v, sz[v]);
    }
  }
}

int count(int x, int d, int lim) {
  int ret = 0;
  for (auto &e : entry[x]) {
    //cout << x << ": " << e.anc << " " << e.dis << " " << e.idx << endl;
    if (d >= e.dis) {
    int rest = d - e.dis;
    if (e.anc != -1) ret += pool[e.idx].get(rest, lim);
    else ret -= pool[e.idx].get(rest, lim);
  }
}
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; ++ i) {
    int u, v; scanf("%d%d", &u, &v); -- u, -- v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  TreeSplit::build(1, n);
  scanf("%d", &m);
  while (m --) {
    int c, d, k; scanf("%d%d%d", &c, &d, &k); -- c;
    int left = 0, right = n - 1;
    while (left < right) {
      int mid = (left + right - 1) >> 1;
      if (count(c, d, mid) >= k) right = mid;
      else left = mid + 1;
    }
    printf("%d\n", left + 1);
  }
  return 0;
}

Problem L. Linear Programmer

给出若干个小于等于关系, 求$x_n-x_1$的最大值.

查分约束建好图, 跑个最短路即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 100000 + 10;
const LL inf = 1ll << 60;
vector<PII> G[MAXN];
LL dis[MAXN];
int vis[MAXN], n, m; 

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++ i) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    G[u].push_back(PII(v, w));
  }
  for (int i = 1; i <= n; ++ i) dis[i] = inf;
  queue<int> Q; Q.push(1); vis[1] = true; dis[1] = 0;
  while (!Q.empty()) {
    int u = Q.front(); Q.pop(); vis[u] = false;
    for (auto &x : G[u]) {
      int v = x.first, w = x.second;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) vis[v] = true, Q.push(v);
      }
    }
  }
  if (dis[n] == inf) puts("Infinity");
  else printf("%lld\n", dis[n]);
  return 0;
}

Problem M. Masha and Dasha

给出一个三角形, 求一条直线将三角形分成面积和周长相等的两部分.

枚举和直线相交的两条边, 然后解一个一元二次方程即可.

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef double flt;
typedef pair<flt, flt> PII;
const flt eps = 1e-9;
flt dis(PII a, PII b) {
  return hypot(a.x - b.x, a.y - b.y);
}

flt area, len;

bool solve(PII A, PII B, PII C) {
  flt a = dis(B, C), b = dis(A, C), c = dis(A, B);
  flt cosa = (b * b + c * c - a * a) / (2.0 * b * c);
  flt sina = sqrt(1.0 - cosa * cosa);
  flt s = (a + b + c) * 0.5, t = area / sina;
  flt delta = s * s - 4.0 * t;
  if (delta < -eps) return false;
  flt x = (sqrt(delta) + s) * 0.5, y = s - x;
  if(b > c) swap(b, c), swap(B, C);
  if (x > y) swap(x, y);
  if (x >= -eps && x <= b + eps && y >= -eps && y <= c + eps) {
    PII P(A.x + (C.x - A.x) * x / b, A.y + (C.y - A.y) * x / b);
    PII Q(A.x + (B.x - A.x) * y / c, A.y + (B.y - A.y) * y / c);
    printf("%.18f %.18f\n%.18f %.18f\n", P.x, P.y, Q.x, Q.y);
    return true;
  }
  x = (s - sqrt(delta)) * 0.5, y = s - x;
  if (x > y) swap(x, y);
  if (x >= -eps && x <= b + eps && y >= -eps && y <= c + eps) {
    PII P(A.x + (C.x - A.x) * x / b, A.y + (C.y - A.y) * x / b);
    PII Q(A.x + (B.x - A.x) * y / c, A.y + (B.y - A.y) * y / c);
    printf("%.18f %.18f\n%.18f %.18f\n", P.x, P.y, Q.x, Q.y);
    return true;
  }
  return false;
}

int main() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  area = 0.5 * b * c;
  PII A(0, 0), B(c, 0), C(a, b);
  solve(A, B, C) || solve(B, C, A) || solve(C, A, B);
  return 0;
}

• Relative Posts