Vasya and Shifts

题目描述

Vasya has a set of $4n$ strings of equal length, consisting of lowercase English letters “a”, “b”, “c”, “d” and “e”. Moreover, the set is split into $n$ groups of $4$ equal strings each. Vasya also has one special string $a$ of the same length, consisting of letters “a” only.
Vasya wants to obtain from string $a$ some fixed string $b$, in order to do this, he can use the strings from his set in any order. When he uses some string $x$, each of the letters in string $a$ replaces with the next letter in alphabet as many times as the alphabet position, counting from zero, of the corresponding letter in string $x$. Within this process the next letter in alphabet after “e” is “a”.
For example, if some letter in $a$ equals “b”, and the letter on the same position in $x$ equals “c”, then the letter in $a$ becomes equal “d”, because “c” is the second alphabet letter, counting from zero. If some letter in $a$ equals “e”, and on the same position in $x$ is “d”, then the letter in $a$ becomes “c”. For example, if the string $a$ equals “abcde”, and string $x$ equals “baddc”, then $a$ becomes “bbabb”.
A used string disappears, but Vasya can use equal strings several times.
Vasya wants to know for $q$ given strings $b$, how many ways there are to obtain from the string $a$ string $b$ using the given set of $4n$ strings? Two ways are different if the number of strings used from some group of $4$ strings is different. Help Vasya compute the answers for these questions modulo $10^9+7$.

题意概述

给定$n$个长度为$m$的五进制数,每个数字最多用四次。定义两个五进制数的加法运算为按位相加后各位对五取模(无进位)。现有$q$组询问,每组询问给定一个长度为$m$的五进制数,求用前面的五进制数相加得到此数的方案数。
数据范围:$1 \le n, m \le 500, \; 1 \le q \le 300$。

算法分析

题目定义的这种加法类似于二进制下的异或运算。容易想到线性基。线性基是一种特殊的基,它通常会在异或运算中出现,它的意义是:通过原集合$S$的某一个最小子集$S_1$使得$S_1$内元素相互异或得到的值域与原集合$S$相互异或得到的值域相同。可以用高斯消元求线性基。对于每一组询问,判断是否可以由线性基相加得到,如果不能则输出$0$,否则方案数为$5^{n-|S_1|}$。

代码

#include <iostream>
#include <cstring>
using namespace std;
const long long mod = 1000000007ll;
long long n, m, q, a[501][501], b[501][501], r[501], p[501], t, ans = 1;
bool vis[501];
string s;
void gauss() {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      if (a[i][j])
        if (!vis[j]) {
          vis[j] = true, ++t;
          for (int k = 1; k <= m; ++k) b[j][k] = a[i][k];
          break;
        } else {
          int t = 0;
          while (a[i][j]) (a[i][j] += b[j][j]) %= 5, ++t;
          for (int k = 1; k <= m; ++k)
            if (j != k) (a[i][k] += b[j][k] * t) %= 5;
        }
}
int main()
{
  cin >> n >> m, ans = 1;
  for (int i = 1; i <= n; ++i) {
    cin >> s;
    for (int j = 1; j <= m; ++j) a[i][j] = s[j - 1] - 'a';
  }
  cin >> q, gauss();
  for (int i = t; i < n; ++i) (ans *= 5) %= mod;
  while (q--) {
    cin >> s, memset(p, 0, sizeof p);
    for (int i = 1; i <= m; ++i) r[i] = s[i - 1] - 'a';
    bool flag = false;
    for (int i = 1; i <= m; ++i) {
      if (p[i] != r[i]) {
        if (!b[i][i]) { flag = true; break; }
        int t = 0;
        while (p[i] != r[i]) (p[i] += b[i][i]) %= 5, ++t;
        for (int j = 1; j <= m; ++j)
          if (i != j) (p[j] += b[i][j] * t) %= 5;
      }
    }
    if (flag) cout << 0 << endl;
    else cout << ans << endl;
  }
  return 0;
}

Strange Radiation

题目描述

$n$ people are standing on a coordinate axis in points with positive integer coordinates strictly less than $10^6$. For each person we know in which direction (left or right) he is facing, and his maximum speed.
You can put a bomb in some point with non-negative integer coordinate, and blow it up. At this moment all people will start running with their maximum speed in the direction they are facing. Also, two strange rays will start propagating from the bomb with speed $s$: one to the right, and one to the left. Of course, the speed $s$ is strictly greater than people’s maximum speed.
The rays are strange because if at any moment the position and the direction of movement of some ray and some person coincide, then the speed of the person immediately increases by the speed of the ray.
You need to place the bomb is such a point that the minimum time moment in which there is a person that has run through point $0$, and there is a person that has run through point $10^6$, is as small as possible. In other words, find the minimum time moment $t$ such that there is a point you can place the bomb to so that at time moment $t$ some person has run through $0$, and some person has run through point $10^6$.

题意概述

