UOJ Logo WrongAnswer的博客

博客

51nod算法马拉松22参赛总结

2017-03-06 09:57:03 By WrongAnswer

又一次RP爆发卡线rank 10……有点爽……


由于周五是我出的校内训练,所以等21:30讲完题回家路上才开始看题。

路上用手机看题。A题看完以后想到FJOI2016一试T3,其实就是Codechef原题FRBSUM。看起来很复杂,其实注意到一个核心性质:把 $S$ 中的元素排序得到 $a_1\le a_2\le\cdots\le a_n$ 以后,最小的满足 $a_i > 1+\sum_{j=1}^{i-1}a_j$ 的 $i$ 对应的 $\sum_{j=1}^{i-1}a_j$ 就是 $S$ 的优美值。

因为当 $0 < i' < i$ 时,如果 $\{a_1,\cdots,a_{i'-1}\}$ 能配出的数为 $[0,\sum_{j=1}^{i'-1}a_j]$,那么 $\{a_1,\cdots,a_{i'}\}$ 就能配出 $[0,\sum_{j=1}^{i'-1}a_j]\cup[a_{i'},\sum_{j=1}^{i'}a_j]=[0,\sum_{j=1}^{i'}a_j]$。而由于 $a_i$ 已排序,所以 $a_{i'} > 1+\sum_{j=1}^{i-1}(i'\ge i)$,因此 $1+\sum_{j=1}^{i-1}$ 配不出来。这样求优美值就很简单了:排序以后,一开始 $\mathrm{sum}=0$,从小到大把 $a_i$ 加入 $\mathrm{sum}$,一旦加入前发现 $a_i\not\in[0,1+\mathrm{sum}]$ 就得到答案了。(FJOI原题是多次询问区间答案,做法是用可持久化线段树加速查询 $[0,\mathrm{sum}+1]$ 区间内的数,因为一次可以把多个数加进 $\mathrm{sum}$,所以 $\mathrm{sum}$ 只会增加 $O(\log\sum a_i)$ 次)

想到这里,这题差不多就会做了,从小到大选 $S_1$ 中的元素,如果 $S_1$ 中没有 $[0,\mathrm{sum}+1]$ 内的元素($\mathrm{sum}$ 为已选元素之和),那么就从 $S_2$ 中贪心选出尽量大的数加入 $S_3$(因为答案是选出数的和,所以不贪心取最大的话可以调整成更大的数更优),直到 $S_1$ 和 $S_2$ 剩下元素都大于 $1+\mathrm{sum}$ 或 $|S_3|=k$。于是我直接在手机上写完,交上去,TLE。

然而我的复杂度是 $O(nm\log m+Tm)$ 啊,应该不会TLE的?回头看一遍数据范围发现这题输入了 $10^6$ 个数,不加输入优化没什么救,然后就在刚到家的时候把输入优化码完,AC了。

回家上电脑接着看了后几题。B题一开始以为是个无聊的卡精度马尔可夫过程,思考了一下才明白决策是自己选的,然后列出来就是最小化一个带一堆 $\min$ 的奇怪式子,不会了。C题题目不是很懂,一大堆 $e$ 看起来很丧。D题让我想到了UOJ #176,然而这题我并不会做,惨啊……

不过好像D可做?用UOJ那题的题解里提到的Boruvka算法,建Trie维护一下可能就OK了?问题是要计数。接着想了一些办法,首先是相同点权构成的点集 $S$ 连的是边权 $0$ 的完全图,一定全部被连起来,方案数是 $|S|^{|S|-2}$。缩完相同点权以后,相同边权的边就没有公共点了,意味着MST唯一?好像很资磁。

于是快要0:00开始写Boruvka,写完一测样例果然萎了。原来……我太SB了,虽然相同边权的边没有公共点但是在缩的时候会把这些边的端点缩到一块去……看样子这么做下去并没有前途。

先去睡觉了。

纠结于5题刚不出来的我冷静了一晚上,感觉好像理解了C题的意思。于是第二天一起来去刚C题。

推了一发式子——

$$[f(x)-e^x]^2=\sum_{i=0}^Na_i^2x^{2i}+2\sum_{i=0}^{N-1}\sum_{j=i+1}^Na_ia_jx^{i+j}-2\sum_{i=0}^Na_ix^ie^x$$

$$(x^i)'=ix^{i-1}\Rightarrow\int_0^1x^i\mathrm{d}x=\frac{1}{i+1}1^{i+1}-\frac{1}{i+1}0^{i+1}=\frac{1}{i+1}$$

然后并没有想清楚 $x^ie^x$ 定积分怎么求,就开始手算小数据:

$$(x^ie^x)'=(ix^{i-1}+x^i)e^x$$

$$\Rightarrow [(x-1)e^x]'=xe^x$$

$$\Rightarrow [(x^2-2x+2)e^x]'=x^2e^x$$

$$\Rightarrow [(x^3-3x^2+6x-6)e^x]'=x^3e^x$$

这样归纳一下好像就推出来了:

$$(e^x\sum_{i=0}^n(-1)^iA_n^ix^{n-i})'=x^ne^x\Rightarrow\int_0^1x^ne^x\mathrm{d}x=e\sum_{i=0}^n(-1)^iA_n^i-(-1)^nn!$$

