第一次参加 \(THU\) 的营,战绩惨不忍睹.
D1
T1
给出 \(d\) , \(n_1\cdots n_d\) , \(l\) , 求
\[\sum_{i_1=0}^{n_1-1} \sum_{2_1=0}^{n_2-1} \cdots \sum_{i_d=0}^{n_d-1} \max (0,(i_1\oplus i_2\oplus \cdots i_d)-l) \]其中 \(d<=10\) , \(n_i<=1e18\) , \(l<=1e9\) .
部分分1
$ d=1 $ 可以直接等差数列求和, 但是抽象输入模数搞得这分骗起来费点劲 , 除的时候要特判(我还开了__int128) , 写法极为抽象,不知道这5分有没有挂.
部分分2
对正解而言比较有用的部分分, \(l=0\) ,也就是说变成了单纯的求抑或和 , 考虑拆位求解.
对于每一位上的 \(i_j\)能贡献多少个1,多少个0,对答案的贡献单独计算即可.
正解
在部分分2的基础上,考虑加入 \(l\) 的限制,不难想到可以把异或和小于 \(l\) 的部分拎出来单独计算,再用整体的贡献减去这一部分.
于是可以把式子变成:
\[\sum_{}^{} ( \mathrm{xor} \{i_1\cdots i_d\} -l) - \sum_{xor<l}^{} (xor-l) \]前一部分沿用刚才的方法就可以求得,后一部分很显然是一个以 \(l\) 为限制的二进制数位DP.
具体地,从 \(l\) 的高位开始逐个填数,考虑当前位是否被 \(l\) 限制,如果不限制就随便填,限制就成对填.因为 \(d\) 较小,可以直接 \(2^d\) 枚举填数.
填数过程中分别统计数量和加和就可以了.
复杂度 \(O(dlogn+2^dlogl )\)
听说可能略微卡常.
T2
给出一个字符串 \(S\) 与正整数 \(k\) ,要求构造一个最短的字符串 \(S'\),满足:
-
\(S\) 是 \(S'\) 的后缀
-
对于任意长度为 \(k\) 的小写字母字符串,都是 \(S'\) 的子序列
\(|S|=1e6\) , \(k=1e5\)
部分分1
这道题十分简单,而且部分分也给出了充分的引导,所以还是从部分分开始思考.
考虑从 \(S\) 向后补全字母.
第一档分给出了 \(k=1\) ,显然,这只需要 \(S'\) 包含所有小写字母就可以了,因此开个桶统计在 \(S\) 中已经出现的字母,把没出现过的补上就可以了.
部分分2
\(k=2\), 可以朴素地保证所有字母都可以分别作为长度为2的子序列的前一个字母和后一个字母就可以了.
因此,首先需要把原来的字符串中不存在的字母补全,保证所有字母都可以作为子序列的开头,然后在后面补上所有小写字母就可以了.
实现上,仍然是开桶统计,不过存在其他情况需要讨论.比如字符串 abcdefghijklmnopqrstuvwxyzaabb,到z的位置,已经满足了26个小写字母的存在,那么后面的aabb是起后一个字母的作用,重新开桶补全后一部分的26个字母即可
同理,就可以得出不需补全的情况:两次开桶之后都填满了26个字母,这时字符串本身已经符合要求.
正解
在 \(k=2\) 的情况的基础上,就可以得到一个构造方式了:
对于原字符串 \(S\) ,开桶从前向后统计26个字母是否存在,一旦桶装满,我们称上次装满桶的位置到这次位置之间"包含一个字符集",同时把桶清空统计下一个"字符集".包含"字符集"的个数 \(k\) 就决定了能容纳 \(k\) 长度的子序列.
因此考虑在原来基础上补全"字符集",先把原串末尾不完整的"字符集"补全,再整个整个地向后补充.
为什么这样构造是正确的呢?
首先证明这样构造能满足限制条件"对于任意长度为 \(k\) 的小写字母字符串,都是 \(S'\) 的子序列":
采用逆证法:
假设对于有 \(k\) 个完整"字符集" 的串 \(S\) ,存在一个长度为 \(k\) 的串 \(T\) ,使得串 \(T\) 不是 \(S\) 的子序列.
考虑在 \(S\) 上从前向后匹配 \(T\) ,由于每个 "字符集" 包含完整26个字母,所以匹配过程中 \(T_i\) 必然可以在 \(S\) 上的第 \(i\) 个"字符集" , \(\Sigma _i\) 上匹配到一位 ,因此到 \(T_k\) 必然已经在 \(\Sigma _k\) 上完成了匹配,矛盾,因此原命题成立.
然后证明这样构造是最优的:
首先 \(S\) 为空串的情况下证明该构造最优:
在\(S\)为空串时,构造出的 \(S'\) 必然是 \(k\) 个"字符集"首尾相接,长度为 \(26k\),
假设存在一个更优的串 \(S''\),长度为 \(26k-1\) .
那么,在最优情况下, \(S''\) 拥有 \(k-1\) 个"字符集" ,且有一个缺少一个字母的不完整"字符集",考虑构造串 \(T\) 使得 \(T\) 恰好在 \(S''\) 的每一个"字符集"上匹配一个字符,并且无法与不完整的"字符集"匹配,此时\(S''\)不符合要求,矛盾,原命题成立
因此,为了构造最优的 \(S'\),一定是尽可能恰好构造出 \(k\) 个"字符集".
在原串基础上,首先使长度为 \(k\) 的串 \(T\) 最多按照上述方式匹配 \(k_0\) 位,考虑增加 \(k-k_0\) 个 "字符集",最优的构造一定是先利用原串后几个字符,补全一个字符集,再首尾链接补充字符集.
复杂度 \(O(|S|+26*k)\)
同时构造出的答案满足长度不大于 \(|S|+26*k-1\) ,可以保证在可接受数据范围内有解.
T3
给一棵树,边是有向边,有一些边确定了方向,另外一些边方向不确定,求一种确定边的方向的方案,使得树上任意一条路径的长度的最大值最小.求这个最小值.
部分分1
\(n<=15\) 直接 \(2^n\) 暴力.
部分分2
链的性质,可以通过讨论解决.
把链拉伸成序列,用 \(\mathrm{L}\) 代表向左的边 \(\mathrm{R}\) 代表向右的边,那么分开路径与路径的一定是形如 \(\mathrm{\cdots L R \cdots }\) 或 \(\mathrm{\cdots RL \cdots }\) ,在原序列上找到这些分界点,对于分界点直接不确定方向的边,尽可能一左一右地分布.
那末,如果形如 \(\mathrm{ L --R }\) 或 \(\mathrm{ L - L }\) 的情况,完全可以保证不确定方向的边独自成为一条路径,同时不对于左右造成贡献.但是形如 \(\mathrm{ L -R }\) 或 \(\mathrm{ L -- L }\) 的情况,需要存在一个边,对于其他路径有贡献,简单的讨论不宜解决.考虑在外层二分答案,贪心地在不超过答案限制下调整这条边的方向,如果还是超出了限制就说明答案不合法.
正解
我太菜了我不会.等我研究研究
T4
真正的工程题
提交答案题.给出10份伪代码,其中的命令包括:
-
\(\mathrm{input(a[x])}\) ,输入
-
\(\mathrm{a[x]=a[y]+a[z]}\),加法运算,\(x,y,z\) 可以重复
-
\(\mathrm{a[x]=a[y]}\),赋值
-
\(\mathrm{output(a[x])}\),输出
定义时间复杂度 \(T\) 为加法执行的次数,空间复杂度 \(M\) 为所有不同的使用 \(a[x]\) 的下标的个数
要求优化这些伪代码,使之时空复杂度降低至给定需求.
sub1-sub3
给出的伪代码实现的是乘法,实现方式是一个一个加.空间复杂度不限制,时间复杂度限制在 \(\mathrm{log}\) 量级.
改成龟速乘,每个点可以获得5-7分不等.
但是龟速乘不是很优秀,因为时间复杂度为 \(logn+popcount(n)\) ,也就是说二进制位上的每一个 \(1\) 都会增加常数,同时提供给我们的巨大空间并没有用上,继续优化可以参考sub4,不断在当前基础上自加,也就是不断进行左移操作,然后不断把 \(1\) 放在最低位,保留中间变量,这样可以用中间变量一次加好几个 \(1\) ,能减少部分常数.
sub4
sub4也是一个乘法操作,而且是一个比较优秀的实现,前8分要求的是在时间复杂度不变下减少空间复杂度,后2分要求在继续减少时间复杂度.
这个题空间复杂度部分完全可以手搓,因为保留的中间变量事实上只有几个起了作用,剩下的只是起倍增的作用,所以可以缩减掉没有用的中间变量.
这样就可以获得5分.
继续优化,发现有用的中间变量之中,有一些使用之后就没有用了,恰好可以充当接下来生成的中间变量,这样轮换着使用,可以优化到8分.
后面的不会,我太菜了.
后面的几个点有的直接提交原代码就能骗分,比较抽象
标签：总结,题解,复杂度,字符集,PART1,cdots,可以,字母,mathrm From： https://www.cnblogs.com/youlv/p/18188715