UOJ Logo vfleaking的博客

博客

UOJ Round #3

2014-12-18 19:33:04 By vfleaking

UOJ Round #3将于12月20日星期六晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第三场UOJ Round。UOJ Round难度定位一如既往地大概还是省选难度~欢迎大家来玩~!

63年前也就是1951年12月20日,美国爱达荷州阿科市,EBR-1 首次由核能产生电能,点亮了四盏灯。于是 EBR-1 成为了世界上第一个核电站。几十年过去了,核电作为相当安全、环保、经济的能源正在逐步的代替其它的各种能源。

为了纪念世界上第一个核电站的诞生以及物理学家利用核裂变发电的脑洞,此次比赛将以核电站为主题。

出题人:delayyy, vfleaking

小熊像超人一样飞

这场成绩将计入rating。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

点击此处直达报名

UPD:很抱歉地通知您,此次比赛将推迟一天。之前由于清华集训导致出题人完全没有时间造题,屋漏偏逢连夜雨,昨天恰好赶上我因为北京的神奇病毒发烧打了一天吊针,今天振作起来赶着造第三题的数据及标程。

考虑到比赛质量为第一位,我很怕这么仓促的准备会影响比赛的题目质量,出一些sb错误,所以比赛将延期一天。

一直以来UOJ都和BestCoder撞了,实在对不起,今天想打BestCoder的同学去打吧 T^T……

真心表示万分抱歉……

时间推迟到12月21日星期日晚上19:00。

UPD:比赛已经结束,恭喜获得前 5 名的选手!

  1. saffah
  2. TakanashiRikka
  3. fotile96
  4. laekov
  5. Starzxy

UOJ Round #2 题解

2014-12-06 22:18:23 By vfleaking

猪猪侠再战括号序列

算法一

有一个超良心测试点满足 $n \leq 4$。注意到 $8$ 个元素的排列最多 $8!$ 个,所以直接使用 bfs 或者 dfs 搜索,每次对于一个序列枚举所有可能的翻转区间然后搜下去就好了。可以获得 10 分。

算法二

算法一显然太无脑了。考虑翻转操作其实用起来非常不爽,因为牵连的元素个数太多。如果题目允许你每次交换序列中的两个元素的位置,那么其实要好办很多。

于是我们重新设定目标,把目标序列变为一个显然是合法的括号序列,类似这样 “(((())))”。

我们从左往右依次处理原序列的前 $n$ 个括号,如果发现有一个右括号,我们就在右边随便找个左括号。由于左括号和右括号都是 $n$ 个,所以我们总能找到。然后我们把当前位置到那个左括号之间的序列翻转过来,这样当前位置就很开心的成了左括号。翻转过来之后当然中间的括号一团糟啦!不过我们是从左往右考虑,所以我们只用保证当前位置以左是与目标一致的。至于右边嘛,这是以后的事情了。

暴力在右边找左括号,然后再暴力翻转序列就能做到 $O(n^2)$ 了。可以获得 50 分。

阅读更多……

UOJ Round #2

2014-12-02 13:11:50 By vfleaking

UOJ Round #2将于12月6日星期六晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第二场UOJ Round。UOJ Round难度定位大概是省选难度~欢迎大家来玩~!

这次我们荣幸地请到了百度贴吧上的 _叫我猪猪侠 来出题!他带来了一道很符合猪猪侠风格的题!敬请期待猪猪侠带来的狂欢题!

出题人:_叫我猪猪侠, vfleaking, jcvb

唔……这次题目难度目测比上次要简单些。上次那么多人看题跑是什么情况……= =……这次坐等神犇AK。

小熊像超人一样飞

这场成绩将计入rating。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD:比赛已经结束,恭喜获得前 5 名的选手!

  1. fotile96
  2. C_SUNSHINE
  3. thomount
  4. latrommI
  5. saffah

UOJ Round #1 题解

2014-11-22 22:03:16 By vfleaking

缩进优化

算法一

方便起见用 $/$ 表示整除,$X$ 表示最大的 $a_i$。

要最小化的就是 $\sum_{i=1}^{n} a_i / x + a_i \bmod x$。

枚举 $x$ 再暴力计算上式并更新答案,由于 $x$ 不超过 $X$,所以复杂度是 $O(nX)$。可以获得20分。

算法二

$a_i$ 相同的可以合并在一起,然后就得到了 $O(n + X^2)$ 的算法,结合算法一可以获得40分。

阅读更多……

UOJ Round #1

2014-11-17 21:14:48 By vfleaking

UOJ Round #1将于11月22日星期六晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第一场UOJ Round。UOJ Round难度定位大概是省选难度~欢迎大家来玩~!

唔……其实UOJ Easy Round只会在每年的noip季节出现,省选难度才是主旋律的。

出题人:delayyy, Picks, vfleaking

小熊像超人一样飞

这场成绩将计入rating。

