【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（1）

我会带着你远行 2022-08-31 05:00 103阅读 0赞

### 文章目录 ###

*  题目集地址
 *  1008 悬线法，栈模拟
 *   *  题意
     *  思路
     *  代码
 *  1006 思维，字典树
 *   *  题意
     *  思路
     *  AC代码

# 题目集地址 #

[2021“MINIEYE杯”中国大学生算法设计超级联赛（1）][2021_MINIEYE_1]  
题目集原地址【[2021“MINIEYE杯”中国大学生算法设计超级联赛（1）][2021_MINIEYE_1 1]】  
这次题目我们只做出了1001 1005两个签到题

# 1008 悬线法，栈模拟 #

[1008][]

## 题意 ##

给出一个矩阵，找到每一列都是非递减的最大子矩阵，输出最大子矩阵的大小

## 思路 ##

题解用的是悬线法。  
这是第一次接触悬线法，关于悬线法的内容我整理了一篇博客.  
悬线法是经典求解最大子矩阵问题的方法，我一开始补题用的是悬线法，但是发现这个有点麻烦。

我后来用单调栈法写，虽然理解上有点难度，但是写起来比较方便。

思路还是将矩阵符合要求的一列看做一条线，然后左右移动，遇到障碍就停下。先创建一个同样大小的二维数组，保存某一坐标处的线的长度，创建一个单调递增的栈，某一点的长度大于栈顶就入栈，小于栈顶就出栈，直到栈为空。当一个元素入栈时弹出的元素的个数表示，当前位置的线在左侧可以移动的长度，当此位置被弹出时，此位置后面的元素就是当前位置的线在右侧可以移动的长度。

还有一种方法是单调栈法。

## 代码 ##

单调栈法

#include <iostream>
    #include <bits/stdc++.h>
    #define maxn 2001
    
    using namespace std;
    
    int matrix[maxn][maxn]; //初始矩阵
    int leng[maxn][maxn];   //以某位置为起点的悬线长度
    
    int main()
    { 
        ios::sync_with_stdio(0),cin.tie(0);
        int n;
        cin >> n;
        int r,c;
        int res;
        while(n--)
        { 
            res = 0;
            cin >> r >> c;
            for(int i = 1;i <= r;i++)
            { 
                for(int j = 1;j <= c;j++)
                { 
                    cin >> matrix[i][j];
                    if(i > 1)
                    { 
                        if(matrix[i][j] >= matrix[i-1][j])
                        { 
                            leng[i][j] = leng[i-1][j] + 1;
                        }
                    }
                }
            }
            stack<int> st;
            stack<int> num;
    
            for(int i = 1;i <= r;i++)
            { 
                st.push(leng[i][1]);
                num.push(1);
                for(int j = 2;j <= c;j++)
                { 
                    if(leng[i][j]>st.top())
                    { 
                        st.push(leng[i][j]);
                        num.push(1);
                    }
                    else
                    { 
                        int c = 0;
                        while(!st.empty())
                        { 
                            if(leng[i][j] <= st.top())
                            { 
                                st.top();
                                c += num.top();
                                res = max(res, (st.top()+1) * c);
                                st.pop();
                                num.pop();
                            }
                            else
                            { 
                                break;
                            }
                        }
                        st.push(leng[i][j]);
                        num.push(c += 1);
                    }
                }
                int c = 0;
                while(!st.empty())
                { 
                    st.top();
                    c += num.top();
                    res = max(res, (st.top()+1) * c);
                    st.pop();
                    num.pop();
                }
            }
            cout << res << endl;
    
            memset(leng,0,sizeof(leng));
            memset(matrix,0,sizeof(matrix));
        }
        return 0;
    }

# 1006 思维，字典树 #

[1006][]

## 题意 ##

对数列做前缀异或，将题面转化为找两个距离最近的数，使得他们的异或值不小于k。

## 思路 ##

思路:首先本题需要构造前缀异或和，为什么呢，举个例子，对于L~R的异或和，直接用1 ~R的异或和与1 ~L-1的异或和异或即可，因为前面的区间都是相同的，异或之后为0，这样就能求出区间的连续异或值了  
构造前缀异或和的字典树，但是每次插入的同时进行查询，求得当前插入的异或和值与字典树已各点(即不同的L)有值的异或和，如果走到一个节点发现接下来不论往左&右遍历，最终得到的异或和都大于等于k,直接返回覆盖该节点的最靠右的异或前缀和下标，即对于插入的异或和满足与其异或大于等于k并且最右的下标，否则返回-1，这样对于每个插入的值都能找到一个自身的最优左端点  
需要特判只需要一个元素就可满足的情况，详见代码

