UOJ Logo dram的博客

博客

LibreOJ #6438 框出一个正方形 题解

2018-06-22 15:37:46 By dram

题目在此 | C++ 标程在此 | Haskell 标程在此

题目里 4/5 的构造

(求 dalao 拍啊,我不知道有没有写对啊。)

这题标解是数论,checker 是计算几何……

时限高于 Haskell 两倍应该算不卡常了吧。

简要题面

在平面直角坐标系中,你可以每次选择两个格点($(x,y)$,其中 $x$ 和 $y$ 都是整数的点),然后做出过这两个点的直线。

画出四条这样的直线,可以围成一个正方形,这个正方形具有面积 $S$。

给定面积有理数 $S = p / q$,是否存在一种方案能围出这个正方形?如果是,请给出一种构造。

暴力解法

不会!

真的,我不会!

我完全不知道有什么 10 分提答的和 40 分暴力的解法……

我不知道有没有人从提答点里看出什么: $$ \begin{array}{rcl} 4999889 &=& 4999889^{1}\\ 3988009 &=& 1997^{2}\\ 4012009 &=& 2003^{2}\\ 4999762 &=& 2^{1} \times 2499881^{1}\\ 3674633 &=& 1901^{1} \times 1933^{1}\\ 4999348 &=& 2^{2} \times 1249837^{1}\\ 4997709 &=& 3^{2} \times 555301^{1}\\ 2000066 &=& 2^{1} \times 1000033^{1}\\ 4782969 &=& 3^{14}\\ 1953125 &=& 5^{9}\\ \end{array} $$

正解

这题看着就不像有什么几何意义,我们来算一波。

直线

既然都是整点连出的直线,那么显然,画出的直线都是这个形式的: $$ Ax+By+C=0 \quad (A,B,C\in \mathbb{Q},\ A^2 + B^2 \neq 0) $$ 乘分母,得 $$ Ax + By + C = 0 \quad (A,B,C\in\mathbb{Z},\ A^2 + B^2 \neq 0) $$ 只要这个直线经过一个整点 $(x_0, y_0)$,那么也会经过 $(x_0 - B, y_0 + A)$。根据 Bezout 等式(俗称 exgcd),我们知道,上述方程有整数解当且仅当 $\gcd(A,B) \mid C$。等式两边除以 $\gcd(A,B)$ 得直线可以画出的充分必要条件为: $$ Ax+By+C=0 \quad (A,B,C \in \mathbb{Z},\ \gcd(A,B)=1) $$

正方形

我们肯定要画两对平行线,且这两对之间垂直。不妨设为: $$ \begin{array}{rcl} Ax+By+C_1 &=& 0 \\ Ax+By+C_2 &=& 0 \\ Bx-Ay+C_3 &=& 0 \\ Bx-Ay+C_4 &=& 0 \\ \end{array} $$ 平行线间距离应该相等,且等于正方形边长: $$ \sqrt{S} = {|C_2 - C_1| \over \sqrt{A^2 + B^2}}={|C_4 - C_3| \over \sqrt{A^2+B^2}} $$ 因为只要 $\gcd(A,B)=1$,四个 $C$ 是可以随便取的,不妨取 $C_1 = C_2 = 0$ 和 $C_3 = C_4 = C$,则: $$ \begin{array}{rcl} Ax+By& &=& 0 \\ Ax+By& +\ C &=& 0 \\ Bx-Ay& &=& 0 \\ Bx-Ay&+\ C &=& 0 \\ \end{array} $$ 因此要构造四条直线等价于构造 $A,B,C$ 使得:

$$ S = {C^2 \over A^2 + B^2} \quad (\gcd(A,B)=1) $$ 得到 $A,B,C$ 后,就可以用 exgcd 算出四条直线需要经过的格点。以 $Ax+By+C=0$ 为例,用 exgcd 得到 $u,v$ 使 $Au+Bv=1$,则只需画过 $(-uC, -vC)$ 和 $(-uC - B, -vC + A)$ 的直线。

平方和 $A^2 + B^2$

$i = \sqrt{-1}$ 是虚数单位。