在一条数轴上有$n$个人,第$i$个人的位置是$x_i$,速度是$v_i$。每个人初始时都面朝数轴正方向或负方向。现在你可以在数轴某一整点上放置一个炸弹。炸弹爆炸后,所有人都会向他当前面朝的方向奔跑。同时,炸弹会从放置点向数轴正负两侧分别发射出一道激光,速度是$s$。当一道激光碰到一个运动方向相同的人时,这个人的速度会立刻加上$s$。求放置炸弹后,至少有一个人到达$0$且至少有一个人到达$10^6$的最小时间。
数据范围:$2 \le n \le 10^5, \; 0 \le x_i \le 10^6, \; 1 \le v_i \lt s \le 10^6$。

算法分析

答案的范围在$0$到$10^6$之间,考虑二分答案。对于一个时间$t$,分别考虑面向负方向和面向正方向的人。对于负方向的情况,如果某个人不用借助激光就能在时间$t$内到达$0$,则直接考虑正方向;如果某个人借助了激光仍无法在时间$t$内到达$0$,则跳过这个人;否则,计算出在这个人到达$0$的情况下炸弹位置的最大值。右边同理,但求的是最小值。这就相当于求出了若干区间,若它们的交为空,则$t$不满足要求。另外还要考虑炸弹的位置比一个面向负方向的人的位置小或比一个面向正方向的人的位置大的情况。

代码

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
const double eps = 1e-10;
long long n, s;
long long x[100001], v[100001], t[100001];
double l, r;
bool check(double p) {
  bool flag1 = false, flag2 = false;
  for (int i = 1; i <= n; ++i)
    if (t[i] == 1 && 1.0 * x[i] / v[i] <= p) flag1 = true;
    else if (t[i] == 2 && (1e6 - x[i]) / v[i] <= p) flag2 = true;
  if (flag1 && flag2) return true;
  if (flag1) {
    for (int i = 1; i <= n; ++i)
      if (t[i] == 2 && (1e6 - x[i]) / (s + v[i]) <= p) return true;
    return false;
  }
  if (flag2) {
    for (int i = 1; i <= n; ++i)
      if (t[i] == 1 && 1.0 * x[i] / (s + v[i]) <= p) return true;
    return false;
  }
  long long before = 0, after = 1e6;
  for (int i = 1; i <= n; ++i)
    if (t[i] == 1 && 1.0 * x[i] / v[i] > p && 1.0 * x[i] / (s + v[i]) <= p) after = min(after, x[i]);
    else if (t[i] == 2 && (1e6 - x[i]) / v[i] > p && (1e6 - x[i]) / (s + v[i]) <= p) before = max(before, x[i]);
  if (before < after) return false;
  long long ma = -1e18, mi = 1e18;
  for (int i = 1; i <= n; ++i)
    if (t[i] == 1 && 1.0 * x[i] / v[i] > p && 1.0 * x[i] / (s + v[i]) <= p)
      ma = max(ma, (long long) floor((x[i] * v[i] + p * (s + v[i]) * (s - v[i])) / s));
    else if (t[i] == 2 && (1e6 - x[i]) / v[i] > p && (1e6 - x[i]) / (s + v[i]) <= p)
      mi = min(mi, (long long) ceil((1e6 * (s - v[i]) + x[i] * v[i] - p * (s + v[i]) * (s - v[i])) / s));
  return mi <= ma;
}
int main()
{
  cin >> n >> s;
  for (int i = 1; i <= n; ++i)
    cin >> x[i] >> v[i] >> t[i];
  l = 0, r = 1e6;
  while (r - l > eps) {
    double mid = (l + r) / 2;
    if (!check(mid)) l = mid; else r = mid;
  }
  cout << setprecision(10) << fixed << l << endl;
  return 0;
}

Coin Troubles

题目描述

In the Isle of Guernsey there are $n$ different types of coins. For each $i \; (1 \le i \le n)$, coin of type $i$ is worth $a_i$ cents. It is possible that $a_i=a_j$ for some $i$ and $j \; (i \neq j)$.
Bessie has some set of these coins totaling $t$ cents. She tells Jessie $q$ pairs of integers. For each $i \; (1 \le i \le q)$, the pair $b_i, c_i$ tells Jessie that Bessie has a strictly greater number of coins of type $b_i$ than coins of type $c_i$. It is known that all $b_i$ are distinct and all $c_i$ are distinct.
Help Jessie find the number of possible combinations of coins Bessie could have. Two combinations are considered different if there is some $i \; (1 \le i \le n)$, such that the number of coins Bessie has of type $i$ is different in the two combinations. Since the answer can be very large, output it modulo $1000000007$ ($10^9+7$).
If there are no possible combinations of coins totaling $t$ cents that satisfy Bessie’s conditions, output $0$.

题意概述

你有$n$种纸币,第$i$种纸币的价值为$a_i$(可能有多个$a_i$相等)。已知所有纸币的总价值为$t$。给定$q$对整数$b_i, c_i$,表示第$b_i$种纸币的数量严格大于第$c_i$种纸币的数量。所有$b_i$均不相等,所有$c_i$均不相等。求满足这些条件的方案数。
数据范围:$1 \le n \le 300, \; 1 \le t \le 10^5, \; 1 \le a_i \le 10^5$。

算法分析

