分类: [OI生涯]

[WC2018]即时战略

题目大意 这是一道非常有趣的题,也是我第一次在现场遇到的交互题。 给定一棵树(选手并不知道),一开始只有1号点是已知的。交互库中提供了一个函数explore(x,y),给这个函数一个已知节点x和(未知)节点y(x!=y),它会返回x到y的链上的第二个点,如果返回的点未知,可以让它变为已知。 要求调用<=T次explore函数,使得树上所有点都变为已知节点。 具体看题目链接 Windows的同学建议看LOJ的题面 Solution 赛场上,我只会写暴力,好像连一条链的都写挂了,然后成功拿到25分的好成绩(大众分70),然后离Ag线差了一分(此处应 ......

证明伸展树与动态树的时间复杂度

Splay时间复杂度证明 定理0 若x=y+z+1,那么$2\lg(x)-\lg(y)-\lg(z)\geq 2$ 证明. $2\lg(x)-\lg(y)-\lg(z)$ $=\lg((y+z+1)^2)-\lg(y)-\lg(z)$ $=\lg(\frac{(y+z+1)^2}{yz})$ $=\lg(\frac{2yz}{yz}+\frac{y^2+z^2+1+2y+2z}{yz})$ $\geq \lg(2+\frac{y}{z}+\frac{z}{y})$ $\geq \lg(2+2)$ $=2$ 定理1 在一棵n个节点的Splay中,对一个节点进行splay操作的时间复杂度为均摊复杂度为$O(\log n)$ 证明. 设size(x)表示节点x的子树大小。势能分析,设节点的势能$r(x)=\lg(size(x))$。 对于Zig-Zig或Zag-Zag的情况,势能的增量为 $r'(x)+r ......

[BZOJ4811]由乃的OJ

题目大意 给你一个有n个点的树,每个点的包括一个位运算opt和一个权值x,位运算有&,l,^三种,分别用1,2,3表示。 有修改和询问两种共m次操作。 每次询问包含三个数x,y,z,初始选定一个数v。然后v依次经过从x到y的所有节点,每经过一个点i,v就变成v opti xi,所以他想问你,最后到y时,希望得到的值尽可能大,求最大值?给定的初始值v必须是在[0,z]之间。 每次修改包含三个数x,y,z,意思是把x点的操作修改为y,数值改为z。 $k<=64$ $x,y,z<2^k$ Solution 其实就是在树上的带修的多次询问的起床困难综合症。 那道题的方法 ......

浅谈快速傅里叶变换

本人太菜了,不是很懂这个东西,只是有点懂了快速傅里叶变换的一种方法,本文没有代码,只是证明了这种快速傅里叶变换的方法是正确的。 本文大量使用复数,i表示$\sqrt{-1}$。 多项式乘法 快速傅里叶变换用于快速解决多项式乘法的问题。即 设$A(x)=\displaystyle\sum_{j=0}^{n-1}a_jx^j$ $B(x)=\displaystyle\sum_{j=0}^{m-1}b_jx^j$ 令$C(x)=A(x)\times B(x)$ 则C(x)可表示为: $\displaystyle\sum_{j=0}^{n+m-2}c_jx^j$ 我们要解决的问题是已知a数组和b数组,求c数组。 举个例子:有多项式$A(x)=6x^3+7x^2-10x+9,B(x)=-2x^3+4x-5 ......

【入门难度】时间复杂度符号的辨析

符号的辨析 Ο,读音:big-oh;表示渐进上界,小于等于。 ο,读音:small-oh;表示上界,小于。 Ω,读音:big omega、欧米伽;表示渐进下界,大于等于。 ω,读音:small omega;表示下界,大于。 Θ,读音:theta、西塔;既是上界也是下界,称为确界,等于。 Ο是渐进上界,Ω是渐进下界。Θ需同时满足大Ο和Ω,故称为确界。Ο极其有用,因为它表示了最差性能。 对于一个算法来说,我们常常需要计算其复杂度来决定我们是否选择使用该算法。 对于一个算法,假设其问题的输入大小为n,那么我们可以用 O(n) 来表示其算法复杂度(time comple ......

luoOJ1898 运动会(Race)题解

[题目传送门][1] 我看到题一脸懵逼,感觉一点思路都没有,然后想了6个小时,搞出来了一个很复杂的一堆前缀和的做法,然后错了。最后我发现其实不需要这么复杂,这题其实是一道水题,我们可以进行一些简单的分析来A了它。 由于每天各个人的分数是异或产生的,很容易想到搞一棵字典树。我又发现对于每一个人,它既要取模又要异或,肯定不会一起来算,因此可以把每一个人的得分分开来考虑。 然后我发现,在字典树中对于每一条通向某人A得分的路径上每一层的另外一棵子树中的人总是一起出现在A排名的前面或者后面,而且前 ......

傻逼的世界题目+题解

一道我自己出的水题,题目描述: 要求支持两种操作:对一个三维区间上的数都加上一个数,或者询问一个三维区间上所有数的和,三维区间的三个坐标都是整数且范围在[1,100],询问10000个。 写个三维树状数组就AC了,是不是很简单。数据: sbworld 标程: var c1,c2,c3,c4,c5,c6,c7,c8:array[1..105,1..105,1..105]of int64; num,x1,y1,z1,x2,y2,z2,n,m,p:longint; v,s1,s2:int64; function lowbit(x:longint):longint; begin exit(x and(-x)); end; procedure add(x,y,z:longint;v:i ......

HNOI2008GT考试题解

我们先简化一下问题,比如我们把字符集变成3,可以先来看下长度为3,字符串为10的答案。我们可以想到构一棵决策树,叶节点就是所有的方案,如果一个树上一个节点到根的路径上构成的字符串中有一个子串匹配就把这个点涂黑。如图是这个例子的决策树: 我们用一个补集思想,考虑对于每一个子树中叶节点被染黑的个数,我们发现其只跟前面至多有多少个字符连成的字符串是原串前缀以及树的高度有关,因此我们可以定义动态规划的状态f[i][j]表示高度为i,前面至多有j个字符连成的字符串是原串前缀的子树中被染黑的叶节点的个数。然后我们 ......

BZOJ3670(NOI2014)动物园题解

题目传送门 一道水题,据说有O(n)做法,我竟然没想到也没看懂。我的做法是KMP后用next数组搞棵树,然后在树上找一个节点前面最后一个符合条件的节点,一种方法是发现这玩意有单调性,然后用一个point数组记录下其父亲的决策点,再拿个ST表倍增或者Tarjan+二分,也可以利用轻重链搞一搞就可以了。这里用了轻重链。这种方法我只能证明有O(n^2lgn)的上界,但平均效率很高。 #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cstring&gt; using namespace std; ......

BZOJ5250: [2018多省省队联测]秘密袭击

原题链接 Solution 先看一份官方题解:秘密袭击simple 然而作为一个连FFT都不会的蒟蒻,又怎么可能在只有五小时,写完前两题的情况下做出这题呢? 所以是时候用暴力吊标算了。 考虑枚举每个点,算出这个点作为第k大时对答案的贡献。如果直接算,可能会算重。 我们可以定义:u的权值大于v当且仅当d[u]>d[v]||(d[u]==d[v]&&u>v),记为$u\rhd v$,即d相同时比较两点的编号。 如果枚举一个点u作为第k大点,那么可以从u开始进行树形DP。 设f[u][k]表示以u为根的子树,选了点u,并且选出的联通块中有k个点权值大于根。 有个 ......