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将于3月8日星期日晚上19：00举行！比赛将进行3个小时，共三道题。
这是UOJ第六场UOJ Round。UOJ Round 还是一如既往的省选难度～！欢迎大家来玩～！
公元321年，就在3月8日的前一天，3月7日，罗马帝国皇帝君士坦丁一世正式宣布星期日为罗马的休息日。屈原跳河只换来端午1天，中国成立只换来国庆7天，各个学校的老师还经常剥夺休息日。你看看人家君士坦丁一世，随手一挥送休息日就每周送一个，简直就是业界良心中的战斗机！
所以本次比赛将以星期日为主题。
出题人：Starzxy, Picks, jiry_2
这场成绩将计入rating。
再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。
UPD:比赛已经结束，恭喜获得前 5 名的选手！
我比较弱看了半天范爷的算法都没太懂……我来讲点奇怪的算法……感觉本质上跟范爷的算法是一样的。
考虑两个布尔变量 $a, b$ 的异或： $a \xor b$。看起来就让人浑身难受，所以我们用 $1$ 表示布尔值 $0$，用 $-1$ 表示布尔值 $1$。也就是用 $(-1)^x$ 代替原来的布尔变量 $x$，这样 $a \xor b = ab$ 了，即 $a$ 和 $b$ 相乘。
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 分。
你需要打个表，然后找规律，就能发现答案是 $n - c(n)$，其中 $c(n)$ 是 $n$ 的二进制表示中 $1$ 的个数。然后就 AC 了！
再见，甲午！
过去的一年是甲午年（提起甲午总是想到120年前那场惨烈的中日甲午战争），值此新春佳节之际，我们将于大年三十的前一天大年二十九下午 13:00 到 18:00 举办一场盛大的 Goodbye Jiawu 赛。
即：2月17日下午 13:00 到 18:00。注意此次比赛时间为 5 小时，共 5 道题 ABCDE 来给大家贺岁～
不要问我为啥甲午的翻译是 Jiawu！谷歌娘告诉我的！
我们准备了一些有趣的题目，不过题目还没有完全确定，过几天会在这里发布出题人。
至于 UOJ Round #6，由于近日来大家都去期末考试去了（从网站的访问量上可以看得出来）。然后二月初也够呛，接着就是一年一度的 WC 了，也没人会打。所以 UOJ Round #6 将被移到再见甲午赛之后。
赛制仍然是OI赛制，但是题目难度嘛……水题和省选难度题兼有。欢迎所有人包括萌萌哒NOIP选手来玩！
提前祝大家春节快乐！（貌似太早了 = =……）
UPD: 公布出题人：Picks, saffah, vfleaking, wangyisong1996
UPD:比赛已经结束，恭喜获得前 5 名的选手！
很久以前写的题解。听说有人找不到他们？
动态仙人掌 系列题解之四 —— link-cut cactus
UPD (2020-08-15): 不好意思，其实后来 163 博客倒闭了，转战 csdn 了
由于 UOJ 什么的七七八八的事情，集训队作业一直缓慢。但是我最终还是做完啦！
第一轮集训队作业试题准备：http://pan.baidu.com/s/1sj6ZhOL
第一轮集训队作业试题泛做：http://pan.baidu.com/s/1kT0zNBx
试题准备就是传说中的每个集训队成员重造 3 道题，试题泛做是传说中的 100 道题题解 = =……都是很久以前的题了，我猜没什么人需要？不过还是挂出来吧。有句古话说得好：彼之砒霜，吾之蜜糖。说不定对你有用？
顺便附第一轮集训队作业内容：http://pan.baidu.com/s/1AlBqu
坐等WC退役。
鄂公网安备 42010202000505 号Server time: 2025-07-07 11:29:12