Bitwise XOR

题目描述

Given a sequence $a$ and an empty sequence $b$, each element in $a$ is added to $b$ with probability $P$ (independently to the other elements). Denote $s=\bigoplus_{i=1}^{|b|} b_i$, where $\oplus$ denotes bitwise xor and $s=0$ if $b$ is empty. Find the expected value of $s^2$.

题意概述

给定一个长度为$n$的序列$a$,其中每个数都有$P$的概率被选中。令被选中的数的异或和为$s$。求$s^2$的期望。

数据范围:$1 \le n \le 10^5, \; 0 \le a_i \lt 10^9+7$。

算法分析

令$P(s)$表示异或和为$s$的概率。把$s$用二进制表示,最低位为第$0$位。

$$\begin{align} \sum_s s^2P(s) &= \sum_s (\sum_{i=0}^{29} [s二进制第i位为1] 2^i)^2P(s) \\ &= \sum_s P(s) \sum_{i=0}^{29} [s二进制第i位为1] 2^i \sum_{j=0}^{29} [s二进制第j位为1] 2^j \\ &= \sum_s P(s) \sum_{i=0}^{29} \sum_{j=0}^{29} [s二进制第i位和第j位都为1] 2^{i+j} \\ &= \sum_{i=0}^{29} \sum_{j=0}^{29} P(s二进制第i位和第j位都为1) 2^{i+j} \end{align}$$

先枚举$i$和$j$,令$f_{k,0/1,0/1}$表示从前$k$个数中选,异或和第$i$位、第$j$为分别为$0/1$、$0/1$的概率,对$f_{n,1,1}2^{i+j}$求和即为答案。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 100005, MOD = 1000000007;
 
int a[N], f[N][2][2];
 
int power(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = 1ll * ret * a % MOD;
        }
        a = 1ll * a * a % MOD;
    }
    return ret;
}
 