将每种硬币看成点,每条限制看成有向边,这样就构成了一张有向图。若这张图中存在环,则方案数为$0$。否则,所有边构成的一定是链。对于一条链上的点$v_1, v_2, \ldots, v_m$,我们将$a_{v_2}$变成$a_{v_1}+a_{v_2}$,将$a_{v_3}$变成$a_{v_1}+a_{v_2}+a_{v_3}$,以此类推。这样做的原因是:如果选了第$v_2$件物品一次,就必须也选第$v_1$件物品一次;如果选了第$v_3$件物品一次,就必须也选第$v_1$和第$v_2$件物品一次。这就变成一个完全背包问题了。注意到完全背包问题中的物品是可以不选的,而在这个问题中有些物品是必须选的。例如,第$v_{m-1}$件物品必须至少选一次,第$v_{m-2}$件物品必须至少选两次(因为题目中要求严格大于)。只需在$t$中减去这些必须选的就可以了。

代码

#include <iostream>
using namespace std;
const long long mod = 1000000007ll;
long long n, q, t, ma, a[301], to[301], f[100001];
bool m[301], in[301], vis[301];
void dfs(long long u, long long d, long long s) {
  ma = d, vis[u] = true;
  if (to[u]) dfs(to[u], d + 1, s + a[u]);
  t -= (ma - d) * a[u], a[u] += s;
}
int main()
{
  cin >> n >> q >> t, f[0] = 1;
  for (int i = 1; i <= n; cin >> a[i], ++i);
  for (int i = 1; i <= q; ++i) {
    long long b, c; cin >> b >> c;
    m[b] = m[c] = true, in[c] = true, to[b] = c;
  }
  for (int i = 1; i <= n; ++i)
    if (m[i] && !in[i]) ma = 0, dfs(i, 0, 0);
  if (t < 0) { cout << 0 << endl; return 0; }
  for (int i = 1; i <= n; ++i)
    if (m[i] && !vis[i]) { cout << 0 << endl; return 0; }
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= t - a[i]; ++j)
      (f[j + a[i]] += f[j]) %= mod;
  cout << f[t] << endl;
  return 0;
}

Cow Program

题目描述

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$, and performs the following operations on a sequence $a_1, a_2, \ldots, a_n$ of positive integers:

  1. Initially, $x=1$ and $y=0$. If, after any step, $x \le 0$ or $x \gt n$, the program immediately terminates.
  2. The program increases both $x$ and $y$ by a value equal to $a_x$ simultaneously.
  3. The program now increases $y$ by $a_x$ while decreasing $x$ by $a_x$.
  4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!
You are given the sequence $a_2, a_3, \ldots, a_n$. Suppose for each $i \; (1 \le i \le n-1)$ we run the program on the sequence $i, a_2, a_3, \ldots, a_n$. For each such run output the final value of $y$ if the program terminates or $-1$ if it does not terminate.

题意概述

有一个包含$n$个数的数列,第$i$项为$a_i$。现有两个数$x=1, \; y=0$。执行以下操作

while (!(x <= 0 || x > n)) {
  y += a[x], x += a[x];
  if (!(x <= 0 || x > n)) y += a[x], x -= a[x];
}

给定$a_2, a_3, \ldots, a_n$,对于所有$i \in [1, n-1]$,求对数列$i, a_2, a_3, \ldots, a_n$执行操作后$y$的值。若无限循环则输出$-1$。
数据范围:$2 \le n \le 2 \times 10^5, \; 1 \le a_i \le 10^9$。

算法分析

直接模拟肯定会超时。易知从一个位置开始执行操作的顺序是固定的,因此可以用记忆化搜索,记录下每一个位置向左或向右执行操作后的$y$值。如果搜索到一个已搜索过但还没有得到答案的位置,则返回$-1$。

代码

#include <iostream>
using namespace std;
long long n, a[300001], ans[300001][2], to[300001][2], vis[300001][2];
long long dfs(long long t, long long m) {
  if (ans[t][m]) return ans[t][m];
  if (vis[t][m]) return ans[t][m] = -1; vis[t][m] = true;
  if (to[t][m] < 1 || to[t][m] > n) return ans[t][m] = a[t];
  long long ret = dfs(to[t][m], !m);
  if (ret == -1) ans[t][m] = -1; else ans[t][m] = a[t] + ret;
  return ans[t][m];
}
int main()
{
  cin >> n, vis[1][1] = true;
  for (int i = 2; i <= n; ++i) cin >> a[i];
  for (int i = 2; i <= n; ++i) to[i][0] = i - a[i], to[i][1] = i + a[i];
  for (int i = 2; i <= n; ++i) if (!ans[i][0]) dfs(i, 0);
  for (int i = 1; i < n; ++i)
    if (ans[i + 1][0] == -1) cout << -1 << endl;
    else cout << i + ans[i + 1][0] << endl;
  return 0;
}

Best Edge Weight

题目描述

You are given a connected weighted graph with $n$ vertices and $m$ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $i$. Let’s determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don’t change the other weights.
You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can’t be two edges with changed weights at the same time.

题意概述

给定一张$n$个点$m$条边的连通无向图,边权均为正数。对于每一条边,询问它的边权至多是多少,使得在其他边权不变的条件下,它在这张图的所有最小生成树中。
数据范围:$2 \le n \le 2 \times 10^5, \; n-1 \le m \le 2 \times 10^5$。

