Traffic Lights

题目描述

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

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

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

题意概述

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

算法分析

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

代码

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

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

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

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

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

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

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)$,因此直接模拟即可。

Cow Program

题目描述

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$, and performs the following operations on a sequence $a_1, a_2, \ldots, a_n$ of positive integers:

  1. Initially, $x=1$ and $y=0$. If, after any step, $x \le 0$ or $x \gt n$, the program immediately terminates.
  2. The program increases both $x$ and $y$ by a value equal to $a_x$ simultaneously.
  3. The program now increases $y$ by $a_x$ while decreasing $x$ by $a_x$.
  4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!
You are given the sequence $a_2, a_3, \ldots, a_n$. Suppose for each $i \; (1 \le i \le n-1)$ we run the program on the sequence $i, a_2, a_3, \ldots, a_n$. For each such run output the final value of $y$ if the program terminates or $-1$ if it does not terminate.

题意概述

有一个包含$n$个数的数列,第$i$项为$a_i$。现有两个数$x=1, \; y=0$。执行以下操作

while (!(x <= 0 || x > n)) {
  y += a[x], x += a[x];
  if (!(x <= 0 || x > n)) y += a[x], x -= a[x];
}

给定$a_2, a_3, \ldots, a_n$,对于所有$i \in [1, n-1]$,求对数列$i, a_2, a_3, \ldots, a_n$执行操作后$y$的值。若无限循环则输出$-1$。
数据范围:$2 \le n \le 2 \times 10^5, \; 1 \le a_i \le 10^9$。

算法分析

直接模拟肯定会超时。易知从一个位置开始执行操作的顺序是固定的,因此可以用记忆化搜索,记录下每一个位置向左或向右执行操作后的$y$值。如果搜索到一个已搜索过但还没有得到答案的位置,则返回$-1$。

代码

#include <iostream>
using namespace std;
long long n, a[300001], ans[300001][2], to[300001][2], vis[300001][2];
long long dfs(long long t, long long m) {
  if (ans[t][m]) return ans[t][m];
  if (vis[t][m]) return ans[t][m] = -1; vis[t][m] = true;
  if (to[t][m] < 1 || to[t][m] > n) return ans[t][m] = a[t];
  long long ret = dfs(to[t][m], !m);
  if (ret == -1) ans[t][m] = -1; else ans[t][m] = a[t] + ret;
  return ans[t][m];
}
int main()
{
  cin >> n, vis[1][1] = true;
  for (int i = 2; i <= n; ++i) cin >> a[i];
  for (int i = 2; i <= n; ++i) to[i][0] = i - a[i], to[i][1] = i + a[i];
  for (int i = 2; i <= n; ++i) if (!ans[i][0]) dfs(i, 0);
  for (int i = 1; i < n; ++i)
    if (ans[i + 1][0] == -1) cout << -1 << endl;
    else cout << i + ans[i + 1][0] << endl;
  return 0;
}

Cards Sorting

题目描述

Vasily has a deck of cards consisting of $n$ cards. There is an integer on each of the cards, this integer is between $1$ and $100000$, inclusive. It is possible that some cards have the same integers on them.
Vasily decided to sort the cards. To do this, he repeatedly takes the top card from the deck, and if the number on it equals the minimum number written on the cards in the deck, then he places the card away. Otherwise, he puts it under the deck and takes the next card from the top, and so on. The process ends as soon as there are no cards in the deck. You can assume that Vasily always knows the minimum number written on some card in the remaining deck, but doesn’t know where this card (or these cards) is.
You are to determine the total number of times Vasily takes the top card from the deck.

题意概述

有$n$张卡牌,第$i$张卡牌上的数字为$a_i$。每次从牌堆顶拿一张牌,如果它上面的数字是当前牌堆中最小的,则将它扔掉,否则将它放到牌堆底。问几次操作后牌堆为空。
数据范围:$1 \le n \le 10^5, \; 1 \le a_i \le 10^5$。

算法分析

先对卡牌上的数进行计数排序,接着从小到大处理:维护一个$now$指针,表示当前走到了第$now$个数;用树状数组维护当前剩余数字个数的前缀和,这样可以快速求出从第$i$个数走到第$j$个数所需要的次数。

