【题解】【原创题目】薇尔莉特

2020/08/02 14:59
阅读数 41

【题解】【原创题目】薇尔莉特

出题人:辰星凌

验题人:无

题目传送门:薇尔莉特

【题目描述】

给出一个 \(n\)\(m\) 列的矩阵(最初全为 \(0\)),有 \(T\) 个操作,每次操作选出一个子矩阵,将其中的所有元素都对 \(x\) 进行一次 \(or\),求最后的矩阵。

【分析】

【Solution #1】

纯暴力,没有坑点,按照题意模拟一下就可以了。

时间复杂度:\(O(Tn^2)\)

分数:\(20pt\)

【Code #1】
#include<algorithm>
#include<iostream>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=503,P=1e9+7;
int n,m,a,b,c,d,x,T,HYJ,Ans1,Ans2,A[N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
//  freopen("123.txt","r",stdin);
    in(n),in(m),in(T),in(HYJ),Ans2=HYJ;
    while(T--){
        in(a),in(b),in(c),in(d),in(x);
        for(Re i=a;i<=c;++i)
            for(Re j=b;j<=d;++j)
                A[i][j]|=x;
    }
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=m;++j)
            (Ans1+=A[i][j])%=P,Ans2^=A[i][j];
    printf("%d %d %d\n",Ans1,Ans2,(LL)Ans1*Ans2%P);
}

【Solution #2】

如果把取“或”换成“异或”就是一个区修单查的二维树状数组板子,可惜 \(or\) 不满足可减性。

那如果如果它分为 \(log\) 个二进制位呢?

对于任意一个二进制位,都是满足可减性的,这下子可以放心地上 \(\text{BIT}\) 了。

直接开 \(log\) 棵二维 \(\text{BIT}\),分别单独处理所有的二进制位,每次操作暴力拆分 \(x\) 进行 \(log\) 次区间修改,最后再对矩阵中所有元素的每一位进行单点查询即可。

时间复杂度:\(O(kTlog^2n+klog^2n)\),其中 \(k\) 最大为 \(30\)

注:要卡下常才能过 \(Subtask\ 2\)

分数:\(60pt\)

【Code #2】

(此代码并非完美,还有至少三处优化,但过 \(Subtask\ 2\) 足矣)

#include<algorithm>
#include<iostream>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=503,P=1e9+7;
int n,m,a,b,c,d,x,T,HYJ,Ans1,Ans2,A[N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct QAQ{//二维树状数组
    int C[N][N];
    inline void add_(Re x,Re y,Re z){while(x<=n){Re i=y;while(i<=m)C[x][i]+=z,i+=i&(-i);x+=x&(-x);}}
    inline void change(Re x1,Re y1,Re x2,Re y2){//子矩阵修改
        add_(x1,y1,1);
        add_(x1,y2+1,-1);
        add_(x2+1,y1,-1);
        add_(x2+1,y2+1,1);
    }
    inline int ask(Re x,Re y){//单点查询
        Re ans=0;
        while(x){Re i=y;while(i)ans+=C[x][i],i-=i&(-i);x-=x&(-x);}
        return ans>0;//只要有一次1即可
    }
}TT[31];
int main(){
//  freopen("123.txt","r",stdin);
    in(n),in(m),in(T),in(HYJ),Ans2=HYJ;
    while(T--){
        in(a),in(b),in(c),in(d),in(x);
        for(Re p=0;p<=30;++p)if((x>>p)&1)TT[p].change(a,b,c,d);//分解inf,只有为1的位才调用BIT
    }
    for(Re p=0;p<=30;++p)
        for(Re i=1;i<=n;++i)
            for(Re j=1;j<=m;++j)
                if(TT[p].ask(i,j))A[i][j]|=(1<<p);//获取最终的A数组
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=m;++j)
            (Ans1+=A[i][j])%=P,Ans2^=A[i][j];
    printf("%d %d %d\n",Ans1,Ans2,(LL)Ans1*Ans2%P);
}

【Solution #3】

