Arkweedy's Blog

Gym入口 Preface 和小木虫一起vp的，赛后补了队友独立写出来的题以及赛时尝试开的两道金牌题。 题解顺序： M-J-D-H-G-F-B M. V-Diagram 签到题，题意大概是给定一个V型数组，取一个最大平均值的子V型数组。 赛时WA了两次后才得到了正确思路。 首先，V型数组至少有3个元素，而且要求是子数组，那么可以去掉的只有两端不与极小值直接相邻的部分。 可以考虑贪心，如果我们要去掉一端的一部分，那么去掉那端全部不与极小值相邻的元素一定是最优的。(因为我们去掉一端时，是先去掉大的再去掉小的，那么要去掉一定是全部去掉) 而贪心一个一个去是不可取的，因为可能去掉一个元素会让平均值减小，但是去掉那一整段又可以让平均值变大。 而去掉两端一定是劣的(这样把较大的值全全去掉了) 故答案为不去，去掉左端可以去掉的部分，去掉右端可以去掉的部分三者平均值中取最大值。 code: 1234567891011121314151617181920212223242526272829303132333435363738void solve(){ ...

比赛入口 C 很简单，建图找一下最远点即可。 不过因为点值比较离散，所以用map存邻接表(cf传统艺能卡ump，所以还是不用的好)。 code: 12345678910111213141516171819202122232425262728293031void dfs(map<ll, vector<ll>>& nxt, map<ll, bool>& vs, ll p, ll &ans){ vs[p] = true; ans = max(ans, p); for (auto s : nxt[p]) { if (!vs[s] && s != 0) { dfs(nxt, vs, s,ans); } }}void solve(){ int n; cin >> n; vector<ll>a(n + 1); for...

比赛入口 C 为了无后效性，我们对每一对可交换的数对，只计算交换对外层的影响(干扰度是否会减少)。而交换是相对的，所以对该层外层的操作与否也不会影响该层内层是否相对该层进行交换 (也就是说我们不需要真的去交换，只计数即可)。 所以做法即为贪心，我们如果发现交换可以使该层对外层的干扰数减少，那就使ans减去这个差值。任意次序遍历数组(比如说由外到内)均可，毕竟层与层之间没有影响。 code: 1234567891011121314151617181920212223242526272829void solve(){ int n; cin >> n; vector<int>a(n + 2); int sum = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; if (a[i] == a[i - 1]) sum++; } vector<int>k(n +...

2014 G. Milky Days 实际上是一道模拟题， 我们定义关键天为牛奶数目可能会非因为喝掉而改变的那天。 利用一个deque去处理关键天时能否供给牛奶即可 则关键天为 \(\min(最近牛奶过期天，下一个获得牛奶的天)\) 我们一边求解答案一边算下一个关键天是哪个 假设关键天序列为\(a_0,a_1,a_2,a_3...\) 初始化\(a_0 = 1\) 由于一个关键天到下一个关键天前,牛奶只会被喝掉而不会过期、增加，那么我们就可以\(O(1)\)处理掉这一段了。 于是我们的算法是： 1. 算出下一个关键天\(a_{i+1}\) 2. 处理区间\([a_i,a_{i+1}-1]\)...

D Robert Hood and Mrs Hood 赛时对l,r分别进行了排序,来测算是否有事件进入，实际上这是没有必要的。 可以直接用一个桶来记录。buc[l]--,buc[r+1]--即可。 不难，时间复杂度为\(O(n)\) E - Rendez-vous de Marian et Robin 赛时魔改dijkstra没有改出来(实际上应该也很难改出来) 赛后了解到分层图，直接开悟 做法是对每个节点，建图建一个有马节点，一个无马节点，有horse的节点就让无马节点向有马节点连边。对于给出的边，有马图和无马图同步建图。最后跑一遍Dijkstra就行。 F -...

C. Lazy Narek dp即可； 不过一定要好好读题才行！！ 就是读题读假了和不仔细，才导致vp赛时没有调出来。 这个dp的优化(或者是自然而然的处理)：数组开1维5个位置即可，不需要对m轮全部开一个位置，否则会tle。状态转移时记得滚动，不要在原数组上面改，否则会出问题(可能跑出来同一层选了两次的结果) D. Alter the GCD analysis 前缀和后缀和gcd自然不用多说。逐一枚举\(\{l，r\}\)即使每次枚举求值是\(O(1)\)也会tle。所以要寻求更好的方法求解。 由于一个数的质因子最多只有\(\log n\)个，考虑gcd prefix是单调非升的，那么有如下性质： 只有最多\(\log n\)个位置 \(i\) 使 $ prefix[i] > prefix[i+1] $ ,其余均为 \(prefix[i] = prefix[i+1]\) 对suffix gcd类似。 那么实际上，绝大多数前后缀gcd是相等的。...

1988D. The Omnipotent Monster Killer 由于只有相邻节点之间才有影响，树形dp即可。 权值每次至少减半，故杀死所有怪物的轮数不会超过\(\log n\)轮，相邻节点删去的轮数不同。 在有根树上dp，\(dp[i][j]\)代表在节点i在第j轮删除时，节点\(i\)子树的最小贡献。 状态转移： \(dp[i][j] = \sum_{v\in S_i}\min(dp[v][k]),k \neq j\) 1977E. Level Up 线段树+二分 第一次用自己写的线段树板子，爽捏。 对于每个位置，大于最小答案的每个k的取值都可以满足要求，故可以二分答案。check是计算答案为k时，前面的最小答案在1-k区间内的个数(即获得的exp)，然后按照题意判断即可。 一定要注意整型溢出的问题！！！ (因为在check的时候，使用了mid*a[i]与exp比较大小，而mid*a[i]是可能溢出的。) (当然，可以直接比exp/mid 和a[i]) 核心代码：...

2008H. Sakurako's Test 关键是前缀和和二分 以及对边界做一点特殊处理防止前缀数组越界 二分有说法的，要通过二分找到右边界(和中位数定义有关) 或许还可以改改代码，感觉自己写的有点怪 1992G. Ultra-Meow 看清这题的数据范围，对\(\sum n^2\)做了限制，所以单测\(O(n^2)\)的复杂度是没有问题的，不需要预处理所有答案然后\(O(1)\)查询。 做法是对于每个可能的\(k = mex(S)\),对\(k\)分讨，算出每种k的贡献次数即可，复杂度\(O(n^2)\)。 需要一点点组合。 组合的板子在对负数的处理上好像有不兼容的的地方？ 回头看看，改一下板子，这句话还在这里就表示没有修改板子以及搞清楚原因