这么看来原式应该就等于

$$\sum_{i=0}^N\frac{1}{2i+1}a_i^2+2\sum_{i=0}^{N-1}\sum_{j=i+1}^N\frac{1}{i+j+1}a_ia_j-2\sum_{i=0}^N[e\sum_{j=0}^i(-1)^jA_i^j-(-1)^ii!]a_i$$

只有二次诶,那只要对每个 $a_i$ 令偏导为 $0$ 就行了,就能得到一个 $N+1$ 元一次方程组(UPD):

$$\frac{2}{2i+1}a_i+2\sum_{0\le j\le N,j\ne i}\frac{1}{i+j+1}a_j-2[e\sum_{j=0}^i(-1)^jA_i^j-(-1)^ii!]=0$$

用高斯消元解方程组就做完了,可是 $a_i=\sum_{j=0}^\infty p_{ij}\cdot e^j$ 什么鬼??难道要把多项式放进去消元,这个是要炸的呀。看了下方程组发现系数矩阵 $A$ 的数都是有理数,那么解方程 $Ax=b$($x,b$ 为列向量)得到 $x=A^{-1}b$,而 $b$ 中的数都能表示成 $p_0+p_1e$ 的形式,所以答案 $x$ 也能表示成 $p_0+p_1e$ 的形式。

出题人真坑,明明答案是 $p_0+p_1$ 的形式,只有 $p_{i0},p_{i1}$ 是有用的,题面偏要写成 $\sum_{j=0}^\infty p_{ij}$ 误导别人存整个多项式。然后又只要输出有用的那两个数。坑爹!!

推导这里就开始写,写完之后测了下样例 $N=0$ 过了,$N=1$ 的WA了。开始怀疑算法有没错。或者是哪一步推导错了。好虚啊。

手算了一边发现算法是对的,调一发程序,是程序把某个式子算错了= =b

改改改。

终于过样例了。

终于过了C。

看了下榜已经一堆人过5题了,而我只有约四十名。我开始做B题。

一开始想枚举每个点的前继然后怎么搞,觉得好像有反例(?)就犹豫了好长时间。不过想了一会儿还是找到了正确的思路:先确定 $0$ 个星的时候的决策,显然升级概率越大越好,再确定 $1$ 个星时候的决策……

因此,记 $f_i$ 为当前有 $i$ 个星,按照最优策略,第一次变成 $i+1$ 星的期望花费,则枚举选择的魔法石 $j$,有 $1-\mathrm{prob}(i,j)$ 概率失败,失败的话就要从 $i-\mathrm{lose}(i,j)$ 星逐步转移到 $i+1$ 星,因此 $f_i=\min_j\{C_j+[ 1 - \mathrm{prob}(i,j) ]\sum_{k=i-\mathrm{lose}(i,j)}^if_k\}$。

移项得到 $f_i=\min_j\{\frac{C_j}{\mathrm{prob}(i,j)}+[\frac{1}{\mathrm{prob}(i,j)}-1]\sum_{k=i-\mathrm{lose}(i,j)}^{i-1}f_k\}$。直接DP会有精度问题吗?

那我写一下交个看看。写完没过样例因为我把 $C_i$ 写丢了(还查了好一会儿),过了样例交上去。结果,居然直接AC了,完全没有卡精度的迹象。

我也不知道为什么没有出精度问题,也许是运气好吧。上次在51nod做同一个出题人出的马尔可夫过程题还卡了好久的精度呢。

再看D的时候D的通过人数已经好多了。这题一定不难,只是我想复杂了。

于是手工模拟了一遍点集 $\{0,1,2,3,4,5,6,7,8\}$ 的Kruskal过程,整个过程如下:

$$\{0\},\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{7\}$$

$$\{0,1\},\{2,3\},\{4,5\},\{6,7\}$$

$$\{0,1,2,3\},\{4,5,6,7\}$$

$$\{0,1,2,3,4,5,6,7\}$$

我好像发现了什么……是按二进制位从低到高合并的!

如果在Trie树上呢?连边 $(u,v)$ 的时候,$(u,v)$ 的权值最高位就是 $u,v$ 在Trie上的LCA高度。因此对Trie树 $T$ 模拟Kruskal的方法是这样的:

Kruskal(T):
    若 T 的左子树非空: Kruskal(T 的左子树)
    若 T 的右子树非空: Kruskal(T 的右子树)
    // 以上两步之后最多只剩左右子树两个连通块,并且这两步过程中连的边权都比剩下可能连的边小,因此是正确的
    若 T 的左子树 T1 和右子树 T2 均非空(假设 |T1| < |T2|):
        x = Infinity, c = 0
        DFS 枚举 T1 节点 u,DFS 过程中在 T2 中贪心地找点 v 使得 a[u] xor a[v] 最小: // 由于缩了相同点,每个 u 对应的 v 唯一
            若 a[u] xor a[v] = x: c += 1
            若 a[u] xor a[v] < x: x = a[u] xor a[v], c = 1
    最小生成树边权和加 x,方案数乘 c

这个问题的性质就是左右子树独立,注意到这一点以后就变地简单多了。然后我把原来写的错误的Trie树Boruvka算法删了一大半,改成直接在树上DFS,过了样例,交上去也过了。

过D的时候12:00多。昨晚觉得B、C、D都一副不可做的样子,不过现在都做出来了,有点爽。

