CF Round#975 Div.2

发表于 2024-10-14 更新于 2024-10-15 分类于 Codeforces

A. Max Plus Size

题意：给定\(n\)个数，可以选任意数染色，但相邻两个数不能同时染色，最大化染色数量+染色最大值之和。

题解：最大值一定会取，取最大值最多带来奇偶性导致的1的损失，考虑该损失是否可以避免，即n是否为偶数或者最大值存在在奇数位置上。

题意：给定\(n\)个点，任意两点间都有一条线段，多次询问被覆盖\(k\)次的点有多少个。

题解：按坐标顺序模拟一下即可，更新覆盖的线段数量，注意一下边界。

题意：卡片上写有1到n的数字，每种卡片有若干张，可以额外购买至多k张任意数字卡片，然后需要将所有卡片等分为若干堆，保证堆内没有相同数字的卡片，求这个堆的最大大小。

题解：堆的大小不会超过n，从大到小枚举判断，首先保证可以按此大小等分不剩余，在这个前提下显然买的多结果不会更差，只需要判断堆的数量是否小于最多种类的卡片数量即可。

题意：有\(n\)个城市排成一列，时刻1可以从任意一个城市开始，每个时刻可以攻占已有城市相邻的任一城市。每个城市有一个时间要求\(a_i\)，求有多少个城市可以作为起始城市使得每个城市都在其时间要求前被攻占。

题解：

想了一下暴力怎么取judge，觉得这个题我一定是思路想歪了，于是去看了一下题解。题解判断合法的方式是对于一个时刻\(t\)，所有时间要求小于等于\(t\)的城市形成的区间不能长于\(t\)，即不关注具体的攻占顺序而作出可行性的判断。

在这个基础上，起始城市相当于把某个城市的\(a_i\)置为1，对于一个时刻\(t\)对应的区间\([l, r]\)，选择城市\(x\)作为起始可能会导致区间发生变化，因此只需要枚举时间，考虑每个时刻对于\(x\)的约束求并即可。

题意：给出一棵树，操作是可以去掉一个叶子结点，求最少多少次操作可以让所有叶子结点深度相同。

题解：枚举最优解中叶子的深度，对于一个深度\(d\)，所有更深的点显然要被去掉，另外所有更浅的叶子也会带来一部分删除，这一部分对应的是最深子节点深度不到\(d\)的所有节点，分开统计即可。

题意：给定\(n\)个数，可以选任意数染色，但相邻两个数不能同时染色，最大化染色数量+染色最大值+染色最小值之和。

题解：借着第一题的思路，考虑枚举最小值，那么限制了所有更小的数不能选，转化为第一题的问题。从小到大枚举最小值，相当于不停地做区间割，在多个区间内完成A题，即维护是否存在区间可以在取最大值的情况下不损耗1即可。