int main() {
    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    int p = 1ll * x * power(y, MOD - 2) % MOD, q = (MOD + 1 - p) % MOD;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    int ans = 0, ans2 = 0;
    f[0][0][0] = 1;
    for (int i = 0; i < 30; ++i) {
        for (int j = i; j < 30; ++j) {
            for (int k = 1; k <= n; ++k) {
                for (int _i = 0; _i < 2; ++_i) {
                    for (int _j = 0; _j < 2; ++_j) {
                        int __i = _i ^ (a[k] >> i & 1);
                        int __j = _j ^ (a[k] >> j & 1);
                        f[k][_i][_j] = (1ll * f[k - 1][_i][_j] * q + 1ll * f[k - 1][__i][__j] * p) % MOD;
                    }
                }
            }
            ans = (ans + (1ll << i + j + (i != j)) % MOD * f[n][1][1]) % MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Unbalanced Coin

题目描述

You have an unbalanced coin, the state of which (head or tail) after tossing depends on the previous state. If the head side is up now, the probability that the coin is still head up after tossing is $p$, and the probability that the tail side comes up is $1-p$. Similarly, if the tail side is up now, the probability that the coin is still tail up after tossing is $p$, and the probability that the head side comes up is $1-p$.

Assume the coin is head up initially. You will then toss it for $n$ times, during these $n$ times, every time the head side is up, you will get one score. What is the probability that you will get exactly $k$ score for $k=0,1,2,\cdots,n$?

题意概述

有一枚初始正面朝上的硬币。每次投掷时,硬币有$p$的概率保持不变,$1-p$的概率翻面。求$n$次投掷后,正面朝上的总次数分别为$0,1,2,\cdots,n$的概率。

数据范围:$1 \le n \le 10^5$。

算法分析

令$f_{i,0/1,j}$表示$i$次投掷后,硬币正面/反面朝上,且正面朝上的总次数为$j$概率。容易想到转移方程:

$$\begin{align} f_{i,0,j} &= f_{i-1,0,j-1} \times p+f_{i-1,1,j-1} \times (1-p) \\ f_{i,1,j} &= f_{i-1,0,j} \times (1-p)+f_{i-1,1,j} \times p \end{align}$$

这样直接转移的复杂度是$O(n^2)$,考虑如何优化。

令$f_{i,0/1}$的普通型生成函数为$F_{i,0/1}$,即$F_{i,0/1}=\sum_{j=0}^i f_{i,0/1,j}x^j$。则上述转移方程可表示为:

$$\begin{align} F_{i,0} &= F_{i-1,0} \times px+F_{i-1,1} \times (1-p)x \\ F_{i,1} &= F_{i-1,0} \times (1-p)+F_{i-1,1} \times p \end{align}$$

容易想到其矩阵形式:

$$\begin{equation} \left[\begin{matrix} px & (1-p)x \\ 1-p & p\end{matrix}\right] \left[\begin{matrix} F_{i-1,0} \\ F_{i-1,1} \end{matrix}\right]= \left[\begin{matrix} F_{i,0} \\ F_{i,1} \end{matrix}\right]\end{equation}$$

如此便可以用矩阵快速幂来优化了。其中多项式乘法需要用FFT计算。

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 200005;
double const PI = acos(-1);
 
int rev[N];
 
struct Complex {
    double a, b;
    Complex(double _a = 0, double _b = 0) : a(_a), b(_b) {}
    friend Complex operator+(Complex const &x, Complex const &y) {
        return Complex(x.a + y.a, x.b + y.b);
    }
    friend Complex operator-(Complex const &x, Complex const &y) {
        return Complex(x.a - y.a, x.b - y.b);
    }
    friend Complex operator*(Complex const &x, Complex const &y) {
        return Complex(x.a * y.a - x.b * y.b, x.a * y.b + x.b * y.a);
    }
    friend Complex operator/(Complex const &x, double const &y) {
        return Complex(x.a / y, x.b / y);
    }
} wn[N], A[2][2][N], B[2][2][N], C[2][2][N];
 
int init(int n) {
    int len = 1, p = 0;
    for (; len < n; len <<= 1, ++p) ;
    for (int i = 1; i < len; ++i) {
        rev[i] = rev[i >> 1] >> 1 | (i & 1) << p - 1;
    }
    for (int i = 0; i < len >> 1; ++i) {
        wn[i] = Complex(cos(2 * PI / len * i), sin(2 * PI / len * i));
    }
    return len;
}
 
void fft(Complex *a, int len, bool inv = 0) {
    for (int i = 0; i < len; ++i) {
        if (i < rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    for (int i = 1; i < len; i <<= 1) {
        for (int j = 0; j < len; j += i << 1) {
            for (int k = 0; k < i; ++k) {
                Complex x = a[j + k], y = wn[len / (i << 1) * k] * a[j + i + k];
                a[j + k] = x + y;
                a[j + i + k] = x - y;
            }
        }
    }
    if (inv) {
        std::reverse(a + 1, a + len);
        for (int i = 0; i < len; ++i) {
            a[i] = a[i] / len;
        }
    }
}
 
struct Matrix {
    int n[2][2];
    double *a[2][2];
 
    friend Matrix operator*(Matrix const &x, Matrix const &y) {
        int len = init(x.n[0][0] + y.n[0][0] - 1);
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < len; ++k) {
                    A[i][j][k] = k < x.n[i][j] ? x.a[i][j][k] : 0;
                    B[i][j][k] = k < y.n[i][j] ? y.a[i][j][k] : 0;
                    C[i][j][k] = 0;
                }
                fft(A[i][j], len);
                fft(B[i][j], len);
            }
        }
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    for (int l = 0; l < len; ++l) {
                        C[i][j][l] = C[i][j][l] + A[i][k][l] * B[k][j][l];
                    }
                }
                fft(C[i][j], len, 1);
            }
        }
        Matrix ret;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                ret.n[i][j] = 0;
                for (int k = 0; k < 2; ++k) {
                    ret.n[i][j] = std::max(ret.n[i][j], x.n[i][k] + y.n[k][j] - 1);
                }
                ret.a[i][j] = new double[ret.n[i][j]];
                for (int k = 0; k < ret.n[i][j]; ++k) {
                    ret.a[i][j][k] = C[i][j][k].a;
                }
            }
        }
        return ret;
    }
} base, ans;
 
