Recover Path

题目描述

Traveller Gregory is famous for his ability to always choose the shortest path for his journey. Ostap is a journalist who seeks for information about the recent Gregory’s trip. He managed to get the evidence that during this trip Gregory visited a number of cities. However, there is no information about the order in which they were visited, and no information about the starting city and the ending city of Gregory’s trip (the entire trip is (one of) the shortest path between these cities). Help Ostap to find any shortest path that contains all specified cities.
Country in which Gregory traveled consists of $n$ cities and $m$ undirected roads between them. For each road Ostap knows the time it takes to travel it, and the “shortest” word above is with respect to those times.
It is guaranteed that there exists some shortest path going through all specified cities.

题意概述

给定一张$n$个点$m$条边的无向图,第$i$条边的权值为$t_i$。给定其中$k$个点,要求找一对点$s, t$,使得这$k$个点都在从$s$到$t$的某条最短路径上,并输出这条路径。保证有解。
数据范围:$1 \le n, m \le 10^5, \; 1 \le t_i \le 10000$。

算法分析

显然,存在一种方案使得$s, t$在给定的$k$个点中。
从$k$个点中任选一个点,找到在$k$个点中距离它最远的点$u$,这个点一定是$s$或$t$,可以用反证法证明。接着从$u$开始跑最短路,得到一张拓扑图。令$f_i$表示从$i$到$u$的最短路径上最多包含多少个$k$个点中的点。只要按距离从小到大枚举$i$,再枚举它的连边是否可以作为最短路径中的边。同时还要记录方案。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne = 1, top, h[N], d[N], que[N], id[N], lst[N], pre[N], ans[N];
bool in[N], v[N];
struct Edge {
  int u, v, w, nxt;
} e[N << 1];

void add_edge(int u, int v, int w) {
  e[++ne] = (Edge){u, v, w, h[u]}, h[u] = ne;
  e[++ne] = (Edge){v, u, w, h[v]}, h[v] = ne;
}

void spfa(int s) {
  int qb = 0, qe = 1;
  memset(d, 0x3f, sizeof d), d[s] = 0, que[0] = s, in[s] = 1;
  for (; qb != qe;) {
    int u = que[qb++];
    in[u] = 0, qb == N && (qb = 0);
    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;
        if (!in[e[i].v]) {
          if (qb == qe || d[e[i].v] > d[que[qb]])
            que[qe++] = e[i].v, in[e[i].v] = 1, qe == N && (qe = 0);
          else
            !~--qb && (qb = N - 1), que[qb] = e[i].v, in[e[i].v] = 1;
        }
      }
  }
}

int main() {
  int n, m, k, t;
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v, w; i <= m; ++i)
    scanf("%d%d%d", &u, &v, &w), add_edge(u, v, w);
  scanf("%d%d", &k, &t), v[t] = 1, spfa(t);
  int s = t;
  for (int i = 2; i <= k; ++i)
    scanf("%d", &t), v[t] = 1, d[s] < d[t] && (s = t);
  spfa(s);
  for (int i = 1; i <= n; ++i)
    id[i] = i;
  std::sort(id + 1, id + n + 1, [&](int const &i, int const &j) { return d[i] < d[j]; });
  for (int i : id) {
    lst[i] += v[i];
    for (int j = h[i]; j; j = e[j].nxt)
      if (d[e[j].v] == d[i] + e[j].w && lst[e[j].v] < lst[i])
        lst[e[j].v] = lst[i], pre[e[j].v] = j;
  }
  for (int i = 1; i <= n; ++i)
    if (lst[i] == k) {
      for (int j = pre[i]; j; j = pre[e[j].u])
        ans[top++] = j >> 1;
      break;
    }
  printf("%d\n", top);
  for (int i = 0; i < top; ++i)
    printf("%d ", ans[i]);
  puts("");
  return 0;
}

Chess Championship

题目描述

Chess Championship is set up in the New Basyuki City. Two national teams, of Berland and Byteland, are going to have a match there. Each team is represented by $n$ players. The championship consists of $n$ games – in each game a pair of players from different teams meets. A game victory brings $1$ point to the team and a game defeat doesn’t add or subtract points.
The championship starts with the sortition – the process that determines opponent pairs. Each player from the first team plays with exactly one player from the second team (and vice versa).
A recent research conducted by Berland scientists showed that every player of either team is characterized by a single number – the level of his chess mastership. No two people among the $2n$ players play at the same level. Funny as it is, the game winner always is the player with the higher level.
The contest organizers received information that a high-ranking Berland official Mr. B. bet $100500$ burles on the victory of his team with a $k$ points gap. Immediately an unofficial “recommendation” came from very important people to “organize” the sortition so that the Berland team gets exactly $k$ points more than the Byteland team.
Write a program that finds the number of distinct sortition results after which Berland gets exactly $k$ points more than Byteland. Two sortitions are considered distinct if there is such player, that gets different opponents by the sortitions’ results.

题意概述

