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

Another Chocolate Maniac

题目描述

Bob really LOVES chocolate. He thinks he never gets enough. Imagine his joy when his parents told him that they would buy him many rectangular chocolate pieces for his birthday. A piece of chocolate is a $2 \times 1$ or $1 \times 2$ rectangle. Bob’s parents also bought him a nice birthday cake, which can be imagined as a matrix having $M$ rows and $N$ columns. Some positions on the cake are occupied by candles, the others are empty. Bob’s parents asked their son to place as many chocolate pieces as he can on the empty squares on the cake, in such a manner that no two chocolate pieces overlap. However, he would like to keep the chocolate pieces to himself. That’s why, he wants to place only a minimal amount of them on the cake and keep the rest. In order not to make Mon and Dad suspicious, Bob wants to place the chocolate pieces in such a way, that no other piece may be placed on the cake (that is, there won’t exist any two adjacent empty squares). Find the minimal number of pieces which need to be placed on the cake, so that they do not overlap and no extra piece may be added.

题意概述

给定一个$M \times N$的网格,其中有些格子是满的。要求用$2 \times 1$和$1 \times 2$两种方块填充空格子,使得不存在两个相邻的空格子。求至少需要多少方块。
数据范围:$1 \le M \le 70, \; 1 \le N \le 7$。

算法分析

令$f_{i, j, k}$表示处理到第$i$行,第$(i-1)$行的状态为$j$且第$i$行的状态为$k$的方案数。转移时要注意判断上下两行是否有相邻的空格子。

代码

#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 = 80;
  static const int M = 8;
  int n, m, f[2][1 << M][1 << M], mp[N];
  void input() {
    io > n > m;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
        char c; io > c, (mp[i] <<= 1) += c == '*';
      }
    mp[0] = mp[n + 1] = mp[n + 2] = (1 << m) - 1;
  }
  void init() { memset(f, 0x1f, sizeof f), f[0][mp[0]][mp[1]] = 0; }
  bool check(int s) {
    bool flag = false;
    for (int i = 0; i < m; s >>= 1, ++ i) {
      if (s & 1) flag = false;
      else { if (flag) return false; flag = true; }
    }
    return true;
  }
  void update(int x, int a, int b, int s, int val, int p) {
    if (check(b) && ! ((1 << m) - 1 - a & (1 << m) - 1 - b)) minify(f[x][b][s], val);
    for (int i = p; i < m; ++ i)
      if (! (b & 1 << i)) {
        if (! (s & 1 << i)) update(x, a, b | 1 << i, s | 1 << i, val + 1, i + 1);
        if (i && ! (b & 1 << i - 1)) update(x, a, b | 1 << i | 1 << i - 1, s, val + 1, i + 1);
      }
  }
  void process() {
    int cur = 0;
    for (int i = 1; i <= n + 1; cur ^= 1, ++ i) {
      memset(f[cur ^ 1], 0x1f, sizeof f[cur ^ 1]);
      for (int j = 0; j < 1 << m; ++ j)
        for (int k = 0; k < 1 << m; ++ k)
          if (f[cur][j][k] < 5e8) update(cur ^ 1, j, k, mp[i + 1], f[cur][j][k], 0);
    }
    io < f[cur][(1 << m) - 1][(1 << m) - 1] < '\n';
  }

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

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

Hardwood Floor

题目描述

The banquet hall of Computer Scientists’ Palace has a rectangular form of the size $M \times N$. It is necessary to lay hardwood floors in the hall. There are wood pieces of two forms:

  • rectangles ($2 \times 1$)
  • corners (squares $2 \times 2$ without one $1 \times 1$ square)

You have to determine $X$ – the number of ways to cover the banquet hall.
Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.

题意概述

有一个$M \times N$的网格,要求用两种方块覆盖它,一种是$2 \times 1$的方块,一种是$2 \times 2$挖去$1 \times 1$的方块。方块可以旋转。求方案数。
数据范围:$1 \le M, N \le 9$。

算法分析

用$f_{i, j}$表示前$(i-1)$行都已填满且第$i$行的状态为$j$的方案数,转移时枚举$j$可以转移到的状态。暴力计算即可发现合法的转移不会太多。

代码