算法分析

题目要求一条边在所有最小生成树中。我们无法求出所有最小生成树,因此先求出其中一棵。这样,图中的边就被分成了两种:一种在这棵最小生成树中,另一种不在这棵最小生成树中。
对于不在这棵最小生成树中的边$(u, v)$,设它的权值为$w$。显然,它和最小生成树上从$u$到$v$的路径构成了一个环。设这条路径上边权的最大值$w_{max}$。如果$w \ge w_{max}$,那么$(u, v)$可能在这张图的一棵最小生成树中,但一定不是所有。因此,可以将$w$设成$w_{max}-1$,因为根据贪心策略,将路径上权值为$w_{max}$的边替换成$(u, v)$,会得到一棵更小的生成树。这种情况很好解决,只要在最小生成树上进行倍增就可以了。
对于在这棵最小生成树中的边$(u, v)$,设它的权值为$w$。假设我们找到了一条不经过这棵最小生成树上的边从$u$到$v$的路径,设这条路径上边权的最小值为$w_{min}$。类似于不在最小生成树的边,如果$w \ge w_{min}$,那么这条边一定不在所有最小生成树中。将它的权值设为$w_{min}-1$,即可满足要求。由于直接求$w_{min}$较为困难,因此可以按边权从小到大枚举不在这棵最小生成树中的边,并用它来更新最小生成树上的一条路径。因为是从小到大枚举,所以最小生成树上的每条边只需要被更新一次,可以用并查集维护。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct line {
  long long u, v, c, id; bool mst;
  bool operator < (const line &a) const { return c < a.c; }
} l[200001];
struct edge {
  long long v, c, id, nxt;
} e[400001];
long long n, m, nume, h[200001], fa[200001], ans[200001];
long long depth[200001], up[200001][20], ma[200001][20], uid[200001];
long long get_fa(long long t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void add_edge(long long u, long long v, long long c, long long id) {
  e[++nume].v = v, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa) {
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa) {
      depth[e[i].v] = depth[t] + 1, up[e[i].v][0] = t;
      ma[e[i].v][0] = e[i].c, uid[e[i].v] = e[i].id, dfs(e[i].v, t);
    }
}
long long get_max(long long u, long long v) {
  long long ret = 0;
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  for (int i = 19; i >= 0; --i)
    if (depth[u] - depth[v] >= (1 << i))
      ret = max(ret, ma[u][i]), u = up[u][i];
  if (u == v) return ret;
  for (int i = 19; i >= 0; --i)
    if (up[u][i] != up[v][i])
      ret = max(ret, max(ma[u][i], ma[v][i])), u = up[u][i], v = up[v][i];
  return max(ret, max(ma[u][0], ma[v][0]));
}
void update(long long u, long long v, long long val) {
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  long long p = u, q = v;
  for (int i = 19; i >= 0; --i)
    if (depth[p] - depth[q] >= (1 << i)) p = up[p][i];
  if (p != q) {
    for (int i = 19; i >= 0; --i)
      if (up[p][i] != up[q][i]) p = up[p][i], q = up[q][i];
    p = up[p][0];
  }
  u = get_fa(u), v = get_fa(v);
  while (depth[u] > depth[p])
    ans[uid[u]] = val - 1, q = get_fa(up[u][0]), fa[u] = q, u = get_fa(u);
  while (depth[v] > depth[p])
    ans[uid[v]] = val - 1, q = get_fa(up[v][0]), fa[v] = q, v = get_fa(v);
}
int main()
{
  cin >> n >> m, memset(ans, -1, sizeof ans);
  if (n == m + 1) {
    for (int i = 1; i <= m; cout << -1 << ' ', ++i); cout << endl; return 0;
  }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; cin >> l[i].u >> l[i].v >> l[i].c, l[i].id = i, ++i);
  sort(l + 1, l + m + 1);
  for (int i = 1; i <= m; ++i) {
    long long u = get_fa(l[i].u), v = get_fa(l[i].v);
    if (u != v) add_edge(l[i].u, l[i].v, l[i].c, l[i].id), fa[u] = v, l[i].mst = true;
  }
  depth[1] = 1, dfs(1, 0);
  for (int i = 1; i < 20; ++i)
    for (int j = 1; j <= n; ++j) {
      up[j][i] = up[up[j][i - 1]][i - 1];
      ma[j][i] = max(ma[j][i - 1], ma[up[j][i - 1]][i - 1]);
    }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; ++i)
    if (!l[i].mst) {
      ans[l[i].id] = get_max(l[i].u, l[i].v) - 1;
      update(l[i].u, l[i].v, l[i].c);
    }
  for (int i = 1; i <= m; cout << ans[i] << ' ', ++i);
  cout << endl;
  return 0;
}

Petya and Tree

题目描述

