一． Mod, Or and Everything

思路：
当i=n/2+1~n时，n%i依次为(n-1)/2~0(连续，这就保证了从最低位到最高位经过或运算都可以变成1)。
当i< n/2+1时,n%i的最大值<=n/2-1<(n-1)/2，所以不需要考虑。我们只需求余数的最大值((n-1)/2)的位数x。
答案就是二进制下的 x个1变成十进制。收获：或运算只要某一位上有1，结果就有1。

本题代码：

#include<iostream>
using namespace std;
int t;
long long n;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        n=(n-1)/2;
        int ans=0;
        if(n)
        {
            while(n)
            {
                n>>=1;
                ans++;
            }    
            long long x=1;
            for(int i=1;i<ans;i++)
            {
                x<<=1;
                x+=1;
            }
            cout<<x<<endl;
        }
        else cout<<0<<endl;    
    }
    return 0;
}

View Code

 

二. Minimum spanning tree
思路：
最小生成树：包含原图的所有点且边的权重和最小。
每两点之间的权重为两点的最小公倍数。可以让合数x与它的因子连起来，这样权重就是合数x，将大于2的素数x与2连起来，权重就是2*x。
故答案为Σ合数+Σ2*（大于2的）素数

本题代码：

#include<iostream>
using namespace std;
const int N=1e7+10;
int prime[N];
int st[N];
int visit[N];
void Prime(){
    for (int i = 2;i <= N; i++) 
    {
        if (!visit[i]) {
            prime[++prime[0]] = i; 
            st[i]=1;
        }

        for (int j = 1; j <=prime[0] && i*prime[j] <= N; j++) {
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }

}
int main()
{
    Prime();
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        long long ans=0;
        cin>>n;
        for(int i=3;i<=n;i++)
        {
            if(st[i])ans+=2*i;
            else ans+=i;
        }
        cout<<ans<<endl;
    }
    return 0;
}

View Code

三. Maximal submatrix
思路：
变成01矩阵用悬线法求最大子矩阵。
时间复杂度O(m*n)
细节：
子矩阵最上端可以为0
收获：
悬线法模板：

if((i-1,j)满足条件)
{
left[i][j]=max(left[i][j],left[i-1][j]);
right[i][j]=min(right[i][j],right[i-1][j]);
up[i][j]=up[i-1][j]+1;
}

View Code

本题代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e3+10;
int le[N][N],ri[N][N],up[N][N],st[N][N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int ans=m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&st[i][j]);
                le[i][j]=ri[i][j]=j;
                up[i][j]=1;
            }
        }
        for(int i=n;i;i--)
        {
            for(int j=1;j<=m;j++)
            {
                if(st[i][j]>=st[i-1][j])st[i][j]=1;
                else st[i][j]=0;
            }
        }
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(st[i][j]&&!st[i-1][j])up[i][j]++;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=2;j<=m;j++)
            {
                if(st[i][j-1])le[i][j]=le[i][j-1];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=m-1;j;j--)
            {
                if(st[i][j+1])ri[i][j]=ri[i][j+1];
            }
        }
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(st[i][j]&&st[i-1][j])
                {
                    le[i][j]=max(le[i][j],le[i-1][j]);
                    ri[i][j]=min(ri[i][j],ri[i-1][j]);
                    up[i][j]=up[i-1][j]+1;
                }
                ans=max(ans,up[i][j]*(ri[i][j]-le[i][j]+1));
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

View Code

四. KD-Graph
思路：

排序+并查集

将n个点分成k个满足要求的集合，如果把边从小到大排序，

每次将权重相同的边放在一个集合里，当我们合并完一个集合时如果此时的集合数正好等于k，那此时的权重就是答案。

本题代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e5+10;
struct edge
{
    int u,v,w;
}h[5*N];
bool cmp(edge aa,edge bb){return aa.w<bb.w;}
int p[N];
int tot,tt;
int n,m,k;
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
void solution()
{
    scanf("%d%d%d",&n,&m,&k);
    int ans=0;
    for(int i=1;i<=n;i++)p[i]=i;
    tt=n;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        h[i]={a,b,c};
    }
    sort(h+1,h+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(h[i-1].w!=h[i].w)
        {
            if(tt==k)
            {
                printf("%d\n",ans);
                return;                
            }
            if(tt<k)
            {
                printf("-1\n");
                return;
            }
        }
        if(find(h[i].u)==find(h[i].v))continue;
        p[find(h[i].u)]=find(h[i].v);
        tt--;
        ans=h[i].w;
    }
    if(tt==k)printf("%d\n",ans);
    else printf("-1\n");
    return;
}
int main()
{
    int t;
    cin>>t;
    while(t--)solution();
    return 0;
}

View Code

五. Xor sum
思路：
将输入进行前缀和，转化为找两个距离最近且异或值大于k的点。
但是不知道为什么枚举右端点之后再找异或和最大的点就可以过去（求高人指点）
tips(A^B=B^A        A^B=C     C^A=B        Trie树)

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int son[31*N][3],idx;
int a[N];
int n,k;
void insert(int x,int y)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int q=x>>i&1;
        if(!son[p][q])
        {
            son[p][q]=++idx;
        }
        p=son[p][q];
    }
    son[p][2]=y;
}
int query(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int c=x>>i&1;
        if(son[p][!c])p=son[p][!c];
        else p=son[p][c];
        if(!p)return -1;
    }
    return son[p][2];
}
void solve()
{
    for(int i=0;i<=idx;i++)
    {
        son[i][0]=son[i][1]=son[i][2]=0;
    }
    idx=0;
    int ans=N;
    int l=-1,r=N;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]^=a[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        int c=query(a[i]);
        if((a[i]^a[c])>=k)
        {
            if(i-c<ans)
            {
                ans=i-c;
                r=i;
                l=c+1;
            }
        }
        insert(a[i],i);
    }
    if(ans==N)printf("-1\n");
    else printf("%d %d\n",l,r);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}

View Code