代码

#include <iostream>
#include <vector>
using namespace std;
struct binary_indexed_tree {
  long long n; vector<long long> a;
  void init(long long t) { n = t + 10, a.clear(), a.resize(n); }
  void add(long long p, long long t) {
    for (long long i = p; i < n; i += i & -i) a[i] += t;
  }
  long long sum(long long p) {
    long long ret = 0;
    for (long long i = p; i; i -= i & -i) ret += a[i];
    return ret;
  }
} tree;
long long n, t, now, ans, pre;
vector<long long> b[100001];
int main()
{
  cin >> n;
  tree.init(n);
  for (long long i = 1; i <= n; ++i) {
    cin >> t; tree.add(i, 1), b[t].push_back(i);
  }
  for (long long i = 1; i <= 100000; ++i) {
    if (!b[i].size()) continue; long long pnt = 0;
    while (pnt < b[i].size() && b[i][pnt] < now) ++pnt; --pnt;
    if (pnt < 0) pnt = b[i].size() - 1;
    if (b[i][pnt] > now) ans += tree.sum(b[i][pnt]) - tree.sum(now);
    else ans += tree.sum(n) - tree.sum(now) + tree.sum(b[i][pnt]);
    for (long long j = 0; j < b[i].size(); ++j) tree.add(b[i][j], -1);
    now = b[i][pnt];
  }
  cout << ans << endl;
  return 0;
}

String Reconstruction

题目描述

Ivan had string $s$ consisting of small English letters. However, his friend Julia decided to make fun of him and hid the string $s$. Ivan preferred making a new string to finding the old one.
Ivan knows some information about the string $s$. Namely, he remembers, that string $t_i$ occurs in string $s$ at least $k_i$ times or more, he also remembers exactly $k_i$ positions where the string $t_i$ occurs in string $s$: these positions are $x_{i, 1}, x_{i, 2}, \ldots, x_{i, k_i}$. He remembers $n$ such strings $t_i$.
You are to reconstruct lexicographically minimal string $s$ such that it fits all the information Ivan remembers. Strings $t_i$ and string $s$ consist of small English letters only.

题意概述

有一个未知的字符串$s$,只知道$n$个它的子串$t_i$以及它们在$s$中出现的次数$k_i$和位置$x_{i, j}$。要求构造出字典序最小的原串。
数据范围:$1 \le n \le 10^5, \; 1 \le \sum |t_i|, \sum k_i, x_{i, j} \le 10^6$。

算法分析

建立双向链表,记录某个位置上一个未填充的位置和下一个未填充的位置。为了防止填充到一个已填充的位置上,我们将子串以位置为第一关键字从大到小排序,以长度为第二关键字从大到小排序,在填充时修改一下链表。最后若有未填充的位置则直接输出a。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
string s[100001];
struct cons {
  int n, p;
  bool operator < (const cons &a) const {
    return p > a.p ? true : p == a.p ? s[n].length() > s[a.n].length() : false;
  }
} con[1000001];
int n, c, p, l, len, ma, top, pre[2000001], nxt[2000001];
char str[2000001];
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= 2000000; ++i) pre[i] = i - 1, nxt[i] = i + 1;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i]; scanf("%d", &c);
    for (int j = 1; j <= c; ++j) {
      scanf("%d", &p), con[++top].n = i, con[top].p = p;
    }
  }
  sort(con + 1, con + top + 1);
  for (int i = 1; i <= top; ++i) {
    if (con[i].p == con[i - 1].p) continue;
    l = len = s[con[i].n].length(), p = con[i].p;
    while (l > 0) {
      ma = max(ma, p), str[p] = s[con[i].n][len - l];
      nxt[pre[p]] = nxt[p];
      pre[nxt[p]] = pre[p];
      l -= nxt[p] - p, p = nxt[p];
    }
  }
  for (int i = 1; i <= ma; ++i) {
    if (str[i] >= 'a' && str[i] <= 'z') printf("%c", str[i]);
    else printf("a");
  }
  printf("\n");
  return 0;
}

Chef and Sign Sequences

题目描述