这次改了下排名系统。如果你某题得零分是不计罚时的(之前好像坑了不少小朋友)。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD:比赛已经结束,恭喜排名前5的选手!

  1. fotile96
  2. SanSiroWaltz
  3. PoPoQQQ
  4. matthew99
  5. thomount

题解在这里

noip 2014 day2 T3 vfk题解

2014-11-09 16:19:05 By vfleaking

jcvbydcPicks跪烂了……

我来讲点低端的。

首先还是选个素数在模意义下 $O(n)$ 求解。不过好像有点卡常数?

没关系!我们可以选一个好取模的素数比如$2^{31} - 1 = 2147483647$。

由于 $a \cdot 2^{31} + b \equiv a + b \pmod{2^{31} - 1}$,所以 x 与 (x & 0x7fffffff) + (x >> 31) 是同余的!

于是:

register unsigned long long y = 0;
for (int i = n; i >= 0; i--)
{
    y = y * x + a[i];
    y = (y & 0x7fffffff) + (y >> 31);
}
y %= 0x7fffffff;

当当当当!这样就跑得快了三倍了!(从$1.2\texttt{s}$变成了$0.4\texttt{s}$)

在此基础上再多加几个奇怪的素数模一模判一判就好了。只要不是零多项式那么至多只有$n$个根,所以后面不加什么常数优化也没关系。

UOJ Easy Round #1 题解

2014-11-02 22:32:05 By vfleaking

猜数

算法一

直接暴力枚举所有可能的 $a, b$ 然后判定。可以得30分。

算法二

由于 $a, b$ 都是 $g$ 的倍数,而 $ab = gl = n$,所以当然 $l$ 也是 $g$ 的倍数。

既然如此,我们可以暴力枚举所有 $l / g = st$ 的拆分,然后 $a = gs, b = gt$。

于是暴力枚举所有 $l / g$ 的约数,是 $O(\sqrt{l / g})$ 的。可以得60分。

阅读更多……

UOJ Easy Round #1

2014-10-30 23:55:38 By vfleaking

大家好~~UOJ Easy Round #1将于11月2日星期天晚上19:00举行!比赛将进行3个小时,共三道题。

这是UOJ第一场Easy Round。UOJ Easy Round难度定位大概是noip难度~欢迎大家来玩~!

出题人:ydc, vfleaking, jiry_2

小熊像超人一样飞

这场成绩将计入rating,UOJ第一场计rating的比赛,就要到来了!

之前Test Round的时候有些同学参加比赛时遇到了些麻烦,请注意必须在比赛前报名才能参加。UOJ赛制比较特殊,比赛时只测样例,比赛结束后会进行最终测试。

比赛答疑在博客下面回复就好了~我能及时看见的。

UPD: 比赛结束了,恭喜前5名的选手!

  1. saffah
  2. thomount
  3. latrommI
  4. Gromah
  5. zangfenziang

题解马上发布。

UPD: 题解可以在这里找到

请大家爱护UOJ,不要恶意Hack

2014-10-24 22:53:08 By vfleaking

已经开始有人自己Hack自己了……

很遗憾,我没有任何措施来判断什么是正常向hack,什么是恶意hack。

对于恶意Hack我只有一个办法:ban人,ban IP。。。

只想说大家爱护UOJ吧……

T_T……虽然大家都知道如果恶意hack明显多于正常向hack时UOJ肯定会移除Hack功能,但是人类就是这样的生物——好奇,喜欢玩,并且更倾向于把当下的这个爽先爽了。对此我只能表示无力了……

一只小熊

我相信大家,不会无聊到卡OJ的地步。

封禁名单:

  • LuckyQueen
  • mosfjh
  • nevermore
  • dasjfko
  • Wither
  • ck
  • mcfx
  • fts2001
  • jefflyy
  • NiroBC
  • samjia2000
  • abcdf

2020-05-22 UPD:

六年来,每隔一段时间就有人跑出来问为什么不关 A+B 的 hack,那是因为对于那些极端好奇的人来说关了 A+B 的 hack 他们就会 hack 别的题了。然后就有人质疑 UOJ 怎么不调低 hack 的测评优先级,问题是这东西测评优先级一直都比正常评测要低呀。。所以并不会影响大家做题啦。但因为自己好奇就跑去搞一些无意义的恶意 hack 真的没有必要,请大家不要这样做(毕竟这道题的 extra test 数量已经达到 207 了。。)

UOJ博客使用教程

2014-10-24 00:18:48 By vfleaking

UOJ博客使用的是Markdown。(好吧……好简陋的……好多功能还没写……)

(喂喂喂我们是OJ好吗……要那么完善的博客功能干啥呢……?)

其实我觉得Markdown不用教!一学就会!

(完蛋了……UOJ好像没有Markdown的语法高亮……= =……)

我就只介绍最基本的功能好了。其它的自己探索吧~比如这里

阅读更多……

共 61 篇博客