Meeting

题目描述

Two of the three members of the winning team of one of the ACM regional contests are going to meet in order to train for the upcoming World Finals. They decided that they will meet sometime between $X$ o’clock and $Y$ o’clock. Because they never get anywhere on time (they were late even on the day of the regional contest), they did not set an exact time when they will meet. However, they decided that the one who gets first at the meeting point will not wait more than $Z$ minutes for the other one (they calculated that, if the other one will not come within $Z$ minutes from the arrival of the first of them, then it is very probable that he will not show up at all).
Knowing that, in the end, both of them will show up at some time between $X$ o’clock and $Y$ o’clock (not necessarily after an integer number of minutes), compute which is the probability that they will actually meet.

题意概述

给定整数$X, Y$和实数$Z$,在$X$时到$Y$时之间任选两个时刻,求时刻之差不超过$Z$分钟的概率。
数据范围:$0 \le X \lt Y \le 24, \; 0 \lt Z \le 60(Y-X)$。

算法分析

在平面直角坐标系内以第一个时刻为$x$轴、第二个时刻满足要求的概率为$y$轴画出一个封闭图形,那么答案就是这个图形的面积除以$X$时与$Y$时之差。分两种情况讨论:$2Z \le 60(Y-X)$和$2Z \gt 60(Y-X)$。两种情况得到的封闭图形均为一个${Z \over 60(Y-X)} \times 60(Y-X)$的矩形加上一个下底长$60(Y-X)$的梯形(上底可为$0$)。前者上底加下底为$2(60(Y-X)-Z)$,高为${Z \over 60(Y-X)}$;后者上底加下底为$2Z$,高为$(1-{Z \over 60(Y-X)})$。

代码

#include <cstdio>

using namespace std;