One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya couldn’t search for elements in this tree. Petya tried many times to choose key and look for it in the tree, and each time he arrived at a wrong place. Petya has been racking his brains for long, choosing keys many times, but the result was no better. But the moment before Petya would start to despair, he had an epiphany: every time he was looking for keys, the tree didn’t have the key, and occured exactly one mistake. “That’s not a problem!”, thought Petya. “Why not count the expectation value of an element, which is found when I search for the key”. The moment he was about to do just that, however, Petya suddenly woke up.
Thus, you are given a binary search tree, that is a tree containing some number written in the node. This number is called the node key. The number of children of every node of the tree is equal either to $0$ or to $2$. The nodes that have $0$ children are called leaves and the nodes that have $2$ children, are called inner. An inner node has the left child, that is the child whose key is less than the current node’s key, and the right child, whose key is more than the current node’s key. Also, a key of any node is strictly larger than all the keys of the left subtree of the node and strictly smaller than all the keys of the right subtree of the node.
Also you are given a set of search keys, all of which are distinct and differ from the node keys contained in the tree. For each key from the set its search in the tree is realised. The search is arranged like this: initially we are located in the tree root, if the key of the current node is larger that our search key, then we move to the left child of the node, otherwise we go to the right child of the node and the process is repeated. As it is guaranteed that the search key is not contained in the tree, the search will always finish in some leaf. The key lying in the leaf is declared the search result.
It is known for sure that during the search we make a mistake in comparing exactly once, that is we go the wrong way, but we won’t make any mistakes later. All possible mistakes are equiprobable, that is we should consider all such searches where exactly one mistake occurs. Your task is to find the expectation (the average value) of the search result for every search key, considering that exactly one mistake occurs in the search. That is, for a set of paths containing exactly one mistake in the given key search, you should count the average value of keys containing in the leaves of those paths.

题意概述

给定一棵包含$n$个节点的二叉搜索树,每个节点都有$0$个或$2$个儿子。如果一个节点有儿子,那么它左子树中的所有节点的值都严格小于这个节点,它右子树中的所有节点的值都严格大于这个节点。由于一些差错,这棵搜索树在查找一个值时总是会犯恰好一次错误——应该往左查找时却往右查找,应该往右查找时却往左查找。现有$k$个树中不存在的值待查找,求每一次查找得到的数的期望。
数据范围:$3 \le n \lt 10^5, \; 1 \le k \le 10^5$。

算法分析

很容易想到暴力的方法:先DFS预处理出每棵子树中的最大值和最小值,接着对于每一个待查找的值,直接在树中查找;若应该往左子树走,则将答案加上右子树中的最小值,否则加上左子树中的最大值,然后往正确的方向走。由于这并不是一棵平衡树,因此最坏情况的时间复杂度为$O(n^2)$。
搜索树中的数将数字划分成了$(n+1)$个区间。对于每一个区间而言,其答案都是一样的。因此,我们可以再进行一次DFS,处理出每个区间的答案。处理方法类似于暴力,但是搜索完一棵子树后需要回溯。最后查找$k$个数时,只需对每个数二分查找属于哪个区间,并输出那个区间的答案。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct node_type {
  long long val, min, max, child[2];
} node[100001];
long long n, k, cnt, times, root, top, id[100001];
double ans[100001];
void dfs(long long t) {
  if (!node[t].child[0]) {
    node[t].min = node[t].max = node[t].val; return;
  }
  dfs(node[t].child[0]), dfs(node[t].child[1]);
  node[t].min = node[node[t].child[0]].min, node[t].max = node[node[t].child[1]].max;
}
void find(long long t) {
  if (!node[t].child[0]) {
    id[top] = node[t].val, ans[top++] = 1.0 * cnt / times; return;
  }
  cnt += node[node[t].child[1]].min, ++times, find(node[t].child[0]), id[top++] = node[t].val;
  cnt += node[node[t].child[0]].max - node[node[t].child[1]].min, find(node[t].child[1]);
  cnt -= node[node[t].child[0]].max, --times;
}
int main()
{
  scanf("%lld", &n);
  for (int i = 1; i <= n; ++i) {
    long long a; scanf("%lld%lld", &a, &node[i].val);
    if (a == -1) root = i;
    else if (!node[a].child[0]) node[a].child[0] = i;
      else {
        node[a].child[1] = i;
        if (node[node[a].child[0]].val > node[node[a].child[1]].val)
          node[a].child[0] ^= node[a].child[1] ^= node[a].child[0] ^= node[a].child[1];
      }
  }
  dfs(root), find(root), scanf("%lld", &k);
  for (int i = top - 2; i >= 0; --i) if (!ans[i]) ans[i] = ans[i + 1];
  while (k--) {
    long long a, l = 0, r = top; scanf("%lld", &a);
    while (l + 1 < r) {
      long long mid = l + r >> 1; if (id[mid] < a) l = mid; else r = mid;
    }
    printf("%.10lf\n", ans[l]);
  }
  return 0;
}

Sum of Medians

题目描述

In one well-known algorithm of finding the $k$-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the middle element of a sorted array (it’s the third largest element for a group of five). To increase the algorithm’s performance speed on a modern video card, you should be able to find a sum of medians in each five of the array.
A sum of medians of a sorted $k$-element set $S={a_1, a_2, \ldots, a_k}$, where $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_k$, will be understood by as $\sum_{i \bmod 5=3} a_i$.
The $\bmod$ operator stands for taking the remainder, that is $x \bmod y$ stands for the remainder of dividing $x$ by $y$.
To organize exercise testing quickly calculating the sum of medians for a changing set was needed.

