没有完结所以也就不截图留念了。

Price List

给定一个无向图,边权都是a,对于任意两个点,如果最短距离为2a,那么在这两个点之间连一条边权为b的边。

这是一道结论题,至于是什么结论就不剧透了,总之暴力是可以过的。(有点卡常数)

Tapestries

给定一个多边形,其中的一些边需要被照亮,询问是否可以在多边形中放入一盏灯满足条件。

没有A掉非常难过,等有兴趣了再看题解吧。

Multidrink

给定一棵树、起点终点,每次可以跳过一个点到一个没有被遍历到的点,询问是否可以遍历整棵树,且到达终点。

起先没有看到要到终点就万劫不复了。先搞出起点到终点的路径,对于路径上的每个点,需要遍历完不在路径上的子树。有两种遍历方案。一:先到这个点,然后遍历它的子树,最后回到它的孩子节点。二:跳过这个点,先遍历它的子树,最后回到这个点。递归实现即可。

Taxis

给定一条长为m的路,起点在0,终点在m。在d的位置有一个出租车公司,其中有n辆出租车,出租车可以走一定的路程,人在没有坐车的情况下不能移动。询问从起点到终点最少要做几辆出租车。

贪心。如果现在在公司的右边,那么就派一辆大于m-d的车即可。那么先拿出这辆车,其余的车从大到小派,直到坐到公司右边。

Take-out

给定一个由"b"和"c"组成的长为n的串,每次从中取出k个b和一个c,且取出的字符之间没有被取过的字符,保证

维护两个栈,一个放"b",一个放"c",如果当前做到"c",那么就从"b"的栈中取"b",如果"b"不够,就把它放入"c"的栈中;如果当前做到"b",若"c"的栈中有需要"b",就把它给那个"c",否则放入"b"的栈中。最后排序。

Walk

每个城市用二进制表示,两个城市有道路相连当且仅当二进制位只有一个数字不同。询问是否可以从一个城市做到另一个城市。

结论题,最多有一个大小超过nk的联通块。那么bfs的时候只需要经过nk个节点即可。

Inspector

每个人会有一段时间处在公司中,给定一些限制条件(t,j,i),表示在时间t,除了第j个人以外还有i个人。询问前k个限制有可能存在的最大的k。

在限制条件中出现过的人构成集合A,其余的人构成集合B。对于A中的每一个人,至少在一段时间在场。按照时间做,使得每个时间都满足要求。在一个时刻,有两种操作,加人、减人。加人优先加入B中的人,如果某时刻有必须加入的人,可以弹出已加入的B集合中的人或已经可以出去的A集合中的人。减人没有优先级。

Triumphal arch

给定一棵树,两个人在在树上玩游戏,每个时刻A会标记k个节点,B起始位置在根,每个时刻走到一个相邻的没有别标记过的点,如果无法走就输。询问使得A赢的最小的k。

答案显然具有可二分性,对于一个k,在树上做一遍dp即可。

Watering can

给定一排树,有两种操作。1:使l~r之间的树高度加1。2:询问l~r之间高度大于k的树的个数。

由于k是给定的,只需把高度大于k的树放入树状数组即可。

Tales of seafaring

给定一个n点m边无向图,边权均为1,有k个询问,每次询问给出(s,t,d),要求回答是否存在一条从s到t的路径,长度为d
路径不必是简单路(可以自交)。

如果存在一条从A点到B点长为d的路径,那么也存在一条长为d+2的路径,只需求出任意两点间长为奇数或偶数的最短的路径。

Tower Defense game

奇怪的题,暴力即可。。。

Bytecomputer

给定n个元素的序列,且。每次操作可以把。询问把序列变成不降序列的最少操作数。

首先可以发现最终序列,那么只需dp即可。

Maze

构造一个n个顶点的多边形,在多边形内右手始终接触多边形的边,按照它的边缘走,如果右转就是P,左转就是L。输出每个点的顶点。(多边形不能自交,坐标绝对值要求在以内)。

有一个显然的结论:有解的充要条件是L的个数是P的个数+4(可以感性理解为L是逆时针转90°,P是顺时针转90°,那么最终一定要转一圈360°)。起先想着分成两块分别构造,再并在一起,然后发现这样做有点难度。一种可行的做法是每次在现有图形的起点加入一个"LP"对,那么共有8种加入的情况。剩下的问题是处理加入"LR"对以后凹进去或凸出来的大小。最初的想法先构出图再调整,发现这样的难度和原问题是差不多的。。。处理的办法是像构图一样用双向链表来表示坐标的大小关系。

Colorful Chain

大水题

Where is the one?

有趣的结论题。
需要给出最小值的位置,有两种询问方式:,返回是否满足,返回是否满足。使得g操作越少越好。

先找出最大值或最小值。这个可以这么找:二分和第一个数的差值d,进行。如果是最大值,再这样做一遍,就可以得到最小值的位置。

Laser

给定平面上的n条线段,可以从原点发射最多k条射线,使得每条线段最多接触到1条射线,求最多能接触的线段条数。

先极角排序把问题转化为一维,之后就是简单的dp。

Polarization

规定一棵树,可以给边规定方向,d为存在路径的两个点的对数。求d的最大值和最小值。

最小值一定是n-1。每条边的贡献至少为1,所以这是理论下界,构造方法是一层向上一层向下。对于最大值,有一个显然的结论:对于一个根,它的各个子树的方向是统一的。那么就要最大化,如果根不是重心,那么只需把size大于n/2的子树的方向设成Up,其余都为Down。如果根是子树,相当于要做一次背包。当然直接背包是不行的。可以把子树按大小分成两类,第一类大于,第二类小于。对于第一类直接背包,对于第二类先算出相同大小的子树个数,再按模数背包。

Postscript

终于写完了。。。
本来想在元旦写完的,又拖了一个多星期。。。

Comments

comments powered by Disqus