## 题目描述

$n$ black and white balls were put into a bag. Petya doesn’t know exactly how many black balls are there among them. He knows, however, that there are $0, 1, \ldots, n$ black balls among all balls in the bag with equal probability.
Petya took $l$ balls from the bag at random, and $l_1$ of them turned out black, while $l_2$ other turned out white ($l_1+l_2=l$). Now he wants to predict how many black balls were there initially in the bag. Of course, if $l \lt n$, he can’t be sure in his prediction, but he wants to predict a segment $[a, b]$, such that the amount $k$ of black balls belongs to it with probability at least $p$.
You are given $n, l_1, l_2$ and $p$, and you must find such $a$ and $b$ that $b-a$ is minimal possible. If there are several such pairs $(a, b)$, choose the one with the smallest $a$.

## 算法分析

$$P(B_i|A)={P(B_i)P(A|B_i) \over \sum_{j=0}^n P(B_j)P(A|B_j)}$$

$$P(B_i)={1 \over n+1}, \; P(A|B_i)={{i \choose l_1}{n-i \choose l_2} \over {n \choose l}}$$

## 代码

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

static int const N = 55;
double a[N];

double get_c(int n, int m) {
if (n < m)
return 0;
double ret = 1;
for (int i = 0; i < m; ++i)
ret *= 1. * (n - i) / (m - i);
return ret;
}

int main() {
int n, l1, l2, p;
scanf("%d%d%d%d", &n, &l1, &l2, &p);
double b = 0;
for (int i = 0; i <= n; ++i)
b += a[i] = 1. / (n + 1) * get_c(i, l1) * get_c(n - i, l2) / get_c(n, l1 + l2);
for (int i = 1; i <= n + 1; ++i)
for (int j = 0; j + i - 1 <= n; ++j) {
double sum = 0;
for (int k = j; k <= j + i - 1; ++k)
sum += a[k];
if (sum / b * 100 + 1e-12 >= p)
return printf("%d %d\n", j, j + i - 1), 0;
}
return 0;
}


## 题目描述

Given a positive integer $n$ and a positive prime number $p$, find $x, y$ and $z$ such that $x^n+y^n \equiv z^n \pmod p$ and $x, y$ and $z$ are nonzero modulo $p$ or report that there’s no such triple.

## 算法分析

$$g^{k_1n}+g^{k_2n} \equiv g^{k_3n}$$

$$G^{k_1}+G^{k_2} \equiv G^{k_3}$$

\begin{align} G^{k_1-k_2}+1 &\equiv G^{k_3-k_2} \\ G^{k_1-k_3}+G^{k_2-k_3} &\equiv 1 \end{align}

$$G^i+1 \equiv G^j \lor G^j+1 \equiv G^i \lor G^i+G^j \equiv 1$$

## 代码

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

static int const N = 1000005;
int a[N], b[N], pri[N];

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

int get_prt(int p) {
int top = 0, k = p - 1;
for (int i = 2; i * i <= k; ++i)
if (!(k % i)) {
pri[top++] = i;
for (; !(k % i); k /= i)
;
}
if (k > 1)
pri[top++] = k;
for (int i = 2; i <= p - 1; ++i) {
bool fg = 1;
for (int j = 0; fg && j < top; ++j)
fg &= power(i, (p - 1) / pri[j], p) > 1;
if (fg)
return i;
}
return 0;
}

int main() {
int T;
scanf("%d", &T);
for (int n, p; T--;) {
scanf("%d%d", &n, &p);
int g = get_prt(p), gn = power(g, n, p), x = 0, y = 0, z = 0;
for (int i = 1, G = gn; i <= p - 1; ++i, G = 1ll * G * gn % p)
if (b[G] == T + 1)
break;
else {
a[G] = i, b[G] = T + 1;
if (b[G + 1] == T + 1) {
x = power(g, i, p), y = 1, z = power(g, a[G + 1], p);
break;
}
if (b[G - 1] == T + 1) {
x = power(g, a[G - 1], p), y = 1, z = power(g, i, p);
break;
}
if (b[1 - G + p] == T + 1) {
x = power(g, i, p), y = power(g, a[1 - G + p], p), z = 1;
break;
}
}
x ? printf("%d %d %d\n", x, y, z) : puts("-1");
}
return 0;
}


## 题目描述

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?

## 代码

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


## 题目描述

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.

## 代码

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


## 题目描述

Hurry! Two well-known software companies are recruiting programmers. Initially the total number of unemployed programmers is $n$. The companies are hiring them one by one, alternately. In one turn a company hires one of the programmers who has not been hired yet. The first company starts hiring.
Furthermore, there are some pairs of friends among the programmers. Of course, a programmer may have several friends. Friendship is a symmetrical relationship, so if $a$ is a friend of $b$ then $b$ is a friend of $a$.
All such pairs are known to the companies, and the companies follow the rule: a new programmer hired by a company must have at least one friend among the programmers already working in this company. The only exception is a programmer that a company starts with, he can be chosen arbitrarily. It may happen that after a number of turns a company can not longer hire anyone else according to the rule. In this case it stops hiring, while the other company can continue.
As usual, not all the programmers are created equal. There are three geniuses among them, and each company wants to hire as many geniuses as possible. Note that each company always can guarantee one genius to itself starting with a genius. So the question is, which company will hire two geniuses, if they both use optimal strategies.
Note that both companies have the full information during the hiring: friendship relations, who are geniuses and which programmers were hired by each company in each turn.