给定两组数$a_i, b_i$,每组$n$个数。保证所有$a_i, b_i$中不会出现相同的数。求有多少个排列$p$满足$\sum_{i=1}^n [a_i \gt b_{p_i}]-\sum_{i=1}^n [a_i \lt b_{p_i}]=k$。
数据范围:$1 \le k \le n \le 500$。

算法分析

当$k \not \equiv n \pmod 2$时,排列不存在。
将所有数从小到大排序。令$f_{i, j, k}$表示在前$i$个数中,有$j$个$a$中的数匹配了$b$中比它小的数,有$k$个$b$中的数匹配了$a$中比它小的数的方案数。转移时只要计算前$i$个数中两组分别有几个数未匹配,枚举第$i$个数是否匹配另一组中比它小的数。最后的答案就是$f_{2n, {n+k \over 2}, {n-k \over 2}}$。
需要滚动数组。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 505;
static int const MOD = 1000000009;
int f[2][N][N];
std::pair<int, int> a[N << 1];

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  if ((n & 1) != (k & 1))
    return puts("0"), 0;
  for (int i = 0; i < n; ++i)
    scanf("%d", &a[i].first);
  for (int i = n; i < n << 1; ++i)
    scanf("%d", &a[i].first), a[i].second = 1;
  std::sort(a, a + (n << 1));
  int cur = 0, s[2] = {0, 0};
  f[0][0][0] = 1;
  for (int i = 0; i < n << 1; ++i, cur ^= 1) {
    for (int j = 0; j <= n; ++j)
      for (int k = 0; j + k <= n; ++k)
        if (f[cur][j][k]) {
          (f[!cur][j][k] += f[cur][j][k]) %= MOD;
          int c[2] = {s[0] - j - k, s[1] - j - k};
          (f[!cur][j + !a[i].second][k + a[i].second] += 1ll * f[cur][j][k] * c[!a[i].second] % MOD) %= MOD;
          f[cur][j][k] = 0;
        }
    ++s[a[i].second];
  }
  printf("%d\n", f[cur][n + k >> 1][n - k >> 1]);
  return 0;
}

Gena vs Petya

题目描述

Gena and Petya love playing the following game with each other. There are $n$ piles of stones, the $i$-th pile contains $a_i$ stones. The players move in turns, Gena moves first. A player moves by choosing any non-empty pile and taking an arbitrary positive number of stones from it. If the move is impossible (that is, all piles are empty), then the game finishes and the current player is considered a loser.
Gena and Petya are the world famous experts in unusual games. We will assume that they play optimally.
Recently Petya started to notice that Gena wins too often. Petya decided that the problem is the unjust rules as Gena always gets to move first! To even their chances, Petya decided to cheat and take and hide some stones before the game begins. Since Petya does not want Gena to suspect anything, he will take the same number of stones $x$ from each pile. This number $x$ can be an arbitrary non-negative integer, strictly less that the minimum of $a_i$ values.
Your task is to find the number of distinct numbers $x$ such that Petya will win the game.

题意概述

给定$n$个正整数$a_i$,求有多少个非负整数$x$,满足$x$小于所有给定的数,且所有给定的数减去$x$之后的异或和为$0$。
数据范围:$1 \le n \le 2 \times 10^5, \; 1 \le a_i \le 10^{18}$。

算法分析

Nim游戏后手胜利的条件是所有数的异或和为$0$。
枚举$x$显然不可行。可以尝试从低位到高位依次确定。
考虑低位对高位的影响,易知只有当低位退位时才会改变高位。而对于每一位,若此位上有偶数个$0$,则此位可以填$1$,若有偶数个$1$则可以填$0$(这样才能使得异或和为$0$)。
令$f_{i, j}$表示从低到高处理到第$i$位时,有$j$个数字在第$(i+1)$位退位的方案数。根据退位的性质,这$j$个数字一定是所有给定的数按后$i$位从小到大排序后的前$j$个。可以在枚举$i$的同时基数排序,枚举$j$的同时维护第$i$位上$0$和$1$的个数(会受退位影响),若满足条件则转移(注意此位填$1$时还要考虑此位$0$的退位)。
最后需要特判一下$x$不能等于所有给定的数中最小的数。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 200005;
static int const M = 65;
int a[N], cnt[M], f[M][N], s[2][N];

signed main() {
  int n;
  scanf("%lld", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld", a + i);
    for (int j = 0; j < M; ++j)
      cnt[j] += a[i] >> j & 1;
  }
  f[0][0] = 1;
  for (int i = 0; i < M - 1; ++i) {
    int c0 = n - cnt[i], c1 = cnt[i], c = 0;
    for (int j = 0; j <= n; ++j) {
      if (j)
        if (a[j - 1] >> i & 1)
          ++c0, --c1;
        else
          --c0, ++c1, ++c;
      if (!(c0 & 1))
        f[i + 1][c + c0] += f[i][j];
      if (!(c1 & 1))
        f[i + 1][c] += f[i][j];
    }
    *s[0] = *s[1] = 0;
    for (int j = 0; j < n; ++j)
      s[a[j] >> i & 1][++*s[a[j] >> i & 1]] = a[j];
    for (int j = 1; j <= *s[0]; ++j)
      a[j - 1] = s[0][j];
    for (int j = 1; j <= *s[1]; ++j)
      a[*s[0] + j - 1] = s[1][j];
  }
  int sum = 0;
  for (int i = 1; i < n; ++i)
    sum ^= a[i] - a[0];
  printf("%lld\n", f[M - 1][0] - (sum == 0));
  return 0;
}

