首页 > 玛卡巴卡玩游戏
开通博客写题解
头像 myee
发表于 2022-03-10 21:56:42
一个结论是一段区间可行当且仅当其总石子个数是偶数且最多者不超过总数一半。 笛卡尔树上启发式合并即可。 （听说数据水，乱搞也能过。） // 笛卡尔树毁我青春 // 隐式构建.jpg ullt S[100005]; uint Cnt[2][100005]; uint A[100005]; struct 展开全文
去ta的博客 赞 (6) 回复(2) 收起
头像 Kostlin
发表于 2022-03-10 22:05:05
首先我们需要讨论一堆石子序列能否消完的充要条件，显然有：当且仅当序列最大值小于等于石子总数一半且石子总数为偶数时，石子序列可消完 。这个可以用每次消最多的石子堆和旁边的石子堆来感性理解，证明不难。 接下来我们考虑分治求解。对于一个分治区间 [l,r][l,r][l,r] ,枚举答案区间右端点 RRR 展开全文
去ta的博客 赞 (3) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”