还剩E、F两题。

下午开始搞E。有点像个大代码数据结构题,不过如果真是这样的话不虚,因为时间充足,呵呵。

一开始题目看错了,以为是链上插入一个元素,查询过一个点的元素中前 $k$ 小的异或。我想这不就是把链拆成到根的路径以后转成查子树区间 $k$ 小吗,可持久化线段树就搞定了。E题肯定不是这么简单!又读了遍题目,才明白真正的题目意思是:每个点 $i$ 维护一个初值为 $0$ 的数组 $c_i$,每个操作 $(u,v,a,b)$ 把链 $(u,v)$ 上所有点 $i$ 的 $c_i[b]$ 增加 $a$,查询的是 $c_w$ 数组中 $c_w[i]$ 前 $k$ 小的 $i$ 的异或。

这下就不太一样了,因为用可持久化线段树虽然可以对每个 $b$ 查出 $c_w[b]$,却不能查出 $c_w[b]$ 前 $k$ 大的 $b$。不给力。

可能我需要换个想法。如果不是树而是序列呢?那就只要按顺序扫一遍过去,维护一个 $c$ 数组,遇到操作的左端点就把 $c[b]$ 加 $a$,遇到右端点就 $c[b]$ 减 $a$。用线段树维护每个 $x$ 对应的满足 $c[i]=x$ 的 $i$ 个数就能查前 $k$ 小了。可是一样多的按 $i$ 排序怎么搞?

那就把每个 $(c[i],i)$ 表示成一个数 $c[i]\cdot B+i$。

值域好像很大的样子,线段树要动态开节点- -那么如果是树呢?树剖一下?

于是一个操作被拆成了 $O(\log n)$ 个,每次要改线段树,复杂度变成 $O(\log^2 n)$ 了- -

不知道能不能过,而且觉得空间会爆炸的样子。不过空间好像不是 $O(m\log^2 n)$ 而是 $O(m\log n)$?我写下。……写完了,调一发。……过样例了。

然后在51nod上运行了第一个点,MLE。

数组改小。

MLE。

再改小。

MLE。

再改小。

RE。

想放弃。

然后记起51nod好像是64位机?如果我把指针改成 int 下标呢?改。

改完。

测一下。

第一个点过了。

交。

WA

WA

WA

……

那应该是我写挂了。回去和暴力拍小数据,怎么都拍不WA,又拍了好多组大数据也拍不WA。这就很尴尬了QAQ

最后还是死于线段树的区间:right = m * 10000000000ll 打成了 right = 10000000000ll。这个小数据不太可能拍出来……

挣扎了一下午,终于在17:00前用两个 $\log$ 把这题卡过去了。

有希望。

现在剩下F。

所有LCS的和?我只会求 $|s_2|$ 遍LCS。可是显然过不去。

或者是需要一些特殊的状态设计?于是开始设计新的DP,结果不管怎么改都要 $O(|s_1||s_2|^2)$。GG。总觉得自己是想复杂掉坑了,可是又总是找不到可行的方法。

最后还是在rank 1的AKF帮助下才得救……AKF表示这题是“All Substring LCS”,是论文题。于是我就去看了论文,然而由于我太菜鸡了,看了很久才看懂。。。

所以到了第二天的下午才搞掉F。一看排行榜,刚好rank 10。有点感动。


这场比赛还是有一些收获的。

A题的贪心算法还是比较妙的,虽然如果做过Codechef原题以后就没什么难度了- -

B题给我的启发是:形如 $f(i)=a_i+\sum_{j=0}^{i+1}c_{i,j}f(j)$(其中 $\sum_{j=0}^{i+1}c_{i,j}=1,c_{i,i}\ne 1$)这样的方程,可以按照 $i=0,1,2,\cdots$ 的顺序递推,这样的好处是,每个 $f(i)$ 可以表示为 $f(i+1)+p_i$ 的形式,可以归纳证明:

$$f(i)=a_i+\sum_{j=0}^{i-1}c_{i,j}[f(i)+\sum_{k=j}^{i-1}p_k]+c_{i,i}f(i)+c_{i,i+1}f(i+1)$$

$$\Rightarrow f(i)=a_i+(1-c_{i,i+1})f(i)+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k+c_{i,i+1}f(i+1)$$

$$\Rightarrow f(i)=\frac{1}{c_{i,i+1}}(a_i+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k)+f(i+1)$$

即 $p_i=\frac{1}{c_{i,i+1}}(a_i+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k)$,若已知 $f(n)=0$,按 $i=0,1,2,\cdots,n-1$ 顺序递推 $p_i$ 可以求出所有的 $f(i)$。另外我还是很好奇这题为什么要注意精度,直接写应该就过了吧?

C题的收获是求 $x^ie^x$ 的积分以及用偏导求多元二次函数的最值(其实原理和初中学的二次函数一模一样)以及克服看到一大坨数学公式时的畏难情绪

D题的思路很不错,也是容易想错的题,主要是容易往基尔霍夫矩阵等复杂算法考虑,却解决不了。能深入理解Kruskal这一个算法,比涉猎各种复杂的图论算法(如基尔霍夫矩阵等)有意义得多。