关于覆盖该点的最右异或前缀和下标  
首先在已经构造的字典树中，当遍历到该结点时(即无论如何走都能大于等于k)，此时已经得到的异或和为插入的前缀异或和的前i位与字典树中的前i位的异或和最大值，即在这一位上已经满足了题设条件，包含了这一结点的所有区间与插入前缀异或和的异或值都能满足题设条件，因为要选取区间长度最小，理所当然应该选取覆盖了该节点的的最右异或前缀和下标

涉及到字典树的使用，还不太会。。

## AC代码 ##

#include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=1e5+10;
    int t,n,k,trie[32*N][2],sum[N],data[N],cnt,mx[32*N],End[32*N];
    void Insert(int x,int pos) { 
        int p=0;
        for(int i=31; i>=0; i--) { 
            int v=(x>>i)&1;//获取数的每一位
            mx[p]=max(mx[p],pos);//更新覆盖该节点的最右异或和下标
            if(!trie[p][v]) { 
                trie[cnt][0]=trie[cnt][1]=0;//在构造的时候就进行清空
                End[cnt]=0;//同上
                trie[p][v]=cnt++;
            }
            p=trie[p][v];
        }
        End[p]=x;//记录这一个节点为一个数
        mx[p]=max(mx[p],pos);
    }
    int Query(int p,int s,int i,int x) { 
        int ans=-1;
        if(s>=k)//如果异或和已经大于k，没有必要向下走
            return mx[p];
        if(s+((1ll<<(i+1))-1)<k)//如果当前异或和+剩下位数全取1仍然小于k，不存在值
            return -1;
        if(trie[p][0])//左子树有值
            ans=max(ans,Query(trie[p][0],s+(x&(1<<i)),i-1,x));//x&(1<<i)为提取i这一位对应的二进制数，与已经得到的异或和相加
        if(trie[p][1])//右子树有值
            ans=max(ans,Query(trie[p][1],s+((x&(1<<i))^(1<<i)),i-1,x));//x&(1<<i))^(1<<i)先提取，然后取反
        return ans;
    }
    signed main() { 
        ios::sync_with_stdio(0),cin.tie(0);
        cin >>t;
        while(t--) { 
            cin >>n>>k;
            cnt=1;//初始化
            trie[0][0]=trie[0][1]=0;//初始化
            int ansl=0,ansr=0,minlen=0x3f3f3f3f;//同上
            for(int i=0; i<=32*n; i++)//初始化
                mx[i]=0;
            for(int i=1; i<=n; i++) { 
                cin >>data[i];
                sum[i]=sum[i-1]^data[i];//异或和
            }
            Insert(0,0);//插入根节点
            for(int i=1; i<=n; i++) { 
                if(data[i]>=k) { //如果出现了一个数据直接大于k，选取这一个数据即可
                    ansl=ansr=i;
                    minlen=1;
                    break;
                }
                int lpos=Query(0,0,31,sum[i]);//获得以当前前缀和为基准异或能不小于k的下标
                if(lpos!=-1&&((sum[i]^sum[lpos])>=k)) { 
                    int len=i-lpos;
                    if(len<minlen) { //更新最值
                        minlen=len;
                        ansl=lpos+1,ansr=i;
                    } else if(len==minlen)
                        if(ansl>lpos+1)
                            ansl=lpos+1,ansr=i;
                }
                Insert(sum[i],i);//插入该点的前缀异或和
            }
            if(minlen!=0x3f3f3f3f)//存在最值
                cout <<ansl<<" "<<ansr<<endl;
            else
                cout <<-1<<endl;
        }
        return 0;
    }

[2021_MINIEYE_1]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A81%A3%A9&source=1&searchmode=source
[2021_MINIEYE_1 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=984
[1008]: https://acm.hdu.edu.cn/showproblem.php?pid=6957
[1006]: https://acm.hdu.edu.cn/showproblem.php?pid=6955