考虑上边那个 $S$ 的式子里面的分母 $K$,注意到: $$ K=A^2+B^2=(A+Bi)(A-Bi) $$ 有个东西叫做**高斯整数**,指的是是形如 $a + bi \ (a,b\in \mathbb{Z})$ 的复数。**高斯质数**指的是所有不能被写成两个非 $\pm 1$ 非 $\pm i$ 的高斯整数的乘积的高斯整数。

所以 $K$ 是平方和等价于 $K$ 是两个共轭高斯整数的乘积。

不那么神奇的结论:高斯整数在不关心乘上 $\pm1,\pm i$ 倍的情况下几乎可以唯一分解,也就是分解得到的每个高斯质数列出来一定能找到 $\pm1,\pm i$ 倍对上。

神奇的结论:根据费马平方和定理,对于质数,质数,质数: $$ (\exists x,y.\ p = (x+yi)(x-yi)) \iff p \bmod 4 = 1 $$ 也就是说,$p = 4k+1$ 时有四种方式写成两个共轭高斯整数的乘积: $$ \begin{array}{rcl} p &=& (x+yi)(x-yi)\\ &=& (x-yi)(x+yi) \\ &=& (y+xi)(y-xi) \\ &=& (y-xi)(y+xi) \end{array} $$ $p = 4k+3$ 时不能。

$p=2$ 时有两种: $$ \begin{array}{rcl} p &=& (1+i)(1-i)\\ &=& (1-i)(1+i) \end{array} $$ 所以我们开开心心地对 $K$ 进行了质因数分解。最后得到的应该是 $K=u \hat{u}$(其中 $\hat{x}$ 是共轭复数)。对于每个质因数幂 $p^\alpha$:

  • 如果 $p = 2$ 或 $p=4k+1$,那么设 $p=x^2+y^2$,则对 $u$ 贡献 $(x+yi)^\alpha$,对 $\hat{u}$ 贡献 $(x-yi)^\alpha$。
  • 如果 $p=4k+3$,那么:
    • 如果 $\alpha = 2m$,则对 $u$ 和 $\hat{u}$ 都贡献 $p^m$
    • 如果 $\alpha = 2m+1$ 就没戏了,return false

然后乘完了之后……

等一下……好像要 $\gcd(A,B)=1$,怎么办。

假设 $gcd(A,B)=c>1$,那么 $u=c \cdot ((A/c) + (B/c)i)$。对 $c$ 进行高斯质因数分解,里面得到的一定是:

  • $p = 4k+3$ 质数的 $p^m$,病在骨髓,无奈何也,显然不行。
  • $p = 4k+1$ 质数的 $(x+yi)^\alpha$,非常安全。
  • $p = 2$ 的 $(1+i)^n$,在 $n=0$ 或 $1$ 时很安全,$n \geq 2$ 就不行了。

后面两个为什么?因为现在我们已经什么可以害怕的让 $p=4k+3$ 的质因数“无奈何也”了,所以 $c$ 分解完一定是一堆共轭虚高斯质数的乘积,也就是 $c$ 的高斯质因子里面,一定有虚高斯质数 $s$ 和其共轭 $\hat{s}$ 同时存在。所以,我们在上面对 $u$ 贡献 $s$ 之后,就不能贡献 $\hat{s},-\hat{s},i\hat{s},-i\hat{s}$。

  • 各个正常质数之间的高斯质因子不互相影响。
  • 对于 $p = 4k+1$,两个 $x+yi$ 之间没有影响(显然 $x \neq y$)。
  • 对于 $p = 2$,很不幸,$s = 1+i$ 的时候 $i \hat{s} = 1+i=s$,而 $\hat{s} = 1-i$,所以 $2$ 的幂大于 $1$ 的时候是没法弄的,所以 $2^\alpha$ 里面只能 $\alpha = 0$ 或者 $\alpha = 1$。

也就是,这样的条件下,最终得到的 $u$ 是一堆 $x+yi$ 乘出来的,如果 $c > 1$,那么不能有 $4k+3$ 质数为约数,如果是别的,那么也可以质因数分解出 $x - yi$ 的因子,但是获得 $u$ 的时候没有它,矛盾。(本段由 hld67890 提供)

