Hack It!

题目描述

Little X has met the following problem recently.
Let’s define $f(x)$ as the sum of digits in decimal representation of number $x$ (for example, $f(1234)=1+2+3+4$). You are to calculate $\sum_{i=l}^r f(i) \bmod a$.
Of course Little X has solved this problem quickly, has locked it, and then has tried to hack others. He has seen the following C++ code:

ans = solve(l, r) % a;
if (ans <= 0) ans += a;

This code will fail only on the test with $\sum_{i=l}^r f(i) \equiv 0 \pmod a$. You are given number $a$, help Little X to find a proper test for hack.

题意概述

令$f(i)$表示$i$各位数字之和。给定$a$,要求找出一对$(l, r)$满足$\sum_{i=l}^r f(i) \equiv 0 \pmod a$。
数据范围:$1 \le a \le 10^{18}$。

算法分析

思路很巧妙。有一个显而易见的结论:$\forall i \in [1, 10^{18}], \; f(i)+1=f(i+10^{18})$。它有一个推论:$\forall x \in [1, 10^{18}], \; 1+\sum_{i=x}^{x+10^{18}-1} f(i)=\sum_{i=x+1}^{x+10^{18}} f(i)$。因此只要算出$t=\sum_{i=1}^{10^{18}} f(i) \bmod a$,将区间右移$a-t$单位。

代码

#include <cstdio>

long long mul(long long a, long long b, long long mod) {
  long long ret = 0;
  while (b) b & 1 && ((ret += a) %= mod), (a <<= 1) %= mod, b >>= 1;
  return ret;
}

int main() {
  long long n; scanf("%lld", &n);
  long long cur = mul(1800000000000000000ll, 45, n) + 1, l = 1, r = 1000000000000000000ll;
  l += n - cur, r += n - cur, printf("%lld %lld\n", l, r);
  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;
}

Funny Strings

题目描述

Let’s consider a string of non-negative integers, containing $N$ elements. Suppose these elements are $S_1, S_2, \ldots, S_N$, in the order in which they are placed inside the string. Such a string is called ‘funny’ if the string $S_1+1, S_2, S_3, \ldots, S_{N-1}, S_N-1$ can be obtained by rotating the first string (to the left or to the right) several times. For instance, the strings $2, 2, 2, 3$ and $1, 2, 1, 2, 2$ are funny, but the string $1, 2, 1, 2$ is not. Your task is to find a funny string having $N$ elements, for which the sum of its elements $S_1+S_2+ \cdots +S_N$ is equal to $K$.

题意概述

定义序列的旋转操作为将序列的最后一个元素移到最前面,定义两个序列等价当且仅当可以通过若干次旋转操作使它们相同,定义一个序列是funny的当且仅当将它的第一个元素加一、最后一个元素减一后得到的序列和原序列等价。要求构造一个长度为$N$、元素之和为$K$的funny序列(所有元素均为非负整数)。
数据范围:$2 \le N \le 1000, \; 1 \le K \le 30000, \; (N, K)=1$。

算法分析

我们只考虑$1 \le K \le N$的情况,因为其他情况都可以通过把所有数减去同一个数得到这种情况。
显然,第一个数一定比最后一个数小$1$,否则新序列和原序列中某些数字出现的次数不同。假设我们有新旧序列如下:
0_______1(旧)
1_______0(新)
新旧序列中空位上的数字是一样的。这意味着我们只要知道了旋转次数,就可以构造出序列。假设旋转次数是$a$,那么第$i$位的数就旋转到了第$((i+a-1)\%N+1)$位。下面模拟$N=9, a=7$的构造过程:
第$8$位
0______11
1______10
第$6$位
0____1_11
1____1_10
第$4$位
0__1_1_11
1__1_1_10
第$2$位
01_1_1_11
11_1_1_10
第$9$位,构造完成
010101011
110101010
由于元素之和为$K$,因此序列中有$K$个$1$,也就是说,从第$1$位开始,模拟$K$次,到达第$N$位。那么$N-1 \equiv K \times a \pmod N$,$a \equiv (N-1) \times K^{-1} \pmod N$。因为$(N, K)=1$,所以$a$一定存在,接下来只要模拟即可。当然也可以用暴力求出$a$。

