省选数学专题
开题顺序： \(E\)
\(A\) [AGC058D] Yet Another ABC String
\(B\) [ABC330G] Inversion Squared
\(C\) [ABC241Ex] Card Deck Score
\(D\) [ABC226H] Random Kth Max
\(E\) [AGC016C] +/- Rectangle
-
观察样例容易得到一种构造方式为任意 \(h\) 行 \(w\) 列子矩形的权值和为 \(-1\) 。
-
无解当且仅当 \(n \bmod h=0 \land m \bmod w=0\) 。
-
继续挖掘性质，不妨先令矩阵中都填上一个相同的元素 \(v\) ，然后选择一些特殊点进行调整，设调整后的边权为 \(x\) 。
-
特殊点取 \(\{ (i,j) | i \bmod h=0 \land j \bmod w=0 \}\) 时比较容易构造（钦定每个子矩形中质只包含一个特殊点），此时有 \(v(hw-1)+x=-1\) ，移项得到 \(x=-1-vhw+v\) 。
-
同时还有 \(v(nm-\left\lfloor \frac{n}{h} \right\rfloor \left\lfloor \frac{m}{w} \right\rfloor)+x\left\lfloor \frac{n}{h} \right\rfloor \left\lfloor \frac{m}{w} \right\rfloor >0\) 的限制，与上式联立得到 \(v(nm-hw\left\lfloor \frac{n}{h} \right\rfloor \left\lfloor \frac{m}{w} \right\rfloor)>\left\lfloor \frac{n}{h} \right\rfloor \left\lfloor \frac{m}{w} \right\rfloor\) ，取 \(v=\left\lfloor \frac{n}{h} \right\rfloor \left\lfloor \frac{m}{w} \right\rfloor+1\) 即可。
点击查看代码
int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n,m,h,w,v,x,i,j; cin>>n>>m>>h>>w; v=(n/h)*(m/w)+1; x=-1-v*h*w+v; if(n%h==0&&m%w==0) { cout<<"No"<<endl; } else { cout<<"Yes"<<endl; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cout<<((i%h==0&&j%w==0)?x:v)<<" "; } cout<<endl; } } return 0; }