#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:
  static const int N = 11;
  int n, m, f[N][1 << N];
  void input() { io > n > m; }
  void update(int x, int y, int s, int val, int p) {
    if (y == (1 << m) - 1) { f[x][s] += val; return; }
    for (int i = p; i < m; ++ i)
      if (! (y & 1 << i)) {
        if (! (s & 1 << i)) {
          update(x, y | 1 << i, s | 1 << i, val, i + 1);
          if (i && ! (s & 1 << i - 1)) update(x, y | 1 << i, s | 1 << i | 1 << i - 1, val, i + 1);
          if (i < m - 1 && ! (s & 1 << i + 1)) update(x, y | 1 << i, s | 1 << i | 1 << i + 1, val, i + 1);
        }
        if (i < m - 1 && ! (y & 1 << i + 1)) {
          update(x, y | 1 << i | 1 << i + 1, s, val, i + 2);
          if (! (s & 1 << i)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i, val, i + 2);
          if (! (s & 1 << i + 1)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i + 1, val, i + 2);
        }
      }
  }
  void process() {
    f[0][(1 << m) - 1] = 1;
    for (int i = 0; i <= n; ++ i)
      for (int j = 0; j < 1 << m; ++ j)
        if (f[i][j]) update(i + 1, j, 0, f[i][j], 0);
    io < f[n + 1][0] < '\n';
  }

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

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

Inheritance

题目描述

The old King decided to divide the Kingdom into parts among his three sons. Each part is a polygonal area. Taking into account the bad temper of the middle son the King gave him a part of Kingdom such that moving straight from any place of this part to any other place of this part he will not cross the boundary.
There are several mineral deposits in the Kingdom. Each mineral deposit looks like a straight line segment. The middle son wants to know what part of mineral deposits is located inside his territory (not including the boundaries).

题意概述

给定一个凸$N$边形,求一条线段在它内部的长度(不包括边界)。
数据范围:$3 \le N \le 400$。

算法分析

由于点的顺序是随机的,因此需要先求凸包,接着计算线段与凸包的交点,根据交点个数来分类讨论。
此题细节很多,需要考虑线段与某条边共线、线段顶点在某条边上、线段经过某个顶点等情况。

代码

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

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) {};
  bool operator < (const Point &p) const { return ! cmp(x, p.x) ? cmp(y, p.y) == -1 : cmp(x, p.x) == -1; }
  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 &a) const { return Point(x * a, y * a); }
  Point operator / (const double &a) const { return Point(x / a, y / a); }
  double operator * (const Point &p) const { return x * p.y - y * p.x; }
  double operator ! () const { return sqrt(x * x + y * y); }
};

struct Line {
  Point a, b;
  Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
  bool operator | (const Line &l) const { return ! cmp((b - a) * (l.b - l.a), 0); }
  Point operator & (const Line &l) const {
    double t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b));
    return a + (b - a) * t;
  }
};

struct Solver {
private:
  static const int N = 410;
  int n, q, top;
  Point point[N], sta[N];
  vector <Point> poly;
  void input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
    scanf("%d", &q);
  }
  void init() {
    sort(point + 1, point + n + 1);
    for (int i = 1; i <= n; ++ i) {
      while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
      sta[++ top] = point[i];
    }
    for (int i = 1; i <= top; ++ i) poly.push_back(sta[i]); top = 0;
    for (int i = n; i; -- i){
      while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
      sta[++ top] = point[i];
    }
    for (int i = 2; i < top; ++ i) poly.push_back(sta[i]);
  }
  bool in(Point p) {
    for (int i = 0; i < poly.size(); ++ i)
      if (cmp((poly[(i + 1) % poly.size()] - poly[i]) * (p - poly[i]), 0) < 0) return false;
    return true;
  }
  void process() {
    Line l;
    scanf("%lf%lf%lf%lf", &l.a.x, &l.a.y, &l.b.x, &l.b.y);
    for (int i = 0; i < poly.size(); ++ i) {
      Line tmp(poly[i], poly[(i + 1) % poly.size()]);
      if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
        printf("0.00\n"); return;
      }
    }
    vector <Point> inter;
    for (int i = 0; i < poly.size(); ++ i)
      if (! (Line(poly[i], poly[(i + 1) % poly.size()]) | l)) {
        Line tmp = Line(poly[i], poly[(i + 1) % poly.size()]);
        Point p = tmp & l;
        if ((cmp(p.x, l.a.x) || cmp(p.y, l.a.y)) && (cmp(p.x, l.b.x) || cmp(p.y, l.b.y)) && cmp(min(l.a.x, l.b.x), p.x) < 1 && cmp(p.x, max(l.a.x, l.b.x)) < 1 && cmp(min(l.a.y, l.b.y), p.y) < 1 && cmp(p.y, max(l.a.y, l.b.y)) < 1 && cmp(min(tmp.a.x, tmp.b.x), p.x) < 1 && cmp(p.x, max(tmp.a.x, tmp.b.x)) < 1 && cmp(min(tmp.a.y, tmp.b.y), p.y) < 1 && cmp(p.y, max(tmp.a.y, tmp.b.y)) < 1) {
          for (int j = 0; j < inter.size(); ++ j) if (! cmp(inter[j].x, p.x) && ! cmp(inter[j].y, p.y)) goto label;
          inter.push_back(p);
        }
        label: ;
      }
    for (int i = 0; i < poly.size(); ++ i) {
      Line tmp(poly[i], poly[(i + 1) % poly.size()]);
      if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
        printf("0.00\n"); return;
      }
    }
    if (inter.empty())
      if (in(l.a) && in(l.b)) printf("%.2lf\n", ! (l.b - l.a));
      else printf("0.00\n");
    else if (inter.size() == 2) printf("%.2lf\n", ! (inter[1] - inter[0]));
    else if (in(l.a)) printf("%.2lf\n", ! (inter[0] - l.a));
    else if (in(l.b)) printf("%.2lf\n", ! (inter[0] - l.b));
    else printf("0.00\n");
  }

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

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

