竞赛讨论区 > 【题解】Wannafly挑战赛26
头像
牛客网小运营
编辑于 2019-06-12 19:33
+ 关注

【题解】Wannafly挑战赛26

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 御坂网络

考虑n只有1000直接枚举圆心是哪一个sister,判断其他sisters到它距离是否相等即可,注意平方的时候可能会爆int。

T2 冥土追魂

首先可以观察到misaka每次会选这一行最大的一个,而kuroko -一定会选完一整行再选下一 行,所以被取完格子的形态一定是行以及某一行前k mod m大的格子,直接枚举哪一行是选了k mod m个格子即可。

T3 七彩线段

先考虑只有一种颜色的线段,选一种出来使得总长度最长,可以将线段按左端点排序,将坐标点离散化,dp[i]表示前i 个坐标点的最大长度,如果一条线段的左端点为l 右端点为r 则dp[r]=max(dp[r],dp[l-1]+r-l); 。过程中取最大值dp[i]=max(dp[i],dp[i-1]);就可以了。
再考虑颜色只有7 种,多加一维状态就可以了。 

T4 禁书目录

 考虑一本魔法值为x的书不失效的概率是是魔力值大于等于它的书本个数。 有一个简单的证明,由于所有魔力值小于它的书都没有影响所以只考虑它和比它大的书的相对顺序。此时当且仅当它排在最左边才不会失效,所以不失效的概率就是
然后考虑每一种记载内容的书的对答案的贡献,补集转换一- 下,求出这一种记载内容在多少种排列会全部失效即可。

T5 蚂蚁开会

如果没有修改操作的话,就是一个简单 dp 题。
考虑如何维护修改操作,在原有的 dp 答案上不好维护修改操作。我们可以假设所有蚂蚁先走到1 号节点(根节点),然后再走到目标节点,总路径长度就是走到1 号节点的总路径减重复走的路径,用树链剖分维护蚂蚁个数、边长度、边重走次数、边重走长度,最后注意下细节就可以了。

T6 Msc的棋盘

设a[1..n]表示每行对应的棋子的数量, 考虑怎么判断一个a是否台法。
考虑网络流,对于左边n个点中的第i个点,从源点向它连流量为a[i]的边,对于右边m个点中的第i个点,从它向汇点连流量为b[i]的边,然后对于左边所有点和右边所有点之间都连一条流量为1的边, 如果这个图的最大流满流那么就说明这个a是合法的。

由于最大流等于最小割,考虑判断这个图的最小割是否与b的和相同。
把右边跟汇点的所有边的切掉就可以得到与b的和相同的割,所以只需要判断是否存在一个割是小于b的和的。

假设左边有x个点与源点的边切开了,右边有y个点与汇点的边切开了,为了得到最小的割,所以左边切开的一定是a[i]的前x小,右边切开的一定是b[i]的前y小。

然后对于剩下的点,左边有n-x个点与源点相连,右边有m-y个点与汇点相连,那么至少还需要切掉(n-x)(m-y)条流量为1的边。

设prea[i]表示a[]中前i小的值的和,preb[i]表示b[]中前i小的值的和。
那么最小割为min{prea[x]+preb[y]+(n-x)(m-y)|0sxsn,0sy≤m}
考虑DP

由于preb[]是已知的,所以对于x,可以预处理出bound[x]表示a[]中的前x小的和至少需要是多少。

然后设f[i][x][s]表示a[]中小于等于i的值有x个且这些值的和为s的方案数,转移的时候枚举i+1有多少个,然后利用预处理出的东西判断合法性集合。
时间复杂度O(n'm2)

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

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

等你来战

查看全部

热门推荐