UOJ Logo r_64的博客

博客

HNOI2018 duliu & road

2018-04-15 13:52:57 By r_64

最近交互题发生的一些事情

2017-11-20 18:05:00 By r_64

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

UOJ 328交互库出漏洞之后,其他的一些交互题的库也陆续爆出漏洞:这里这里

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

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

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


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

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

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

干了一件有趣的事情

2017-08-12 22:22:28 By r_64

听说有一个东西叫做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。CPascalPython

阅读更多……

Hack狂魔养成记(雾)

2016-04-28 18:35:13 By r_64

打个广告

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


upd

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

这是我第一次玩github。。

CTSC2008 river

2015-07-27 11:38:42 By r_64

先回顾一下题目吧,给定一个$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。

r_64 Avatar