代码

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

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 = 1010;
  int n, k, a[N];
  void input() { io > n > k; }
  void init() {
    int t = k / n;
    for (int i = 1; i <= n; ++ i) a[i] = t, k -= t;
  }
  void process() {
    int sum = n - 1;
    while (sum % k) sum += n;
    int p = sum / k + 1;
    for (; p < n; p = (p - 1 + sum / k) % n + 1) ++ a[p]; ++ a[n];
    for (int i = 1; i <= n; ++ i) io < a[i] < ' ';
    io < '\n';
  }

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

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

Erasing Edges

题目描述

Little Johnny painted on a sheet of paper a polygon with $N$ vertices. Then, for every edge of the polygon, he drew the middle point of the edge. After that, he went to school. When he came back, he found out that his brother had erased the polygon (both the edges and the vertices). The only thing left were the middle points of the edges of the polygon. Help Johnny redraw his polygon.

题意概述

给定一个$N$边形各边的中点,还原这个$N$边形。边可以相交。
数据范围:$3 \le N \le 10000$。

算法分析

设$N$边形第$i$个点的坐标为$(x_i, y_i)$,第$i$条边中点的坐标为$(x_i’, y_i’)$,可以得到以下方程
$$
\left\{
\begin{array}{c}
x_1+x_2=2x_1′ \\
x_2+x_3=2x_2′ \\
\cdots \\
x_N+x_1=2x_N’
\end{array}
\right.
$$
对$y$同理。当$N$为奇数时,方程有唯一解,解出即可;当$N$为偶数时,方程无解或有无数解,只需尝试构造一组解并判断是否合法。

代码

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

#define random (1.0 * rand() / RAND_MAX)

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) {
  return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1;
}

struct Point {
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
  Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
  Point operator * (const double &n) const { return Point(x * n, y * n); }
  Point operator / (const double &n) const { return *this * (1 / n); }
  Point operator | (const Point &p) const { return *this + (p - *this) * 2; }
};

struct Solver {
private:
  static const int N = 10010;
  int n;
  Point point[N];
  vector <Point> ans;
  void input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
  }
  void process() {
    Point p;
    if (n & 1) {
      double sum = 0;
      for (int i = 1; i <= n; ++ i) sum += point[i].x;
      for (int i = 2; i <= n; i += 2) sum -= point[i].x * 2;
      p.x = sum, sum = 0;
      for (int i = 1; i <= n; ++ i) sum += point[i].y;
      for (int i = 2; i <= n; i += 2) sum -= point[i].y * 2;
      p.y = sum;
    } else p = Point(random * 100000, random * 100000);
    for (int i = 1; i <= n; ++ i) ans.push_back(p), p = p | point[i];
    if (cmp(p.x, ans[0].x) || cmp(p.y, ans[0].y)) printf("NO\n");
    else {
      printf("YES\n");
      for (int i = 0; i < ans.size(); ++ i) printf("%.6lf %.6lf\n", ans[i].x, ans[i].y);
    }
  }

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

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

Open the Brackets

题目描述

There is a syntactically correct boolean expression.
The definition of syntactically correct expression follows as:

  1. “a”, “b”, “c”, …, “j” are syntactically correct expressions.
  2. If A is a correct expression, then !A and (A) are correct expressions too.
  3. If A is a correct expression and B is a correct expression, then A||B, A&B, A<=>B, A=>B, A#B are syntactically correct expressions too.

Syntactically correct expression doesn’t contain spaces.
Small Latin letters are variables, ! denotes negation, || – disjunction, & – conjunction, <=> – equality, => – implication, # – excepting or.
Negation has the highest priority, conjunction has middle priority, and other operations have low priority. Brackets change the order of operations executing.
Two expressions are called identical if their values are the same in any values of variables.
Make the expression, which will be identical with given expression. New expression must be free of brackets.

题意概述

将一个逻辑表达式$s$转化成一个不包含括号的等价表达式$t$。保证$s$中变量的个数不超过$10$。
数据范围:$1 \le |s| \le 2048, \; 1 \le |t| \le 32768$。

算法分析

由于变量数不超过$10$,因此可以枚举每个变量的值,计算表达式的值,若为真,则在答案中加入这个状态(状态间用||隔开,变量间用&隔开)。如果最后答案为空,则直接输出!a&a

代码

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

using namespace std;