int main() {
    int n;
    double p;
    scanf("%d%lf", &n, &p);
    base.n[0][0] = base.n[0][1] = 2;
    base.n[1][0] = base.n[1][1] = 1;
    base.a[0][0] = new double[2];
    base.a[0][0][0] = 0;
    base.a[0][0][1] = p;
    base.a[0][1] = new double[2];
    base.a[0][1][0] = 0;
    base.a[0][1][1] = 1 - p;
    base.a[1][0] = new double;
    base.a[1][0][0] = 1 - p;
    base.a[1][1] = new double;
    base.a[1][1][0] = p;
    ans.n[0][0] = ans.n[1][1] = 1;
    ans.a[0][0] = new double;
    ans.a[0][0][0] = 1;
    ans.a[1][1] = new double;
    ans.a[1][1][0] = 1;
    int b = n;
    for (; b;) {
        if (b & 1) {
            ans = ans * base;
        }
        if (b >>= 1) {
            base = base * base;
        }
    }
    for (int i = 0; i <= n; ++i) {
        printf("%.10f\n", ans.a[0][0][i] + ans.a[1][0][i]);
    }
    return 0;
}

BBQ

题目描述

You are a master of barbeque, and now you are trying to string dumplings with a bamboo stick.

The dumplings are placed in a $n \times m$ grid. Each grid contains exactly one dumpling. The color of each dumpling is red ("R"), green ("G") or white ("W").

You can choose three consecutive grids from left to right, or from top to bottom, and string the corresponding dumplings into a string from left to right or from top to bottom. So there will be exactly three dumplings on a string, let’s denote a string of dumpling by their colors in order.

Now, you want to make strings "RGW" as many as possible. Note that the dumplings can not be reused in multiple strings. So how many strings "RGW" can you make?

题意概述

给定一个$n \times m$的字符矩阵。每次可以从上到下或从左到右取连续三个字符构成一个字符串,每个字符只能取一次。求最多能取几个RGW

数据范围:$1 \le n, m \le 3000$。

算法分析

只需考虑最多能取几个G。可以发现,只有在同一条与副对角线平行的直线上的G会相互影响。分别计算每一条直线,令$f_{i, 0/1/2}$表示第$i$个位置不取/从左到右取/从上到下取的情况下,前$i$个位置最多能取几个G。最后把所有直线的结果加起来得到答案。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 3005;
char mp[N][N];
int f[N][N][3];
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", mp[i] + 1);
    }
    for (int k = 2; k <= n + m; ++k) {
        for (int i = 1; i < k; ++i) {
            int j = k - i;
            if (i <= n && j <= m) {
                f[i][j][0] = std::max(f[i - 1][j + 1][0], std::max(f[i - 1][j + 1][1], f[i - 1][j + 1][2]));
                if (mp[i][j - 1] == 'R' && mp[i][j] == 'G' && mp[i][j + 1] == 'W') {
                    f[i][j][1] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][1]) + 1;
                }
                if (mp[i - 1][j] == 'R' && mp[i][j] == 'G' && mp[i + 1][j] == 'W') {
                    f[i][j][2] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][2]) + 1;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        ans += std::max(f[i][1][0], std::max(f[i][1][1], f[i][1][2]));
    }
    for (int i = 1; i <= m; ++i) {
        ans += std::max(f[n][i][0], std::max(f[n][i][1], f[n][i][2]));
    }
    printf("%d\n", ans);
    return 0;
}

Fence

题目描述

A team of $K$ workers should paint a fence which contains $N$ planks numbered from $1$ to $N$ from left to right. Each worker $i$ should sit in front of the plank $S_i$ and he may paint only a compact interval (this means that the planks from the interval should be consecutive). This interval should contain the $S_i$ plank. Also a worker should not paint more than $L_i$ planks and for each painted plank he should receive $P_i$\$. A plank should be painted by no more than one worker. All the numbers $S_i$ should be distinct.

Being the team’s leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income.

Write a program that determines the total maximal income obtained by the $K$ workers.

