2021“MINIEYE杯”中国大学生算法设计超级联赛（1）

Minimum spanning tree

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N=10000010;

int t;
int n;
int st[N];
int cnt,primes[N];

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])  primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)  break;
        }
    }
}

int main(){
    scanf("%d",&t);
    get_primes(1e7);
    while(t--){
        scanf("%d",&n);
        LL sum=1ll*n*(n+1)/2;
        sum-=3;
        int i=0;
        for(int i=1;i<cnt;i++){
            if(primes[i]>n)    break;
            sum+=primes[i];
        }
        printf("%lld\n",sum);
    }
}

Maximal submatrix

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=2010;

int t;
int n,m;
int a[N],w[N];
int stk[N],top;
int g[N][N],b[N][N];

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&g[i][j]);
        for(int i=1;i<=m;i++)
            for(int j=n;j>=1;j--){
                b[j][i]=1;
                if(j==n)    continue;
                if(g[j][i]<=g[j+1][i])    b[j][i]=b[j+1][i]+1;
            }

        int ans=0;
        for(int k=1;k<=n;k++){
            a[m+1]=top=0;
            for(int i=1;i<=m;i++)    a[i]=b[k][i];
            for(int i=1;i<=m+1;i++){
                if(a[i]>stk[top]){
                    stk[++top]=a[i];
                    w[top]=1;
                }
                else{
                    int width=0;
                    while(stk[top]>a[i]){
                        width+=w[top];
                        ans=max(ans,width*stk[top]);
                        top--;
                    }
                    stk[++top]=a[i];
                    w[top]=width+1;                                                   
                }
            }
        }
        printf("%d\n",ans);
    }
}