Empty Graph
算法本质
思维
题目大意
存在n个点，给定一个数组a[]用于表示任意两点的距离：
- $dis_{u-v} = \min_{i=u}^v{a_i}$
定义美丽值：
- 最大的某对点距离
现在玩家有k次操作机会，每次操作可以改变某个元素的值（范围[0~1e9]）。
输出操作后最大化的美丽值。
思路推演
稍加模拟可以发现，令bot为a[]的最小值，则美丽值 <= 2*bot。
在这个限制之下，可以发现最大距离一定出自某两个相邻的点。
这时就可以发现，如果我们用k-2个操作去改善最小值，剩余2个操作用于改善某对相邻点，这是一个相对不错的解法。
这时就可以发现，本质上，操作可以分成2种：
- 改善最小值
- 改善相邻值
改善相邻值至多需要2个操作，所以我们仅需枚举改善相邻值的操作：2、1、0即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>k;
vector<int> a(n+5);
set<vector<int>> st; // {值，id}
for (int i=1; i<=n; i++)
cin>>a[i], st.insert({a[i], i});
auto f = [&] { // 找到最小值id，赋值1e9 改善最小值的函数
int id = (*st.begin())[1]; // 最小值id
st.erase({a[id], id});
a[id] = 1e9;
st.insert({a[id], id});
k--;
};
while (k>2) // k>2时，操作都用于改善最小值
f();
int ans = 0;
if (k==2)
{
ans = max(ans, (*st.begin())[0] * 2); // 剩余2个操作可以改善相邻值，所以可以直接用最小值*2
f();
}
if (k==1)
{
int bot = (*st.begin())[0]; // 最小值
for (int i=1; i<n; i++)
{
int res = max(a[i], a[i+1]); // 因为还剩余1个操作，所以可以取大值
res = min(res, bot*2); // 上限是bot*2
ans = max(ans, res);
}
f();
}
if (k==0)
{
int bot = (*st.begin())[0]; // 最小值
for (int i=1; i<n; i++)
{
int res = min(a[i], a[i+1]); // 没有操作了，所以得取小值
res = min(res, bot*2); // 上限是bot*2
ans = max(ans, res);
}
}
ans = min(ans, (int)1e9); // 之前没有限制ans的最小值，这里需要限制
cout<<ans<<endl;
return;
}LCM Sum (easy version)
LCM Sum (hard version)
算法本质
思维
题目大意
对于区间[l~r]，计数满足下列条件的三元组(a,b,c)个数：
a < b < clcm(a, b, c) >= a+b+c
简单版仅有5个区间，困难版有2e5个区间。
l r <= 2e5思路推演
稍加模拟可以发现，通常lcm(a,b,c)是远远大于a+b+c的，所以反向思考其小于的情况：
lcm(a,b,c) == clcm(a,b,c) == 2c
其中枚举lcm(a,b,c)==c的情况相对简单，我们仅需要知道c的合法范围的因数个数即可，简单版本可以直接暴力枚举。困难版本需要一些优化技巧，大概思索可以用二分优化，先不细究，思考第二种情况。
lcm(a,b,c)==2c的情况稍显复杂，为了保证最后是2c，则必须a和b至少有一个元素提供足够多的2的指数。
笔者的思路大抵如此，接下来只需要分类讨论即可。
但是cup思路更加优秀，所以后面使用cup的思路。但是cup的思路因为没有分情况讨论，所以会跑满，需要注意常数。
分情况讨论不会跑满。
但实际上，这两种情况联系紧密，可以一起讨论。
规定a b必须是2c的因数即可，但是这个过程要注意：
- 保证
l <= a < b < c
对于简单版本，这不成问题，仅需暴力检测即可。
接下来思考困难版本如何处理。
思考时先假设做离线处理，如果后续发现不需要可以撤去
显然一个合适的做法就是将这些数据存在a或者c中，然后用bit求和即可。
因为删除相对麻烦，在模拟的时候发现，还是离线比较好使。
最后选择存在a中，然后从小遍历右端点即可。
ac核心代码 - 优雅暴力
注意这版本代码会T，优化一下BIT的常数就能过。
头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<int> factor[maxn];
vector<pair<int,int>> tol[maxn];
int top = 2e5;
inline void solve()
{
cin>>n;
vector<int> ans(n);
BIT bit(top);
for (int i=0; i<n; i++)
{
int l=in(), r=in();
tol[r].push_back({l,i});
}
for (int r=1; r<=top; r++)
{
int c=r;
vector<int> &v = factor[2*c];
for (int b:v)
{
if (b>=c) break;
for (int a:v)
{
if (a>=b) break;
if (c%a || c%b) bit.add(a, a, a+b+c > c*2); // lcm(a,b,c)==2c
else bit.add(a, a, 1); // lcm(a,b,c)==c
}
}
for (auto [l, id] : tol[r])
{
int res = (r-l+1)*(r-l)*(r-l-1)/6 - bit.getsum(l, r);
ans[id] = res;
}
}
for (int x:ans)
cout<<x<<endl;
return;
}
inline void solve_init()
{
for (int i=1; i<=top; i++)
for (int w=2; i*w<=top*2; w++)
factor[i*w].push_back(i);
return;
}ac核心代码 - 分类讨论
头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<pair<int,int>> tor[maxn]; // {r值， id值}
vector<int> cod[maxn], cod2[maxn];
inline void solve()
{
cin>>n;
vector<int> ans(n);
for (int i=0; i<n; i++)
{
int l, r;
cin>>l>>r;
tor[l].push_back({r, i});
}
int top = 2e5;
BIT bit(2e5);
int cnt=0;
for (int l=top; l>=1; l--)
{
for (int w=2; l*w<=top*2; w++)
{
if (w%2) cod2[l*w].push_back(l); // 说明l*b的所有2因子全部由i提供
else cod[l*w].push_back(l);
// 考虑lcm(a,b,c) == c的情况
if (l*w<=top)
{
int c=l*w;
int num = cod[c].size() + cod2[c].size();
bit.add(c, c, num-1);
}
// 考虑lcm(a,b,c) == 2c && a+b+c > 2c的情况
if (l*w%2==0)
{
int c=l*w/2;
sort(cod2[2*c].begin(), cod2[2*c].end());
sort(cod[2*c].begin(), cod[2*c].end());
int a=l, b=c-a; // 当另一个数的选择>b时会无效
int res=0;
if (w%2)
{
// 新增a值在cod[2c]的情况
res += cod[2*c].end() - upper_bound(cod[2*c].begin(), cod[2*c].end(), b) - 1; // 这里需要手动-1，因为cod[2c]必然有因数c，我们不能让b==c
// 新增a值在cod2[2c]的情况
if (a < b)
res += cod2[2*c].end() - upper_bound(cod2[2*c].begin(), cod2[2*c].end(), b);
}
else
res += cod2[2*c].end() - upper_bound(cod2[2*c].begin(), cod2[2*c].end(), b);
bit.add(c, c, res);
}
}
for (auto [r, id]:tor[l])
{
int len = r-l+1;
int res = bit.getsum(l, r);
ans[id] = len*(len-1)/2*(len-2)/3 - res;
}
}
for (int x:ans)
cout<<x<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)