题意概述

$K$个工人要粉刷一面长度为$N$的篱笆,第$i$个工人要么不粉刷,要么粉刷一段连续且长度不超过$L_i$的包含第$S_i$块木板的篱笆,他每粉刷一块木板可以获得$P_i$的报酬。每一块木板要么不被粉刷,要么仅被一个工人粉刷。求所有工人获得的总报酬的最大值。

数据范围:$1 \le K \le 100, \; 1 \le N \le 16000$。

算法分析

令$f_{i, j}$表示前$i$个工人粉刷前$j$块木板(不一定全刷)的最大报酬,则可分三种情况讨论:

  • 第$i$个工人不粉刷,$f_{i, j}=f_{i-1, j}$;
  • 第$j$块木板不被粉刷,$f_{i, j}=f_{i, j-1}$;
  • 第$i$个工人粉刷第$(k+1)$到第$j$块木板,$f_{i, j}=f_{i-1, k}+(j-k) \times P_i$。

在第三种情况中,转移方程变形后得$f_{i, j}=(f_{i-1, k}-k \times P_i)+j \times P_i$,$f_{i-1, k}-k \times P_i$与$j$无关,$j \times P_i$与$k$无关,因此对于确定的$i$和$j$,方程后半部分为常数,只要求前半部分的最大值。因为前半部分只与$k$有关,所以可以用单调队列维护其最大值。注意$k$要满足的条件是$k+1 \le S_i \le j$与$j-(k+1)+1 \le L_i$,即$j-L_i \le k \lt S_i$。算法的时间复杂度为$O(KN)$。

代码

#include <cstdio>
#include <algorithm>

int const K = 105, N = 16005;
int f[K][N];
struct Carpenter {
    int l, p, s;
    bool operator < (Carpenter const &t) const {
        return s < t.s;
    }
} c[K];
std::pair<int, int> que[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d%d", &c[i].l, &c[i].p, &c[i].s);
    }
    std::sort(c + 1, c + k + 1);
    for (int i = 1; i <= k; ++i) {
        int qb = 0, qe = 0;
        for (int j = 0; j < c[i].s; ++j) {
            for (; qb < qe && que[qe - 1].first <= f[i - 1][j] - c[i].p * j; --qe) ;
            que[qe++] = std::make_pair(f[i - 1][j] - c[i].p * j, j);
        }
        for (int j = 1; j <= n; ++j) {
            f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
            if (c[i].s <= j && j < c[i].s + c[i].l) {
                for (; qb < qe && que[qb].second < j - c[i].l; ++qb) ;
                f[i][j] = std::max(f[i][j], que[qb].first + c[i].p * j);
            }
        }
    }
    printf("%d\n", f[k][n]);
    return 0;
}

Friendly Points

题目描述

Consider $n$ distinct points on a plane.
Two points from that set are said to be friends, when there exists a rectangle with sides parallel to coordinate axes that contains those two points and doesn’t contain any other point from the given set. A rectangle is said to contain a point if the point lies within the rectangle or on its border.
How many pairs of friends are there among the given points?

题意概述

给定平面上的$n$个点。定义一对点是友好点对当且仅当存在一个各边平行于坐标轴的矩形仅包含这两个点。一个点被一个矩形包含当且仅当该点在矩形内部或边界上。求有多少对友好点对。
数据范围:$1 \le n \le 10^5$。

算法分析

用CDQ分治,把平面上的问题转化为序列上的问题。将点分成上下两个部分,考虑属于不同部分的点对有多少,递归处理两个部分。
对$y$坐标分治,把两个部分中的点按$x$坐标从小到大排序,依次处理。假设处理到一个上半部分的点,当上半部分只有这个点时,下半部分可以与它构成友好点对的点的$y$坐标严格下降。因此我们可以对上半部分维护一个$y$坐标严格上升的单调栈,对下半部分维护一个$y$坐标严格下降的单调栈。在处理上半部分的某个点$p$时,用上半部分的单调栈找出$x$坐标最大的$y$坐标不大于它的点$q$,在下半部分的单调栈里二分出$x$坐标大于$q$的点有多少个,即是与$p$构成友好点对的点的个数。下半部分同理。
有一些细节:$y$坐标相同的点需放在同一部分,若某一部分中所有点的$y$坐标相同,则直接加上这一部分的答案,不递归处理;若有多个$x$坐标相同的点,上半部分只考虑$y$坐标最小的,下半部分只考虑$y$坐标最大的;两个部分中$x$坐标相同的点需同时处理。

