集训队一次作业试题泛做zsyzzsoft.pdfVIP

试题编号名称题目大意算法讨论时空复杂度

CodechefChefProtectionPlan有T(T=100)组数据，每组数先将待处理字符串的括号两边加时O(N)

MAY13据输入一个格式串，再输入上空格，保证每个语段的都可以被空O(N)

Q(Q=1000)个匹配串，问每个空格分开。然后对字符串进行语法

匹配串是否满足格式串。分析，这里使用简化的递归递减分

析的方法，这种方法不需要回溯，

分析字符串的时间复杂度为O(N)。

在分析的过程中，将其转化为正则

表达式，即可转化为正则表达式的

匹配，然后可以直接使用库文件

regex.h来解决正则表达式的匹

配问题。

CodechefQueriesontreeagainN(N=100000)个点N条边的首先将整个图分解成一个环和若时O(QlogN)

MAY13无向连通图，Q次操作，每次干外向树。对每棵树进行树链剖空O(NlogN)

操作对u到v的最短路径上所分。在树链剖分后的每个路径上，

有边的权值取相反数，或求u用线段树每个线段上最大的

到v的最短路径上连续边权之连续区间和，包括左端点的连续区

和的最大值。间和以及包括右端点的连续区间

和。这样段树上便可以合并。

区间翻转时我们需要段树上

打一个标记，然后用lazytag线段

树懒惰下传。再用一个线段树

环上的情况即可。单次操作时间复

杂度O(logN)。

CodechefKnightMoving骑士从(0,0)开始，可以走到如果A和B线性无关，则先忽略所时O(2KK)

SEP12(u+A,v+A)或者(u+B,v+B)，有有点计算方案数，然后用容斥空O(2KK)

xyxy

K(K=15)个格，问走到(X,原理减去经过若干点的方案

Y)有多少种走法。数。否则我们对所有的坐标缩放

(A,B)使其线性无关。

CodechefAnnualParade有N(N=250)座城市，M(M先求任意两点之间的最短路径，然时O(N3logN)

SEP12=30000)