2021HDU多校1

比赛地址

A题 Mod, Or and Everything 题目地址

题目大意:求(n mod 1) or (n mod 2) or ... or (n mod (n - 1)) or (n mod n).

打表轻松找到规律。
代码:

#include<bits/stdc++.h>
using namespace std;
long long a[100010];
int main()
{
    long long t;
    cin>>t;
    long long n;
    a[0]=0;
    a[1]=0;
    for(int i=2;i<=100000;i++)
    {
        a[i]=a[i-1]*2+1;
    }
    while(t--)
    {
        scanf("%lld",&n);
        long long nn=1;
        int cnt=0;
        while(nn<n)
        {
            nn*=2;
            cnt++;
        }
        //cout<<cnt<<endl<<endl;
        cout<<a[cnt]<<endl;
    }
    /*for(int i=1;i<=100;i++)
    {
        int ans=0;
        for(int j=1;j<=i;j++)
        {
            ans=ans|(i%j);
        }
        cout<<i<<" "<<ans<<endl;
    }*/
}
/*
2 0
2 1
4 3
8 7
16 15
64 31*/

E题 Minimum spanning tree 题目地址

题目大意:两点边权为LCM,求最小生成树。

求质数,每个数都和最小因子连,然后最小因子都和2连,答案为3-n的加和,再加上所有质数和。
代码

#include<bits/stdc++.h>
using namespace std;
int t;
long long n;
const int maxnum = 1e7;
int prime[maxnum];
void getPrime(){
    for(int i=2; i<maxnum; i++){
        if(prime[i]==0){
            prime[++prime[0]]=i;
        }
        for(int j = 1;j<=prime[0]&&i*prime[j]<=maxnum;j++){
            prime[i*prime[j]]=1; 
            if(i%prime[j]==0) break;
        } 
    }
}
int main()
{
    getPrime();
    cin>>t;
    while(t--)
    {
        cin>>n;
        long long ans=(long long)(3+n)*(n-2)/2;
        for(int i=2;i<=prime[0];i++)
        {
            if(prime[i]<=n)
            {
                ans+=prime[i];
            }
        }
        cout<<ans<<endl;
    }
}

H题 Maximal submatrix 题目地址

题目大意:给出一个矩阵,要你找一个最大的子矩阵,要求这个子矩阵每一列从上往下都是单调不下降序列。输出最大子矩阵的面积。

先标记好单调序列,然后直接找最大矩阵(单调栈)。
代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[2010][2010];
int sum[2010][2010];
int stk[2010],top=0;
int w[2010];
int now[2010];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(a[i][j]>=a[i-1][j])
                sum[i][j]=sum[i-1][j]+1;
                else
                sum[i][j]=1;
            }
        }  
        int res=0;
        for(int i=1;i<=n;i++)
        {
            top=0;
            for(int j=1;j<=m;j++)
            now[j]=sum[i][j];
            int ans=0;
            for(int j=1;j<=m;j++)
            {
                int x=now[j];
                if(top==0||stk[top]<=x)
                stk[++top]=x,w[top]=1;
                else
                {
                    int wid=0;
                    while(top&&stk[top]>x)
                    {
                        wid+=w[top];
                        ans= max(ans,wid*stk[top]);
                        top-= 1;
                    }
                    stk[++top]=x;
                    w[top]=wid+1;
                }
            }
            int wid=0;
            while(top)
            {
                wid+=w[top];
                ans=max(ans,stk[top]*wid);
                top--;
            }
            res=max(ans,res);
        }
        printf("%d\n",res);
    }
    return 0;
}

I题 KD-Graph 题目地址

题目大意:给定一个图,求一个长度D,使得这个图可以分成K份,满足每一份之中的两两之间的距离 <= D,两份之间距离要>D。

思路:

贪心+并查集,只需要把不断把最小的边加入,求出来D。
代码:

#include<bits/stdc++.h>
using namespace std;
struct dian
{
    int x,y,w;
}a[500010];
int n,m,k;
bool cmp(dian a,dian b)
{
    return a.w < b.w;
}
int fa[100010];
void init()
{
    for(int i=0;i<100010;i++)
    fa[i] = i;
}
int Find(int x)
{
    if(x == fa[x])    return x;
    return fa[x] = Find(fa[x]);
}
bool merge(int x,int y)
{
    x = Find(x);
    y = Find(y);
    if(x != y)
    {
        fa[x] = y;
        return 1;
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d %d %d",&n,&m,&k);
        for(int i=0;i<m;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
        if(n == k)
        {
            cout<<"0"<<endl;
        }
        else
        {
            sort(a,a+m,cmp);
            int nn=n;
            int ans=-1;
            int i=0;
            while(i<m)
            {
                int cw=a[i].w;
                while(i<m&&cw==a[i].w)
                {
                    int x=a[i].x;
                    int y=a[i].y;
                    if(merge(x,y))
                    nn--;
                    i++;
                }
                if(nn==k)
                {
                    ans=cw;
                    break;
                }
            }
            printf("%d\n",ans);
        }    
    } 
}