代码

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

static int const N = 100005;
static int const MAX = 1000000001;
long long ans;
struct Point {
  int x, y;
  friend bool operator<(Point const &a, Point const &b) {
    return a.x < b.x;
  }
} p[N], s1[N], s2[N], tmp[N];

void calc(int l, int r) {
  if (l == r)
    return;
  int mid = (l + r) >> 1, L = mid - 1, R = mid + 1;
  for (; l <= L && p[L].y == p[mid].y; --L)
    ;
  for (; R <= r && p[R].y == p[mid].y; ++R)
    ;
  if (l > L && R > r) {
    std::sort(p + l, p + r + 1);
    return void(ans += r - l);
  }
  mid = l <= L ? L : R - 1;
  int p1 = l, p2 = mid + 1, p3 = l, t1 = 0, t2 = 0;
  calc(l, mid), calc(mid + 1, r);
  for (; p1 <= mid && p2 <= r;) {
    int x = std::min(p[p1].x, p[p2].x), mx = -MAX, mn = MAX;
    for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
      mx = std::max(mx, p[p1].y);
    for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
      mn = std::min(mn, p[p2].y);
    for (; t1 && s1[t1 - 1].y < mx; --t1)
      ;
    for (; t2 && s2[t2 - 1].y > mn; --t2)
      ;
    Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0}, r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
    for (; t1 && s1[t1 - 1].y == mx; --t1)
      ;
    for (; t2 && s2[t2 - 1].y == mn; --t2)
      ;
    if (mx > -MAX)
      ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
    if (mn < MAX)
      ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
  }
  for (; p1 <= mid;) {
    int x = p[p1].x, mx = -MAX;
    for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
      mx = std::max(mx, p[p1].y);
    for (; t1 && s1[t1 - 1].y < mx; --t1)
      ;
    Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0};
    for (; t1 && s1[t1 - 1].y == mx; --t1)
      ;
    ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
  }
  for (; p2 <= r;) {
    int x = p[p2].x, mn = MAX;
    for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
      mn = std::min(mn, p[p2].y);
    for (; t2 && s2[t2 - 1].y > mn; --t2)
      ;
    Point r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
    for (; t2 && s2[t2 - 1].y == mn; --t2)
      ;
    ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
  }
  for (int i = l; i <= r; ++i)
    p[i] = tmp[i];
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &p[i].x, &p[i].y);
  std::sort(p, p + n, [](Point const &a, Point const &b) { return a.y < b.y; });
  calc(0, n - 1), printf("%I64d\n", ans);
  return 0;
}

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;
}

Traffic Lights

题目描述

The main street of Berland’s capital is a segment with length $s$. The main street has traffic lights installed along it. The traffic lights have been functioning since time immemorial, cyclically changing colors from red to green and vice versa. Each traffic light can be described by four numbers $x_i, r_i, g_i, d_i$, which stand for:

  • $x_i$ – the distance from the beginning of the street to the traffic light ($1 \le x_i \lt s$),
  • $r_i$ – the duration of the red light illumination ($10 \le r_i \le 20$),
  • $g_i$ – the duration of the green light illumination ($10 \le g_i \le 20$),
  • $d_i$ – the minimum non-negative moment of time when the traffic light changes the light from green to red ($0 \le d_i \lt r_i+g_i$).