综上,$\exists A,B.\ K = A^2+B^2\ (\gcd(A,B)=1)$,当且仅当 $K$ 质因数分解后,没有 $p = 4k+3$ 的质因数,且 $2$ 的幂是 $0$ 或 $1$。

面积 $S$

我们可以拿 $K​$ 当分母,另一个平方数 $C^2​$ 当分子。

既然 $S$ 是有理数,我们也可以给 $S$ 质因数分解。想办法凑出每个 $p^\alpha$:

  • $p = 4k+1$,我们可以在分子上 $\alpha_n\ \mathtt{\text{+=}}\ 2$ 任意次,也可以在分母上 $\alpha_d\ \mathtt{\text{-=}}\ 1$ 任意次,也就是 $\alpha$ 任意
  • $p = 4k+3$,我们只能在分子上 $\alpha_n\ \mathtt{\text{+=}}\ 2$ 任意次,不能在分母减,所以 $\alpha \geq 0$ 且 $\alpha \bmod 2 = 0$
  • $p = 2$,我们可以在分子上 $\alpha_n\ \mathtt{\text{+=}}\ 2$ 任意次,分母上 $\alpha_d\ \mathtt{\text{-=}}\ 1$ 最多一次,所以 $\alpha \geq -1$

得到平方数分子 $C^2$,就可以得到 $C$;得到分子 $K$,就可以用上一小节里面的方法凑出 $A,B$。然后用 exgcd 求出 8 个点的坐标。

平方和 $A^2 + B^2$ 续

怎么得到可以写成质数的平方和是哪两个数的平方和?打表:

for (i = 1; i * i < maxn; i ++)
    for (j = i; j * j < maxn - i * i; j ++)
        m = i * i + j * j
        A[m] = i
        B[m] = j

为什么不用直接对 $K$ 查表?因为 $K$ 可能会超过 maxn

算法总结

  • 打表打出 $A, B$
  • 线性筛,预处理“质因数分解树”
  • 对每个查询 $S$
    • 质因数分解 $S$
    • 化为 $S = C^2 / K$ 的形式
    • 如果能求出 $A, B$
      • 求出点的坐标并输出
    • 否则:
      • 输出 impossible

复杂度:$O(M+T\log M)$

这个……这个,好像有点快啊。

感谢

首先感谢国家,为我提供了良好的教育环境和指导,培养了我的学习兴趣。

然后感谢 3blue1brown 的视频 'Pi hiding in prime regularities' 让我得知了平方和和高斯整数相关的知识。

然后感谢最开始提出这个问题的人。真的是很有趣的问题,原题和当时我给的答案在这里

然后感谢 Geogebra,我用的这个软件画的题里的那个图,真的很漂亮。

然后感谢 Typora,题解是用这个软件写的。

感谢 LibreOJUOJ 给我提供了这个交流的机会。

LibreOJ #6203 可持久化队列 题解

2017-07-13 09:02:45 By dram

参考文献


题解比较详细,请大家不要慌张。

记得用读入优化了么?

被 log 卡过了

dalao 的程序在此,$\log$ 碾 $O(1)$ 好妙啊

题目在此 标程在此

题目大意

维护一个可持久化的 std::queue 类似物,支持(可持久化的) push_backpop_front

各种记号的总结

记号 表示
$\mathtt{rev}(A)$ 列表 $A$ 反转
$\langle A=\dots\ \rvert\ B=\dots\ \rvert\ \dots\rangle$ 数据结构(struct 之类的)
$a_1\to a_2\to \dots\to a_n\to\mathtt{nil}$ 链表结构($\mathtt{nil}$ 就是表示空链表的假节点,指针 0 之类的)
$[a_1,a_2,\dots,a_n]$ 序列
$A+B$ 列表 $A$ 和 $B$ 相连
$\lvert A\rvert$ 列表 $A$ 的长度
$\mathtt{next}$ 链表指向下一个节点的指针
$\mathtt{value}$ 链表当前节点指向的值

列表和指向链表的指针不做区分

算法 1