Boxes

题目描述

There are two boxes. There are $A$ balls in the first box, and $B$ balls in the second box. It is possible to move balls from one box to another. From one box into another one should move as many balls as the other box already contains. You have to determine, whether it is possible to move all balls into one box.

题意概述

给定两个数$A$和$B$,每次操作可以将两个数中较大的数减去较小的数,再将较小的数翻倍。问至少经过多少次操作后两个数中有一个为$0$,若不可能则输出$-1$。
数据范围:$1 \le A+B \le 2147483647$。

算法分析

可以发现在任何时候,将两个数同时除以它们的最大公约数并不会影响答案;若两个数的和为奇数,则永远不可能结束。基于以上两点,答案不会超过$\log(A+B)$,因此直接模拟即可。

Broken Line

题目描述

There is a closed broken line on a plane with sides parallel to coordinate axes, without self-crossings and self-contacts. The broken line consists of $K$ segments. You have to determine, whether a given point with coordinates $(X_0, Y_0)$ is inside this closed broken line, outside or belongs to the broken line.

题意概述

给定一个简单$N$边形,它的每条边都平行于坐标轴。问点$(X_0, Y_0)$是否在多边形内。
数据范围:$4 \le N \le 10000$。

算法分析

从$(X_0, Y_0)$向右水平射出一条射线,若射线与$N$边形有奇数个交点则该点在多边形内。
判断一条边是否与射线相交就是要看该边的两个端点是否在射线异侧,在射线上或射线上方算同一侧,在射线下方算另一侧。

代码

#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 Line { int x1, y1, x2, y2; };

struct Solver {
private:
  static const int K = 10010;
  int k, x, y;
  Line l[K];
  void input() {
    io > k;
    for (int i = 1; i <= k; ++ i) {
      io > l[i].x1 > l[i].y1 > l[i].x2 > l[i].y2;
      if (l[i].x1 > l[i].x2 || l[i].y1 > l[i].y2) swap(l[i].x1, l[i].x2), swap(l[i].y1, l[i].y2);
    }
    io > x > y;
  }
  bool in(int x, int y, Line l) {
    if (l.x1 == l.x2) return x == l.x1 && l.y1 <= y && y <= l.y2;
    else return y == l.y1 && l.x1 <= x && x <= l.x2;
  }
  void process() {
    for (int i = 1; i <= k; ++ i) if (in(x, y, l[i])) { io < (char *) "BORDER\n"; return; }
    int cnt = 0;
    for (int i = 1; i <= k; ++ i)
      cnt += l[i].x1 == l[i].x2 && l[i].x1 > x && ((l[i].y1 <= y) ^ (l[i].y2 <= y));
    if (cnt & 1) io < (char *) "INSIDE\n"; else io < (char *) "OUTSIDE\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;
}