Each traffic light retains its light cycle from the ancient past.
The King of Berland asked the transport minister to customize the traffic lights according to a “green wave” principle. That means that if you start driving from the beginning of the street at the recommended speed, you can drive through the entire street without stopping, that is, you pass each traffic light when it has the green light on.
Now it is time to show the “green wave” to the King, but the work is not even started yet. You may assume that the King starts driving at the moment of time $0$ from the beginning of the street. So the minister decided to choose some speed $v_0$ and tell the king that the “green wave” works specifically for this speed. Moreover, they can switch any number of traffic lights to the “always green” mode. The minister’ aim is to ensure that if the King drives through the street at the recommended speed $v_0$ he encounters no red traffic light. Driving exactly at the moment when the colors are changed is not considered driving through the red light.
Any transport’s maximum speed is limited in Berland: it should not exceed $v_{\max}$. On the other hand, the King will be angry if the recommended speed is less than $v_{\min}$. Thus, the minister should choose such value of $v_0$, which satisfies the inequation $v_{\min} \le v_0 \le v_{\max}$.
Help the minister to find such $v_0$ value, that the number of traffic lights to switch to the “always green” mode is minimum. If $v_0$ is not uniquely defined, choose the maximum possible value of $v_0$.

题意概述

一条长为$s$的公路上有$n$个红绿灯。第$i$个红绿灯在距离起点$x_i$的位置上,周期是$r_i$单位时间红灯加$g_i$单位时间绿灯,第一次从绿灯变成红灯的时刻是$d_i$。一辆车以速度$v_0$从起点开到终点,途中不能停顿。求在$v_{\min} \le v_0 \le v_{\max}$且闯过的红灯数最少的情况下,$v_0$的最大值。
数据范围:$1 \le n \lt 20000, \; 1 \le s \le 20000, \; 10 \le v_{\min} \le v_{\max} \le 50$。

算法分析

把速度看成数轴,那么每个红绿灯可以对应到数轴上的若干个区间——即若$v_0 \in [l, r]$,则经过这个红绿灯时闯了红灯。
由于题目的特殊限制($10 \le r_i, g_i \le 20, \; 10 \le v_{\min} \le v_0 \le v_{\max} \le 50$),这样的区间不会太多,可以把它们都求出来。问题转化成求数轴上一个点使得覆盖它的区间数最少。离散化后模拟即可。

代码

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

static int const N = 20005;
static double const EPS = 1e-12;

int pm(double const &n) {
  return fabs(n) < EPS ? 0 : n < 0 ? -1 : 1;
}

std::bitset<N> ans, cur;
struct Query {
  int id, op;
  double x;
  friend bool operator<(Query const &a, Query const &b) {
    return pm(a.x - b.x) ? !~pm(a.x - b.x) : a.op < b.op;
  }
} itv[N * 100];

int main() {
  int n, s, vmn, vmx, top = 0;
  scanf("%d%d%d%d", &n, &s, &vmn, &vmx);
  for (int i = 0, x, r, g, d; i < n; ++i) {
    scanf("%d%d%d%d", &x, &r, &g, &d);
    if (d > g) {
      double l = 1. * x / (d - g);
      itv[top++] = (Query){i, 1, l};
    }
    for (;; d += r + g) {
      double l = 1. * x / (d + r), r = d ? 1. * x / d : 1e9;
      if (pm(r - vmn) < 1) {
        break;
      }
      if (pm(vmx - l) < 1) {
        continue;
      }
      itv[top++] = (Query){i, 1, l}, itv[top++] = (Query){i, -1, r};
    }
  }
  itv[top++] = (Query){n, 1, 0. + vmx};
  std::sort(itv, itv + top);
  int ac = n, cc = 0;
  double vc = 0;
  for (int i = 0; i < n; ++i) {
    ans.set(i);
  }
  for (int i = 0; i < top && pm(itv[i].x - vmx) < 1; ++i) {
    if (itv[i].op == 1) {
      if (cc <= ac && pm(vmn - itv[i].x) < 1) {
        ans = cur, ac = cc, vc = itv[i].x;
      }
      if (itv[i].id < n) {
        cur.set(itv[i].id), ++cc;
      }
    } else {
      cur.reset(itv[i].id), --cc;
    }
  }
  printf("%.10lf\n%d\n", vc, ac);
  for (int i = 0; i < n; ++i) {
    if (ans.test(i)) {
      printf("%d ", i + 1);
    }
  }
  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;
}