竞赛讨论区 > 【题解】2020牛客暑期多校训练营(第五场)
头像
是瑶瑶呀
编辑于 2020-07-25 18:23
+ 关注

【题解】2020牛客暑期多校训练营(第五场)

A-   Portal

任务就是要依次经过2k个点

考虑最暴力的DP

f[i][u][a][b]表示已经完成了前i个任务,当前在点u,两个传送门分别位于ab的最短距离。• 转移有三种:

1.u设立传送门

2.u走到一个相邻节点

3.如果u等于a或者b,那么可以使用传送门

这个DP的转移显然是有环的,因此需要使用Dijkstra算法。

仔细观察,发现记录两个传送门的位置是没有用的,只需要记录一个。因为如果我们要使用一个传送门, 一定是走到那个节点再使用(我们可以随时在当前节点创建传送门)

 f[i][u][p]表示当前已经完成了前i个任务,在节点u,其中一个传送门位于点p

转移有4

1.u走到相邻节点

2.u设置传送门,令p=u 

3.u传送到

4.u设置传送门,传送到p,并只保留u的传送门(交换up) 

再仔细观察,发现可以继续精简状态,设c[i]表示第i个任务的节点。

f[i][p]表示当前已经完成了前i个任务,当前正在c[i]上,传送门的位置在p

可以证明,只需要3种转移,就可以覆盖所有情况

1.直接从c[i]走到c[i+1] 

 2.枚举走到c[i+1]之后,传送门的位置变为了哪个节点,设这个节点是q。第二种转移是从c[i]走到q,在q设置传送 门,从q传送到p,再从p走到c[i+1] 

3.第三种转移是从c[i]传送到p,从p走到q,在q设置传送门,最后从q走到c[i+1] 

复杂度为O(kn^2) 

B-   Graph

做法:可以发现任意两个点之间连边的权值都是固定的。由于图始终联通,所以两点间始终存在至少一条 路径,如果存在多条,根据环的异或和为0,两点间的路径的异或和应该相等,且始终是固定的。

所以可以给每个点一个权值,那么两点间的连边权值就应该是两端点权的异或。

接下来的问题就是异或最小生成树。

字典树

boruvka 

C-Easy

做法:

生成函数 𝛴min(N, M)*(x^N)*(y^M) = xy/((1-x)(1-y)(1-xy)) 枚举(1/(1-xy))^K的次数

1/(1-x)^K 1/(1-y)^K补到N-KM-K 

D- Drop Voicing 

题解

我们将模型转换成有一个圆盘,圆盘上有n个位置,且有一个指针(初始时指针指向原 来的最后一个元素

连续若干次操作1等价为改变指针指向的数所处的位置连续若干次操作

连续若干次操作2等价为改变指针的位置

容易观察到,我们只需要取环上最长的一个上升子序列,然后调整其它数,即可得到答 案

时间复杂度O(n^3)O(n^2) 

E-Bogo Sort 

所有cycle 长度的LCM

由于cycle 长度总和是n,所以一定不会大于位数,不取模即可。

最长的答案也就几百位。

F- DPS 

做法:

模拟即可。注意恰好爆intdouble 可能有精度问题。

G-Greetings Souvenir 

题解

首先进行预处理,我们可以通过DFS以及启发式合并预处理出每个子树中的颜色分布,从而计算得到

每个节点u可以得到哪些不同的value[u]

我们可以由此得到一个二分图:左侧为n个不同的点,右侧为n个不同的value,如果左侧的节点u可以 得到右侧的value则进行连边。

可惜这样边数为O(n^2),而本题内存只有64MB,是不能通过此题的。

事实上我们可以把二分的log去掉

假设当前答案在[L,R]之间,我们先判断mid=(L+R)/2是否合法

如果mid不合法,我们继续对[L,mid]进行二分

如果mid合法,我们继续对[mid,R]进行二分,此时我们只需要在mid状态下的残余网络上继续进行网 络流即可。

时间复杂度O(n^2logn) 

这里向本题被卡TLE/MLE的选手表示一下抱歉,可能这个题确实卡的比较紧。

H-Interval

做法:对于固定的左端点或者右端点,不同的值至多只有log• 先把这些值找出来,然后去掉具有包含关系的相同的值

对于固定的左端点或者右端点,不同的值至多只有log

先把这些值找出来,然后去掉具有包含关系的相同的值

单纯的二维偏序求和无法处理相同的值

那么把相同的值按顺序放在一起(l1,r1)(l2,r2)...(lp,rp) 

那么如果查询包含了(l1,r2)(l2,r3)...(lp-1,rp)这些区间,答案就应该-1 。所以设置一些权值为-1的区间,再二维偏序即可。

 I-Hard Math Problem 

做法:(i+j)%3 =0 交错2

答案是2/3 

因为这样每个1旁边恰好有一个23,而任意两个23不相邻。

可以计算出这是上限。

 J-Cone Walker

题意:无穷大的圆锥表面上两个不同的圆,求相交的面积

思路:计算几何,分类讨论

做法:

1.先把圆锥面按照两个圆心的角度分成四块,分别展开成扇形,转化为扇形和两个圆的交

2.分类讨论,按照两个圆的位置关系(包含和相交),扇形顶点和两个圆的位置关系(在交的 内部和外部),以及扇形的两条射线和两圆相交区域的交点情况(相交,相切,不相交)分类讨论。

K-Git Merge 

做法:

大模拟

先预处理出两个文件,然后dp[i][j][0/1/2] 表示第一个文件第行,第二个文 件第行,在公用/ifdef 1/ifdef 2 内,切换有代价1dp n m 0 是答案。dp 可以存在short 里。

  

 

 

 

 

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