AGC016C +/- Rectangle

题意简述:给(H , W , h, w)。构造一个(H*W)的矩阵,满足矩阵元素之和为正数,且每个(h*w)的子矩阵元素之和是负数。

感觉是比较简单且比较巧妙的构造题,可惜自己还是太弱,没能做出来。orz wsq

首先考虑第一个样例给出的提示,我们可以在一般位置放1,在满足(i \% h==0,j \% w==0)的位置((i,j))(-(w*h))

然后我们考虑有这么一种情况,就是剩下部分的1无法补满之前矩阵贡献的-1,如:(H=1,W=4,h=1,w=3)

我们按照我们的思路就会出现:(1,1,-3,1),然后我们发现总和是小于0的,就会输出no,然而有如下一组可行解:(2,2,-5,2)

所以我们考虑改进上述构造方法,我们可以在一般位置放k,在满足(i \% h==0,j \% w==0)的位置((i,j))(-k*(w*h-1)-1),那么我们只要使(k)尽量大,就可以尽可能地补足之前产生的(-1)了。

还有特判(H%h==0,W%w==0)时无解,因为这样只会构造出(frac{H*W}{h*w})(-1)子矩阵,那么权值和就小于0了。

#include<cstdio>
#include<algorithm>
using namespace std;
int W,H,w,h,sum,ans[510][510],v;
int main(){
    scanf("%d%d%d%d",&H,&W,&h,&w);
    if(H%h==0&&W%w==0){puts("No");return 0;}
    v=500*500/(w*h-1);
    for(int i=1;i<=H;i++)
        for(int j=1;j<=W;j++){
            if(i%h==0&&j%w==0)ans[i][j]=-(w*h-1)*v-1;
            else ans[i][j]=v;
            sum+=ans[i][j];
        }
    if(sum>0){
        puts("Yes");
        for(int i=1;i<=H;i++,puts(""))
            for(int j=1;j<=W;j++)
                printf("%d ",ans[i][j]);
    }
    else puts("No");
}

原文地址:https://www.cnblogs.com/yxc2003/p/10730512.html