题意概述

有一个初始为空的集合。有三种操作:①向集合中加入一个元素,保证操作前这个元素不存在;②从集合中删除一个元素,保证操作前这个元素存在;③询问集合中元素排序后下标模$5$余$3$的元素之和。共有$n$次操作。
数据范围:$1 \le n \le 10^5$。

算法分析1

直接用平衡树来维护。对于每个节点储存它子树的大小以及它子树排序后下标模$5$余$0$、余$1$、…、余$4$的元素之和。显然,一个节点的左子树可以直接更新当前节点,而右子树则需根据左子树的大小进行处理后再更新当前节点。

代码1

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
long long n, x;
string o;
struct treap {
  int tot, root;
  struct node_type {
    int child[2], rank;
    long long val, size, mod[5];
  } node[100001];
  void update(int t) {
    node[t].size = node[node[t].child[0]].size + node[node[t].child[1]].size + 1;
    for (int i = 0; i < 5; ++i)
      node[t].mod[i] = node[node[t].child[0]].mod[i] + node[node[t].child[1]].mod[(i + 99999 - node[node[t].child[0]].size) % 5];
    node[t].mod[(node[node[t].child[0]].size + 1) % 5] += node[t].val;
  }
  void rotate(int &t, int dire) {
    int p = node[t].child[!dire];
    node[t].child[!dire] = node[p].child[dire], node[p].child[dire] = t;
    update(t), update(p), t = p;
  }
  void insert(int &t, long long val) {
    if (!t) {
      t = ++tot, node[t].rank = ((rand() & ((1 << 16) - 1)) << 10) ^ rand(), node[t].val = node[t].mod[1] = val, node[t].size = 1;
      return;
    }
    ++node[t].size;
    if (val < node[t].val) {
      insert(node[t].child[0], val);
      if (node[node[t].child[0]].rank > node[t].rank) rotate(t, 1);
    } else {
      insert(node[t].child[1], val);
      if (node[node[t].child[1]].rank > node[t].rank) rotate(t, 0);
    }
    update(t);
  }
  void remove(int &t, long long val) {
    if (!node[t].child[0] && !node[t].child[1]) { t = 0; return; }
    if (val == node[t].val) {
      if (node[node[t].child[0]].rank > node[node[t].child[1]].rank) rotate(t, 1);
      else rotate(t, 0);
    }
    if (val < node[t].val) remove(node[t].child[0], val);
    else remove(node[t].child[1], val);
    update(t);
  }
  long long query() { return node[root].mod[3]; }
} tree;
int main()
{
  srand(time(NULL));
  cin >> n;
  while (n--) {
    cin >> o;
    if (o[0] == 'a') { cin >> x; tree.insert(tree.root, x); }
    else if (o[0] == 'd') { cin >> x; tree.remove(tree.root, x); }
    else cout << tree.query() << endl;
  }
  return 0;
}

算法分析2

将操作离线,并将所有操作数离散化,用线段树来维护离散后的区间。和平衡树类似,对于每个节点储存区间内的元素个数以及区间内的元素排序后下标模$5$余$0$、余$1$、…、余$4$的元素之和。更新操作也大同小异。

Opening Portals

题目描述

Pavel plays a famous computer game. A player is responsible for a whole country and he can travel there freely, complete quests and earn experience.
This country has $n$ cities connected by $m$ bidirectional roads of different lengths so that it is possible to get from any city to any other one. There are portals in $k$ of these cities. At the beginning of the game all portals are closed. When a player visits a portal city, the portal opens. Strange as it is, one can teleport from an open portal to an open one. The teleportation takes no time and that enables the player to travel quickly between rather remote regions of the country.
At the beginning of the game Pavel is in city number $1$. He wants to open all portals as quickly as possible. How much time will he need for that?

题意概述

给定一张$n$个点$m$条边的无向图,其中$k$个点上有传送器,每条边都有一个权值。初始时所有传送器都处于关闭状态,你在$1$号点。你需要走到所有有传送器的点,将传送器打开。你可以从一个已经打开的传送器直接传送到另一个已经打开的传送器。求经过的所有边的权值和的最小值。
数据范围:$1 \le k \le n \le 10^5, \; 0 \le m \le 10^5$。

算法分析