E题后来immortalCO给我讲了一个更简单的做法:按照我之前的想法拆链之后,不用可持久化线段树前缀和来查询,而是对每个节点维护子树的 $c$ 数组以及对应的排序列表,用平衡树启发式合并来维护。这样虽然时间也是 $O(n\log^2n)$ 的,但空间是 $O(n)$ 的,不需要强行优化内存常数。想想我去年做一道Codechef的启发式合并题想了好几天才想到正解。可见我还需要加强数据结构的灵活变通能力。

F题的收获是学习了一个新的算法ALCS,这个算法思想是很不错的,利用特殊的单调性来改变状态设计。希望能找到这类问题的更多应用。

一些可能可以使UOJ #289改成真正的提交答案题的方法

2017-03-01 22:03:46 By WrongAnswer

以下是本人的一些脑洞,不喜勿喷。

UOJ #289(【WC2017】排序)是一道提交答案题,然而在UOJ上却以传统题的形式出现。这看起来十分不和谐,违背了UOJ(Universal Online Judge)的“Universal”特点。况且改成传统题以后做题也十分不方便,比如本人第1个测试点写的是 $O(n^2K)$ 的程序,尽管可以跑出来但无法在 $2\texttt{s}$ 内跑出来,于是虽然考场上可以通过,却无法在UOJ上提交通过。

之前本人联系过管理员jiry_2将这题改为提交答案题,得到的答复是:不太行,上传的文件太大了。然而仅仅因为输出文件太大就可以让这题“变味”吗?显然不行!

于是,我有以下几种想法:

1、压缩提交文件大小

这题一共 $\sum T=100$ 组数据,每组数据输出的比较器可以达到 $num=10^6$ 个,这意味着需要输出 $10^8$ 个三元组 $(u,v,t)$。

由于 $1\le u < v\le n\le 10^5$,$1\le t\le 150$,所以本质不同的比较器约有 $7.5\times 10^{11}$ 种,而 $2^{40} > 10^{12}$,意味着存储一个比较器需要用大约 $40$ 个bit。如果要存 $10^8$ 个这样的三元组,那么就需要 $4\times 10^9$ 个bit,约 $500\texttt{MB}$。

这个数据文件实在太大了,能不能压缩?

注意到 $t\le 150$,可以对每一个 $t$ 存这一层所有的 $(u,v)$ 二元组。另外,这些二元组是顺序无关的,可以将所有的二元组按 $u$ 排序,然后存相邻两个 $u$ 的距离。考虑一种比较坏的情况:每层都有 $10^6/150$ 个二元组,相邻的 $u$ 距离相等,这个距离约是 $15$。考虑用这种方法表示一个数:先输出 $t$ 个 $1$,然后输出一个 $0$,最后输出一个 $4t$ 位整数。如果按平均 $t=2$ 来估计,由于同时也要存所有的 $v$,那么输出一个二元组平均需要 $11+17=28$ 个bit,这样总共文件大小就是 $2.8\times 10^9$ 个bit,约 $350\texttt{MB}$。

遗憾的是输出文件似乎仍然很大。并不知道能否用一些数据压缩算法来进一步减小数据大小。不过看起来不太可行……(也许jiry_2有更好的办法?)

2、在本机上进行评测

那么,是不是可以参考现场的评测方法呢?

考试现场是在本机上测试的。实际上,选手在做题的时候就已经知道了得分。

因此可以用一种方法:在本机上测试完之后,将得分提交到UOJ。不过直接提交得分是有问题的,因为选手可以直接改这个得分,如果选手并没有通过这题,但通过直接修改得分而制造了满分的假象,就很不公平了。

我们设计一个程序 $P$,$P$ 接受用户的输入文件,计算出各测试点的得分情况 $S$,然后输出 $O=f(S)$,其中 $f$ 是一个加密函数。提交到UOJ之后,将提交的文件 $O$ 进行解密,得到 $S=f^{-1}(O)$。如果加密函数 $f$ 设计得足够好,在不知道 $f$ 函数的情况下,提交文件 $O$,解密出的 $S=f^{-1}(O)$ 相当于一个随机数,能够通过测试的可能性几乎为 $0$。

这样得到的结果可能是所有人提交的文件都相同,就像UOJ #200一样。其实这并没有什么关系……

Q:如果选手用其他人的提交文件然后直接AC了,怎么办?

A:可以将题目设置为AC以后才能查看代码,如UOJ #259。另外即使不这么做也没关系,可以使加密文件大小超过 $500\texttt{B}$,由于UOJ只能查看提交的前 $500\texttt{B}$ 文件,使用其他人的提交文件也不管用了。

另外此做法可能还是有一些漏洞,欢迎提出。

UPD:目前还有一个待解决的问题:如何防止反编译程序破解加密器。这个问题本人暂时还没想到如何解决,欢迎提供建议。

清华集训2016订正记录(待更新)

2017-02-24 11:32:11 By WrongAnswer

UOJ上终于有了清华集训2016的题,喜闻乐见。于是乎,本人开始考后订正了。

这里是本人参加清华集训2016留下的各种遗憾:http://wronganswer.blog.uoj.ac/blog/2161


Day 1

T1:Alice和Bob又在玩游戏

http://uoj.ac/problem/266

考场情况

这题我的考场情况是这样的:

一眼作业题,我会 $O(n^2)$,很快码完60分。然后不是很会,之后思考的时候通过打表找规律,但没有发现任何有意义的性质,研究了几种构造性的方法但都是错误的。花费1h以上,没做出来。

怎么办?回到原来的式子,强行用个数据结构维护每个子树的所有转移?这样看来就是个Trie树合并?好像会做了。

写了1h,最后10min写完,连样例都没过,没时间调。

最后得分:60。就是开场提交的暴力分。

考后分析

这种博弈论问题属于我最经常掉坑的各类问题之一。显然可以想到一种基于Sprague-Grundy定理的暴力算法:用 $T_v$ 表示以 $v$ 为根的子树,记 $g(v)$ 为 $T_v$ 的Grundy值,转移时枚举选择的点 $x$,设 $T_v$ 中与 $x$ 到 $v$ 的路径相邻的点集为 $S_{v,x}$,那么选择 $x$ 转移到的状态Grundy值为 $\bigoplus_{u\in S_{v,x}}g(u)$。从而 $T_v$ 的所有操作转移到的状态的Grundy值集合 $G_v$ 为

$$G_v=\{\bigoplus_{u\in S_{v,x}}g(u)\lvert x\in T_v\}$$

可得 $g(v)=\mathrm{mex}G_v$。设根节点集合为 $R$,那么先手必胜当且仅当 $\bigoplus_{v\in R}g(v)>0$。关键在于如何快速计算所有的 $g(v)$。

这个问题直接做就行了。用 $C_v$ 表示 $v$ 的子节点集合,设 $x_v=\bigoplus_{u\in C_v}g(u)$。如果选择的点 $x=v$,那么转移到的状态Grundy值为 $x_v$。如果选择的点 $x\ne v$,那么 $x$ 就在以某个 $u\in C_v$ 为根的子树内。枚举这个 $u$,那么对于一个 $x\in C_u$,$x$ 到 $v$ 的路径分成 $x$ 到 $u$ 一段以及 $v$ 单点这两部分。和 $x$ 到 $u$ 这段路径相邻的点集 $S_{u,x}$ 的Grundy值为 $\bigoplus_{y\in S_{u,x}}g(y)$,和 $v$ 相邻的点集的Grundy值为 $x_v\oplus g(u)$,因此

$$G_v=\{x_v\}\cup\bigcup_{u\in C_v}\{\left(\bigoplus_{y\in S_{u,x}}g(y)\right)\oplus x_v\oplus g(u)\lvert x\in C_u\}=\{x_v\}\cup\bigcup_{u\in C_v}\{g'\oplus x_v\oplus g(u)\lvert g'\in G_u\}$$

同样地 $g(v)=\mathrm{mex}G_v$。暴力求出所有集合 $G_v$ 以得到所有 $g(v)$ 复杂度仍然是 $O(n^2)$ 的,可以用数据结构来维护集合。这里的操作是,对每个 $v$ 将所有子节点 $u\in C_v$ 的 $G_u$ 集合中所有数异或上一个数 $x_v\oplus g(u)$,然后求出这些集合的并,再加入一个数 $x_v$。把每个 $G_v$ 建成一个二进制Trie树,整体异或可以用标记实现,查询 $g(v)=\mathrm{mex}G_v$ 可以在树上二分以 $O(\log n)$ 的时间求出。合并集合时,用Trie树合并可以在 $O(n\log n)$ 的时间内完成所有合并。

这样总复杂度就是 $O(Tn\log n)$,得分100。代码实现并不复杂,主要在于要想清楚,注重思维。

总结

这题的得分情况是:现场大多数人AC了这道题,少数(不足20个)没有AC这题的人也有大多数是因为正解写挂导致的。我没能做出此题可以说是很不应该的。可以看出我平时有一大思维误区:做博弈论题不管三七二十一先打个表再说。对于这种没有太多性质、直接用数据结构就能维护的问题,打表并没有什么卵用,反而浪费了太多时间,用朴素的想法去考虑是必不可少的。

阅读更多……

WC2017 暴力之战

2017-02-08 21:15:04 By WrongAnswer

由于我太狭隘了并不知道别的东西有哪些值得写,我就讲下自己这次参加WC比赛的状态吧。

考前几天刷了一波题:http://wronganswer.blog.uoj.ac/blog/2314 ,尽管改变不了我是无实力选手的事实。


8:35,终于开考了。

首先开场的时候看了下三道题。第一题看起来是个要推性质的题,我这种辣鸡水平就别想做出来了。第二题是个卡常数题,感觉很丧病。第三题是个构造类提交答案题,不太确定自己能搞多少分。

于是开场看第1题,发现有 10 分 $n\le 8$,开个 $8^7$ 的数组暴力 DFS 就过了,再看下面 $m=n-1$ 有 10 分,树上以 $0$ 为起点的路径只有 $n$ 条,DFS 枚举路径然后更新答案。后面还有 20 分 $m=n$,基环外向树,那么路径肯定是从起点往环上走,绕几圈,再往下走到终点,那么把起点和终点都移到根,去掉 $0$,看下环是不是循环同构的。

这样分三个 namespace 写就有 $40$ 分了,写完以后把树和暴力拍,过了,很开心,然后把基环外向树和暴力拍,WA 了,调了好久发现我只判了环是循环同构的,没判剩下树的部分相同,改完就过了。

