比赛 2024暑假C班集训C 评测结果 WWWTTTTTTTTTTTTTTTTW
题目名称 洛希的极限 最终得分 0
用户昵称 djyqjy 运行时间 79.985 s
代码语言 C++ 内存使用 3.48 MiB
提交时间 2024-07-12 11:17:22
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=2010,Q=500010;
const long long MOD=1e9+7;
struct rec
{
    int x1,x2,y1,y2;
}rs[Q];
int n,m,q;
int t;
pair<int,long long> dp[N][N];
bool pan(int x,int y,int xx,int yy)
{
    for(int i=1;i<=q;i++)
    {
        if(rs[i].x1<=x&&x<=rs[i].x2&&rs[i].y1<=y&&y<=rs[i].y2&&rs[i].x1<=xx&&xx<=rs[i].x2&&
           rs[i].y1<=yy&&yy<=rs[i].y2) return 1;
    }
    return 0;
}
void dfs(int x,int y,int d,long long f)
{
    bool flag=0;
    if(dp[x][y].first)
    {
        if(dp[x][y].first>d) return;
        if(dp[x][y].first==d) dp[x][y].second=(dp[x][y].second+f)%MOD,flag=1;
    }
    if(!flag) dp[x][y]=make_pair(d,f);
    for(int xx=x+1;xx<=n;xx++)
    {
        for(int yy=y+1;yy<=m;yy++)
        {
            if(pan(x,y,xx,yy))
            {
                dfs(xx,yy,dp[x][y].first+1,dp[x][y].second);
            }
        }
    }
    return;
}
long long ansd,ansf;
int main()
{
    freopen("roche.in","r",stdin);
    freopen("roche.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d%d",&rs[i].x1,&rs[i].y1,&rs[i].x2,&rs[i].y2);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(dp[i][j].first!=0) continue;
                dfs(i,j,1,1);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(ansd<dp[i][j].first) ansd=dp[i][j].first,ansf=dp[i][j].second;
                else if(ansd==dp[i][j].first) ansf=(ansf+dp[i][j].second)%MOD;
                dp[i][j].first=0;
            }
        }
        printf("%lld %lld\n",ansd,ansf);
        ansd=ansf=0;
    }
    return 0;
}