我们可以用平衡树维护这个队列

时间复杂度 $O(T\log T)$

算法 m

我们可以在操作树上用倍增找到队首

时间复杂度 $O(T \log T)$ 竟然卡过了

dalao 的程序在此,$\log$ 碾 $O(1)$ 好妙啊

算法 x

对于没有加密的数据,我们可以离线构建出操作树来,这样只要遍历一遍就可以得到结果。

时间复杂度 $O(T)$

算法 2

我们维护两个链表 $L$ 和 $R$,那么整个队列就是 $L + \mathtt{rev}(R)$

比如 $\langle L=1\to2\to3\to\mathtt{nil}\ |\ R=6\to5\to4\to\mathtt{nil}\rangle$ 就表示 $\langle1,2,3,4,5,6\rangle$。

那么 $\mathtt{push\_back}$ 就是往 $R$ 前面加元素,$\mathtt{pop\_front}$ 就是从 L 前面拿元素。

比如这里 $\mathtt{pop\_front}$ 出来之后就会变成 $\langle L=2\to3\to\mathtt{nil}\ |\ R=6\to5\to4\to\mathtt{nil}\rangle$

$\mathtt{push\_back}(7)$ 就会变成 $\langle L=1\to2\to3\to\mathtt{nil}\ |\ R=7\to6\to5\to4\to\mathtt{nil}\rangle$

一看就可以可持久化对吧。今天的世界也很和平。

等下,如果 $L$ 直接就是 $\mathtt{nil}$ 怎么办?

凉拌。


我们来考虑一下,如果 $L​$ 是 $\mathtt{nil}​$ 的话,那么全队列就是 $\mathtt{rev}(R)​$。那么我们可以考虑先把 $L​$ 替换成 $\mathtt{rev}(R)​$,然后再 $\mathtt{pop\_front}​$。

如果 $R$ 也是 $\mathtt{nil}$ 怎么办?我不是说过不会出现 $\mathtt{pop\_front}$ 一个空队列的情况么?

那么比如 $\langle L=\mathtt{nil}\ |\ R=7\to6\to5\to4\to\mathtt{nil}\rangle$,我们就先把它变成 $\langle L=4\to5\to6\to7\to\mathtt{nil}\ |\ R=\mathtt{nil}\rangle$ ,然后开开心心地 $\mathtt{pop\_front}$ 出一个 $4$ 来就好了。

每个元素会被 $\mathtt{push\_back}$ 进来,被 $\mathtt{rev}$ 一次,再被 $\mathtt{pop\_front}$ 出来,所以是 $O(n)$ 的。

慢着,这个分析在可持久化的情况下是错的,因为……

我们不停地给 $\langle L=\mathtt{nil}\ |\ R=7\to6\to5\to4\to\mathtt{nil}\rangle$ 进行 $\mathtt{pop\_front}$,那么这几个元素就会一遍一遍地过 $\mathtt{rev}$,结果:$O(N^2)$

算法 3

APIO 2017 讲课的时候好像说过,我们可以把重构数据结构的时间真·平摊到单个操作上。那……把 $\mathtt{rev}(R)$ 摊到 $|R|$ 次操作上好了。

但是不太妙的是 $\mathtt{pop\_front}$ 的时候我们需要回答开头的元素啊。我们可以一般化重构的操作,不一定在 $L=\mathtt{nil}$ 的时候重构,而是可以提前:

