almost 2 years ago

这清华集训打得有点萎,这几天就来更一下题解好了。感想就不写了 代码写的比较惨,就不贴了


Alice和Bob又在玩游戏

关键词:SG函数,Trie的合并

题目描述

个节点,条边(),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。

Alice和Bob轮流操作(Alice先手),每回合选择一个没有被删除的节点,将及其所有祖先全部删除,不能操作的人输。

需要注意的是,树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。
比如: 这样一条链,号点是根节点,删除号点之后,号点还是号点的父节点。
假设Alice和Bob都足够聪明,问Alice有没有必胜策略。

对于的数据,,输入数据保证不会形成环,且每棵树的大小

算法简述

这个题其实今年集训队作业里是有的,只是这里的数据范围大了一些。考虑用SG函数,表示以为根的子树的SG值。 这样直接搞的复杂度是,可以用来维护sg值和求mex操作,合并子树的时候可以用的合并。复杂度


魔法小程序

关键词:高维前缀和

题目描述

有这样一段魔法的程序:(其中所有的数组下标从 开始,所有的除法的结果为整数,且向 取整)

定义数组 a[], b[], c[]
定义函数 魔法(x, y, z):
{
    如果 a 的长度 == z:
        返回 x >= y
    如果 x % a[z] < y % a[z]:
        返回 假
    返回 魔法(x / a[z], y / a[z], z + 1)
}
定义函数 主程序():
{
    读入 a[], b[]
    令 c[] 的长度与 b[] 的长度相同,且 c[] 的每个元素均为 0
    令 变量 i 从 0 循环至 b 的长度 - 1:
        令 变量 j 从 0 循环至 i:
            如果 魔法(i, j, 0):
                c[i] += b[j]
    输出 a[], c[]
}

这个程序目前十分低效(显然时间复杂度至少是平方量级的),无法快速完成百万级别的计算,但我们现在的任务不仅是优化它。

现在我们给出这段程序的输出,你需要完成一个“非确定机”的工作,给出一个可能的输入。

的长度不会超过  的每一个元素不会超过

的长度不会超过 。对  的元素的范围没有直接的保证,但是保证存在一个解 ,使得 的每一个元素的绝对值都不超过

都至少拥有一个元素。

算法简述

这个题第一眼看起来,解应该只有一个,因为可以解个方程算出来。再看一看,发现这个东西和比较像,这其实就是一个高维的前缀和。就可以反过来搞,对每一维分开来求差分,最后就能还原出来了。要注意细节问题。


数据交互

关键词:树链剖分

题目描述

一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据交互时,数据会经过连接这两个服务器的路径上的所有服务器(包括这两个服务器自身)。每个数据交互请求都有一个非负的重要度,越重要的请求显然需要得到越高的优先处理权。此外,如果在某一个时刻存在一条非常重要(可以看作重要度无穷大)、且数据量巨大的交互请求,则所有被该交互经过的服务器都会优先处理这条交互并阻塞,从而导致其他通过这些服务器的交互出现延迟。

现在,你作为一个网络系统的管理员,要监控整个系统的运行状态。系统的运行也很简单,在每一个时刻,只有可能出现下列二种事件中的一种:

  • 在某两个服务器之间出现一条新的数据交互请求;
  • 某个数据交互请求结束。 我们假设这些事件中的交互请求的数据量都足够小。

你的任务是在每一个时刻的事件结束后,求出:如果突然出现一条非常重要、且数据量巨大的交互请求,那么因其造成延迟的数据交互请求的重要度之和最大可能是多少?

算法简述

这个题的idea我感觉还是挺不错的。首先把每个边都拆出点来。每一次添加数据交互请求就相当于给路径上所有边点都减去权值,点点都加上权值。每次要求的答案就相当于这个树的直径。这样就变成了,链修改,求直径的问题,可以套用Qtree7的做法,搞链剖,维护最高点在每一条重链上的最长的路径。这个题稍稍有点繁琐的地方在于,一条路径上的点有两种,点点和边点交替出现,每次修改的时候,边点和点点的加的值正好相反。那么就可以在线段树上多维护一些信息,把起点终点是点点和边点的分开来维护,就可以了。

← 一些题目
 
comments powered by Disqus