Chef found a strange string yesterday – a string of signs $s$, where each sign is either a ‘<‘, ‘=’ or a ‘>’. Let $N$ be the length of this string. Chef wants to insert $N+1$ positive integers into this sequence and make it valid. A valid sequence is a sequence where every sign is preceded and followed by an integer, and the signs are correct. That is, if a sign ‘<‘ is preceded by the integer $a$ and followed by an integer $b$, then $a$ should be less than $b$. Likewise for the other two signs as well.
Chef can take some positive integers in the range $[1, P]$ and use a number in the range as many times as he wants.
Help Chef find the minimum possible $P$ with which he can create a valid sequence.

题意概述

给定一个由'<‘、’=’和’>’组成的字符串,要求在首尾和每两个相邻的符号间填入一个数,使得表达式成立。求数字的最小种类数。
数据范围:$1 \le |s| \le 10^5$。

算法分析

将’=’删去后,计算出只由'<‘或’>’组成的最长连续子串的长度,加$1$即得到答案。证明如下:

‘=’对最终结果没有影响,可以全部忽略。设找到了一个只由'<‘或’>’组成的最长连续子串,长度为$l$。在这个子串的左边填入$a$,右边填入$a+l$。由于其他只由'<‘或’>’组成的连续子串的长度均不大于$l$,因此也可以分别在它们左右填入$a$和$a+l$,这样必定可以满足题目要求。

由此得证。

代码

#include <iostream>
#include <algorithm>
using namespace std;
int n, ans, len, out;
string s;
int main()
{
  cin >> n;
  while (n--) {
    cin >> s;
    ans = out = 0;
    len = s.length();
    for (int i = 0; i < len; ++i) {
      if (s[i] == '<') {
        if (ans < 0) ans = 0;
        ++ans;
      }
      if (s[i] == '>') {
        if (ans > 0) ans = 0;
        --ans;
      }
      out = max(out, abs(ans) + 1);
    }
    cout << out << endl;
  }
  return 0;
}

Karen and Game

题目描述

On the way to school, Karen became fixated on the puzzle game on her phone!
The game is played as follows. In each level, you have a grid with $n$ rows and $m$ columns. Each cell originally contains the number $0$.
One move consists of choosing one row or column, and adding $1$ to all of the cells in that row or column.
To win the level, after all the moves, the number in the cell at the $i$-th row and $j$-th column should be equal to $g_{i, j}$.
Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!

题意概述

给定一个初始全为$0$的矩阵$s$和一个目标矩阵$g$,两矩阵大小均为$n \times m$。每次操作可以将矩阵$s$中某一行或某一列的数全部加一。求一个能将$s$变成$g$且操作数最少的操作序列。
数据范围:$1 \le n, m \le 100, \; 0 \le g_{i, j} \le 500$。

算法分析

可以倒过来思考:每次操作将$g$中某一行或某一列的数全部减一,要求得到所有数均为$0$的矩阵。显然,操作序列满足交换律。因此,只要找到所有数都非$0$的一行或一列,就可以立刻对这一行或一列进行操作。由于要求操作数最少,所以先枚举较短的一条边,再枚举较长的一条边。

代码

#include <iostream>
using namespace std;
int n, m, p, q, top, f, a[101][101], ans[100001], mode[100001];
bool check(int t, int mode) {
    if (!mode) {
        for (int i = 1; i <= m; ++i) if (!a[t][i]) return false;
        for (int i = 1; i <= m; ++i) --a[t][i];
        return true;
    } else {
        for (int i = 1; i <= n; ++i) if (!a[i][t]) return false;
        for (int i = 1; i <= n; ++i) --a[i][t];
        return true;
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    p = n, q = m;
    if (p > q) {
        p ^= q ^= p ^= q;
        f = 1;
    }
    for (int i = 1; i <= p; ++i) while (check(i, f)) {
        ans[++top] = i;
        mode[top] = f;
    }
    for (int i = 1; i <= q; ++i) while (check(i, !f)) {
        ans[++top] = i;
        mode[top] = !f;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j]) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << top << endl;
    for (int i = 1; i <= top; ++i) {
        if (!mode[i]) cout << "row ";
        else cout << "col ";
        cout << ans[i] << endl;
    }
    return 0;
}