struct Solver {
private:
  int x, y; double z;
  void input() { scanf(" %d %d %lf", &x, &y, &z); }
  void process() {
    int all = (y - x) * 60;
    double sum = 0;
    if (2 * z <= all) sum = z + 2 * (all - z) * (z / all) / 2;
    else sum = z + 2 * z * (1 - z / all) / 2;
    printf("%.8lf\n", sum / all);
  }

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

int main() {
  solver.solve();
  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;
}

Jumping Joe

题目描述

Joe is a frog who likes to jump a lot. In fact, that’s all he does: he jumps forwards and backwards on the integer axis (a straight line on which all the integer numbers, both positive and negative are marked). At first, Joe sits next to the point marked with $0$. From here, he can jump in the positive or the negative direction a distance equal to either $x_1$ or $x_2$. From the point where he arrived, he can jump again a distance equal to $x_1$ or $x_2$, in the positive or the negative direction and so on.. Joe wants to arrive next to the point marked with the number $P$, after exactly $K$ jumps. You have to decide whether such a thing is possible.

题意概述

给定$x_1, x_2, P, K$,求一组非负整数$(P_1, N_1, P_2, N_2)$满足:
$$
\left\{
\begin{align}
P_1x_1-N_1x_1+P_2x_2-N_2x_2&=P \\
P_1+N_1+P_2+N_2&=K
\end{align}
\right.
$$
数据范围:$0 \lt x_1, x_2 \lt 40000, \; -40000 \lt P \lt 40000, \; 0 \le K \lt 2 \times 10^9$。

算法分析

设$g=(x_1, x_2)$,如果$g \not \mid P$则无解,否则可以将$x_1, x_2, P$同时除以$g$,对答案没有影响。
设$a=P_1-N_1, \; b=P_2-N_2$,则$ax_1+bx_2=P$,可用扩展GCD求出它的一组解。若$(a, b)$是一组解,则$(a+kx_2, b-kx_1)$也是一组解。只要在$\pm P$的范围内枚举$k$,判断是否存在$(P_1, N_1, P_2, N_2)$满足第二个方程即可。

代码

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

#define int long long

using namespace std;

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:
  int x1, x2, p, k;
  void input() { io > x1 > x2 > p > k; }
  int ex_gcd(int a, int b, int &x, int &y) {
    if (! b) { x = 1, y = 0; return a; }
    int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
  }
  bool check(int x, int y) {
    if (abs(x) + abs(y) > k) return false;
    if (k - abs(x) - abs(y) & 1) return false;
    io < (char *) "YES\n";
    int t = k - abs(x) - abs(y) >> 1;
    if (x > 0) io < x + t < ' ' < t < ' ';
    else io < t < ' ' < -x + t < ' ';
    if (y > 0) io < y < ' ' < 0 < '\n';
    else io < 0 < ' ' < -y < '\n';
    return true;
  }
  void process() {
    int x, y, gcd = ex_gcd(x1, x2, x, y);
    if (p % gcd) io < (char *) "NO\n";
    else {
      x1 /= gcd, x2 /= gcd, p /= gcd, x *= p, y *= p;
      for (int i = -abs(p) - 1; i <= abs(p) + 1; ++ i)
        if (check(x + x2 * i, y - x1 * i)) goto label;
      io < (char *) "NO\n";
      label: ;
    }
  }

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

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

Integer Sequences

题目描述

A sequence $A$ is called an integer sequence of length $N$ if all its elements $A_1, A_2, \ldots, A_N$ are non-negative integers less than $2000000000$. Consider two integer sequences of length $N, A$ and $X$. The result of their multiplication $(A \cdot X)$ is an integer number $R=\sum_{i=1}^N A_iX_i$. Your task is to solve the equation $A \cdot X \equiv B \pmod P$, given the integer sequence $A$ and the integer numbers $B$ and $P$.

题意概述

给定一个长度为$N$的向量$A$、两个整数$B, P$,求一个长度为$N$的向量$X$使得$A \cdot X \equiv B \pmod P$。向量中的数均为非负整数。
数据范围:$1 \le N \le 100, \; 0 \le B \lt P \le 10000$。

算法分析

设$g_i$表示$(A_1, A_2, \ldots, A_i)$,则有如下方程:
$$
\left\{
\begin{align}
A_1x_1+A_2y_1&=g_2 \\
g_2x_2+A_3y_2&=g_3 \\
\cdots& \\
g_{N-1}x_{N-1}+A_Ny_{N-1}&=g_N \\
g_Nx_N+Py_N&=(g_N, P)
\end{align}
\right.
$$
若$B \nmid (g_N, P)$,则无解;否则,解出所有$x_i, y_i$,即可还原出所有$X_i={B \over (g_N, P)} \cdot y_{i-1} \cdot \prod_{j=i}^N x_j$。

代码

#include <cctype>
#include <cstdio>

using namespace std;

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 = 101;
  int n, p, m, a[N], x[N], y[N];
  int ex_gcd(int a, int b, int &x, int &y) {
    if (! b) { x = 1, y = 0; return a; }
    int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
  }
  void input() {
    io > n > p > m;
    for (int i = 1; i <= n; ++ i) io > a[i], a[i] %= p;
  }
  void process() {
    int g = a[1]; x[0] = y[0] = 1;
    for (int i = 2; i <= n; ++ i) g = ex_gcd(g, a[i], x[i - 1], y[i - 1]);
    g = ex_gcd(g, p, x[n], y[n]);
    if (m % g) io < (char *) "NO\n";
    else {
      io < (char *) "YES\n", g = m / g;
      for (int i = 1; i <= n; ++ i) {
        int t = g * (y[i - 1] + p);
        for (int j = i; j <= n; ++ j) t = 1ll * t * (x[j] + p) % p;
        io < t < ' ';
      }
      io < '\n';
    }
  }

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

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

Games of Chess

题目描述

$N$ friends gathered in order to play chess, according to the following rules. In the first game, two of the $N$ friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the $N$ friends played, find a schedule for the games, so that the above rules are obeyed.

题意概述

有$N$个人玩游戏,第一局任意两个人参加,第一局胜利者和除他以外的一个人参加第二局(可以选择第一局失败者),第二局胜利者和除他以外的一个人参加第三局…不存在平局。给定每个人参加游戏的局数,构造一种可行的游戏方案。
数据范围:$2 \le N \le 100$。

算法分析

显然每个人参加游戏的次数之和为偶数,除以$2$即是游戏局数。考虑安排每一局的胜利者和失败者。设某个人参加游戏的次数为$n$,则先安排他连续胜利$(n-1)$局,接着失败一局,直到安排了所有局的胜利者。在安排失败者的时候,要注意不能和胜利者相同,因此应尽量先安排参加游戏局数较多的人胜利,减少冲突的可能。

代码

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

using namespace std;

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 = 110;
  int n, sum;
  pair <int, int> a[N];
  vector <pair <int, int> > ans;
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > a[i].first, a[i].second = i, sum += a[i].first;
  }
  void process() {
    io < sum >> 1 < '\n';
    sort(a + 1, a + n + 1, greater <pair <int, int> >());
    int p = 1;
    for (int i = 0; i < sum >> 1; ++ i) {
      if (a[p].first == 1) ans.push_back(make_pair(a[p + 1].second, a[p].second)), -- a[p].first, -- a[++ p].first;
      else ans.push_back(make_pair(a[p].second, 0)), -- a[p].first;
    }
    for (int i = 0; i < sum >> 1; ++ i)
      if (! ans[i].second)
        for (int j = 1; j <= n; ++ j) if (a[j].first && a[j].second != ans[i].first) { ans[i].second = a[j].second, -- a[j].first; break; }
    for (int i = 0; i < sum >> 1; ++ i) io < ans[i].first < ' ' < ans[i].second < '\n';
  }

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

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