日志 - vfleaking的博客

UOJ Round #6 题解

2015-03-08 20:45:20 By vfleaking

破解密码

from：Starzxy

~~这都是vfk出的QAQ你萌别打我~~

算法一

暴力枚举每一位的字母,判段Hash值是否相等,时间复杂度$O(26^n)$。可以获得20分。

算法二

用高斯消元消元就好啦，时间复杂度$O(n^3)$。可以获得50分。

算法三

对于每一个$a_i$，把它变为$a_{i+1}$就是把$a_i$的首字母移到最后一位，对应的，设$a_i$首字母为$c$，$h_{i+1}=((h_i - 26^{n-1}\mathrm{num}(c))\times 26+\mathrm{num}(c))\bmod p$。对于每一位，我们枚举$c$，因为$p$是大于$26$的质数，且数据保证有解，可以确定每一位有且仅有$1$个小写字母满足。

UOJ Round #6

2015-03-02 22:21:08 By vfleaking

UOJ Round #6将于3月8日星期日晚上19：00举行！比赛将进行3个小时，共三道题。

这是UOJ第六场UOJ Round。UOJ Round 还是一如既往的省选难度～！欢迎大家来玩～！

公元321年，就在3月8日的前一天，3月7日，罗马帝国皇帝君士坦丁一世正式宣布星期日为罗马的休息日。屈原跳河只换来端午1天，中国成立只换来国庆7天，各个学校的老师还经常剥夺休息日。你看看人家君士坦丁一世，随手一挥送休息日就每周送一个，简直就是业界良心中的战斗机！

所以本次比赛将以星期日为主题。

鼓掌熊

出题人：Starzxy, ~~Picks~~, jiry_2

这场成绩将计入rating。

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

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

matthew99
qmqmqm
PoPoQQQ
Dylan_Sun
wyh2000

WC2015 混淆与破解题解

2015-02-22 16:39:31 By vfleaking

~~我比较弱看了半天范爷的算法都没太懂……~~我来讲点奇怪的算法……感觉本质上跟范爷的算法是一样的。

考虑两个布尔变量 $a, b$ 的异或： $a \xor b$。看起来就让人浑身难受，所以我们用 $1$ 表示布尔值 $0$，用 $-1$ 表示布尔值 $1$。也就是用 $(-1)^x$ 代替原来的布尔变量 $x$，这样 $a \xor b = ab$ 了，即 $a$ 和 $b$ 相乘。

Goodbye Jiawu 题解

2015-02-17 17:30:24 By vfleaking

新年的巧克力棒

from Picks

数据是 vfleaking 造的，题解也是 vfleaking 写的。

算法一

有20分的数据巧克力棒长度非常小，直接搜索下或者手算就行了。

算法二

对于 $n \leq 1000$，我们可以用 DP 解决。 $f[i] = \max(f[k] + f[i - k] + [k == i - k])$。$[k = i - k]$ 表示 $k = i - k$ 时为 $1$ 否则为 $0$。时间复杂度 $O(n^2)$，可以通过前 $5$ 个点获得 50 分。