Requirements

题目描述

An undergraduate student, realizing that he needs to do research to improve his chances of being accepted to graduate school, decided that it is now time to do some independent research. Of course, he has decided to do research in the most important domain: the requirements he must fulfill to graduate from his undergraduate university. First, he discovered (to his surprise) that he has to fulfill $5$ distinct requirements: the general institute requirement, the writing requirement, the science requirement, the foreign-language requirement, and the field-of-specialization requirement. Formally, a requirement is a fixed number of classes that he has to take during his undergraduate years. Thus, for example, the foreign language requirement specifies that the student has to take $4$ classes to fulfill this requirement: French I, French II, French III, and French IV. Having analyzed the immense multitude of the classes that need to be taken to fulfill the different requirements, our student became a little depressed about his undergraduate university: there are so many classes to take…
Dejected, the student began studying the requirements of other universities that he might have chosen after high school. He found that, in fact, other universities had exactly the same $5$ requirements as his own university. The only difference was that different universities had different number of classes to be satisfied in each of the five requirement.
Still, it appeared that universities have pretty similar requirements (all of them require a lot of classes), so he hypothesized that no two universities are very dissimilar in their requirements. He defined the dissimilarity of two universities $X$ and $Y$ as $\sum_{i=1}^5 |x_i-y_i|$, where an $x_i$($y_i$) is the number of classes in the requirement $i$ of university $X$($Y$) multiplied by an appropriate factor that measures hardness of the corresponding requirement at the corresponding university.

题意概述

给定$n$个五维的点,求其中任意两点曼哈顿距离的最大值。
数据范围:$1 \le n \le 10^5$。

算法分析

考虑二维的情况。设有两个点$(x_1, y_1), (x_2, y_2)$,它们之间的曼哈顿距离为$|x_1-x_2|+|y_1-y_2|$。拆开绝对值符号后有四种情况:
$$
\begin{align}
(x_1+y_1)&-(x_2+y_2) \\
(x_1-y_1)&-(x_2-y_2) \\
(-x_1+y_1)&-(-x_2+y_2) \\
(-x_1-y_1)&-(-x_2-y_2)
\end{align}
$$
而原式则等于这四个式子中的最大值。观察发现四个式子中两点对应维度的符号都相同。这个结论也适用于五维的情况。因此可以枚举每一维的符号,$O(n)$计算出这种状态下所有点可能得到的最大值$mx$和最小值$mn$,答案就是每种状态下$(mx-mn)$的最大值。

代码

#include <cstdio>
#include <algorithm>

using std :: min;
using std :: max;

static const int N = 100000;
double a[N][5];

int main() {
  int n;
  while (~ scanf("%d", &n)) {
    for (int i = 0; i < n; ++ i)
      for (int j = 0; j < 5; ++ j) scanf("%lf", &a[i][j]);
    double ans = 0;
    for (int i = 0; i < 32; ++ i) {
      double mx = -1e100, mn = 1e100;
      for (int j = 0; j < n; ++ j) {
        double rec = 0;
        for (int k = 0; k < 5; ++ k)
          if (i & 1 << k) rec += a[j][k]; else rec -= a[j][k]; 
        mx = max(mx, rec), mn = min(mn, rec);
      }
      ans = max(ans, mx - mn);
    }
    printf("%.2lf\n", ans);
  }
  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;
}