接着再想有没别的部分分拿,想想网格图感觉就是个八数码,这不是 NP-Hard 的?又想了想每条边最多属于一个环的,发现两个环相接的不会处理,就放弃了。

这样第1题正常情况下就有 $40$ 了,接着看第2题。

第2题是个三合一,第一个Subtask是把 $n$ 个小于 $2^{32}$ 的非负整数排序,我会Radix Sort,不知效率如何。然后我就用链表写了个Radix Sort,写的时候发现指针数组 next 和存答案的数组 b 开了以后就爆内存了,就把输出答案的函数拷到了主程序里面一边遍历一边输出。写完过了测试点1,运行下测试点2,结果……

跑了10+s。

怎么办?我想一定是数组访问不连续导致这么慢。那就在Radix Sort之前先求出每个radix的出现次数,然后开一个连续的数组,算出每个radix对应的区间实现类似不定长数组来替代链表,改完以后WA了。调了好久才发现我原本是倒着 for,改写法以后要正着 for。这样测试点2跑进2s,测试点3……跑不过去。

觉得自己很没救就看子任务2,看起来像卷积,想FFT发现不会处理区间询问,如果再怎么处理一下复杂度就炸。这个点做法应该是压位?于是写了很久的压位,还调了很久,终于调出各种诸如 <<>> 打反之类的错误,终于过了测试点4,却过不了测试点5。想加优化,结果不管怎么优化都要跑十几秒。暴力分即视感。

感觉我真是逗比得不行,明明分没多,我干嘛去写细节巨狗的压位啊= =b

阅读更多……

WC前的刷题记录

2017-02-03 20:53:53 By WrongAnswer

就要WC了,然而我还是一堆简单题不会做。人弱就要多刷题,于是就刷了一些我觉得很难的题。

如果大家发现有什么问题欢迎提出。


目录

  • 1、Codeforces 717A
  • 2、TCO2014 Round 3B Div1 1000
  • 3、Codeforces 722E
  • 4、Codeforces 713D
  • 5、Codeforces 762F
  • 6、UOJ #54
  • 7、Codeforces 715C
  • 8、LYDSY 3451
  • 9、UOJ #59

1、Codeforces 717A

给定整数 $k,l,r$,设 $T$ 为所有长度在 $[l,r]$ 间且不存在相邻两个0的01串的集合,求从 $T$ 中取出恰好 $k$ 个长度相同的串的方案数除以 $1,000,000,007$ 的余数。$1\le k\le 200,1\le l\le r\le 10^{18}$。

http://codeforces.com/problemset/problem/717/A

这场比赛我参加过,然后挂了……主要就是一开始想了很久的这一题,一直以为是矩阵快速幂,结果想了很久没能把矩阵构造出来。最后只好放弃了这题。

后来看了题解才发现这题做法好神。

首先,记 $f_i$ 为长度等于 $i$ 且不存在相邻两个0的01串个数,显然 $f_0=1,f_1=2$。考虑一个长度等于 $i$ 的01串,如果第 $i$ 位是1,那么只需前 $i-1$ 位不存在两个相邻的0即可,有 $f_{i-1}$ 种,如果第 $i$ 位是0,那么第 $i-1$ 位是1,有 $f_{i-2}$ 种,即

$$f_i=f_{i-1}+f_{i-2}$$

不难发现这就是一个Fibonacci数列,如果记 $F_i=\begin{cases}i,&i < 2,\\F_{i-1}+F_{i-2},&i\ge 2\end{cases}$,那么 $f_i=F_{i+2}$,于是答案等于

$$\sum_{i=l}^rC_{f_i}^k=\sum_{i=l}^rC_{F_{i+2}}^k$$

用经典的计数方法,记 $S_n=\sum_{i=0}^{n-1}C_{F_i}^k$,则答案为 $S_{r+3}-S_{l+2}$。

前面的这些转化都很简单,问题来了,如何计算 $S_i$?

阅读更多……

为什么开O2比不开O2慢?

2017-01-31 12:12:58 By WrongAnswer

WC滚粗前的倒数第二帖

UOJ#103先求后缀数组,预处理height数组的Sparse Table,然后用Manacher找出每一个回文串在后缀数组中二分,结果TLE了。

http://uoj.ac/submission/124418