我们假设所有的点都是传送器。根据最小生成树的性质,这时的最优解就是这张图的最小生成树。显然,如果我们把这张图抽象成只由$k$个有传送器的点构成的“传送图”,这时的最优解也就是“传送图”上的最小生成树。如何构造这张图呢?
计算出每个点到离它最近的传送器的位置$p_i$和距离$d_i$。对于一条权值为$w$的边$(u, v)$,我们将它想象一条权值为$(d_u+w+d_v)$的边$(p_u, p_v)$。这样,这张图上的所有边也就变成了连接$k$个传送器的边。这就可以用Kruskal求最小生成树来解决。这棵最小生成树的边权之和是固定的,因此当$1$号点没有传送器时,可以先走到离它最近的一个有传送器的点。
求$p_i$和$d_i$可以用多源SPFA来完成。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long n, m, k, nume, tot, ans, mi = 1e18;
long long h[100001], p[100001], d[100001], fa[100001], pre[100001];
bool in[100001];
struct edge { long long v, w, nxt; } e[200001];
struct line {
  long long u, v, w;
  bool operator < (const line &a) const {
    return d[u] + w + d[v] < d[a.u] + a.w + d[a.v];
  }
} l[200001];
void add_edge(long long u, long long v, long long w) {
  e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void spfa() {
  queue<long long> que;
  while (!que.empty()) que.pop();
  for (int i = 1; i <= n; ++i)
    if (!d[i]) in[i] = true, que.push(i);
  while (!que.empty()) {
    int u = que.front(); in[u] = false, que.pop();
    for (int i = h[u]; i; i = e[i].nxt)
      if (d[e[i].v] > d[u] + e[i].w) {
        d[e[i].v] = d[u] + e[i].w, pre[e[i].v] = pre[u];
        if (!in[e[i].v]) in[e[i].v] = true, que.push(e[i].v);
      }
  }
}
long long get_fa(long long t) {
  return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    long long u, v, w; cin >> u >> v >> w; add_edge(u, v, w);
  }
  memset(d, 0x1f, sizeof d), d[1] = 0, spfa(); cin >> k;
  for (int i = 1; i <= k; ++i) {
    cin >> p[i]; if (d[p[i]] < mi) mi = d[p[i]];
  }
  ans = mi, memset(d, 0x1f, sizeof d);
  for (int i = 1; i <= n; ++i) fa[i] = i, pre[i] = i;
  for (int i = 1; i <= k; ++i) d[p[i]] = 0; spfa();
  for (int i = 1; i <= n; ++i)
    for (int j = h[i]; j; j = e[j].nxt)
      l[++tot].u = i, l[tot].v = e[j].v, l[tot].w = e[j].w;
  sort(l + 1, l + tot + 1);
  for (int i = 1; i <= tot; ++i) {
    long long u = get_fa(pre[l[i].u]), v = get_fa(pre[l[i].v]);
    if (u != v) fa[u] = v, ans += d[l[i].u] + l[i].w + d[l[i].v];
  }
  cout << ans << endl;
  return 0;
}

DZY Loves Fibonacci Numbers

题目描述

In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:
$$F_1=1, \; F_2=1, \; F_n=F_{n-1}+F_{n-2} \; (n \gt 2)$$
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of $n$ integers: $a_1, a_2, \ldots, a_n$. Moreover, there are $m$ queries, each query has one of the two types:

  • Format of the query “1 $l$ $r$”. In reply to the query, you need to add $F_{i-l+1}$ to each element $a_i$, where $l \le i \le r$.
  • Format of the query “2 $l$ $r$”. In reply to the query you should output the value of $\sum_{i=l}^r a_i$ modulo $1000000009$ ($10^9+9$).

Help DZY reply to all the queries.

题意概述

给定一个长度为$n$的数列,第$i$个数为$a_i$。有两种操作:①对于$i \in [l, r]$,将$a_i$加上$F_{i-l+1}$;②询问区间$[l, r]$内的数字之和。其中$F_i$表示Fibonacci数列的第$i$项。操作有$m$次。
数据范围:$1 \le n, m \le 3 \times 10^5, \; 1 \le a_i \le 10^9$。

算法分析

在一个Fibonacci数列上加一个Fibonacci数列,其结果仍然是Fibonacci数列。而对于一个Fibonacci数列,只要知道前两个数,就能知道接下来的所有数。可以用线段树来维护,对于每一个节点记录下区间和,以及可以代表这个区间上Fibonacci数列的前两个数。设前两个数分别为$a, b$,预处理出Fibonacci数列每一项$a$和$b$的系数,即可在$O(1)$时间内计算出Fibonacci数列的任意一项。其前缀和亦然。

代码

