填坑计划第二弹……把这个没填完的坑搬过来啦

上次勉强填完NEERC的坑…..在qq空间里发现了这个雪藏了很久的坑….赶紧挂出来填了吧

终于填完啦…虽然还有一道交互题….

代码[戳这里]


Game

考虑所有空的格子排成一串,相邻两个空的格之间设为一级台阶(从左到右逐级降低),这级台阶上的石子数量即为这两空格之间的棋子数量

为了方便处理,我们把数组倒序排放

可以看出一次棋子移动等价于把第\(n+1\)号台阶上的任意颗石子移动到第\(n\)级。我们从\(0\)开始编号

那么,我们可以发现,其实奇数位是没有影响的,显然,移到\(0\)位置的时候会出现败态

从奇数位到偶数位,我们在移回来即可

但是可以发现,偶数位的移动\(x\)颗棋子,相当于去掉了这\(x\)颗棋子

也就是,现在转化成了nim取石子了

那么,我们判断偶数位的\(xor\)值便可以得到先手的胜败态

现在要求的是先手胜利,第一步的方案数

显然,就是要求让每一个偶数位经过更改,使得\(xor=0\)的情况

\(xor\)的性质就是,只有相等的时候才\(=0\),且\(xor\)可逆,那么直接\(O(n)\)枚举即可

不过要注意一些边界的情况


Strings

首先考虑第一问

对于一个节点\(i\),用\(f[i]\)表示覆盖\(i\)为根节点的子树和\((i,fa(i))\)这条边所需的最少线段树

我们来讨论一个节点\(x\)\(f[x]\)求法

显然,不考虑合并线段的话,那么\(f[x]=\sum f[y]\)(\(y\)\(x\)的孩子)\(+1\)

