【SCOI2016】解题报告全

SCOI2016解题报告

——成都七中 杨景钦&&唐宇豪

2016.04.09 第一场机试

第一题

题意:

给你N个互不相同的字符串,记Si为第i个字符串,现在要求你指定N个串的出现顺序,我们用Vi表示第i个字符串是第几个出现的,则V为1到N的一个排列。我们希望你指定的出现顺序可以使总代价最小

一个出现顺序的代价的计算方法如下:

依次考虑第i个串Si对代价的贡献:假如存在一个串Sj,Sj为Si的后缀,且Vj>Vi则第i个串对代价的贡献为N*N

否则,如果不存在一个串Sj,使得Sj为Si的后缀,则第i个串对代价的贡献为Vi

否则,记Pi为所有满足Sj为Si的后缀的j中Vj的最大值,第i个串对代价的贡献为Vi-Pi

你需要输出这个最小的总代价,不取模

数据范围:

对于所有的数据,1<=N<=100000,字符串总长<=510000。

解题报告:

初看这道题没有什么思路,但是很快可以发现,在最优解中,不会存在一个串对代价的贡献是N*N。证明如下:

由于所有串互不相同,则我们显然可以指定一个顺序,使得不存在两个串i,j,Sj是Si的后缀且Vj<Vi,那么此时的代价之和最大为N*(N+1)/2,由于N为正整数,此时N*N>=N*(N+1)/2,证毕

同时我们可以发现:

后缀关系是具有传递性的,即如果A是B的后缀,B是C的后缀,那么A也是C的后缀。

此题中后缀关系不会成环,即不会出现A是B的后缀,B是C的后缀,C是A的后缀,因为没有两个相同的串。

于是我们可以把后缀关系建成一个有根树,每个点代表一个字符串,串Si是串Sj的父亲当且仅当Si是Sj的长度最长的出现过的后缀。并新建一个虚拟节点Root,如果一个串Si没有出现过的后缀,则Si的父亲为Root,Root为这棵树的根

不难发现,此时问题变成了给有根树的每个点标号,满足每个点的标号互不相同且在0到N之间,使得每个点的标号大于其父节点的标号,且所有点的标号减去其父节点的标号之和最小。

这个问题是经典的贪心问题,我们可以发现在最优解中,以某个点为根的子树中所有点的标号一定是一个连续的值域段。那么我们可以采用如下的贪心策略,Dfs一遍给每个点标号,每一次选择子树最小的子节点递归下去,如果不存在子节点则返回。通过计算贡献的方式可以证明这个贪心策略,在此略去。

剩下的问题则是这个有根树应该如何建出来。我们考虑把每个串倒过来建一个字典树,则每个点的父亲就是字典树上最近的一个被标记的祖先。问题至此迎刃而解。

注意在Dfs字典树的时候手写栈来防止栈空间溢出。

复杂度O(N+字符串总长)

 

第二题

题意:

给你一个N个点的带点权的树,Q次询问,每次询问从某两点之间的简单路径上任选任意多个点,点权异或和的最大值。

数据范围:

N<=20000,Q<=200000,0<=点权<2^60

解题报告:

(为了方便叙述,在下文中用P来表示权值对2取对数的结果)

先考虑一个简化版的问题,给你若干个数,从中任选若干个出来,使得异或和最大。

经典做法是异或高斯消元求得线性基,在线性基上贪心,复杂度O(NP)

现在这道题放在了树的路径上,我们首先考虑树链剖分,容易发现两条路径的线性基是可以合并的,因为高斯消元的结果是可以合并的,合并一次的复杂度是O(P2)

于是显然有一个O(NlgNP+ Qlg2NP2)的做法,即树链剖分,对线段树每个节点存储这个节点所有权值的线性基,暴力合并。能得到大概30分。

因为这道题不带修改,一个显然的优化方法是使用类似于求LCA的思路,用Fi,j存储从第i个点到i号点的第2^j个祖先这条路径上所有点的线性基,暴力合并线性基,对于询问用求LCA的方法进行查询。复杂度O(NlgNP2+QlgNP2),大概能得到70分。

正解的做法与上一个做法类似,但在询问的时候可以发现:线性基与最小值类似,可以用ST在查询时的思想,不用理会重复添加进线性基的数,因为他们对结果没有影响。复杂度O(NlgNP2+QP2),如果优化常数可以拿100分。

我在考场上的做法比正解优在预处理时的复杂度。面对题目中的对于路径的询问问题,我想到了点分治。我们使用点分治的时候,对于每个分治重心,维护它到当前分治到的所有点的线性基,那么在查询的时候只需要合并两个线性基即可。而在预处理的时候因为每个点权只会被加到lgN个线性基里面,所以总复杂度为O(NlgNP+QP2),轻松拿到100分

 

第三题

题意:

