「Codeforces 593C」Beautiful Function

题目链接:Codeforces 593C

给定 $n$ 个圆,第 $i$ 个圆的坐标为 $(x_i,y_i)$,半径为 $r_i$。构造两个合法的函数 $f(t),g(t)$,设点集 $S = \{(f(t),g(t))\mid t\in [0,50],t\in\mathbb{Z}\}$。你需要保证对于每个圆,至少存在一个园内的点(包括边界)在点集 $S$ 中。

令 $w(t)$ 和 $h(t)$ 为两个合法的函数,那么合法的函数由如下几种函数复合而成:

  1. $s(t) = \operatorname{abs}(w(t))$
  2. $s(t) = (w(t) + h(t))$
  3. $s(t) = (w(t) - h(t))$
  4. $s(t) = (w(t)\times h(t))$
  5. $s(t) = C$(其中 $C\in\mathbb{Z}$)
  6. $s(t) = t$

在 $f(t)$ 和 $g(t)$ 中,至多只能出现 $50$ 次函数相乘操作,函数长度不能超过 $100n$,输出时不能出现空格,并且对于任意的整数 $t\in[0,50]$ 都有 $-10 ^ 9 \le f(t), g(t) \le 10 ^ 9$。

数据范围:$1\le n\le 50$,$0\le x_i, y_i\le 50$,$2\le r_i\le 50$。


Solution

以下内容参考 Codeforces 官方题解

这里有一个很有趣的函数(卧槽这谁想得到啊 QAQ)

$$ y = 1 - \operatorname{abs}(t - i) + \operatorname{abs}(1 - \operatorname{abs}(t - i)) $$

我们设 $a = 1, b = \operatorname{abs}(t - i)​$,那么这个函数为:

$$ y = a - b + \operatorname{abs}(a - b) $$

考虑对 $a, b$ 分类讨论:

  1. 当 $a\le b$ 时,有 $a - b + \operatorname{abs}(a - b) = 0$。
  2. 当 $a>b$ 时,有 $a - b + \operatorname{abs}(a - b) = 2a - 2b$。

那么 $a > b$ 到底意味着什么?我们接下来慢慢分析:

$$ \operatorname{abs}(t - i) < 1\Rightarrow t - 1 < i < t + 1 $$

对于整数 $i$,其取值只有 $i = t$。换言之,这个函数 $f$ 的值不为 $0$ 当且仅当 $i = t$,此时函数值为 $2$。

这就是说,我们可以构造出一个函数,使得它只在指定的整数位置的值非零。显而易见,由于坐标范围是 $[0,50]$,那么对于第 $i$ 个圆,我们要构造的函数就是:

$$ y = \left\lfloor\frac{x_i}{2}\right\rfloor(\operatorname{abs}(t - i) + \operatorname{abs}(1 - \operatorname{abs}(t - i))) $$

这样 $t = i$ 时,其值为 $\left\lfloor\frac{x_i}{2}\right\rfloor\times 2$,这个位置和圆心的距离不超过 $1$。但是所有圆的半径都不小于 $2$,因此这个位置一定在圆内。

对于 $x_i,y_i$ 分别构造这样的函数即可。括号嵌套毒瘤!

时间复杂度:$\mathcal O(n)$。


Code

#include <iostream>
#include <cstdio>

std::string calc(int x, int i) {
    char s[105];
    x >>= 1;
    sprintf(s, "(%d*((%d-abs((t-%d)))+abs((%d-abs((t-%d))))))", x, 1, i, 1, i);
    return s;
}
int main() {
    int n;
    scanf("%d", &n);
    std::string f, g;
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d%*d", &x, &y);
        f += calc(x, i);
        g += calc(y, i);
        if (i > 1) {
            f = "(" + f + ")";
            g = "(" + g + ")";
        }
        f += "+\n"[i == n];
        g += "+\n"[i == n];
    }
    std::cout<<f<<g;
    return 0;
}

4 条评论

  1. realSpongeBob

    $$ \texttt{QwQ} $$

  2. realSpongeBob

    $$ \texttt{QAQ} $$

  3. realSpongeBob

    %%%
    $\color{black}S\color{red}{iyuan}$ 太强辣

    1. Siyuan
      @realSpongeBob

      $\color{black}{\text{C}}\color{red}{\text{YY}}$ 太假了

发表评论