$$ \langle L=A\ |\ R=B\rangle \Longrightarrow \langle L=A+\mathtt{rev}(B)\ |\ R=\mathtt{nil}\rangle $$ 如果 $|A|=n$ 而 $|B|=n+1$,(这么选取使得是为了把操作凑到正好,下面就明白了)那么我们把 $A+\mathtt{rev}(B)$ 的时间摊成 $n$ 份,用一种类似 lazy 标记的思路,在链表中除了这个节点的值 $\mathtt{value}$ 和下一个节点的指针 $\mathtt{next}$ 以外,再储存额外的信息 $\mathtt{r_1}$ 和 $\mathtt{r_2}$,用 $\langle \mathtt{value}\ |\ \mathtt{next}\ |\ \mathtt{r_1}\ |\ \mathtt{r_2}\rangle$ 表示我们这个链表其实是 $\mathtt{value} \to (\mathtt{next} + \mathtt{rev}(\mathtt{r_1})+\mathtt{r_2})$。注意到 $\mathtt{rev}(m\to X)+Y=\mathtt{rev}(X)+(m\to Y)$。(别忘了 $u\to [a_1,a_2,\dots,a_n]=[u,a_1,a_2,\dots,a_n]$)我们可以这么下发 lazy 标记:

  • ($\mathtt{next}\neq\mathtt{nil}$)$u\to ((v\to M)+\mathtt{rev}(z\to X)+Y) \Longrightarrow u\to v\to(M+\mathtt{rev}(X)+(z\to Y))$
  • ($\mathtt{next}=\mathtt{nil}$)$u\to(\mathtt{nil}+\mathtt{rev}(\mathtt{a\to b\to nil})+Y)\Longrightarrow u\to b \to a \to Y$

下发 lazy 的过程可以参照图片(图中标的数字,是这几个元素在完全发完 lazy 标记之后的相对顺序)

flandre.svg

不要忘了,我们创建 lazy 标记 $A+\mathtt{rev}(B)$ 的时候,有 $|A|=n$,$|B|=n+1$。如果 $A\neq \mathtt{nil}$。设 $A=u\to M$,则创建 $\langle u\ |\ \mathtt{next}=M\ |\ \mathtt{r_1}=B\ |\ \mathtt{r_2}=\mathtt{nil}\rangle$ 表示它。否则,$B$ 只有一个元素,$A+\mathtt{rev}(B)=B$。可以验证上面说的下发 lazy 标记的情况确实完整覆盖了所有可能。

注意:我们下发 lazy 标记的时候,其实确实是修改了之前版本的数据结构,但是我们并没有改变序列的内容,只改变了结构,所以没关系。

为了使得我们可以一边操作一边发 lazy,我们还需要在队列里维护一个指针 $\mathtt{cur}$ 表示我们的 lazy 发到哪儿了。

接下来,我们只要做到如下的事情,就可以成功维护队列了:

  • $|L|-|R|\geq0$,保证只要队列非空我们就可以直接从 $L$ 里面 $\mathtt{pop\_front}$ 出东西来,免得浪费时间算 $\mathtt{rev}(R)$。
  • 在 lazy 被发下去之前,我们不会去碰一个有 lazy 的节点

在这样的条件下,我们只要保证每次操作都是 $O(1)$ 的就保证了复杂度,这很简单。关键是怎么保证这两个条件。

