题目链接：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)$ 为两个合法的函数，那么合法的函数由如下几种函数复合而成：
- $s(t) = \operatorname{abs}(w(t))$
- $s(t) = (w(t) + h(t))$
- $s(t) = (w(t) - h(t))$
- $s(t) = (w(t)\times h(t))$
- $s(t) = C$（其中 $C\in\mathbb{Z}$）
- $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$ 分类讨论：
- 当 $a\le b$ 时，有 $a - b + \operatorname{abs}(a - b) = 0$。
- 当 $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 条评论
$$ \texttt{QwQ} $$
$$ \texttt{QAQ} $$
%%%
$\color{black}S\color{red}{iyuan}$ 太强辣
$\color{black}{\text{C}}\color{red}{\text{YY}}$ 太假了