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; }