你有一个N位的大整数(不含前导0),我们把它看成一个长度为N的字符串。有M个限制,每个限制告诉你某两个子串完全相等。问有多少个满足条件的大整数。

数据范围:

N<=100000,M<=100000,保证每个限制中两个子串长度相等且合法。

解题报告:

一个直观的想法是,每一次可以确定某两个字符相同,我们暴力地做并查集,每一次合并若干次两个位置所在的集合,最后知道等价类的个数即可统计答案。复杂度O(NM),无法接受。

很快可以发现,这个限制与上一题类似,重复限制两个字符相同对最后的答案不会产生影响,于是我们可以用ST的拆分方法,把所有限制分成lgN个不同的长度进行处理

如何对这lgN个长度进行处理呢?我们考虑按照长度从大往小进行处理。假设已经处理完了长度为2i的操作,知道了从某些位置开始的长度为2^i的字符串完全相同,现在我要进行长度为2i-1 的操作。我们暂时不考虑原有的操作,考虑由长度不小于2i的操作对长度为2i-1的操作带来的影响。由于已知若干个从某些位置开始的长度为2i的字符串完全相同的信息,为了维护这些信息,我对于一个大小为P的等价类,会需要把他们划分成左右两部分2i-1长度的操作,每一部分只需要P-1个操作就可以维护这些信息在2i-1长度的操作做完后仍然成立所以所有长度超过2i的操作只会增加O(N)个2i-1长度的操作,于是总复杂度近似于O(NlgN),我们忽略并查集的复杂度。问题至此解决。

 

 

 

 

 

 

 

 

2016.04.09 第二场机试

第一题:

 

    题意:

        给定n个整数对(Ai,Bi),请选择一个实数k是的Ai+Bi+Ai*k+Bi/k的最大值最小(n<=1e6,1s

    题解:

        假设我们确定了一个k值,设此时第i个数对的值为Si,那么可以推出

Si>Sj

Ai+Bi+Ai*k+Bi/k>Aj+Bj+Aj*k+Bj/k

(1+k)(Ai-Aj)>(1+1/k)(Bj-Bi)

-(1+k)/(1+1/k)<(Bj-Bi)/(Aj-Ai)

       我们把每一个数对看成平面上的一个点,那么等式的右边就是一对点之间的斜率,很容易看出,只有在下凸壳上的点对计算答案才有意义。

所以我们只需要求出下凸壳,然后一次确定把每一个点作为最大值的时候k值的取值范围,然后最值要么在函数的最低点,要么在取值范围的两个端点。

       这样我们就可以在除了排序O(nlogn)以外,线性的时间复杂度内完成此题。

 

第二题:

题意:

    给你N个数,M个询问,每次给出W,X,L,R,表示询问max(W xor (X + Ai)),L <= i <= R(所有数<=1e5,4s)

题解:

    考虑贪心的依次确定Ai答案的每一位,假设当前已经确定的X+Aj是cur,且我们确定到第i位,假设W的这一位为0,那么如果答案中下一位能够填1当且仅当存在(X+Aj)的第i位为1,即存在(cur|1<<i) < Aj+X < (cur|(1<<(i+1))-1),是否存在我们只需要在线段树上查询即可,W这一位位0时也是相同的做法,请读者自行思考。

        这样,我们就可以在O(nlog^2n)的时间内完成此题。

 

 

第三题

题意:

有一个N行M列的棋盘,每个格子上有’B’,’W’,’X’三种字符中的一个,Q次询问,每次询问给你一个2行C列的字符矩阵,问有多少个不同的棋盘,至少有一个2行C列的子矩阵与给出的矩阵完全相同

数据范围:

N=100,M=12,C=6,Q=5与N=2,M=12,C=3,Q=5两个范围。

解题报告:

首先用补集转化的思想,用总共的棋盘个数减去没有一个2行C列的子矩阵满足条件的棋盘个数来得到答案。

总共的棋盘个数显然为3N+M,问题变成如何求没有一个子矩阵满足条件的棋盘个数。我们考虑容斥

一种显然的容斥是枚举每个子矩阵是否必须满足条件,先判断是否合法,然后求此时的方案数(即3不被限制的格子数。显然TLE。我们试着用动态规划进行优化

首先发现,在i这个子矩阵与j这个子矩阵同时必须满足条件时,i可能会对j的合法性产生影响,当且仅当i这个子矩阵与j这个子矩阵相交。于是我们考虑dp[i][j][k],表示考虑到前i行,以第i行为第二行的子矩阵中必须合法的子矩阵状态为j(用二进制表示),必须合法的子矩阵个数奇偶性为k的方案数

暴力枚举下一行的子矩阵有哪些必须合法,然后计算一下贡献即可进行转移。注意到贡献与i无关,我们可以预处理转移矩阵,复杂度O(QN22(M-C)M),可以通过

 

 

 

 

 

 

 

 

 

 

 

 


评论
热度(8)

© yjq_1999 | Powered by LOFTER