SDUT 2022 Autumn Team Contest 7th

时间:2022-09-11 11:28:43

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