1.J题：给你T组数据，每一组数据给你一个区间，让你求这个区间的范围，区间的起始时间和终止时间可能被包含或重复
思路：思路的话，就是直接把给定的两个区间的之间的数包括端点存到vector去重，然后直接输出个数即可，或者直接存到set里直接系统去重也可
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; vector<int> ans; int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--)
{
int a,b;
cin>>a>>b;
for(int i=a;i<=b;i++)
{
ans.push_back(i);
}
}
sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());
cout<<ans.size()<<endl;
return 0;
}
2.L题：给你T个数让你求每个数的非质因数的因数个数
思路：一开始我们想到的是直接预处理，直接在前面预处理出来答案，然后按O(1)的时间复杂度查询就可以了，但是其实这样的话再做预处理的时候就会超时，然后我们知道了怎么算因数的个数，根据惟一分解定理我们可以知道，每一个数都可以被分成几个质数的几次方相乘的乘积，然后把每一个数的指数加一，然后乘起来就是因数的个数，此时我们把质因数的个数去掉之后，就可以得到非质因数的个数。然后我们可以直接去求质因数，这样的话及可以求出每一个质因数的个数（及指数）又可以求出质因数的个数，这样的话我们就可以求出最终的答案，但是直接这样写的话还是会超时，因为它有3e6次的询问，但是我们最大的数才是2e6所以有的数肯定不止被算了一遍，这样的话我们可以记录一下，如果这个数被算过的话我们就直接输出，没有被算过的时候再进行计算
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 3e6 + 10;
int res[N]; void divide(int x)
{
int k=x;
int ans=1;
int ans2=0;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0)
{
x /= i, s ++ ;
}
ans*=s+1;
if(x!=1)
ans2++;
}
if (x > 1) ans*=2;
printf("%d\n",ans-ans2-1);
res[k]=ans-ans2-1;
} int main()
{
res[1]=1;
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
if(res[n]!=0)
printf("%d\n",res[n]);
else
divide(n);
}
return 0;
}
3.B题：意思是一开始给我们一张图，然后其中有一台主机会被病毒给侵染，但是我们想让它一次就把所有的主机感染，并且我们会加上一些边保证能一次感染，问我们加边的条数最少是多少，病毒只可以隔一个侵染。
思路：翟老板全程提供思路，此题其实我们如果想让它在只侵染一台主机的情况下，想要把所有的机器都通过跳跃的毒素侵染的话，我们首先至少得把所有的点全部连在一起，这样的话我们可以用并查集，通过并查集我们可以求出一共有几个图，我们首先要把不连在一起的图连在一起，这样的话我们就会有ans=父节点等于其本身的点的个数减一。然后我们再考虑，光连同还不行，必须要存在一个奇数环，这样的话才能保证在只侵染一个主机的前提下，主机通过病毒去侵染别的主机进而侵染全部，然后奇数环的话我们可以联想到二分图，二分图就是没有奇数环的无向图，这样的话我们只需要通过染色法判断它是否是个二分图即可，如果是二分图的话，我们就要加上一条边（及凑出奇数环），如果不是二分图的话，说明我存在奇数环，最后直接输出ans即可。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e6 + 10;
int p[N];
int e[N],ne[N],h[N],color[N],idx; void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
} int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
} bool dfs(int u,int c)
{
color[u]=c; for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!color[j])
{
if(!dfs(j,3-c))
return false;
}
else if(color[j]==c)
{
return false;
}
}
return true;
} int main()
{
int ans=0;
memset(h,-1,sizeof h);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
int pa=find(a);
int pb=find(b);
p[pa]=pb;
}
for(int i=1;i<=n;i++)
{
if(p[i]==i)
ans++;
}
ans=ans-1;
bool flag=true;
for(int i=1;i<=n;i++)
{
if(!color[i])
{
if(!dfs(i,1))
{
flag=false;
break;
}
}
}
if(flag==true)
{
ans++;
}
printf("%d\n",ans);
return 0;
}
