普及组小朋友也能看懂的CF1991I题解
lrb828281
·
2026-11-07 12:25:13
·
题解
前言：感谢 @Bingxiu2 帮我减少了大量的分讨。
duel 场切的第二道 *3500 祭。
这题注意到一个东西就做完了，思维链比较短，所以这里除了具体的交互过程，我还会讲怎么想到的这个结构。
思考方式
我一开始想的是类似 (i,j) 填 (i-1)\times m+j 的填法，但这样肯定是不行的，因为玩到后期可以选的数太多了，无法保证交互库选不到很小的数，但是你可以把整个网格分成若干个 1\times 2 ，感性理解一下可以发现你可以保证如果你的数和更大也不会大太多。
然后你就可以发现当 n\times m 都是奇数的话可以把整个网格分成若干个 1\times 2 ，每个 1\times 2 填两个大小差 1 的数，剩下一个格子填 n\times m ，那么你可以强制让交互库选 n\times m ，然后剩下每个 1\times 2 局部最多比交互库大 1 ，所以最终的和一定是严格小于交互库的。
当 n\times m 是偶数的时候上面那种方法就不奏效了。为什么呢？考虑两个人的选数方式。上面那种方法中交互库可以随意地选数，而你只能在交互库选 x 时选 x\operatorname{xor} 1 ，这种方法由于交互库多选一个数所以可行，而在 n\times m 是偶数时如果交互库可以随意地选数，那么交互库可以每次选剩下的最小的数，容易证明这样你是没有必胜策略的，所以考虑把一些数“藏起来”，就是考虑这样的一个结构：中间是一个很小的数，外面有一圈很大的数，当只剩下这些数的时候交互库被迫选一个很大的数，这样你就可以选中间的很小的数。由前面的做法，我们容易发现可以将整个网格分成若干个大小为偶数的子连通块，这样就可以在每个连通块内都让交互库先手，所以考虑 "T 字形" 结构：一个格子周围有三个格子，并且长边在网格的边缘，如下图所示。
其中钦定中间的格子中数比较小，旁边的格子中数比较大，且 "T 字形" 的长边在网格的边缘。考虑如果能将网格分成 4 个 "T 字形" 和若干个 1\times 2 矩阵，那么你可以适当操作使得交互库最多选到一个 "T 字形" 的中心，而你可以选到至少三个，并且剩下的 1\times 2 中也不会比交互库大出多少，所以可以感性理解这就是对的，然后思考的难点到此就结束了（怎么操作和严谨证明等会讲）。
分割网格方式
$n\times m$ 是偶数时，所以 $n,m$ 至少有一个是偶数。为了方便实现，我们钦定 $n$ 是偶数，如果两个数都是偶数那么 $n$ 是较小的那个。如图，我们分三种情况讨论：（图中空白部分表示竖着的 $1\times 2$）
$n=m=4$：如左图所示填入 "T 字形" 即可。
$m=5$：在上面塞入三个 "T 字形"，剩下一个横着放左下角，然后在 $(3,4)(3,5)$ 和 $(n,4)(n,5)$ 横着塞 $1\times 2$，剩下用竖着的 $1\times 2$ 填满即可。（中图中为 $n=8,m=5$ 的情况）
$m\ge 6$：分别在左上角和左下角各横着塞两个 "T 字形"，剩下用竖着的 $1\times 2$ 填满即可。（右图中为 $n=6,m=7$ 的情况）
### 填数方式
当 $n\times m$ 是奇数时，将 $1\times 2$ 标号为 $1,2,\cdots,\frac{n\times m-1}{2}$，第 $i$ 个 $1\times 2$ 填入 $i\times 2-1,i\times 2$，剩下的一个格子填 $n\times m$ 。
当 $n\times m$ 是偶数时，我们想让每个 "T 字形" 中小数和大数差距尽量的大，又因为交互库能最多选到一个 "T 字形" 的小数我们还想让每个 "T 字形" 的大数与小数之差差不多，于是我们这样构造：
将 "T 字形" 标号为 $1,2,3,4$，$1\times 2$ 标号为 $1,2,\cdots,\frac{n\times m-12}{2}$。
对第 $i$ 个 "T 字形"，在中间填入 $i$，旁边三个格子分别填入 $n\times m+i\times 3-14,n\times m+i\times 3-13,n\times m+i\times 3-12$ 。（顺序任意）
对第 $i$ 个 $1\times 2$，填入 $i\times 2+3,i\times 2+4$ 。
### 交互策略
考虑交互库选的格子所在的块：
如果交互库选完后这个块没有格子可选了，那么任选一个能选的格子即可。
如果交互库选完后这个块恰有一个格子可选，那么选那一个格子。
如果交互库选完后这个块有三个格子可选，并且交互库选的不是这个块中间的格子，那么选这个块内中间的格子。
如果交互库选完后这个块有三个格子可选，并且交互库选的是这个块中间的格子，那么选这个块内其它三个格子中数值最小的格子。
### 实现与代码
我们可以将交互策略简化为以下过程：考虑交互库选的格子所在的块，如果还有能选的格子就选最小的那一个，否则就选任意一个别的格子，这样会好写一些。
实现的时候随时注意 $n$ 和 $m$ 是否被交换。
code:
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &x){
bool f=0;
x=0;char c='?';
while(c<'0'||c>'9'){
if(c=='-')f=1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
if(f)x=-x;
}
int n,m,k;
bool swp;
int siz[105],cur[105];
pair<int,int>qwq[105][4];
int id[15][15],a[15][15];
bool fl[15][15];
void out(int x,int y){
if(swp)cout<<y<<" "<<x<<'\n';
else cout<<x<<" "<<y<<'\n';
fflush(stdout);
fl[x][y]=1;
}
pair<int,int>rd(){
int x,y;
cin>>x>>y;
if(swp)return {y,x};
else return {x,y};
}
void op(int x,int y){
fl[x][y]=1;
cur[id[x][y]]++;
}
int l,r;
void add(int x,int y,int xx,int yy){
k++;
id[x][y]=id[xx][yy]=k;
siz[k]=2;
a[x][y]=(++l),a[xx][yy]=(++l);
qwq[k][0]={x,y},qwq[k][1]={xx,yy};
}
void add2(int x,int y,int xx,int yy,int X,int Y,int XX,int YY){
k++;
id[x][y]=id[xx][yy]=id[X][Y]=id[XX][YY]=k;
siz[k]=4;
a[x][y]=(++l),a[xx][yy]=(++r),a[X][Y]=(++r),a[XX][YY]=(++r);
qwq[k][0]={x,y},qwq[k][1]={xx,yy},qwq[k][2]={X,Y},qwq[k][3]={XX,YY};
}
void solve(){
memset(id,0,sizeof(id)),memset(cur,0,sizeof(cur)),memset(fl,0,sizeof(fl));
k=0;
cin>>n>>m;
if((n*m)&1){
swp=0;
l=0,r=n*m+1;
for(int i=1;i<n;i+=2){
for(int j=1;j<=m;j++)add(i,j,i+1,j);
}
for(int j=1;j<m;j+=2)add(n,j,n,j+1);
id[n][m]=(++k);
siz[k]=1;
a[n][m]=(++l);
qwq[k][0]={n,m};
}
else{
swp=0;
if(n&1){
swap(n,m);
swp=1;
}
if(!((n+m)&1)){
if(n>m){
swap(n,m);
swp^=1;
}
}
l=0,r=n*m-12;
if(m==4){
add2(1,2,1,1,1,3,2,2);
add2(3,1,2,1,4,1,3,2);
add2(4,3,4,2,4,4,3,3);
add2(2,4,1,4,3,4,2,3);
}
else if(m==5){
add2(2,1,1,1,2,2,3,1);
add2(1,3,1,2,1,4,2,3);
add2(2,5,2,4,1,5,3,5);
add2(n,2,n,1,n,3,n-1,2);
add(3,3,3,4),add(n,4,n,5);
for(int i=4;i+1<=n-1;i+=2){
add(i,1,i+1,1);
add(i,3,i+1,3);
add(i,4,i+1,4);
add(i,5,i+1,5);
}
for(int i=3;i+1<=n-2;i+=2)add(i,2,i+1,2);
}
else{
add2(1,2,1,1,1,3,2,2);
add2(1,5,1,4,1,6,2,5);
add2(n,2,n,1,n,3,n-1,2);
add2(n,5,n,4,n,6,n-1,5);
for(int i=1;i<=n;i+=2)
for(int j=7;j<=m;j++)add(i,j,i+1,j);
for(int i=2;i+1<=n-1;i+=2){
add(i,1,i+1,1);
add(i,3,i+1,3);
add(i,4,i+1,4);
add(i,6,i+1,6);
}
for(int i=3;i+1<=n-2;i+=2){
add(i,2,i+1,2);
add(i,5,i+1,5);
}
}
}
for(int i=1;i<=(swp?m:n);i++){
for(int j=1;j<=(swp?n:m);j++)cout<<(swp?a[j][i]:a[i][j])<<" ";
cout<<'\n';fflush(stdout);
}
int t=(n*m)/2;
while(t--){
pair<int,int>p=rd();
int x=p.first,y=p.second;
op(x,y);
if(siz[id[x][y]]==cur[id[x][y]]){
int xx=0,yy=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!fl[i][j])
if(fl[i][j-1]||fl[i][j+1]||fl[i-1][j]||fl[i+1][j])xx=i,yy=j;
out(xx,yy);
op(xx,yy);
}
else{
int mn=-1,pwp=id[x][y];
for(int i=0;i<siz[pwp];i++)
if(!fl[qwq[pwp][i].first][qwq[pwp][i].second]){
int X=qwq[pwp][i].first,Y=qwq[pwp][i].second;
if(fl[X][Y-1]||fl[X][Y+1]||fl[X-1][Y]||fl[X+1][Y]){
if(mn==-1)mn=i;
else if(a[qwq[pwp][i].first][qwq[pwp][i].second]<a[qwq[pwp][mn].first][qwq[pwp][mn].second])mn=i;
}
}
if(mn==-1)assert(0);
out(qwq[pwp][mn].first,qwq[pwp][mn].second);
op(qwq[pwp][mn].first,qwq[pwp][mn].second);
}
}
if((n*m)&1)rd();
}
int main(){
// ios::sync_with_stdio(0),cin.tie(0);
// init();
int T=1;
// read(T);
cin>>T;
while(T--)solve();
return 0;
}
```
### 严谨证明
我们记总价值 $S$ 为你选的数之和减去交互库选的数之和，一个块的价值同理，显然有 $S$ 等于所有连通块的价值之和，只需证明 $S<0$ 即可。
对于 $n\times m$ 是奇数的情况，每个 $1\times 2$ 的价值最大为 $1$，而右下角单独的格子价值为 $-n\times m$，故：
$$
S=\frac{n\times m-1}{2}\times 1-n\times m=\frac{1-n\times m}{2}<0
$$
对于 $n\times m$ 是偶数的情况，可以选择一个特殊的 "T 字形"，使得其它三个 "T 字形" 中你都能保证选到最小的数，分三个部分考虑：
每个 $1\times 2$ 的价值最大为 $1$ 。
特殊的 "T 字形" 价值最大为 $n\times m+i\times 2-13\le n\times m-5$ 。
剩下 "T 字形" 价值之和最大为 $3\times(-n\times m-2\times t+15)\le -3\times n\times m+33$ 。（其中 $t$ 是剩下 "T 字形" 的平均编号）
故总价值为 $1\times\frac{n\times m-16}{2}+n\times m-5-3\times n\times m+33=\frac{40-3\times n\times m}{2}\le\frac{40-3\times 4\times 4}{2}=-4<0$ 。
然后我们就严谨证明完了这道题。
### 总结
这道题想到把网格分成若干个块是简单的，难点在于注意到 "T 字形" 结构，注意到这个之后后面的思路就很顺了，摆放方式的不同只会影响分讨的多少，对整体的思路没有很大影响。