但我们可以任意的把两两的线段合并起来(包括\((i,fa(i))\),我们假设他有\(d\)和孩子,那么\(f[x]\)也就是\(\sum f[y]\)(\(y\)\(x\)的孩子)\(+1-[(d+1)/2]\)

对于第二问,考虑二分

我们二分线段的长度上界\(x\)

\(g[u]\)表示将\(u\)的子树中所有边以及边\((u,p[u])\)按上述方法覆盖(并满足\(x\)的限制)后,边\((u,p[u])\)所在线条的最小长度

\(u\)的孩子为\(v_1,v_2,…,v_d\)。不妨设\(d+1\)为偶数,恰好需要将\(d+1\)根线头两两配对(若\(d+1\)是奇数,添一根长度\(g[v]=0\)的线头,不会影响结果)

假设与\((u,p[u])\)配对的线头来自\(v_k\),剩下的\(g[v_1],g[v_2],…g[v_k-1],g[v_k+1],…,g[v_d]\)的最优配法是排序后首尾配对,配完后检查能否都在\(x\)以内

从而可以二分出\(g[v_k]\)的最小值,于是\(g[u]=g[v_k]+1\)


Spies

贪心地选择当前点\(x\)为观察员,那么\(a[x]\)\(spy\),则,下一个观察员为\(a[a[x]]\)

用拓扑排序来实现。显然,当没有读入为\(0\)的点时,剩下的为环,那么,继续在环上贪心的找即可


The Competition

首先考虑暴力的做法, 枚举出发点和结束点,即\(1->x->…->y->1\)

然后寻找\(x->y\)的不经过\(1\)的最短路

时间复杂度\(O(n^2logn)\),吃不消

考虑优化,我们变成枚举一个点\(y\),那么我们需要得到\(1->x->…->y\)的最短路\(d[y]\),然后要保证现在\(x!=y\),那么我们用\(p[y]\)表示到\(y\)的最短路的\(1\)后面一个点是\(p[y]\),这样,只要\(y!=p[y]\),就是合法的;那么如果\(y=p[y]\)的话,我们需要另找一条路径,也就是\(p[y]!=y\)的最短路

以上需要的最短路和次短路,可分别经过两边最短路算法得到,然后只需要枚举\(y\)即可

时间复杂度\(O(2*nlogn)\)


The Bridge

显然,对于一个人\(x\),他有两种最有的方法过桥:

1、选择时间最少的\(a[1]\)与他过去,\(a[1]\)回去,\(t=a[x]+a[1]\)

2、选择一个时间和他差不多的过去,在让另一个小的回来,\(t=a[x+1]+a[1]+a[2]*2\)

注意特判\(n=1\)的情况\


Gates

一次尽可能的把所有的点标向\(1\),另一次尽可能的把所有的点标向\(0\)

具体的BFS方法是:以标为\(1\)为例,先把出去\(0\)\(1\)以外的所有点的输入全部标为\(1\),然后从\(0\)开始拓展,一旦一个点的类型发生了改变,入队,以此BFS即可

最后,两边BFS结果类型一样的,说明是确定的,否则输出


Cave

论文结论题,我个看论文差点看不懂的,就不瞎比比了

下面就给出论文截图吧QwQ


Passage

考虑直接状压来做,对于当前状态\(x\),表示每个人是否已经过去了,那么预处理的时候,首先把所有的人排序,然后我们可以找到时间最长的一个人,这个人一定要过去了

因为当前来说,他花费的时间最长,一定有一个时间是他的,然后暴力枚举他可以带走的人\(O(2^n)\)

这样,乍一看时间复杂度是\(O((2^n)^2)\),会TLE

我们来仔细证明一下复杂度:

求解\(f[X]\)最坏情况下需暴力枚举\(2^(k-1)\),这样的集合\(X\)共有\(C_n^k\)个。对所有状态求和,总共需要枚举次数为\(\)T(\sum_{k1}^{n}C_n^k*2^{k-1})=T(3^n)\(\)

那么\(3^{16}=4kw+\),粗略看起来是卡的进去的….事实确实如此


The Tournament

几个结论:

1、出度最大的点,一定是可以胜利的点

2、和可能胜利的点之间没有直接输赢关系的点,均是可能胜利的点

那么,我们可以根据性质1,直接求出一个点来

然后剩下的问题就是求和第一个点在补图上联通的点

直接bfs就可以解决,具体的方法是次枚举一个未在连通块的点,然后从它开始宽搜出它所在的连通块

具体是枚举它的所有原图的边,标记起来,枚举边之后再枚举所有的点,将未标记的点加入该连通块,并加入队列继续宽搜

为了加快速度,开了链表来存未在当前联通块中的点


Guesswork

交互题…..还是先弃坑吧…..

思考了一下我的准确略达不到这么高

大概的想法就是第一问按照分成九等份来回答,准确率似乎挺高的

后面的问题对于第\(i\)次猜测,设\(a_L<x<a_R\)(\(a_L\),\(a_R\)为已猜的数),那么将\(x\)放在\(a[L+trunc(\frac {(R-L-2)*(x-a_L)}{a_R-a_L})+1]\)

大约估算了一下,准确略在\(3.2\%\)左右,但题目的要求准确率应当在\(3.3\%\)以上….gg..不会


East-West

mdzz….内存卡的好紧啊

假设我们已经找到了分割点(就是能把东海岸的点和西海岸的点分开的点)

那么,显然,对于分割点到西海岸的时间局势他们的距离\(g[i]\)

因为从东海岸到西海岸必经这个点,所以从这个点出发的火车,出发时间各不相同,显然不会冲突

那么考虑东边的怎么处理,我们用\(f[i]\)表示东海岸结点\(i\)到分割点的距离,那么求完以后排序

显然,为了解决冲突,排序以后\(f[i]=max{f[i],f[i-1]+1}\)

这样以后,我们把\(f[i]\)\(g[i]\)大小搭配,求得最小解即可

现在的关键是怎么求分割点,显然我们可以用lca来做,但是无论是倍增求LCA还是树剖来做,都要爆内存……

考虑用染色来解决:方法是把所有西端节点标号\(2\),如果一个点有\(≥2\)个的有标号节点儿子则标号\(2\),如果有\(1\)个有标号儿子标号\(1\),深度最小的标号为\(2\)的点即为关键结点,可以直观的画个图来理解

那么,在求出关键点以后,直接dfs一遍就可以求出\(f[i]\)\(g[i]\)了咯


### The Islands

把多边形拆分,按照\(y\)轴排序,\(x\)轴离散,这样就变成了区间覆盖求最大值问题

按照\(y\)轴上的顺序扫描即可

但是需要注意一个特殊情况,比如样例,感叹号区域是属于多边形外侧的

那么,我们只需要对于同一个多边形,按照\(y\)轴排序,然后已经出现过的区间应该减去1,否则应该加上1

然后在按照所有的操作排序,扫一遍即可

mdzz……我个制杖线段树的标记下传写错了愣是没发现,盯着看了半个小时QAQ


C-algae

考虑第一种构造方法,原图一定是不联通的,那么我们把原图拆成几个子图再去判断即可

考虑第二种构造方法,其补图一定是不联通的,根据补图拆分原图再去判断即可

当图中点数\(≤2\)时,一定成立

直接dfs即可….

但是时间卡的比较紧,各种xjb优化….stl辅助优化….

但是POI官网上还是跑不过去….bzoj上,开了O2以后开始跑进去了那就不管了


Maximal Orders of Permutations

先不考虑字典序的问题,我们先来解决第一个问题:有\(\sum_{i=1}^{k} x_i\leq n\)(\(\sum_{i=1}^{k} x_i<n\)的时候用\(1\)填充)\(LCM\{x_1,x_2,…,x_k\}\)的最大值

容易证明\(x_i\)均为质数的幂次且两两互异的时候LCM最大,于是\(LCM\{x_1,x_2,…,x_k\}=\prod_{i=1}^{k}x_i\)的乘积

那就打一张质数表,然后直接用背包问题解决这个最大值即可,需要注意乘积会很大,我们直接取个对数做加法就好

然后怎么求得方案呢?显然对于每一个状态记录下所有的值会MLE

我是直接记录了前一个状态的下标,然后倒着做一遍,求得结果就好

试几组大数据后发现,我们的质数表打到\(400\)以内就够了,不到\(100\)个质数

现在还剩一个问题,求得了\(\{x_1,x_2,…,x_k\}\),怎么使得字典序最小

这个其实观察一下样例就可以发现,首先我们要把\(\{x_1,x_2,…,x_k\}\)按照升序排序,然后每一个置换都是从第二个开始,把第一个放在最后,这样是最优的



发表评论

电子邮件地址不会被公开。 必填项已用*标注