9.13 补题记录

d-p-n-i- / 2024-10-13 / 原文

https://codeforces.com/contest/1834/problem/D
我想到的是我们的答案肯定是两个区间不重合的地方最大的然后这样想的话就要for两遍然后还想差分来着但是都挺麻烦的
这个题解是真的太聪明了
就是说我们的答案肯定是在一段的区间上的某部分（前面后面两头）那我们直接来看让这一区间前面剩余最大的就是找l[i]最大的那一段是吧后面剩余就是找r[i]最小的一段
然后还有一个就是剩余两头但剩余两头一定是存在一大段完整的包含了一小段那我们直接用最长的一段减去最短的一段就完成了（我们假设他们重合嘛没关系因为如果没有重合我们取前端和后端的时候答案肯定更大就替代掉了不影响的）
所以这题就变得特别简单！！！
void solve()
{
int n,m,mi=100000000000,ma=0,mal=0,mir=100000000000;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>l[i]>>r[i];
cnt[i]=r[i]-l[i]+1;
mal=max(l[i],mal);
mir=min(mir,r[i]);
ma=max(cnt[i],ma);
mi=min(cnt[i],mi);
}
int sum=ma-mi;//取两头
for(int i=1;i<=n;i++)
{
sum=max(sum,min(max(mal-l[i],r[i]-mir),cnt[i]));
}
cout<<sum*2<<endl;
}

https://codeforces.com/contest/1834/problem/E
E题很明显就是要知道全部字段的lcm这样时间复杂度暴力是nn 然后我们优化了了一下就是每一个数以它为终点的全部字段是以他前面一个数为终点的全部lcm的结果和a[i]再来一个lcm
我感觉这个还挺好想的但是这样居然不会爆！！？？震惊
我想可能是这样的 1e9里的质数就不到6e7个但是你这样下去很快数字就会超过1e7会被pass掉导致没剩几个
破案了 100以内的质数相乘都20位了包优化的
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
int lcm(int a,int b)
{
return (a*b)/gcd(a,b);
}
void solve()
{
int n;
cin>>n;
setp,s;

for(int i=1;i<=n;i++)
{
    cin>>a[i];
}
for(int i=1;i<=n;i++)
{
    set<int>tmp;
    tmp.insert(a[i]);
    s.insert(a[i]);
    for(auto x:p)
    {
        int cnt=lcm(a[i],x);
        if(cnt>=10000000) continue;
        tmp.insert(cnt);
        s.insert(cnt);
    }
    p.swap(tmp);
}
int ans=1;
while(s.count(ans)) ans++;
cout<<ans<<endl;

}