title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
Survey in Class
算法本质
思维
题目大意
存在m道题目、n个同学，每个同学会做的题目恰好能做l[i] ~ r[i]的题目。
现在老师可以出若干道题（每种题至多出一次），若遇到不会做的题，同学分数-1，反之+1。
输出最大化的同学分数差。
思路推演
最大的同学分数差，即最高分-最低分。
枚举任意2个同学，其分数区间用AB表示，分数差最大可以表示为：A - A∩B。
思维惯性可以想到，使用某种排序，可以在局部优化部分。
比如以左-右端点排序，如果相交的线段不存在包含的情况，则确实有序，但是包含的情况计算方式不一样，无法排序。
处理这点核心还是在于最大分数差这个思路的核心，对于某个区间来说，若其为最高分，那最低分的选择，最好是那种毫不相关的——交集为0，这个可以通过检查排序后两侧的区间来实现。
包含的情况，交集至少就是低分区间本身长度，其越短越好，所以我们可以直接检查最短的区间，特判其和当前区间的情况（无论包含、相交、无交集），可以保证的是，任意其他包含区间的情况都非最优解。
至此我们就可以用排序的方式解决问题，但是这里答案提供了一个优雅至极的方式：在遍历高分区间的基础上
- 考虑高分区间和低分区间是包含的情况
直接计算len(高分区间) - len(低分区间)，这样相当于计算了所有包含区间的值 - 其他情况
找到最大的l端点和最小的r端点
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>m;
int maxl=0, minr=m, len=1e9;
vector<pair<int, int>> v;
for (int i=1; i<=n; i++)
{
int l, r;
cin>>l>>r;
v.push_back({l, r});
maxl = max(maxl, l);
minr = min(minr, r);
len = min(len, r-l+1);
}
int ans=0;
for (auto [l,r] : v)
{
int res = max(max(r-minr, maxl-l), r-l+1-len);
res = min(res, r-l+1);
ans = max(ans, res);
}
ans *= 2;
cout<<ans<<endl;
return;
}MEX of LCM
算法本质
思维
题目大意
给定长度n的数组a[]，任意区间的最小公倍数放入set，求得set的mex值。
n <= 3e5思路推演
求mex值，总方法有2：
- 从1开始遍历，直到某个元素发现无法求解
计算某个数字是否可行，至少需要log复杂度 - 计算出所有元素，找到mex值
显然第二个方法可行度高一些，但是朴素来说一共有n^2^的元素个数，复杂度不行，接下来就需要找到lcm的特征来优化。
对于一个区间，若其扩展，其lcm值不一定发生变化，若固定某个端点，另一次延申，则至多有log(A)个lcm值。
这告诉我们，此题的最优算法复杂度可达O(nlogn)，接下里就是去优化。
假如顺序遍历，固定左端点，右侧存在log个lcm值，但是左端点移动时，信息并不能充分利用。
如果固定右端点，左侧存在log个lcm值，移动右端点，其可以较好复用。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
vector<int> a(n+5);
int top = n*n;
for (int i=1; i<=n; i++)
cin>>a[i];
set<int> st, pre;
for (int i=1; i<=n; i++) // 枚举右端点
{
set<int> now;
st.insert(a[i]); // 新增的情况
now.insert(a[i]);
for (auto x:pre) // 继承的情况
{
int y=lcm(x, a[i]);
if (y > top) continue; // 过大的数字会爆且其没有意义
st.insert(y);
now.insert(y);
}
pre = now;
}
int ans=1;
while (st.count(ans)) ans++;
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)