struct Solver {
private:
  string s;
  void input() { cin >> s; }
  int len(char c) {
    switch (c) {
      case '!' : return 0;
      case '&' : return 0;
      case '|' : return 1;
      case '<' : return 2;
      case '=' : return 1;
      case '#' : return 0;
    }
  }
  int priority(char c) {
    switch (c) {
      case '!' : return 1;
      case '&' : return 2;
      case '|' : return 3;
      case '<' : return 3;
      case '=' : return 3;
      case '#' : return 3;
      case '(' : return 4;
    }
  }
  bool single(bool a, char c, bool b) {
    switch (c) {
      case '&' : return a && b;
      case '|' : return a || b;
      case '<' : return a == b;
      case '=' : return a || ! b;
      case '#' : return a ^ b;
    }
  }
  int match(string s, int p) {
    int cnt = 1;
    while (cnt) ++ p, cnt += (s[p] == '(') - (s[p] == ')');
    return p;
  }
  stack <char> symbol;
  stack <bool> number;
  void pop() {
    if (symbol.top() == '!') {
      symbol.pop(); bool p = number.top(); number.pop(), number.push(! p);
    } else {
      bool p = number.top(); number.pop();
      bool q = number.top(); number.pop();
      number.push(single(p, symbol.top(), q));
      symbol.pop();
    }
  }
  bool calc(string s) {
    for (int i = 0; i < s.length(); ++ i) {
      if (isdigit(s[i])) number.push(s[i] - '0');
      else if (s[i] == '(') symbol.push('(');
      else if (s[i] == ')') {
        while (symbol.top() != '(') pop();
        symbol.pop();
      } else {
        while (! symbol.empty() && priority(symbol.top()) <= priority(s[i])) pop();
        symbol.push(s[i]), i += len(s[i]);
      }
    }
    while (! symbol.empty()) pop();
    return number.top();
  }
  bool check(int p, string s) {
    for (int i = 0; i < s.length(); ++ i)
      if (isalpha(s[i])) s[i] = ((p & 1 << s[i] - 'a') > 0) + '0';
    return calc(s);
  }
  void process() {
    for (int i = 0; i + 1 < s.length(); ++ i)
      while (i + 1 < s.length() && s[i] == '!' && s[i + 1] == '!')
        s = s.substr(0, i) + s.substr(i + 2);
    string ans, sep;
    for (int i = 0; i < 1 << 10; ++ i)
      if (check(i, s)) {
        ans += sep, sep = "||";
        string s;
        for (int j = 0; j < 10; ++ j) {
          ans += s, s = "&";
          if (! (i & 1 << j)) ans += "!";
          ans += j + 'a';
        }
      }
    if (ans.length() == 0) ans = "!a&a";
    cout << ans << endl;
  }

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

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

Snake

题目描述

There are $N$ points given by their coordinates on a plane. All coordinates $(x_i, y_i)$ are integers in a range from $-10000$ up to $10000$ inclusive . It is necessary to construct a broken line satisfying the following conditions:

  • The broken line should be closed.
  • End points of each segment (verteces) of the broken line can only be the given points, and all given points should be used.
  • Each two consecutive segments of the broken line should form a corner of 90 degrees in each vertex point.
  • The sides of the broken line should be parallel to coordinate axes.
  • The broken line should have no self-crossing and self-contact.
  • The broken line should have the minimal length.

You have to either find the length $L$ of the constructed broken line, or determine that it is impossible to construct such a broken line.

题意概述

平面上有$N$个点,现在要用这$N$个点构造一个图形,满足:

  • 这个图形是闭合的;
  • 每条边的端点必须是给定的点,且每个给定的点必须被用到;
  • 每个点连接的两条边必须互相垂直;
  • 每条边必须平行于坐标轴;
  • 任意两条边除了顶点外不能相交;
  • 这个图形的周长最小。

如果有解,输出最小周长,否则输出$0$。
数据范围:$4 \le N \le 10000$。

算法分析

将所有点以横坐标为第一关键字、纵坐标为第二关键字从小到大排序。
显然,如果有解,那么对于任意整数$x$,横坐标等于$x$的点的个数必须是偶数个,只要将第一个点和第二个点、第三个点和第四个点…相连,再以纵坐标为第一关键字、横坐标为第二关键字从小到大排序,进行一样的操作。最后需要判断是否连通以及是否有相交。

代码

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

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 Point { int x, y, id; };

bool cmpx(Point a, Point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmpy(Point a, Point b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct Line { Point a, b; };

struct Solver {
private:
  static const int N = 10010;
  int n, top, fa[N];
  Point point[N];
  Line line[N];
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > point[i].x > point[i].y, point[i].id = i;
  }
  bool inter(Line p, Line q) {
    if (p.a.x == p.b.x && q.a.x == q.b.x) {
      if (p.a.y > q.a.y) swap(p, q);
      if (p.a.x != q.a.x) return false;
      else return p.b.y > q.a.y;
    } else if (p.a.y == p.b.y && q.a.y == q.b.y) {
      if (p.a.x > q.a.x) swap(p, q);
      if (p.a.y != q.a.y) return false;
      else return p.b.x > q.a.x;
    } else {
      if (p.a.x != p.b.x) swap(p, q);
      return p.a.y < q.a.y && q.a.y < p.b.y && q.a.x < p.a.x && p.a.x < q.b.x;
    }
  }
  int get_fa(int t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
  void process() {
    int l = 0, r = 0, cnt = n - 1;
    sort(point + 1, point + n + 1, cmpx);
    for (int i = 1; i <= n; i = r) {
      l = i, r = i + 1;
      while (r <= n && point[r].x == point[l].x) ++ r;
      if (r - l & 1) { io < 0 < '\n'; return; }
      for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
    }
    sort(point + 1, point + n + 1, cmpy);
    for (int i = 1; i <= n; i = r) {
      l = i, r = i + 1;
      while (r <= n && point[r].y == point[l].y) ++ r;
      if (r - l & 1) { io < 0 < '\n'; return; }
      for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
    }
    sort(point + 1, point + n + 1, cmpi);
    for (int i = 1; i <= top; ++ i)
      if (line[i].a.x > line[i].b.x || line[i].a.y > line[i].b.y) swap(line[i].a, line[i].b);
    for (int i = 1; i < top; ++ i)
      for (int j = i + 1; j <= top; ++ j)
        if (inter(line[i], line[j])) { io < 0 < '\n'; return; }
    for (int i = 1; i <= n; ++ i) fa[i] = i;
    for (int i = 1; i <= top; ++ i) {
      int p = get_fa(line[i].a.id), q = get_fa(line[i].b.id);
      if (p != q) fa[p] = q, -- cnt;
    }
    if (cnt) { io < 0 < '\n'; return; }
    int ans = 0;
    for (int i = 1; i <= top; ++ i) ans += line[i].b.x - line[i].a.x + line[i].b.y - line[i].a.y;
    io < ans < '\n';
  }

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

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

The Book

题目描述

There is a group of $N$ people which are numbered $1$ through $N$, and everyone of them has not less than $\left[ {N + 1 \over 2} \right]$ friends. A man with number $1$ has the book, which others want to read. Write the program which finds a way of transferring the book so that it will visit every man only once, passing from the friend to the friend, and, at last, has come back to the owner. Note: if A is a friend of B then B is a friend of A.

题意概述

在一个满足Ore性质的图中寻找一条哈密顿回路。
数据范围:$2 \le N \le 1000$。

算法分析

Ore性质:一张阶数等于$N$的图中任意两个不相邻的点的度数之和不小于$N$。
若简单图$G$满足Ore性质,且阶数大于$2$,则图$G$中一定存在哈密顿回路。
考虑先从点$1$开始构造一条链,接着对这条链进行扩展:

  • 在链上找到一点$p$(设它的下一个点是$q$),满足链头和$q$连通、链尾和$p$连通,可以删去$p$、$q$之间的边,连接链头和$q$、链尾和$p$,构成一个环;
  • 如果环上的点数小于$N$,找到一个和环上一点$p$连通且不在环上的点$q$,可以删去一条$p$的边,连接$p$和$q$,构成一条链,回到上一步。

代码

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

using namespace std;

int read(char s[]) {
  char c = getchar(); int len = 0;
  while (~ c && c != '\n') s[len ++] = c, c = getchar();
  s[len] = '\0'; return len;
}

struct Solver {
private:
  static const int N = 1010;
  int n, pre[N], nxt[N], near[N];
  bool mp[N][N], vis[N];
  char s[N << 3];
  void input() {
    scanf("%d", &n), read(s);
    for (int i = 1; i <= n; ++ i) {
      int len = read(s), t = 0;
      for (int j = 0; j <= len; ++ j)
        if (isdigit(s[j])) (t *= 10) += s[j] - '0'; else mp[i][t] = true, t = 0;
    }
  }
  void dfs(int t, int fa) {
    vis[t] = true;
    for (int i = 1; i <= n; ++ i)
      if (mp[t][i] && ! vis[i]) { nxt[t] = i, pre[i] = t, dfs(i, t); return; }
  }
  int get_pre(int t) { if (! pre[t]) return t; else return get_pre(pre[t]); }
  int get_nxt(int t) { if (! nxt[t]) return t; else return get_nxt(nxt[t]); }
  void reverse(int p) {
    nxt[p] = pre[p]; if (! pre[p]) return; reverse(pre[p]), pre[pre[p]] = p;
  }
  void process() {
    int cnt = 0; dfs(1, 0);
    for (int i = 1; i <= n; ++ i) cnt += pre[i] || nxt[i];
    for (int i = 1; i <= n; ++ i) if (pre[i] || nxt[i])
      for (int j = 1; j <= n; ++ j) if (mp[i][j] && ! pre[j] && ! nxt[j]) near[j] = i;
    while (cnt <= n) {
      int head = 0, tail = 0;
      for (int i = 1; i <= n; ++ i) if (pre[i]) { head = get_pre(i); break; }
      for (int i = 1; i <= n; ++ i) if (nxt[i]) { tail = get_nxt(i); break; }
      int p = head;
      for (; nxt[p]; p = nxt[p])
        if (mp[nxt[p]][head] && mp[p][tail]) {
          int tmp = nxt[p]; pre[tmp] = nxt[p] = 0, reverse(p);
          nxt[head] = tmp, pre[tmp] = head, nxt[tail] = p, pre[p] = tail;
          break;
        }
      if (cnt < n)
        for (int i = 1; i <= n; ++ i) if (! pre[i] && ! nxt[i] && near[i]) {
          nxt[i] = near[i], nxt[pre[near[i]]] = 0, pre[near[i]] = i;
          for (int j = 1; j <= n; ++ j) if (mp[i][j] && ! pre[j] && ! nxt[j]) near[j] = i;
          break;
        }
      ++ cnt;
    }
    int p = 1; putchar('1');
    do printf(" %d", p = nxt[p]); while (p != 1);
    putchar('\n');
  }

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

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

Bridges Painting

题目描述

New Berland consists of $N$ islands, some of them are connected by bridges. There can be no more than one bridge between any pair of islands. Mr. President issued a law to paint all bridges. A bridge can be painted white or black. Any island must have at least one white bridge and at least one black (of course if an island has more than one bridge).

题意概述

给定一张图,要求将所有边染成黑白两种颜色,使得每个度数大于$1$的点的连边都至少有一条黑色和一条白色。
数据范围:$1 \le N \le 100$。

算法分析

显然,我们可以分别考虑每个连通块。如果某个连通块仅由一个奇环构成,则不存在合法方案;否则,在连通块内任选一个度数不为$2$的点,从它开始进行交错染色(DFS);如果所有点的度数均为$2$,则任选一个点开始进行交错染色,再检验合法性。证明如下:

考虑DFS的过程。如果DFS经过一个点(进入并出去),根据交错染色的原则,入边和出边的颜色一定不相同。对于连通块内某个度数为$1$的点,它的连边可以任意染色;而对于度数大于$2$的点,如果从它开始DFS,则一定会再经过这个点至少一次。

由此得证。

代码

#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, col[N][N];
  vector <int> mp[N];
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) {
      int t; io > t;
      while (t) mp[i].push_back(t), io > t;
    }
  }
  void dfs(int t, int c) {
    for (int i = 0; i < mp[t].size(); ++ i)
      if (! col[t][mp[t][i]]) col[t][mp[t][i]] = col[mp[t][i]][t] = c, dfs(mp[t][i], c = 3 - c);
  }
  void process() {
    for (int i = 1; i <= n; ++ i) if (mp[i].size() != 2) dfs(i, 1);
    for (int i = 1; i <= n; ++ i) dfs(i, 1);
    for (int i = 1; i <= n; ++ i) {
      bool w = false, b = false;
      for (int j = 0; j < mp[i].size(); ++ j) w |= col[i][mp[i][j]] == 1, b |= col[i][mp[i][j]] == 2;
      if (mp[i].size() > 1 && ! (w && b)) { io < (char *) "No solution\n"; return; }
    }
    for (int i = 1; i <= n; ++ i) {
      for (int j = 0; j < mp[i].size(); ++ j) io < col[i][mp[i][j]] < ' ';
      io < 0 < '\n';
    }
  }

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

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