## 算法分析

$$\exists i, \; \forall j, \; \sum_{k=1}^3 [d_{k, i} \gt d_{k, j}] \lt 2$$

## 代码

#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne, h[N], d[N], que[N];
struct Edge {
int v, nxt;
} e[N << 2];

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

void get_d(int s, int *d) {
int qb = 0, qe = 1;
d[s] = 0, que = s;
for (; qb < qe;) {
int u = que[qb++];
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + 1)
d[e[i].v] = d[u] + 1, que[qe++] = e[i].v;
}
}

int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0, u, v; i < m; ++i)
memset(d, 0x3f, sizeof d);
for (int i = 0; i < 3; ++i)
get_d(i, d[i]);
bool flag = 0;
for (int i = 0; !flag && i < n; ++i) {
bool ls = 1;
for (int j = 0; ls && j < n; ++j) {
int cnt = 0;
for (int k = 0; k < 3; ++k)
cnt += d[k][i] > d[k][j];
ls &= cnt < 2;
}
flag |= ls;
}
puts(flag ? "1" : "2");
return 0;
}


## 题目描述

Inspired by Stephen Graham, the King of Berland started to study algorithms on strings. He was working days and nights, having a feeling that the full potential in this area is still to be unlocked. And he was right!
One day, all the sudden, he made a huge breakthrough by discovering the fact that strings can be magically transformed into integer numbers. It was so simple! You just have to map different letters to different digits and be careful enough not to introduce any leading zeroes.
Here is what he wrote in his textbook about the string ‘lalala’:

• it can be transformed to an $282828$ by mapping ‘l’ to $2$, and ‘a’ to $8$,
• it can also be transformed to $909090$ by mapping ‘l’ to $9$, and ‘a’ to $0$,
• acouple of examples of invalid transformations are $050505$ (the resulting number has a leading zero), $333333$ (different letters are mapped to the same digit), $123456$ (no mapping to the original letters at all).

But then things started to become more interesting. Obviously, it was known from very beginning that a single string can potentially be mapped to a variety of different integer numbers. But the King couldn’t even imagine that all numbers produced by the same string pattern might have common properties!
For example, every single number that can be produced from string ‘lalala’ is always divisible by $259$, irrespective of the letter-to-digit mapping you choose. Fascinating!
So the King ended up with the following problem. For any given string, he wanted to come up with an algorithm to calculate the set of its divisors. A number is called a divisor of the given string if all positive integers, that could possibly be produced from the given string, are divisible by it.
As usual, the King desperately wants you to help him, so stop thinking and start acting!

## 算法分析

• 引理 $\forall a \le b, \; (a, b) \mid b-a$。

## 代码

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

static int const L = 15;
static int const M = 10000005;
char s[L];
int top, cnt, cc, p[M];
long long v, dv[L], dc[L], ans[M];

long long get_gcd(long long a, long long b) {
for (long long c; b; c = a % b, a = b, b = c)
;
return a;
}

void init() {
top = 0;
for (int i = 2; i < M; ++i) {
if (!p[i])
p[top++] = i;
for (int j = 0; j < top; ++j) {
int k = i * p[j];
if (k >= M)
break;
p[k] = 1;
if (!(i % p[j]))
break;
}
}
}

void dfs(int t, long long v) {
if (t == cnt)
return void(ans[cc++] = v);
for (int i = 0; i <= dc[t]; ++i, v *= dv[t])
dfs(t + 1, v);
}

int main() {
int n;
scanf("%d", &n), init();
for (int _ = 1; _ <= n; ++_) {
printf("Case %d:", _), scanf("%s", s);
int len = strlen(s), st = 0;
for (int c = 0; c < 26; ++c) {
v[c] = 0;
for (int i = 0; i < len; ++i) {
v[c] *= 10;
if (s[i] == c + 'a')
++v[c];
}
st += v[c] > 0;
}
long long gcd = 0;
if (st < 10)
for (int i = 0; i < 26; ++i)
gcd = get_gcd(gcd, v[i]);
else {
int k = 0;
for (int i = 0; i < 26; ++i)
if (v[i])
gcd += k++ * v[i];
for (int i = 0; i < 26; ++i)
for (int j = 0; j < 26; ++j)
if (v[i] && v[j] && v[i] < v[j])
gcd = get_gcd(gcd, v[j] - v[i]);
}
cnt = cc = 0;
for (int i = 0; i < top && 1ll * p[i] * p[i] <= gcd; ++i)
if (!(gcd % p[i])) {
dv[cnt] = p[i], dc[cnt] = 0;
for (; !(gcd % p[i]);)
gcd /= p[i], ++dc[cnt];
++cnt;
}
if (gcd > 1)
dv[cnt] = gcd, dc[cnt] = 1, ++cnt;
dfs(0, 1), std::sort(ans, ans + cc);
for (int i = 0; i < cc; ++i)
printf(" %lld", ans[i]);
puts("");
}
return 0;
}


## 题目描述

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$.

## 代码

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