Kyoya and Train

题目描述

Kyoya Ootori wants to take the train to get to school. There are $n$ train stations and $m$ one-way train lines going between various stations. Kyoya is currently at train station $1$, and the school is at station $n$. To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after $t$ time units, he will have to pay a fine of $x$.
Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line $i$ has ticket cost $c_i$, and a probability distribution $p_{i, k}$ which denotes the probability that this train will take $k$ time units for all $1 \le k \le t$. Amounts of time that each of the trains used by Kyouya takes are mutually independent random values (moreover, if Kyoya travels along the same train more than once, it is possible for the train to take different amounts of time and those amounts are also independent one from another).
Kyoya wants to get to school by spending the least amount of money in expectation (for the ticket price plus possible fine for being late). Of course, Kyoya has an optimal plan for how to get to school, and every time he arrives at a train station, he may recalculate his plan based on how much time he has remaining. What is the expected cost that Kyoya will pay to get to school if he moves optimally?

题意概述

有$n$座城市和$m$条铁路,第$i$条铁路从$a_i$号城市出发,到达$b_i$号城市,票价为$c_i$。某人要在$t$个单位时间内从$1$号城市到$n$号城市,如果超过时间就会被罚款$x$。已知每次搭乘第$i$条铁路有$p_{i, k}$的概率需要$k \; (1 \le k \le t)$个单位时间。求在采取最优策略的情况下总花费的期望。
数据范围:$2 \le n \le 50, \; 1 \le m \le 100, \; 1 \le t \le 20000, \; 0 \le x \le 10^6$。

算法分析

首先考虑最暴力的DP。令$f_{i, j}$表示当前时刻为$j$,在最优策略下从$i$号城市到$n$号城市的总花费的期望。那么
$$
f_{i, j}=
\begin{cases}
\min(c_e+\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k} \mid e \in [1, m] \land a_e=i), & i \lt n \land j \le t \\
d_{i, n}+x , & i \lt n \land j \gt t \\
0, & i=n \land j \le t \\
x, & i=n \land j \gt t
\end{cases}
$$
第二部分中的$d_{i, n}$表示在只考虑铁路票价的情况下从$i$号城市到$n$号城市的最小花费(因为已经超时了,所以不如走总票价最少的路)。
这样做的复杂度是$O(mt^2)$的,需要对它进行优化。令
$$S_{e, j}=\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k}$$
转移方程的第一部分变为
$$f_{i, j}=\min(c_e+S_{e, j} \mid e \in [1, m] \land a_e=i)$$
对于$S$,它类似于卷积,可以将其中一部分翻转后用FFT求值;对于$f$,可以用CDQ分治,统计较大的$j$对较小的$j$的贡献。
具体来说,假设我们要计算$l \le j \le r$的$f_{i, j}$,令$mid=\lfloor {l+r \over 2} \rfloor$,那么先计算$mid \lt j \le r$的$f_{i, j}$,用这些来更新$l \le j \le mid$的$S_{e, j}$($m$条边分别用FFT更新,复杂度$O(m(r-l)\log (r-l))$),最后计算$l \le j \le mid$的$f_{i, j}$。当$l=r$时$f$可以直接由$S$得到。总复杂度降至$O(mt\log^2t)$。
实现时细节很多,要注意DP边界条件和FFT下标变换。

代码

