https://www.zhihu.com/question/272303098/answer/367368615

呃。。最近从这个submission开始，陆续有不少人通过交互题中交互库的漏洞来骗取AC。

在UOJ 328交互库出漏洞之后，其他的一些交互题的库也陆续爆出漏洞：这里和这里。

(后一个提交记录是我小号。。我抱着试试看的心态玩了玩没想到APIO2016这样的正规比赛交互库也会出漏洞(或者是uoj管理员配置得不好?

怎么说呢。。一方面大家做题的时候不能总是抱着戏耍交互库的心态做题，另一方面出题人们也要尽量保证交互库不被cha掉。。(出交互题真难啊)

关于怎么加强安全性，我目前还没有很明确的想法。。欢迎大家提建议。。也希望uoj上的交互题能越出越好>_>

想法1:在输出文件的开头输出一个保密的字符串(比如说交互库内部的一个很长的随机串)，选手不知道该字符串就无法伪装交互库的输出。这个想法有两个弱点：一是不能防止这种骗输入的情况；二是这个串要非常长(uoj的输出可以看到前100b来着?)或者交互题就不能查看输出。

想法2:加密输入。最好真实数据的输入格式跟题面描述中的不同。这样应该可以防止骗输入，但是又带来了不能hack的问题。如果要允许hack，那可能还需要出题人写一个将hack数据加密的程序，不知道uoj能否实现这样的功能?

想法3:对于牵扯到随机性的题，随机种子最好自己写而不是使用系统库的(其实这是个教训，见这里

听说有一个东西叫做Polyglot，就是写一份能由多种语言的编译器编译运行成功的程序。

然后我花了两个多小时摸索出了一个Pascal，C，Python3的Polyglot→_→(以UOJ上编译器为准)

(*c),d=2//len('''
;/*)var a,b:longint;begin read(a,b);writeln(a+b) end.*/
#include <stdio.h>
a,b;main(){scanf("%d%d",&a,&b);printf("%d",a+b);return 0;}
/*'''),3
print(sum(map(int,input().split())))
#*/

见我的submission。C，Pascal，Python。

阅读更多……

打个广告

(就是写了个脚本扒程序。。感觉好暴力啊。。

upd

欢迎热爱hack的同学来加强uoj的数据! (其实就是：玩了一天就玩腻了。。不准备再玩了。。)

这是我第一次玩github。。

先回顾一下题目吧，给定一个$n$个元素的偏序集(就当是DAG的传递闭包)，求：

1)最长反链的长度；

2)一个最长反链；

3)哪些元素可能在最长反链中。

很久以前看到这个题的时候我还没有意识到它就是dilworth定理。。。然后看着题解做了第一问。觉得“第二问好像很水的样子，随便构造就出来了”，可是试了很多种方案都没有构造出来。百度上搜到的blog都是“bzoj上只有第一问的数据，那么我就只做第一问吧”，然后问了一些同学他们也不知道第二问怎么做的样子。某天膜了一下vfk的博客，发现了dilworth定理的一个证明，可惜不是构造性的(就是我不能看着这个证明就构造处一个最长反链)。

最近几天搜到了一个网页。

我就抄袭一下这个上面的内容，顺便orz回答这个问题的大爷。。。

回忆一下最小链覆盖的求法。令$n$为偏序集的点数，建立一个二分图，$X$部的$i$号点用$x(i)$表示，$Y$部的$i$号点用$y(i)$表示。对于偏序集中的一条关系$u < v$，在$x(u)$与$y(v)$之间连边。令$m$为二分图的最大匹配的大小。则答案为$n-m$。

构出了二分图之后我们可以构出其最大独立集$I$(怎么构的话英文wiki和上面的网页上都有吧)。对于一个$1\le i\le n$，如果$x(i)\in I$且$y(i)\in I$，那么将$i$加入我们的反链$A$。

首先我们证明$A$的确是个反链。否则的话假设$u\in A,v\in A,u < v$。那么应该存在$x(u)$到$y(v)$的边。而$x(u),y(v)$却是在同一个独立集中的。所以产生矛盾，$A$是反链。

然后我们证明这个反链的大小至少为$n-m$。把独立集中的点称作黑点，其他点称作白点。那么黑点的数目是$2n-m$。而黑点的数目=$|A|$+(满足$x(i)\in I$或$y(i)\in I$的$i$的数目)，后者不会超过$n$，则前者至少是$n-m$。

这样！我们构造出了一个大小至少是$n-m$的反链！然后最小链覆盖的大小就是$n-m$，反链的大小不会超过它，所以这个反链的大小就是$n-m$，且是我们要求的最大反链。

数据、某蒟蒻写的spj、某蒟蒻写的程序 提取密码：tjqs(好像不需要提取密码)

spj可以直接用于lemon。

如果发现程序或spj有错请在下方评论或私信r_64。