Codeforces Round 879 (Div. 2)

vp的非常炸裂的一把。

A喵了

B卡住了，到最后都没做出来。
其实思路已经有了，但是我觉得是错的，就难蚌。
其实就是找第一位不一样的，后面就是0和9这样的最优的选择了。

C其实推导一下就能够发现其实BOB的操作没什么意义，直接统计两个字符串不一样的地方有几个，然后反转一下再统计，这两个取min就是答案，其中有一些部分需要特殊处理。没了。

D题，看错题了，搞得比赛的时候白写了。其实分析一下，很简单的。
首先可以发现，学了的+1和没学的-1其实和直接把学了的+2是完全等价的。
我们先假设有两个学生是我们最后的答案的两个选择，一个最高，一个最低
简单分析一下，共计三种情况，一种是这两个人的区间没有相交，一种是有相交，一种是包含。
没有相交的话，那这个答案就是这两个人里面区间长的那个人的区间长度\(\times 2\)
有相交，就是两个人里面没相交的部分的最大值\(\times 2\)，要是包含的话就是大的区间减去小的区间\(\times 2\)

这个时候就可以用数据结构维护了，但是其实仔细考虑一下，完全可以更简单。
我们对每一个区间，尝试把它当作答案中大的那个区间来计算答案。那么，如果有一个区间的左边界在这个区间的右边，或者是右边界在左边，那都能够让第一种情况价值最大化。然后考虑第二种情况，也是一样的，如果存在第一种情况，那么第二种肯定是没有第一种优秀的。如果不理解，把公式写出来就看出来显然了。再是第三种情况，更是一样，这个情况对于单个区间甚至可以不统计，直接找到最长的区间和最短的区间，让答案的初值等于他们相减，很显然，这样的答案是第三种情况里面最大的，而如果这两个区间不构成第三种情况，那么第三种情况将不会是答案。

所以就有了离谱的O(n)做法

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int a=0,b=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
	return a*b;
}
int l[100001],r[100001];
int L,R,Max,Min,n,m;
int main()
{
	int T=read();
	while(T--)
	{
		n=read(),m=read();
		L=m+1;R=0;Max=0;Min=m+1;
		for(int i=1;i<=n;i++)
		{
			l[i]=read(),r[i]=read();
			L=min(L,r[i]);
			R=max(R,l[i]);
			Max=max(Max,abs(r[i]-l[i]+1));
			Min=min(Min,abs(r[i]-l[i]+1));
		}
		int ans=Max-Min;
		for(int i=1;i<=n;i++)
		{
			if(l[i]<=L&&r[i]>=R)ans=max(ans,max(r[i]-L,R-l[i]));
			else ans=max(ans,r[i]-l[i]+1);
		}
		cout<<ans*2<<endl;
	}
	return 0;
}
 

这个E题，哎

今年昆明邀请赛里面有一题和这个非常像，用的是同一个结论。
就是gcd或者是lcm的数量。
首先，对于一个不断长变长的区间，lcm只能是单调递增的。
而你的lcm，每次增加，都必定是在前面的基础上\(\times 2\)，或者是一个更大的数字。这也就意味着，你的lcm的种类，最多只有\(log_2(max)\)个，而这里，这个max可以是很大。\(1e9\)都无所谓。那也就是说，你对每个位置，以它为起始位置，往后枚举它的所有的以这个点为起始位置的区间的lcm，是可行的。
具体操作，就是把所有不同位置开始的lcm全部放到set中，这个set最大只有\(log_2 (max)\)，每次我们就把这里面的全部取出，然后计算每个数字和\(a[i]\)的lcm，再放回去。然后把超出\(max\)的lcm不要。统计到最后，找到最小的没有遇到过的数字，就是答案。用stl写起来巨快。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int a=0,b=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
	return a*b;
}
inline int gcd(int a,int b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
inline int lcm(int a,int b)
{
	return 1LL*a*b/gcd(a,b);
}
int n,a[300001];
set<int> s,vis;
int main()
{
	int T=read();
	while(T--)
	{
		n=read();
		for(int i=1;i<=n;i++)
		{
			a[i]=read();
		}
		s.clear();vis.clear();
		s.insert(a[1]);vis.insert(a[1]);
		for(int i=2;i<=n;i++)
		{
			set<int> tmp;tmp.insert(a[i]);
			for(int x:s)
			{
				int ned=lcm(x,a[i]);tmp.insert(ned);
			}
			s=tmp;
			while(s.size()&&(*(--s.end()))>=1e9)s.erase(*(--s.end()));
			for(int x:s)vis.insert(x);
		}
		int ans=1;
		while(vis.count(ans)!=0)ans++;
		cout<<ans<<endl;
	}
	return 0;
}
 

哎，这一场的B，是真的。。。
D其实很简单，差点就出来了。很可惜。
想想怎么想才能做出来？
B其实正解我确实想到了，但是我当时的脑子太乱。。。想不清楚了，也是对于进制的理解还是太狭隘了吧，当时在想上一位虽然不一样了，也不代表下一位可以任意选，其实差的是那个一个全9一个全0 的部分，那确实是差了些。

D的话，看错题了，看对了题目我估计也花大时间写数据结构了。ea的做法确实是太优越了，这个是这个贪心确实是降维打击了。太强了，我完全弄懂策略的时候如果再进一步想一想也许能想到。

E，其实就是那个gcd和lcm的结论。没什么，学到了就好了。

加训。