首页 > 牛牛的Link Power II
开通博客写题解
头像 一Wa哇一天
发表于 2020-02-08 20:50:51
@[TOC] 题目链接：牛牛的Link Power II 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述牛牛有一颗大小为n的神奇Link-Cut 数组，数组上的每一个节点都有两种状态，一种为lin 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 CoolGuang!
发表于 2020-02-10 17:12:29
题意大家都知道了..毕竟是为了看题解才来看题解.. 这个题比赛过程中没有写是因为被I题规律卡了一个半小时，没有时间写了..其实后来想想发现也挺简单的。比赛过程中大体看了一眼感觉是线段树，只想着维护一棵线段树，但是其实需要维护两颗线段树。 具体思路：首先我们根据 I 题里面求出序列初始的 CUT值：假 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 --嘤色暴撃--
发表于 2020-02-08 18:53:19
分块大法吼啊！(ಡωಡ) 虽然知道是线段树。但是我觉得好久没搞线段树。我不会打惹过于无趣。所以用了分块。谁叫这题数据<=，明摆着练分块的，分块的每次操作是然后就是经常有的：码字15分钟，debug 2小时，搞得我连模拟题都没做完。。。。难受qwq 分块思想 把一个整体分成一块块，遍历块比遍历点 展开全文
去ta的博客 赞 (2) 回复(2) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”