/*
 * Your nature demands love and your happiness depends on it.
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 55;
static int const M = 105;
static int const T = 100000;
static double const PI = acos(-1);
int rev[T];

class Point {
public:
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  std::pair<double, double> pair() {
    return std::make_pair(x, y);
  }
  friend Point operator+(Point const &a, Point const &b) {
    return Point(a.x + b.x, a.y + b.y);
  }
  friend Point operator-(Point const &a, Point const &b) {
    return Point(a.x - b.x, a.y - b.y);
  }
  friend Point operator*(Point const &a, Point const &b) {
    return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
  }
  Point operator/(double const &n) {
    return Point(x / n, y / n);
  }
} wn[T], A[T], B[T];

int init(int n) {
  int m = n, l = 0;
  for (n = 1; n <= m; n <<= 1, ++l)
    ;
  for (int i = 1; i < n; ++i)
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
  for (int i = 0; i < n >> 1; ++i)
    wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
  return n;
}

void fft(Point *a, int n, int inv = 0) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i])
      std::swap(a[i], a[rev[i]]);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i << 1)
      for (int k = 0; k < i; ++k) {
        Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
        a[j + k] = x + y, a[j + k + i] = x - y;
      }
  if (inv) {
    std::reverse(a + 1, a + n);
    for (int i = 0; i < n; ++i)
      a[i] = a[i] / n;
  }
}

int n, m, t, x, mp[N][N];
double p[M][T], s[M][T], f[N][T];
struct Line {
  int a, b, c;
} li[M];

void update(int l, int r) {
  int mid = l + r >> 1, len = init(r - l + r - mid - 2);
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j < len; ++j)
      A[j] = B[j] = 0;
    for (int j = mid + 1; j <= r; ++j)
      A[j - mid - 1] = f[li[i].b][r - j + mid + 1];
    for (int j = 1; j <= r - l; ++j)
      B[j - 1] = p[i][j];
    fft(A, len), fft(B, len);
    for (int j = 0; j < len; ++j)
      A[j] = A[j] * B[j];
    fft(A, len, 1);
    for (int j = l; j <= mid; ++j)
      s[i][j] += A[r - j - 1].x;
  }
}

void solve(int l, int r) {
  if (l == r) {
    for (int i = 1; i <= m; ++i)
      f[li[i].a][l] = std::min(f[li[i].a][l], s[i][l] + li[i].c);
    return;
  }
  int mid = l + r >> 1;
  solve(mid + 1, r), update(l, r), solve(l, mid);
}

int main() {
  scanf("%d%d%d%d", &n, &m, &t, &x);
  memset(mp, 0x3f, sizeof mp);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &li[i].a, &li[i].b, &li[i].c);
    mp[li[i].a][li[i].b] = std::min(mp[li[i].a][li[i].b], li[i].c);
    for (int j = 1; j <= t; ++j)
      scanf("%lf", &p[i][j]), p[i][j] /= 100000;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      for (int k = 1; k <= n; ++k)
        mp[j][k] = std::min(mp[j][k], mp[j][i] + mp[i][k]);
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= t << 1; ++j)
      if (i == n)
        if (j <= t)
          f[i][j] = 0;
        else
          f[i][j] = x;
      else
        if (j <= t)
          f[i][j] = 1e9;
        else
          f[i][j] = x + mp[i][n];
  update(0, t << 1), solve(0, t), printf("%.8lf\n", f[1][0]);
  return 0;
}

Picnic Cows

题目描述

It’s summer vocation now. After tedious milking, cows are tired and wish to take a holiday. So Farmer Carolina considers having a picnic beside the river. But there is a problem, not all the cows consider it’s a good idea! Some cows like to swim in West Lake, some prefer to have a dinner in Shangri-la, and others want to do something different. But in order to manage expediently, Carolina coerces all cows to have a picnic!
Farmer Carolina takes her $N$ cows to the destination, but she finds every cow’s degree of interest in this activity is so different that they all loss their interests. So she has to group them to different teams to make sure that every cow can go to a satisfied team. Considering about the security, she demands that there must be no less than $T$ cows in every team. As every cow has its own interest degree of this picnic, we measure this interest degree’s unit as “Moo~“. Cows in the same team should reduce their Moo~ to the one who has the lowest Moo~ in this team – It’s not a democratical action! So Carolina wishes to minimize the TOTAL reduced Moo~s and groups $N$ cows into several teams.
For example, Carolina has $7$ cows to picnic and their Moo~ are ‘$8 \; 5 \; 6 \; 2 \; 1 \; 7 \; 6$’ and at least $3$ cows in every team. So the best solution is that cow No. $2, 4, 5$ in a team (reduce $((2-1)+(5-1))$ Moo~) and cow No. $1, 3, 6, 7$ in a team (reduce $((7-6)+(8-6))$ Moo~), the answer is $8$.

题意概述

有$N$头牛,每头牛有一个快乐值。要将牛分成若干组,使得每组至少有$T$头牛。分在一组中的牛的快乐值都会变成那组中最小的快乐值。求分组前后总快乐值之差的最小值。
数据范围:$1 \lt T \le N \le 4 \times 10^5$。

算法分析

将牛的快乐值$a_i$从小到大排序。根据贪心策略,一定存在最优分组方案是将排序后的牛分成若干连续段。
令$f_i$表示排序后前$i$头牛分组前后总快乐值之差的最小值,$s_i=\sum_{j=1}^i a_j$,$b_i=a_{i+1}$。可以得到转移方程
$$f_i=\min(f_j+(s_i-s_j)-(i-j)b_j \mid i-j \ge T)$$
假设$k \lt j \lt i$,且决策$j$比决策$k$更优,那么
$$
\begin{align}
f_j+(s_i-s_j)-(i-j)b_j &\le f_k+(s_i-s_k)-(i-k)b_k \\
(f_j-s_j+j \cdot b_j)-(f_k-s_k+k \cdot b_k) &\le i(b_j-b_k)
\end{align}
$$
$i$单调递增,因此可以斜率优化。但要注意两点:当$i-j \lt T$时$f_j$不能转移到$f_i$;当$i \lt T$时$f_i$没有意义。

代码

/*
 * You attempt things that you do not even plan because of your extreme
 * stupidity.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 400005;
int a[N], f[N], s[N], b[N], que[N];

int dety(int i, int j) {
  return f[j] - s[j] + b[j] * j - (f[i] - s[i] + b[i] * i);
}

int detx(int i, int j) { return b[j] - b[i]; }

signed main() {
  for (int n, k; ~scanf("%lld%lld", &n, &k);) {
    for (int i = 1; i <= n; ++i)
      scanf("%lld", &a[i]);
    std::sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
      s[i] = s[i - 1] + a[i], b[i - 1] = a[i];
    int qb = 0, qe = 1;
    que[0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (; qb + 1 < qe &&
             dety(que[qb], que[qb + 1]) <= i * detx(que[qb], que[qb + 1]);
           ++qb)
        ;
      f[i] = f[que[qb]] + s[i] - s[que[qb]] - b[que[qb]] * (i - que[qb]);
      if (i - k + 1 >= k) {
        for (;
             qb + 1 < qe &&
             dety(que[qe - 2], que[qe - 1]) * detx(que[qe - 1], i - k + 1) >=
                 dety(que[qe - 1], i - k + 1) * detx(que[qe - 2], que[qe - 1]);
             --qe)
          ;
        que[qe++] = i - k + 1;
      }
    }
    printf("%lld\n", f[n]);
  }
  return 0;
}

Print Article

题目描述

Zero has an old printer that doesn’t work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has $N$ words, and each word $i$ has a cost $C_i$ to be printed. Also, Zero know that print $k$ words in one line will cost
$$\left(\sum_{i=1}^k C_i\right)^2+M$$
$M$ is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

题意概述

一篇文章中有$N$个单词,输入第$i$个单词的代价为$C_i$。将连续$k$个单词排在一行的总代价为$\left(\sum_{i=1}^k C_i\right)^2+M$。求输入这篇文章的最小代价。
数据范围:$0 \le N \le 5 \times 10^5, \; 0 \le M \le 1000$。

算法分析

令$f_i$表示输入前$i$个单词的最小代价,$s_i=\sum_{j=1}^i C_j$。考虑第$i$个单词的所在行,可以得到转移方程
$$f_i=\min(f_j+(s_i-s_j)^2+M)$$
假设$k \lt j \lt i$,且$j$这个决策更优,即
$$f_j+(s_i-s_j)^2+M \le f_k+(s_i-s_k)^2+M$$
化简得
$$
\begin{align}
f_j-2s_is_j+s_j^2 &\le f_k-2s_is_k+s_k^2 \\
f_j+s_j^2-(f_k+s_k^2) &\le 2s_i(s_j-s_k) \\
{f_j+s_j^2-(f_k+s_k^2) \over 2s_j-2s_k} &\le s_i
\end{align}
$$
也就是说,在满足这个不等式时,对于状态$i$,决策$j$比决策$k$更优。
我们知道$s_i$单调不递减,即如果对于状态$i_0$,$k \lt j \lt i$且决策$j$更优,那么对于状态$i_1 \gt i_0$,决策$j$也一定更优,因此我们可以抛弃决策$k$。
对于每个$i$,假设平面中有点$(2s_i, f_i+s_i^2)$。对于不等式左侧这个东西,把它看成平面直角坐标系里直线的斜率。由于要最小化$f_i$,因此需要找到一个$k$使得不存在$k \lt j \lt i$满足不等式。可以发现我们只要用单调队列维护前$(i-1)$个点的下凸壳(斜率单调递增)。这样时间复杂度就是$O(N)$的了。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 500005;
int a[N], s[N], f[N], que[N];

int detx(int i, int j) { return s[j] - s[i] << 1; }

int dety(int i, int j) { return f[j] + s[j] * s[j] - f[i] - s[i] * s[i]; }

int main() {
  for (int n, m; ~scanf("%d%d", &n, &m);) {
    for (int i = 1; i <= n; ++i)
      scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
      s[i] = s[i - 1] + a[i];
    int qb = 0, qe = 1;
    for (int i = 1; i <= n; ++i) {
      for (; qb + 1 < qe &&
             dety(que[qb], que[qb + 1]) <= s[i] * detx(que[qb], que[qb + 1]);
           ++qb)
        ;
      f[i] = f[que[qb]] + (s[i] - s[que[qb]]) * (s[i] - s[que[qb]]) + m;
      for (; qb + 1 < qe &&
             dety(que[qe - 2], que[qe - 1]) * detx(que[qe - 1], i) >=
                 dety(que[qe - 1], i) * detx(que[qe - 2], que[qe - 1]);
           --qe)
        ;
      que[qe++] = i;
    }
    printf("%d\n", f[n]);
  }
  return 0;
}

The Child and Binary Tree

题目描述

Our child likes computer science very much, especially he likes binary trees.
Consider the sequence of $n$ distinct positive integers: $c_1, c_2, \ldots, c_n$. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex $v$, the weight of $v$ is in the set ${c_1, c_2, \ldots, c_n}$. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices’ weights.
Given an integer $m$, can you for all $s \; (1 \le s \le m)$ calculate the number of good vertex-weighted rooted binary trees with weight $s$? Please, check the samples for better understanding what trees are considered different.
We only want to know the answer modulo $998244353$ ($7 \times 17 \times 2^{23}+1$, a prime number).

题意概述

有$n$种点,每种点有无限个,第$i$种点的权值为$c_i$。定义一棵二叉树的权值等于它所有点的权值之和。求对于所有$s \in [1, m]$,权值为$s$的二叉树有几棵。两棵二叉树不同当且仅当它们左子树或右子树不同,或者根节点权值不同。
数据范围:$1 \le n, m, c_i \le 10^5$。

算法分析

令$f(x)$表示权值为$x$的二叉树个数,$F(x)$为其生成函数($F(x)=\sum_{i \ge 0} f(i)x^i$)。
令$C(x)$为给定$c$的集合的生成函数($C(x)=\sum_{i=1}^n x^{c_i}$)。
根据DP转移方程,易知
$$
f(x)=\sum_{w \in {c_1, c_2, \ldots, c_n}} \sum_{i=0}^{x-w} f(i)f(x-w-i)
$$

$$
F(x)=C(x)F(x)^2+1
$$
解得
$$
F(x)={1 \pm \sqrt{1-4C(x)} \over 2C(x)}={2 \over 1 \pm \sqrt{1-4C(x)}}
$$
显然,若取减号,则当$x$趋近$0$时分母为$0$,因此只能取加号。接着就是多项式开根和多项式求逆了。

  • 多项式求逆:
    求$GF \equiv 1 \pmod {x^n}$。

    假设已知$G_0F \equiv 1 \pmod {x^{\lceil n/2 \rceil}}$
    $G-G_0 \equiv 0 \pmod {x^{\lceil n/2 \rceil}}$
    $G^2-2GG_0+G_0^2 \equiv 0 \pmod {x^n}$
    $G-2G_0+G_0^2F \equiv 0 \pmod {x^n}$
    $G \equiv 2G_0-G_0^2F \pmod {x^n}$

  • 多项式开根:
    求$G^2 \equiv F \pmod {x^n}$。

    假设已知$G_0^2 \equiv F \pmod {x^{\lceil n/2 \rceil}}$
    $(G_0^2-F)^2 \equiv 0 \pmod {x^n}$
    $(G_0^2+F)^2 \equiv 4G_0^2F \pmod {x^n}$
    $\left({G_0^2+F \over 2G_0}\right)^2 \equiv F \pmod {x^n}$
    $G \equiv {G_0+G_0^{-1}F \over 2} \pmod {x^n}$

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static const int N = 500000;
static const int MOD = 998244353;
static const int G = 3;
static const int INV2 = 499122177;
int n, m, c[N], C[N], rev[N], wn[N], tmp[N], tmp2[N], tmp3[N];

int power(int a, int b) {
  int ret = 1;
  for (a %= MOD, b %= MOD - 1; b; b >>= 1)
    b & 1 && (ret = 1ll * ret * a % MOD), a = 1ll * a * a % MOD;
  return ret;
}

void init(int &n) {
  int m = n << 1, l = 0;
  for (n = 1; n < m; n <<= 1, ++l)
    ;
  for (int i = 1; i < n; ++i)
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << (l - 1);
}

void ntt(int *a, int n, bool inv) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i])
      std::swap(a[i], a[rev[i]]);
  wn[0] = 1, wn[1] = power(G, (MOD - 1) / n);
  for (int i = 2; i < n >> 1; ++i)
    wn[i] = 1ll * wn[i - 1] * wn[1] % MOD;
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i << 1)
      for (int k = 0; k < i; ++k) {
        int x = a[j + k], y = 1ll * wn[n / (i << 1) * k] * a[j + k + i] % MOD;
        a[j + k] = (x + y) % MOD, a[j + k + i] = (MOD + x - y) % MOD;
      }
  if (inv) {
    for (int i = 1; i < n >> 1; ++i)
      std::swap(a[i], a[n - i]);
    int rec = power(n, MOD - 2);
    for (int i = 0; i < n; ++i)
      a[i] = 1ll * a[i] * rec % MOD;
  }
}

void get_inv(int *f, int *g, int n) {
  if (n == 1)
    return void(g[0] = power(f[0], MOD - 2));
  int rec = n;
  get_inv(f, g, (n + 1) >> 1), init(n);
  for (int i = (rec + 1) >> 1; i < n; ++i)
    g[i] = 0;
  for (int i = 0; i < rec; ++i)
    tmp[i] = f[i];
  for (int i = rec; i < n; ++i)
    tmp[i] = 0;
  ntt(g, n, 0), ntt(tmp, n, 0);
  for (int i = 0; i < n; ++i)
    g[i] = 1ll * g[i] * (MOD + 2 - 1ll * g[i] * tmp[i] % MOD) % MOD;
  ntt(g, n, 1);
  for (int i = rec; i < n; ++i)
    g[i] = 0;
}

void get_sqrt(int *f, int *g, int n) {
  if (n == 1)
    return void(g[0] = 1);
  int rec = n;
  get_sqrt(f, g, (n + 1) >> 1);
  for (int i = 0; i<(n + 1)>> 1; ++i)
    tmp2[i] = g[i];
  for (int i = (n + 1) >> 1; i < n; ++i)
    tmp2[i] = 0;
  get_inv(tmp2, tmp3, n), init(n);
  for (int i = (rec + 1) >> 1; i < n; ++i)
    g[i] = 0;
  for (int i = 0; i < rec; ++i)
    tmp2[i] = f[i];
  for (int i = rec; i < n; ++i)
    tmp2[i] = 0;
  ntt(tmp2, n, 0), ntt(tmp3, n, 0);
  for (int i = 0; i < n; ++i)
    tmp3[i] = 1ll * tmp3[i] * tmp2[i] % MOD;
  ntt(tmp3, n, 1);
  for (int i = 0; i < rec; ++i)
    g[i] = 1ll * (g[i] + tmp3[i]) * INV2 % MOD;
  for (int i = rec; i < n; ++i)
    g[i] = 0;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i)
    scanf("%d", &c[i]);
  for (int i = 0; i < n; ++i)
    if (c[i] <= m)
      ++C[c[i]];
  for (int i = 1; i <= m; ++i)
    C[i] = (MOD - (C[i] << 2)) % MOD;
  C[0] = 1;
  get_sqrt(C, c, m + 1), ++c[0], get_inv(c, C, m + 1);
  for (int i = 1; i <= m; ++i)
    printf("%d\n", (C[i] << 1) % MOD);
  return 0;
}

Similarity of Necklaces 2

题意概述

给定四个数组$M, P, L, R$,要求构造一个数组$T$,使得
$$\sum_{i=1}^N M_iT_i=0 \; (L_i \le T_i \le R_i)$$
求$\sum_{i=1}^N P_iT_i$的最大值。
数据范围:$1 \le N \le 200, \; 1 \le M_i \le 20, \; 0 \le P_i \le 10^5, \; -25 \le L_i \lt R_i \le 25$。

算法分析

令$D_i=T_i-L_i$,那么限制条件变为$\sum_{i=1}^N M_iD_i=-\sum_{i=1}^N M_iL_i \; (0 \le D_i \le R_i-L_i)$,要求的值变为$\sum_{i=1}^N P_iD_i+\sum_{i=1}^N P_iL_i$。这就相当于有$N$种物品,第$i$种物品有$(R_i-L_i)$个,每一个的体积为$M_i$,价值为$P_i$,背包的体积为$-\sum_{i=1}^N M_iL_i$,求物品恰好装满背包时的最大价值。这是分组背包问题,用单调队列优化DP即可。

代码

#include <cstdio>
#include <cstring>

int min(int a, int b) {
  return a < b ? a : b;
}

static const int N = 205;
int p[N], m[N], u[N], l[N];
int f[N << 10], q1[N << 10], q2[N << 10];

int main() {
  int n;
  while (~ scanf("%d", &n)) {
    int v = 0, w = 0;
    for (int i = 0; i < n; ++ i) {
      scanf("%d%d%d%d", &p[i], &m[i], &l[i], &u[i]);
      if (l[i]) u[i] -= l[i], v -= l[i] * m[i], w -= l[i] * p[i];
    }
    memset(f, -0x3f, sizeof f), f[0] = 0;
    for (int i = 0; i < n; ++ i) {
      u[i] = min(u[i], v / m[i]);
      for (int d = 0; d < m[i]; ++ d) {
        int l = 1, r = 0;
        for (int j = 0; j <= (v - d) / m[i]; ++ j) {
          int val = f[j * m[i] + d] - j * p[i];
          while (l <= r && q1[r] < val) -- r;
          q2[++ r] = j, q1[r] = val;
          if (j - q2[l] > u[i]) ++ l;
          f[j * m[i] + d] = q1[l] + j * p[i];
        }
      }
    }
    printf("%d\n", f[v] - w);
  }
  return 0;
}

Manhattan Wiring

题目描述

There is a rectangular area containing $n \times m$ cells. Two cells are marked with “2”, and another two with “3”. Some cells are occupied by obstacles. You should connect the two “2”s and also the two “3”s with non-intersecting lines. Lines can run only vertically or horizontally connecting centers of cells without obstacles.
Lines cannot run on a cell with an obstacle. Only one line can run on a cell at most once. Hence, a line cannot intersect with the other line, nor with itself. Under these constraints, the total length of the two lines should be minimized. The length of a line is defined as the number of cell borders it passes. In particular, a line connecting cells sharing their border has length $1$.
Fig. 1(a) shows an example setting. Fig. 1(b) shows two lines satisfying the constraints above with minimum total length $18$.
Example

题意概述

给定一张$n \times m$的有障碍矩阵,其中恰有两个2和两个3,其余有些格子上有障碍。求分别连接两个2和两个3的两条不相交路径长度之和的最小值。
数据范围:$1 \le n, m \le 9$。

算法分析

插头DP,维护一排插头,令$f_{i, j, s}$表示处理到第$i$行第$j$列的格子且插头的状态为$s$时的最小值,根据当前格子的状态进行相应的转移。

代码

#include <cstdio>
#include <cstring>

void minify(short &a, short b) {
  a > b && (a = b);
}

static const int N = 11;
int rec[1 << 20];
short mp[N][N], f[2][N][1 << 20]; // 0 for no wire, 2 for wire 2, 3 for wire 3

int modify(int s, int p, int v) {
  return (s & ((1 << (p << 1)) - 1)) | (((s >> ((p + 1) << 1) << 2) + v) << (p << 1));
}

int query(int s, int p) {
  return s >> (p << 1) & 3;
}

int main() {
  int n, m, top = 0;
  for (int i = 0; i < 1 << 20; ++ i) {
    for (int j = 0; j < N; ++ j) if (query(i, j) == 1) goto illegal;
    rec[top ++] = i; illegal: ;
  }
  while (scanf("%d%d", &n, &m), n) {
    for (int i = 0; i < n; ++ i)
      for (int j = 0; j < m; ++ j) scanf("%hd", &mp[i][j]);
    int cur = 0; memset(f, 0x3f, sizeof f), f[cur][0][0] = 0;
    for (int i = 0; i < n; ++ i, cur ^= 1) {
      for (int j = 0; j < m; ++ j)
        for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
          if (f[cur][j][k] < 10000) {
            int p = query(k, j), q = query(k, j + 1);
            if (mp[i][j] == 0) {
              if (! p && ! q)
                minify(f[cur][j + 1][k], f[cur][j][k]),
                minify(f[cur][j + 1][modify(modify(k, j, 2), j + 1, 2)], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(modify(k, j, 3), j + 1, 3)], f[cur][j][k] + 1);
              else if (! p ^ ! q)
                minify(f[cur][j + 1][modify(modify(k, j, p + q), j + 1, 0)], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, p + q)], f[cur][j][k] + 1);
              else if (p && p == q)
                minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, 0)], f[cur][j][k] + 1);
            } else if (mp[i][j] == 1) {
              if (! p && ! q) minify(f[cur][j + 1][k], f[cur][j][k]); 
            } else {
              if (! p && ! q)
                minify(f[cur][j + 1][modify(k, j, mp[i][j])], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(k, j + 1, mp[i][j])], f[cur][j][k] + 1);
              else if (p == mp[i][j] && ! q)
                minify(f[cur][j + 1][modify(k, j, 0)], f[cur][j][k] + 1);
              else if (! p && q == mp[i][j])
                minify(f[cur][j + 1][modify(k, j + 1, 0)], f[cur][j][k] + 1);
            }
          }
      for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
        if (! query(k, m)) minify(f[cur ^ 1][0][k << 2 & (1 << ((m + 1) << 1)) - 1], f[cur][m][k]);
      for (int j = 0; j <= m; ++ j)
        for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _]) f[cur][j][k] = 16000;
    }
    printf("%d\n", f[cur][0][0] < 10000 ? f[cur][0][0] - 2 : 0);
  }
  return 0;
}

Long Live the Queen

题目描述

The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen’s name. This new country contains $N$ towns. The towns are connected by bidirectional roads and there is exactly ONE path between any two towns, walking on the country’s roads. For each town, the profit it brings to the owner is known. Although the Bytelanders love their queen very much, they don’t want to conquer all the $N$ towns for her. They will be satisfied with a non-empty subset of these towns, with the following $2$ properties: there exists a path from every town in the subset to every other town in the subset walking only through towns in the subset and the profit of the subset is maximum. The profit of a subset of the $N$ towns is equal to the sum of the profits of the towns which belong to the subset. Your task is to find the maximum profit the Bytelanders may get.

题意概述

给定一棵$N$个节点的树,每个节点都有权值。求它连通子图节点权值之和的最大值。
数据范围:$1 \le N \le 16000$。

算法分析

考虑树形DP。假定$1$号点为根节点。令$f_{0, i}$表示$i$的子树中以$i$为根的连通子图节点权值之和的最大值,$f_{1, i}$表示$i$的子树中不以$i$为根的连通子图节点权值之和的最大值。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

namespace std {
  template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
  template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 16010;
  int n, nume, h[N], w[N], f[2][N];
  struct Edge {
    int v, nxt;
  } e[N << 1];
  void add_edge(int u, int v) {
    e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
    e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
  }
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > w[i];
    for (int i = 1; i < n; ++ i) {
      int u, v; io > u > v, add_edge(u, v);
    }
  }
  void init() { memset(f, -0x3f, sizeof f); }
  void dfs(int t, int fa) {
    f[0][t] = w[t];
    for (int i = h[t]; i; i = e[i].nxt)
      if (e[i].v != fa) {
        dfs(e[i].v, t);
        maxify(f[1][t], max(f[0][e[i].v], f[1][e[i].v]));
        f[0][t] += max(f[0][e[i].v], 0);
      }
  }
  void process() { dfs(1, 0), io < max(f[0][1], f[1][1]) < '\n'; }

public:
  void solve() { input(), init(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}