考虑如何优化 \(Solution\ \#2\)

依旧是对于每个二进制位单独处理。

想想“或”还有没有什么其他的性质?

单次覆盖性!(其实就是自己瞎取的一个名字)

现在只看一个元素,只要有一次操作中对 \(1\) 取了 \(or\),那么以后不管和谁 \(or\),都依然是 \(1\)。换句话说,将操作中 \(x\)\(1\) 的二进制位视作一张大小为 \((x_2-x_1)*(y_2-y_1)\) 的布,无论有多少张布覆盖了这个元素,且无论覆盖了多少次,只要有其中一次盖住了它,那么它最终就一定属于被盖住的部分(即对应的二进制位为 \(1\))。

因此,如果我们在一次操作中覆盖了某个元素,那么下一次枚举到这里时就可以直接跳过它(或者说直接删掉该元素),易知每一个元素都只会被覆盖一次,因此对于一个二进制位下的矩阵覆盖总复杂度为 \(O(n^2)\)

其中“删除元素”可以用并查集实现:对于每一行都开一个并查集表示该行中所有列的覆盖情况,当 \((i,j)\) 被覆盖后,把 \((i,j)\)\((i,j+1)\) 所在的联通块连起来,然后再枚举该行下一个联通块(即 \((i,j+1)\) 所在连通块),大致代码如下:

/*从x1到x2枚举i*/
for(Re j=find(y1);j<=y2;j=find(j+1))
    (i,j)=1,merge(j,j+1);

当然,这样子做只优化了对于列的枚举,行的枚举同理,稍作修改即可。

时间复杂度:\(O(kT+n^2\alpha^2(n)+kn^2)\),其中 \(k\) 最大为 \(30\)(一个不需要卡常也能轻松 \(\text{AC}\) 的优秀算法)。

分数:\(100pt\)

【Code #3】
#include<algorithm>
#include<iostream>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=503,P=1e9+7;
int n,m,a,b,c,d,x,T,HYJ,Ans1,Ans2,A[N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct QAQ{
    bool B[N][N];
    struct QWQ{
        int fa[N];
        inline void CL(){for(Re i=0;i<=m+1;++i)fa[i]=i;}//注意初始化要枚举到n+1
        inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
    }f[N];
    inline void CL(){
        for(Re i=1;i<=n;++i)f[i].CL();//第i(1<=i<=n)个f表示第i行中各列的覆盖情况
        for(Re i=1;i<=n+1;++i)f[0].fa[i]=i;//用第0个f表示行的覆盖情况
    }
    inline void change(Re x1,Re y1,Re x2,Re y2){
        for(Re i=f[0].find(x1);i<=x2;i=f[0].find(i+1)){
            for(Re j=f[i].find(y1);j<=y2;j=f[i].find(j+1))
                B[i][j]=1,f[i].fa[j]=f[i].find(j+1);//第i行第j个被覆盖,去掉它(放到j+1脚下)
            if(f[i].find(1)==m+1)f[0].fa[i]=f[0].find(i+1);
            //如果第i行全部被覆盖(即1到m全部都放到了m+1脚下),则可以将第i行去掉了(放到第i+1行脚下)
        }
    }
}TT[31];
int main(){
//  freopen("123.txt","r",stdin);
    in(n),in(m),in(T),in(HYJ),Ans2=HYJ;
    for(Re p=0;p<=30;++p)TT[p].CL();//初始化
    while(T--){
        in(a),in(b),in(c),in(d),in(x);
        for(Re p=0;p<=30;++p)if((x>>p)&1)TT[p].change(a,b,c,d);//分解inf
    }
    for(Re p=0;p<=30;++p)
        for(Re i=1;i<=n;++i)
            for(Re j=1;j<=m;++j)
                if(TT[p].B[i][j])A[i][j]|=(1<<p);//获取最终的A数组
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=m;++j)
            (Ans1+=A[i][j])%=P,Ans2^=A[i][j];
    printf("%d %d %d\n",Ans1,Ans2,(LL)Ans1*Ans2%P);
}

【题外话】

本题实际上是两个知识点的糅合:
\((1).\) 按照二进制位拆分单独处理(见 【题解】\(\text{GXOI/GZOI2019}\) 机房游记 \(\text{Day1T1}\)
\((2).\) 冰茶姬优化矩阵覆盖的枚举(见 【杂文】随心一记 小知识第二条)

\(Code\ \#2\) 最初第 \(4\) 个点死活卡不过去,最后将结构体套结构体换成一个单一的结构体就过了(没想到结构体的调用对常数影响这么大)。

加上样例一共 \(12\) 个不同的 \(HYJ\)\(12\) 个数字 \(11\) 个梗您知道几个?

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部