(后来改成在单调栈上二分过了 http://uoj.ac/submission/124428

本机上构造了一组数据 $s=\mathrm{abacabadabacaba...}$($|s|=300000$),跑不到 $1\texttt{s}$ 就跑出来了。在UOJ自定义测试里面运行了 $1\sim 1.1\texttt{s}$。

感觉很奇怪,难道是O2变慢了?

于是本机开了O2,也要跑 $1.1\sim 1.2\texttt{s}$。UOJ自定义测试里面加上 __attribute__((optimize("-O0"))) 以后,也只要 $0.7\sim 0.9\texttt{s}$ 了。

加上 __attribute__((optimize("-O0"))) 以后卡过去了,而且还不一定能卡过去。

http://uoj.ac/submission/124462

另外UOJ#201的题面 $v_4$ 应该改成 $v_3$

记一次冒险的举动

2017-01-26 18:39:35 By WrongAnswer

今天是Goodbye Bingshen。

好久没打UOJ比赛了,于是就来打了一次。

一开场看到第1题,感觉我以前思考过这个问题,于是推了个很简单的结论:如果 $n < 4$,答案是 $1$,否则是 $-1$。交上去以后重新想了下发现证明有问题,但重新证明以后发现结论是对的。

接着看第2题,构造题,继续猜结论,每个点和 $n$ 连边,自己试到 $n \le 9$ 好像都没有反例。也就这么交了。

交完以后重新想了下,发现如果 $n$ 大一点,答案是 $2n-3$,如果先构一条 $5$ 点的链,在中点往下构一个这种树,答案是 $3n-13$。卧槽。

于是就想枚举一下树的深度,然后先构最长链,再递归下去构造。用一个类似记忆化搜索的东西求了下发现最优解深度不超过 $70$,于是就 $10000\times 70^2$ 做完了。

看了下第三题,感觉暴力做法就是对于每个询问 $(s,t)$ 将 $s$ 子树的每个点对应一个平面点 $(w_i,d_i)$($d_i$ 为 $i$ 在树中的深度)然后记 $f(x)=\min\{d_i|w_i\ge x\}$,$s$ 到 $t$ 的最大点权为 $w_\max$,答案就是 $\sum_{x=1}^{w_\max}f(x)+d_t-d_s$。这个好像可以维护一下单调栈之类的东西,然后算一下面积?不过这只是单次询问的。多次询问就把这个东西启发式合并一下……?

Splay启发式合并,应该是 $O(n\log^2n)$ 的?(反正我只会证明是 $O(n\log^2n)$)时限 $2\texttt{s}$?看起来可以过,写一写。

UPD:后来immortalCO告诉我复杂度其实是 $O(n\log n)$

于是就开始码Splay……码了一会儿有点虚犹豫要不要码下去,于是看了后两题。

第4题好神啊,似乎不太可做,先不管了。第5题……居然是个交互式证明,要理解源代码,看了下源代码巨长无比,不太容易理解,也先不管了。

后两题都不太可A,好像还是搞第3题比较有救?

于是继续码Splay。写完基本操作以后开始维护每个点到上一个点的类似面积的东西。代码写得很长,而且自己看着都觉得常数大有点要TLE的样子。

子任务制啊,要是挂了岂不是只有暴力分了?惨!

不过既然已经写了那我就把它写完吧。写完维护面积和、树上二分、插入节点以及删除左侧不在单调栈上的节点,最后写完查询,代码已经差不多4KB了。

然后,测一下样例1,RE了……实现逻辑出了不少问题,改了一会儿输出了6……原来我忘了加上 $d_t-d_s$ 了。加上以后过了样例1,再测样例2,发现输出的顺序是乱的,才发现忘了离线询问顺序输出答案。加了个存答案的数组就搞定了。

感觉应该差不多了。交一发。

然后。

阅读更多……

做TopCoder题的一些总结

2017-01-25 10:17:36 By WrongAnswer

集训队第一次作业结束了。作业是TopCoder的156题(我完成了154题,理论上8分完成分我可以得到7.8分)。虽然我在提交的时候出了各种问题,感觉作业分会爆炸。然而我并不想退役QAQ

以下是我做TopCoder的一些总结。


1、题目形式

TopCoder和大多数OJ的题不太一样,大多数OJ都是使用用标准输入输出,而TopCoder只需实现一个关键的类(class)中的一个函数即可。函数传入的参数和返回值取代了标准输入输出。

TC的输入输出规模比较小,大多数题的数据范围都在 $50$ 以内,这是因为太大的数据点超出了Arena的容纳范围。事实上数据范围只有 $50$ 的题仍然颇有难度,这一点在之后会提到。

大多数的题目和日常做的OI题还是很类似的,但侧重点不一样。TC的组合计数以及组合优化类问题比较多,大多数题的主要难点在于思维上(当然也不乏代码题),很多题都是“暴力是指数级复杂度,难点在于想出一个多项式算法”,例如SRM 577的500,只要想到DP状态如何设计,很高的复杂度都能通过。当然也有一些 $O(n^3)$ 卡 $O(n^4)$ 之类的题,通常需要用特殊的方式进行输入(如输入字符串解密数字,输入随机数种子递推出随机数)。

2、解题遇到的困难

TC题比较难(当然是对我而言,对于C_SUNSHINE、matthew99、immortalCO等神犇来说应该是比较容易的?),我在做的时候遇到了不少的困难。

有一类问题,一开始看到的时候毫无思路,经过长时间多种方向的尝试最后才解决。

SRM 562的1000是一道有结论的树形DP问题,这题我研究了很久,终于推出了两种不同情况下的结论。其中一种情况是:$2k > n$ 时,排列 $p_0,p_1,...,p_{n-1}$ 合法当且仅当:①$p_{n-k},p_{n-k+1},...,p_{k-1}$ 这 $2k-n$ 个点构成一个连通块;②将该连通块删掉后,如果 $p_i,p_j$ 位于同一连通块,那么或者 $i,j < n-k$,或者 $i,j\ge k$;③对任意 $i < n-k$,$p_i,p_{i+1},...,p_{n-k-1}$ 构成连通块,以及对任意 $i\ge k$,$p_k,p_{k+1},...,p_{i-1}$ 构成连通块。想到这个结论以后我开始尝试用树形DP求出有多少个连通块大小恰为 $2k-n$,用树形背包的经典算法容易把满足③的排列个数也算进来,但是,对于每种选连通块的方案,贡献为满足②的把点分成 $i < n-k$ 和 $i\ge k$ 两类的方案数,这个我并不会统计。绕了不少弯路才发现其实是不从“对每个 $[n-k,k)$ 求有多少个 $[0,n-k)$ 和 $[k,n)$ 以及它们的排列方案数”考虑而是从“对每个 $[0,n-k)$、$[n-k,k)$、$[k,n)$ 求有多少个排列方案数”,也就是DP时把位于中间和位于两边的点数都计入状态。这样问题就得以解决了。事实证明这样的求和的问题转化思路是相当有趣的,以后可以出这类的题。

阅读更多……

失败的FJWC2017&FJOI2017

2017-01-19 19:21:56 By WrongAnswer

高二第二次参加省冬令营以及省选。退役前的倒数第二次冬令营。

并不希望得到多么好的成绩,只希望不要挂得太惨。

然而很遗憾,我挂惨了。


1月18日

报到。由于是外地生,和Paladin100100住进了宾馆。宾馆的质量不想吐槽。

晚上刷TC。一个晚上才刚出一道SRM 594的550网络流,1000想了个DP感觉可以优化然而没做出来,SRM 595的900调细节调了好久没调出来。我好菜啊。


1月19日

省冬第一天。

上午讲了一些偏基础的图论建模技巧,包括网络流建模技巧。有几道题还是蛮有趣的。

中午吃完饭发现手机屏幕又坏了,不明原因。有点郁闷。

下午训练。只有三个小时,手速赛差评。

第一题:给定 $h\times w$ 的矩阵,常数 $m$ 以及 $n$ 个子矩形,每个子矩形可以用 $x_1,y_1,x_2,y_2,v$ 描述,表示从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的子矩形最大值为 $v$。问有多少个矩阵满足每个数都是 $1$ 到 $m$ 的整数,且满足子矩形要求。$h,w,m\le 10^4$,$n\le 10$,$1\le x_1\le x_2\le h$,$1\le y_1\le y_2\le w$,$v\le m$。

看到 $n\le 10$ 想了想就是个容斥裸题。花了十几分钟写了个离散化+容斥过了样例就不管了。

第二题:题意比较复杂,简单的说就是给定有向图 $G=(V,E)$ 和 $s\in V$,求所有点对 $(u,v)$ 满足存在两条点不相交的路径 $s\rightarrow u$ 和 $s\rightarrow v$。$|V|\le 10^3$,$|E|\le 10^4$。

理解了很久的题意,感觉是支配树?因为如果 $s$ 到 $u,v$ 有同一个必经点就挂了,否则……好像都能构造出两条路径……可是我不会写支配树QAQ

第三题:给定字符串 $s$ 和常数 $K$,支持两种操作,一种是给定 $l,r,c$,对所有 $l\le i\le r$ 修改 $s_i$ 为 $c$,另一种是给定 $l,r$,求有多少对 $l\le l'\le r'\le r$ 且 $r'-l'+1 \le K$ 使得 $s[l..r]$ 是回文串。

看起来挺可做的啊……我来推一下。如果建个线段树,那么信息怎么合并?好像合并是 $O(K)$ 的于是单次 $O(K\log|s|)$ 不是很优秀啊。不太会。那就分块试试?以 $B>50$ 为块大小,记录下块内和块间的长度不超过 $K$ 的回文串个数,修改和查询时枚举整个的块,不满的用 manacher 暴力统计即可,就可以做到修改和查询复杂度均为 $O(B+\frac{|s|}{B}+K)$ 了?然而细节很多的样子……先是推导过程已经让我挺烦的,然后觉得这题如果不做出来应该没什么救,就刚了2个小时……写完分块准备敲 manacher 发现并不熟练QAQ

决定回去做第二题。数据规模这么小,能否不写支配树?那就是枚举两个点,把非源的必经点集合求个交,如果为空说明可行。$O(|V||E|+\frac{|V|^3}{w})$ 不知道能不能A。

第三题写了个暴力,分块写完 manacher 还没写,发现似乎有问题,然而没剩多少时间了,决定交暴力。

感觉今天正常应该有100+100+20=220吧?

出了考场,突然意识到一个问题——我离散化没检查,似乎写错了!样例里面的相邻矩形边界相差都是 $1$,发现不了这个问题!!

卧槽!!!

阅读更多……

关于UOJ#219的时限 & UOJ#264的样例

2016-12-16 16:57:50 By WrongAnswer

无聊在UOJ上乱逛发现两个问题

UOJ#219

http://uoj.ac/problem/219

这题时限是1.5s

然而我测了一下,怀疑时限是1s

http://uoj.ac/submission/114145 卡时1.3~1.7s,全部TLE

http://uoj.ac/submission/114147 卡时0.8~1.2s,部分测试点TLE,且没有TLE的点运行时间都在1s内

UOJ#264

http://uoj.ac/problem/264

这题原题第3个样例第一行有一个空行

并且样例说明里也说了第一行需要输出一个空行

但是UOJ上样例并没有空行

http://uoj.ac/submission/114149 另外经过测试,不输出空行也是对的

共 37 篇博客