Chopping Carrots (Hard Version)
算法本质
思维
题目大意
给定长度n数组a[]，玩家需要构建长度n的p[]（元素范围[1~k]），最小化：
- $\max(\left \lfloor \frac{a_i}{p_i} \right \rfloor) - \min(\left \lfloor \frac{a_i}{p_i} \right \rfloor)$
简单版本：
n k a[] p[] <= 3e3
困难版本：
n k a[] p[] <= 1e5思路推演 - 简单版本
只需要枚举min值即可，枚举3e3次，每次枚举检查复杂度O(n)。
思路推演 - 困难版本
显然需要使用某种优化。
对于某个a[i]值，我们取p[i]值时，其结果似乎没有a[i]个，其结果数目大概是根号个。
证：
对于数n，i遍历1~n，求v=n/i(向下取整)的结果数目是根号个
当i的范围是[1~sqrt(n)]时，可以视作所有结果b各不相同——这里有sqrt(n)个v。
当i>sqrt(n)时，b<sqrt(n)，至多存在sqrt(n)个v。
得证。然后检查复杂度，题目给的时间应该允许O(n^1.5^)，一个朴素的想法是枚举这n^1.5^个可选值为min值，然后维护即可。
根据上面的证明，这些值可以处理出来，这里介绍一种在线枚举的方式：
当v值增加时，有时候不仅+1，其可以用v = a[i] / (a[i] / (v+1))展示
这是因为p[]的取值并不重要，v值才是最后的值。
a[i] / (v+1)就是当v增加后的p[]值，然后求出新的v值ac核心代码
注意这个代码会T，但是和这篇知乎题解的做法十分类似，复杂度也相同。
这里是官方题解，有空看一下。
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>k;
vector<int> a(n+5), p(n+5), v(n+5); // v[i] = a[i] / p[i]
for (int i=1; i<=n; i++)
cin>>a[i], p[i]=k, v[i]=a[i]/p[i];
sort(a.begin()+1, a.begin()+1+n);
set<pair<int,int>> st;
for (int i=1; i<=n; i++)
st.insert({v[i], i});
int ans = st.rbegin()->first - st.begin()->first;
while (1)
{
if (ans==0) break;
int id=st.begin()->second;
st.erase(st.begin());
p[id] = a[id] / (v[id] + 1);
if (p[id]==0) break;
v[id] = a[id] / p[id];
st.insert({v[id], id});
ans = min(ans, st.rbegin()->first - st.begin()->first);
}
cout<<ans<<endl;
return;
}Qpwoeirut and Vertices
算法本质
思维、数据结构
题目大意
顺序给定m条边，接下来给定q次询问：
- 每次询问给定
l r，若希望保证l~r的所有点在同一连通块，则至少需要前多少条边（注意这里是边的前缀）
n q m <= 2e5思路推演
由于每次询问的是一个区间的点，所以我们可以抽象出两个图：
- 图1：
正常图，即按照题目给定规则，每次给边的 - 图2：
有n个点，初始相邻点有没激活的边（n-1条）
每次图1的操作后，其也会对图2做出改变。
在模拟过程中发现，对于任意下标相邻的点来说，其距离可以视作图1中两点路径的最大边权，这个距离也可以视作图2两点的边权。
对于l r的询问，实际是在图2中找这个区间的最大边权。
所以现在我们希望对图1作处理，使其能够log级别查询任意两点的距离（这个距离是被我们定义的距离）。
使用LCA类似的树上倍增即可实现。
然后查询处理图2，最后应答询问。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)