出题互测测试数据alpha

1、Solution福州一中 卓亮March 24, 2012警告：这只是初步版本，并非提交的最终版本！如果有错误，欢迎指出！1x命题背景1.1本题是本人在做一道数学题时想出的。一开始打算写一个程序来打表找规律，后来灵机一动，弄出了一个重要的等式。虽然那道数学题没有完整解出来，但是编一道有意思的题目。可以利用这个等式1.2算法分析第一问十分简单。间复杂度是O(log n)直接利用题目所给的数列定义式，就可以求出xn的值了。这一问的时再看第二问，容易发现，如果解决了第三问，那么第二问也解决了。因而先尝试解决第三问。用Sn表示数列xn的前n项和。考虑S4n(n 1)。根据x2k = xk, x2k1

2、= (1)k+1xk(k 1)，4nXS4n=xii=12n2nXX=x+x2i12ii=1i=12n2nXXi+1=(1)x xiii=1i=12nXi+1=(1)x x )iii=1nX2x=2ii=1Xn= 2xii=1= 2Sn(1)由式(1)，立即得到一个快速求Sn的做法：若4 - n，那么Sn = Sn1 + xn；否则，Sn =2Sn。这个算法的时间复杂度由下式给出：T (n) = T (n/4)+O(log n)，解得T (n) = O(log2 n)。1注意到这个算法有系数3，即每次除以4，最多要3轮。意到还可以对此进行一些优化。注2n+2x4n+1 + x4n+2 = (1

3、)x2n+1 x2n+1 = 0S4n+2 = S4n + x4n+1 + x4n+2 = S4n(2)可以得到(3)这样，在每一次除以4的时候最多只要算1次xn，就消除了系数3。有了第三问，第二问显然也可以做到O(log2 n)。不过有更优的算法。首先，可以用数学归纳法证明，Sn 0。因而，只需要找出哪些位置是0。容易看出，S2n1 6= 0。这是因为，数列xn只含数字1和-1。由于Si+1 = Si + xi+1，因此Si+1与Si奇偶性不同。而S1 = 1为奇数，S2n1与S1奇偶性相同，因而也为奇数。而0是偶数，故而S2n1 6= 0。根据式(1)(3)，以及S2 = 0, S4 6=

4、 0，可以看出Sn = 0当且仅当n的4进制表示仅含0和2。这样第二问就做到了O(log n)。1.3数据设置本题先赠送了50分，直接使用暴力即分数。到。对于这3问的掌握情形不同，也可以得到不同的2crisis命题背景范浩强介绍了新的数据结构，我尝试就此出一道题。2.2算法分析可以看到，如果对位于(x, y)的士兵进行了移动操作，那么它新的位置(x0, y0)就满足x0 = x + a, y0 = y + b。如果对它进行了旋转操作，那么x0 = x cos a y sin a, y0 =x sin a + y cos a。如果进行了潜伏，那么x0 = 0, y0 = 0。考虑到这3个命令都是

5、变换，可以尝试用矩阵写出。即 x0 y0 1a1,1 a2,1 a3,1a1,2 a2,2 a3,2a1,3 a2,3 a3,3xy1 = 由此，看出，一开始给的位置并没有在变换中起作用。由于矩阵乘法具有结合律，可以用3 3的矩阵维护信息。来看如果没有撤销和重做，应当如何解决。首先，的命令，相当于把一个区间全部乘一个矩阵。然而，的询问只问一个点的状态。因而，可以考虑采用线段树解决。对每个线段维护，这个线段全部乘了什么矩阵。一开始全部设为单位矩阵。在插入时，如果完整覆盖，那么，要插入的矩阵乘到线段上。否则，就把首先要把这个线段的矩阵下传到两个儿子上。然后把这个线段的矩阵设为单位矩阵，接着分别在至

6、多两个儿子上处理插入操作。询问时，可以自底向上，依次乘经过的线段上的矩阵。如果没有潜伏，也就是说所有矩阵是可逆的。可以构建一棵“版本”树。如果某一时刻a，每个点的状态和另一个时刻b 完全相同，那么它们同属一个点。如果某一个时刻a的状态，经过一次命令，得到另一个时刻b的状态，那么a就向b连一条边。容易看出，一次命令相当于走一个儿子，撤销相当于找若干次父亲，而重做相当于沿着找父亲的路径退回去。而询问就可以挂在当前停留位置上。这样，棵“版本”树了。就能够建立起这一接着对这棵版本树进行深度优先搜索。只有两种可能的情况。入栈，即乘对应的矩阵。出栈，即乘对应矩阵的逆。这样就解决了没有潜伏的情况了。有潜伏的