#include <cstdio>
#include <iostream>
using namespace std;
const long long mod = 1000000009ll;
struct node_type {
  long long l, r, val[2], sum, child[2];
} node[1000001];
long long n, m, o, l, r, tot = 1, a[300001], x[300001][2], y[300001][2];
void build_tree(int root) {
  if (node[root].l == node[root].r) return; long long mid = node[root].l + node[root].r >> 1;
  node[++tot].l = node[root].l, node[tot].r = mid, node[root].child[0] = tot, build_tree(tot);
  node[++tot].l = mid + 1, node[tot].r = node[root].r, node[root].child[1] = tot, build_tree(tot);
}
void push_down(int root) {
  if (node[root].l == node[root].r || node[root].val[0] == 0 && node[root].val[1] == 0) return;
  if (node[node[root].child[0]].l == node[node[root].child[0]].r) node[node[root].child[0]].sum += node[root].val[0];
  else {
    (node[node[root].child[0]].val[0] += node[root].val[0]) %= mod, (node[node[root].child[0]].val[1] += node[root].val[1]) %= mod;
    node[node[root].child[0]].sum += y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][0] * node[root].val[0] % mod;
    node[node[root].child[0]].sum += y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][1] * node[root].val[1] % mod;
  }
  long long p = (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][0] * node[root].val[0] + x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][1] * node[root].val[1]) % mod;
  long long q = (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][0] * node[root].val[0] + x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][1] * node[root].val[1]) % mod;
  if (node[node[root].child[1]].l == node[node[root].child[1]].r) node[node[root].child[1]].sum += p;
  else {
    (node[node[root].child[1]].val[0] += p) %= mod, (node[node[root].child[1]].val[1] += q) %= mod;
    node[node[root].child[1]].sum += y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][0] * p % mod;
    node[node[root].child[1]].sum += y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][1] * q % mod;
  }
  node[root].val[0] = node[root].val[1] = 0;
}
void push_up(int root) {
  if (node[root].l == node[root].r) return;
  node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum;
}
void insert_line(int root, int l, int r, int val) {
  if (node[root].r < l || node[root].l > r) return;
  if (node[root].l >= l && node[root].r <= r) {
    if (node[root].l == node[root].r) node[root].sum += x[val][0] + x[val][1];
    else {
      (node[root].val[0] += x[val][0] + x[val][1]) %= mod;
      (node[root].val[1] += x[val + 1][0] + x[val + 1][1]) %= mod;
      node[root].sum += y[node[root].r - node[root].l + 1][0] * (x[val][0] + x[val][1]) % mod;
      node[root].sum += y[node[root].r - node[root].l + 1][1] * (x[val + 1][0] + x[val + 1][1]) % mod;
    }
    return;
  }
  push_down(root);
  insert_line(node[root].child[0], l, r, val);
  insert_line(node[root].child[1], l, r, max(1ll, val + node[node[root].child[1]].l - max((long long) l, node[node[root].child[0]].l)));
  push_up(root);
}
long long get_sum(int root, int l, int r) {
  if (node[root].r < l || node[root].l > r) return 0;
  if (node[root].l >= l && node[root].r <= r) return node[root].sum;
  long long ret;
  push_down(root);
  ret = get_sum(node[root].child[0], l, r) + get_sum(node[root].child[1], l, r);
  push_up(root);
  return ret;
}
int main()
{
  scanf("%lld%lld", &n, &m);
  x[1][0] = x[2][1] = y[1][0] = y[2][0] = y[2][1] = 1;
  for (int i = 3; i <= n; ++i) {
    x[i][0] = (x[i - 1][0] + x[i - 2][0]) % mod;
    x[i][1] = (x[i - 1][1] + x[i - 2][1]) % mod;
    y[i][0] = (y[i - 1][0] + x[i][0]) % mod;
    y[i][1] = (y[i - 1][1] + x[i][1]) % mod;
  }
  node[1].l = 1, node[1].r = n, build_tree(1);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] += a[i - 1];
  while (m--) {
    scanf("%lld%lld%lld", &o, &l, &r);
    if (o == 1) insert_line(1, l, r, 1);
    else printf("%lld\n", ((get_sum(1, l, r) + a[r] - a[l - 1]) % mod + mod) % mod);
  }
  return 0;
}

DZY Loves Modification

题目描述

As we know, DZY loves playing games. One day DZY decided to play with a $n \times m$ matrix. To be more precise, he decided to modify the matrix with exactly $k$ operations.
Each modification is one of the following:

  • Pick some row of the matrix and decrease each element of the row by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
  • Pick some column of the matrix and decrease each element of the column by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.

DZY wants to know: what is the largest total value of pleasure he could get after performing exactly $k$ modifications? Please, help him to calculate this value.

题意概述

给定一个$n \times m$的矩阵,每次可以从这个矩阵中选取一行或一列,将这一行或一列的数字之和加到你的分数上,再将这一行或一列上的每个数字减去$p$。共进行$k$次操作,求分数的最大值。
数据范围:$1 \le n, m \le 1000, \; 1 \le k \le 10^6, \; 1 \le p \le 100$。

算法分析

可以发现交换操作顺序对答案没有影响。因此,可以先计算出只取$i$行可以得到的最大值以及只取$j$列可以得到的最大值,根据贪心策略,可以用优先队列维护一行或一列的数字之和。接着枚举取了$i$行,那么也就取了$(k-i)$列,减去重复部分,取最大值,即可得到答案。

代码

#include <iostream>
#include <queue>
using namespace std;
priority_queue<long long> r, c;
long long n, m, k, p, s, t, ans = -1e18, a[1001][1001], rr[1000001], cc[1000001];
int main()
{
  cin >> n >> m >> k >> p;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> a[i][j];
  for (int i = 1; i <= n; ++i) {
    long long s = 0;
    for (int j = 1; j <= m; ++j) s += a[i][j];
    r.push(s);
  }
  for (int j = 1; j <= m; ++j) {
    long long s = 0;
    for (int i = 1; i <= n; ++i) s += a[i][j];
    c.push(s);
  }
  for (int i = 1; i <= k; ++i) {
    long long u = r.top(); r.pop();
    rr[i] = rr[i - 1] + u;
    r.push(u - p * m);
    u = c.top(); c.pop();
    cc[i] = cc[i - 1] + u;
    c.push(u - p * n);
  }
  for (int i = 0; i <= k; ++i) ans = max(ans, rr[i] + cc[k - i] - p * i * (k - i));
  cout << ans << endl;
  return 0;
}