我们发现,在不重构的情况下,$\mathtt{push\_back}$ 和 $\mathtt{pop\_front}$ 都会导致 $|L|-|R|$ 减小 $1$。而我们往 $\mathtt{next}$ 指针走的时候,$|\mathtt{cur}|$ 也会减小 $1$。于是我们可以直接保持 $\mathtt{cur} = |L| - |R|$。当 $\mathtt{cur} = \mathtt{nil}$ 的时候再操作,就导致 $|L|-|R|=-1$,正好该重构了。别忘了,我们的重构指的是: $$ \langle L=A\ |\ R=B\rangle \Longrightarrow \langle L=A+\mathtt{rev}(B)\ |\ R=\mathtt{nil}\rangle $$ 从版本 $v$ 生成版本 $i$ 的操作的时候:(设中间结果为 $i'$)

  • ($\mathtt{v\to cur=\mathtt{nil}}$)那么此时 $|v\to A|=|v\to B|$,操作完 $|i' \to A|-|i'\to B|=-1$,此时我们重构。最终得到的 $i\to A=i\to\mathtt{cur}= \langle i'\to A\to \mathtt{value}\ |\ \mathtt{next}=i'\to A\to \mathtt{next}\ |\ X=i'\to B\ |\ Y=\mathtt{nil}\rangle$,而 $i\to B=\mathtt{nil}$。
  • ($v\to \mathtt{cur}\neq \mathtt{nil}$)那么我们先给 $\mathtt{cur}$ 下发 lazy(要不然万一 $A$ 直接就是一个有 lazy 没发的节点就爆炸了),然后按照算法 2 操作。新的 $i\to \mathtt{cur}=v\to \mathtt{cur}\to\mathtt{next}$

这样我们连链表长度都不需要维护了,毕竟 $\mathtt{cur}$ 指针会告诉我们。

除了重构以外,其余可以参考算法 2 的前半部分。因为 $|L|-|R|\geq 0$,所以对于合法的操作一定不会遇到 $L=\mathtt{nil}$。

详见标程

时间复杂度 $O(T)$

算法 y

如果我们记录 $|L|$ 和 $|R|$ 来确定何时重构,并且不使用 $\mathtt{cur}$ 指针进行标记的提前下发,那么我们可能一次操作需要下发多重 lazy。但是可以证明每次操作仍然是均摊 $O(1)$ 的。

是的。

这是可持久化数据结构。均摊。

时间复杂度 $O(T)$


关于题图

肯定没有提醒你用两个链表表示队列,对吧

关于树状数组的部分操作的奇怪的解释

2017-01-22 00:12:05 By dram

原文在此,注意作者就是我,放在这里当然是为了防止你们怀疑我(虽然我并不确定你们会怀疑什么)

树状数组的构造过程是这样的: 对于一段序列 $A[1\dots{}n]$,把所有奇数项偶数项分开得到数组 $P$ $Q$,偶数项每项加上其左边的奇数项得到 $P + Q$,偶数项求一遍树状数组得到 $T(P + Q)$,最后把 $P$ 和 $T(P + Q)$ 交替排列出来。

举例:

$$\begin{array}{|c|c|c|c|c|l|} \hline 1&3&5&6&8&原数组\\\hline &3&&6&&分离偶数项\\\hline &4&&11&&每个偶数项加上其左边的奇数项\\\hline &4&&15&&递归求树状数组\\\hline 1&4&5&15&8&把奇数项交替排列回去\\\hline \end{array}$$

树状数组,一个数 $n$ 能当偶数项 $k$ 次,进入 $k$ 次递归中,那么 $n$ 的二进制最后有 $k$ 个 $0$,因为每“当”一次偶数项,它所管辖的区间就会加倍,所以它的值就是原数组里以 $n$ 结尾长度为 $2^k$ 的一段区间。注意到 $lowbit(n) = 2^k$。如果区间写成左开右闭的,那么树状数组里第 $n$ 项就是原数组 $(n - lowbit(n), n]$ 的和。

举例。要查询前 $10$ 个数的前缀和,二进制是 $(1010)_2$,我们可以将其拆成如下两个区间:$(8, 10]$ 和 $(0, 8]$。

修改的话,观察构造树状数组的过程,观察原数组的某下标上如果被加上了一个变化量 $d$,那么这个 $d$ 会怎样传播。

在某一层,如果这个下标 $n$ 是偶数项,那么它左边的奇数项被加过来,这两项原本应该是 $a$ 和 $a + b$ 的,变成了 $a$ 和 $a + b + d$,恰好就是第 n 位被改了;但是如果是奇数项的话,$a$ 和 $a + b$ 要变成 $a + d$ 和 $a + d + b$,也就是说 $d$ 被传播到了 $n$ 右边的偶数项。当然影响是要传递的。

所以我们修改的下标 $n$ 在某一层作为奇数项的时候,它影响到了它在这一层右边的偶数项 $n'$,$n'$ 又会影响到 $n''$,以此类推。

举例:$10$ 在第 $2$ 层的时候,它在这层的编号是 $5$,很不幸地影响到了这层编号是 $6$,即原编号 $12$ 的元素。

我们来看一下二进制表示。$10 = (1010)_2$ 在第 $2$ 层是 $5 = (101)_2$,影响到的是 $5 + 1 = 6 = (110)_2$。(此处感谢 UOJ 用户 rabbit_lb 提醒修改)在第 $2$ 层,加的这个 $1$,应该对应原数组上的 $1 \times 2^1 = 2$,就是 $lowbit(10)$!

这是为什么呢?因为一个二进制最后有 $k$ 个 $0$ 的下标 $n$ 会在第 $k + 1$ 层,作为 $n \over 2^k$ 影响到 $1 + {n \over 2^k}$,在原数组上的下标就是 $n$ 影响到 $2^k + n = lowbit(n) + n$。

当然影响是要传递的,所以修改的时候就是不停加 $lowbit$ 改就行了

(敲 $ 敲到手抽筋。。。)

(然后还发现一个神奇的事情

\begin{array}
1&2&3\\
4&5&6
\end{array}

\begin{array} 1&2&3\\ 4&5&6 \end{array}

论不好好记 TeX 命令用法的坏处)

Quine 题解

2016-08-08 14:06:19 By dram

无聊的 dram 表示居然写这么无聊的题解。

http://uoj.ac/problem/8 Quine

写一个程序,使其能输出自己的源代码。

先来讲个笑话

$ cat quine.rb
quine.rb:1: syntax error, unexpected tINTEGER, expecting tSTRING_CONTENT or tSTRING_DBEG or tSTRING_DVAR or tSTRING_END
quine.rb:1: syntax error, unexpected tI...
          ^
$ ruby quine.rb
quine.rb:1: syntax error, unexpected tINTEGER, expecting tSTRING_CONTENT or tSTRING_DBEG or tSTRING_DVAR or tSTRING_END
quine.rb:1: syntax error, unexpected tI...
          ^
$ cat quine.py
  File "quine.py", line 1
    File "quine.py", line 1
    ^
IndentationError: unexpected indent
$ python quine.py
  File "quine.py", line 1
    File "quine.py", line 1
    ^
IndentationError: unexpected indent
$ cat quine.hs
[1 of 1] Compiling Main             ( quine.hs, quine.o )

quine.hs:1:4: parse error on input ‘of’
$ ghc quine.hs
[1 of 1] Compiling Main             ( quine.hs, quine.o )

quine.hs:1:4: parse error on input ‘of’

可惜 CE 是不能算 AC 的

正经内容

所以我们想要输出自己的源代码的话怎么办呢?

思路 1

cout << "cout << \"cout ...

程序需要无限长,失败。

思路 2

我们尝试构造一个字符串是整个程序的源代码

char s[] = "char s[] = ...;\ncout << s;\n";
cout << s;

程序需要无限长,失败。

思路 3

我们尝试构造一个字符串是程序的一部分的源代码

char s[] = "cout << s;";
cout << s;

输出不对,失败。

思路 4

思路 3 好像已经很接近了啊,如果这样行不行?

1. s = 2 3 两步的代码
2. 输出第 1 步的代码
3. 输出 s

等等,第 1 步的代码从哪里来呢?

咱不是有 s 么?

s='print "s="+repr(s)\nprint s'
print "s="+repr(s)
print s

什么?不会 python?See this C++

#include <stdio.h>
char s[] = {59,10,105,110,116,32,109,97,105,110,40,41,32,123,10,9,112,114,105,110,116,102,40,34,35,105,110,99,108,117,100,101,32,60,115,116,100,105,111,46,104,62,92,110,99,104,97,114,32,115,91,93,32,61,32,123,34,41,59,10,9,102,111,114,32,40,105,110,116,32,105,32,61,32,48,59,32,105,32,60,32,115,105,122,101,111,102,40,115,41,59,32,105,32,43,43,41,10,9,9,112,114,105,110,116,102,40,34,37,100,37,99,34,44,10,9,9,9,40,105,110,116,41,32,115,91,105,93,44,10,9,9,9,105,32,61,61,32,115,105,122,101,111,102,40,115,41,32,45,32,49,32,63,32,39,125,39,32,58,32,39,44,39,41,59,10,9,112,117,116,115,40,115,41,59,10,9,114,101,116,117,114,110,32,48,59,10,125,0};
// 上面那行是第一步
//(实现细节:第二行结尾的分号放在 s 里面了,就是那个 `59`)
int main() {
    printf("#include <stdio.h>\nchar s[] = {"); // --+
    for (int i = 0; i < sizeof(s); i ++)        //   |
        printf("%d%c",                          //   +-- 这部分大概相当于是第二步
            (int) s[i],                         //   |
            i == sizeof(s) - 1 ? '}' : ',');    // --+
    puts(s);                                    // ------ 第三步
    return 0;
}

当然这段代码是跑不过的,因为被我加了注释。请删除注释后提交。

哦不对,请将这段代码的输出提交

哦不对,你们怎么能提交我的代码呢?

交互版

void submit(const char *str); // 交互库提供
void quine();                 // 选手实现

要求:调用 submit 一次,参数是选手提交的源代码作为字符串。

多题合并版

可以修改一个程序,使得里面多出一个字符串是程序自己的源代码。

So?

编写一个程序,输出本身源代码的后缀数组。

除此之外为了进一步证明你确实有给 Quine 的后缀排序的超能力,请另外输出 n−1 个整数分别表示排序后相邻后缀的最长公共前缀的长度。

话说大家有什么好的方法么?比如不需要构造字符串之类的做法?

倒是有一个并卵的思路:写一个字符递增的或者增减性简单的代码

参考资料

主要是 http://www.madore.org/~david/computers/quine.html 一位 Quine 大神写的

一个编译器

2016-07-29 22:14:52 By dram

传送门

特别感谢 peg.js (提供语法解析支持)和 decimal.js (提供高精支持)

  • (我是更新区,这里经常变)
  • 目前加入了节点链接功能,可以稍微方便点地查看数据流。
  • 然后加入了奇怪的 hover 高亮和变量名标注

各位大神一起来把 flea-compiler 黑掉吧!谢谢啦!

(话说是不是出成 uoj 题就会有一堆人来找 bug 来 hack 了 2333)

另外跪求 sigmoid 的靠谱计算方法。。。


众所周知,NOI 2016 旷野大计算,vfk 提供的题解里面,代码是写成这样的

x = in()
p = s((x + 1e-30) << 500) << 152 
y = s((x >> 150) + p)
r  = x + ((-y + 0.5) << 153) + p
out(r)

于是我就开了个坑,写了个编译器

语法稍微有点变动的说:

          { 我是注释 }
x = in(1) { 1 代表第一个输入 }
p = s((x + 1e-30) << 500) << 152 
y = s((x >> 150) + p)
r  = x + ((-y + 0.5) << 153) + p
out(r)

可是为什么会这样改呢?因为。。我觉得 I 全在前面没有问题啊。。

那为什么 O 不要都在后面呢。。

这个。。哎呀。。 不要在意那些细节。。

于是生成的代码是

I
C 1 0.000000000000000000000000000001
< 2 500
S 3
< 4 152
> 1 150
+ 6 5
S 7
- 8
C 9 0.5
< 10 153
+ 1 11
+ 12 5
O 13

表达式的语法大家自己体会体会吧 orz,网页上也有一个 help

(话说可以改进呢,泥萌如果想要的话我可以搞几个优先级不一样的 shl shr cmp max 之类的保留字运算符出来啊,大家有意可以在下面讨论)

后来的变量会隐藏前面的变量,所以排序那题就不用生成一大堆临时名字了

写完之后点那个 [Share your fleas] 然后地址栏里就是一个自带代码的网址了,然后就可以 Share 了。哎呀好像有点长。。

然后目前有两个优化:

  • 如果整个子表达式或者整个变量就是个常数,它会被尽量内联,同时造成精度损失(额)。如果真的需要常量节点的话,这么算:$C = (\texttt{in(1)} \gg 10000) + C$

    (以下是一点题外话)

      $ cat compute.out 
      I
      > 1 10000
      O 2
      $ ./checker -f compute.out
      1
      0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

    但是 $2^{-10000} \approx 5.0124\times 10^{-3011}$

  • 公用子表达式消除!Common sub-expression elimination, CSE。发现重复出现的表达式可以避免重复计算。

具体可以见默认的样例代码。

文件的话有这些

  • http://dram.cf/flea-compiler/
    • vendor/decimal.min.js
    • index.html
    • parse.pegjs
    • parse.jsparse.pegjs 生成
    • compiler.js
dram Avatar