ZigZagK

Never give up fighting!

[计数]BZOJ5366(Lydsy1805月赛)【代码派对】题解

[计数]BZOJ5366(Lydsy1805月赛)【代码派对】题解

题目概述

\(n\) 个矩阵,问多少三元组 \((i,j,k),i<j<k\) 满足三个矩阵至少有一个相交的格子。

解题报告

我怎么连计数题都不会……这种题目肯定要考虑枚举相交的格子来统计贡献,但是不可能枚举相交的矩阵,我们再观察一下就会发现只需要枚举相交矩阵的一个角就行了。

然后开始疯狂分类讨论,只要按照一定顺序枚举所有方案并判断该方案是否可行就行了,我们先记录:

\(S_{1,i,j}\) :左下角为 \((i,j)\) 的矩阵个数。\(S_{2,i,j}\) :左边界包含 \((i,j)\) 的矩阵个数(不含左下角)。

\(S_{3,i,j}\) :下边界包含 \((i,j)\) 的矩阵个数(不含左下角)。\(S_{4,i,j}\) :包含 \((i,j)\) 的矩阵个数(不含左边界下边界)。

这些用容斥和差分就可以 \(O(1000^2)\) 求出来了,接下来列举所有情况(前面的数字表示选了几个),自己推去吧,我根本没想让你们看懂

[3S_1];[2S_1,S_2];[2S_1,S_3];[2S_1,S_4];[2S_2,S_1];[2S_2,S_3];[2S_3,S_1];[2S_3,S_2];[2S_4,S_1];[S_1,S_2,S_4];[S_1,S_2,S_4];[S_1,S_3,S_4];[S_2,S_3,S_4]

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=1000;

int te,n,s[4][maxm+5][maxm+5];LL ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
#define C2(x) ((LL)(x)*((x)-1)/2)
#define C3(x) ((LL)(x)*((x)-1)*((x)-2)/6)
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (readi(te);te;te--,memset(s,0,sizeof(s)),ans=0){
        for (int i=(readi(n),1);i<=n;i++){
            int xl,yl,xr,yr;readi(xl);readi(yl);readi(xr);readi(yr);
            s[0][xr][yl]++;s[3][xl][yl+1]++;s[3][xl][yr+1]--;s[3][xr][yl+1]--;s[3][xr][yr+1]++;
            s[1][xl][yl]++;s[1][xr][yl]--;s[2][xr][yl+1]++;s[2][xr][yr+1]--;
        }
        for (int j=1;j<=1000;j++) for (int i=1;i<=1000;i++) s[1][i][j]+=s[1][i-1][j];
        for (int i=1;i<=1000;i++) for (int j=1;j<=1000;j++) s[2][i][j]+=s[2][i][j-1];
        for (int i=1;i<=1000;i++) for (int j=1;j<=1000;j++) s[3][i][j]+=s[3][i-1][j]+s[3][i][j-1]-s[3][i-1][j-1];
        for (int i=1;i<=1000;i++)
            for (int j=1;j<=1000;j++){
                ans+=C3(s[0][i][j]);
                ans+=C2(s[0][i][j])*(s[1][i][j]+s[2][i][j]+s[3][i][j]);
                ans+=C2(s[1][i][j])*(s[0][i][j]+s[2][i][j]);
                ans+=C2(s[2][i][j])*(s[0][i][j]+s[1][i][j]);
                ans+=C2(s[3][i][j])*s[0][i][j];
                ans+=(LL)s[0][i][j]*s[1][i][j]*(s[2][i][j]+s[3][i][j]);
                ans+=(LL)s[2][i][j]*s[3][i][j]*(s[0][i][j]+s[1][i][j]);
            }
        printf("%lld\n",ans);
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]