想了想决定把这几题也随便水个解题报告...
bzoj https://www.luogu.org/problemnew/show/P5300
思路:
首先肯定得拆成二进制 30 位啊
此后每一位的就是个 01 矩阵
Q1 就是全是 1 的矩阵个数
Q2 就是总矩阵个数减去全是 0 的矩阵个数
玉蟾宫警告
就是单调栈乱搞对吧
本题完结
事实上有了思路其他的都是多余的对吧所以就不要介意代码了
- #include<cstdio>
- #define mo 1000000007
- const int N=1011;
- template<typename tp>inline void read(tp &tar)
- {
- tp ret=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
- tar=ret*f;
- }
- int n,ai[N][N],a1[N][N],a0[N][N];
- int ans1,ans0;
- int sta1[N],sta0[N];
- int main()
- {
- read(n);
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- read(ai[i][j]);
- }
- }
- for(int k=0,o=1;k<31;k++,o<<=1)
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- if(ai[i][j]&o)
- a1[i][j]=a1[i-1][j]+1,a0[i][j]=0;
- else
- a0[i][j]=a0[i-1][j]+1,a1[i][j]=0;
- }
- }
- for(int i=1;i<=n;i++)
- {
- int hop1=0,hop0=0,tmp1=0,tmp0=0;
- for(int j=1;j<=n;j++)
- {
- tmp1+=a1[i][j];
- while(hop1&&a1[i][j]<a1[i][sta1[hop1]])
- {
- tmp1+=(sta1[hop1]-sta1[hop1-1])*(a1[i][j]-a1[i][sta1[hop1]]);
- hop1--;
- }
- ans1=(ans1+((1ll*tmp1)<<k)%mo)%mo;
- sta1[++hop1]=j;
- tmp0+=a0[i][j];
- while(hop0&&a0[i][j]<a0[i][sta0[hop0]])
- {
- tmp0+=(sta0[hop0]-sta0[hop0-1])*(a0[i][j]-a0[i][sta0[hop0]]);
- hop0--;
- }
- ans0=(ans0+((1ll*(i*j-tmp0))<<k)%mo)%mo;
- sta0[++hop0]=j;
- }
- }
- }
- printf("%d %d\n",ans1,ans0);
- return 0;
- }
我又被卡常了啊啊啊
[GXOI/GZOI2019] 与或和 (单调栈)
来源: http://www.bubuko.com/infodetail-3099601.html