SDUT 2022 Autumn Team Contest 7th

1.J题：给你T组数据，每一组数据给你一个区间，让你求这个区间的范围，区间的起始时间和终止时间可能被包含或重复

　　　　思路：思路的话，就是直接把给定的两个区间的之间的数包括端点存到vector去重，然后直接输出个数即可，或者直接存到set里直接系统去重也可

#include 
#include 
#include 
#include 
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<endl;
    return 0;
}

2.L题：给你T个数让你求每个数的非质因数的因数个数

思路：一开始我们想到的是直接预处理，直接在前面预处理出来答案，然后按O(1)的时间复杂度查询就可以了，但是其实这样的话再做预处理的时候就会超时，然后我们知道了怎么算因数的个数，根据惟一分解定理我们可以知道，每一个数都可以被分成几个质数的几次方相乘的乘积，然后把每一个数的指数加一，然后乘起来就是因数的个数，此时我们把质因数的个数去掉之后，就可以得到非质因数的个数。然后我们可以直接去求质因数，这样的话及可以求出每一个质因数的个数（及指数）又可以求出质因数的个数，这样的话我们就可以求出最终的答案，但是直接这样写的话还是会超时，因为它有3e6次的询问，但是我们最大的数才是2e6所以有的数肯定不止被算了一遍，这样的话我们可以记录一下，如果这个数被算过的话我们就直接输出，没有被算过的时候再进行计算

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