7、情况，由于不存在逆，势必要记录下每一个历史版本，也就是“版本”树的每个节点的状态。这就是本题的考点，可持久化。可持久化数据结构(Persistent data structure)，可参考1，总是记录下它之前的版本，当它被修改的时候。本题需要对线段树进行可持久化。最朴素的方法是，每一次复制一下整棵线段树。这个方法不太优秀。注意到，修改操作最多只会涉及O(log n)个线段树节点。这就意味着，大部分的节点，是和之前一模一样的。因而，如果一个节点的左子树和之前一模一样，不是把整个左子树复制一遍，而是用一个指针，指向过去的左子树，代表这个节点的左子树与被指的部分完全一样。如果右子树一样，也同理操作。

8、这样，虽然一个线段树中的节点，可能被很多点指向，也就是说有很多父亲，但是一个节点仍然只有两个儿子。而的线段树操作可以自顶向下实现，亦即，不需要找父亲操作。因而这个方法是完全可行的。注意到每次操作最多新建O(log n)的节点，因而这个算法的空间复杂度是O(n + q log n)的。2.3数据设置在前期，基本只出命令操作。在后期，出撤销和重做的机会大大增加。3flare命题背景因为看到一题，是给G0，求G3的点数和边数。于是这题。联想，反过来是否可做呢？于是有了3.2算法分析容易看出，简单变换不改变连通性。因而对不同连通块分别处理。现在单考虑G1是一个连通块的情形。抓取一个G1点，它在G0中是

9、一条边，假设两端点分别为(a, b)。在G1中和它相邻的点，在G0中，要么连着a，要么连着b。根据简单变换的规则，凡是在G0中连着同一个点的，在G1中都有边相连，因而形成一个团。因此，这些点有两个团，外加一些杂边。对于杂边，有一个观察，一个点不能连出两条杂边，否则就会出现重边了。如果取一个补图，就是二分图了。在这些点中随便选一个，让它连着a。在补图中，尝试确定每个点的连向谁。如果不是二分图，说明无解。否则一些点会被确定。图被分为X, Y 两部。接下来看没有被确定的点。分几种情况讨论。|X| = 1, |Y | = 0。即没有点连着b。如果未确定的点数大于等于2，说明所有的点都应该连a。这是根据

10、对杂边的观察。|X| = 1, |Y | 1，或|X| 1, |Y | = 1。即有一部只有1个点，剩下的一部有超过1个点，那么未确定的点应该归大于1个点的那部。|X| 1, |Y | 1。即每部都大于1个点，而且还有未确定的点，就无解。|X| = 1, |Y | = 1。未确定的点大于2个，而且每部都恰有一个点，那么无解。这样未确定的点最多2个。枚举它们属于哪一部。然后采用B号。最后检查是否合法即可。定其余点的标这里说明在抓取点的时候。如果抓取度数最小的点，是没有问题的。如果这个点2m 。的度数是d，容易看出，nd 2m，因而d 如果随意抓取点是否有问题呢？事实上可以用一些不等式来确定范围。

11、希望补图的边尽量多，而原图的边尽量少，因为有两个团，所以边根本少不到哪里去。亦11即 x(x 1) + (d x)(d ，这样，也就是说，度数不能太大。这个观x 1) md2m22察使得求补图的时间复杂度是O(m)的。接下来说明如何BFS。BFS的目的是给每个点一个形如(a, b)的标号，代表G0中对应的边。一开始所有点的标号都是(?, ?)。被抓取的点标号已确定。与被抓取点相邻的点，标号确定了一半，有的是(a, ?)，有的是(b, ?)。每一次，选一个标号已经确定了一半的点(x, ?)。查看是否存在与它相邻的，标号确定了一半的点(y, ?)。如果存在，那么这两个点的标号都应该是(x, y)。与该点相邻的，完全未确定的点(?, ?)，改为(y, ?)。否则，选一个新的数z，将其标为(x, z)。与该点相邻的，完全未确定的点(?, ?)，改为(z, ?)。这样，就能在O(n + m)的时间内确定每个点的标号了。最后说明如何检查合法性。首先，检查是否有重边，自环。接着，检查求得P的G 生成的G