D-小红的矩阵不动点_牛客周赛 Round 104

赛时这道题卡了一段时间，赛时代码如下：

#include<bits/stdc++.h>
using namespace std;
int ans,h;
int a[505][505];
signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]==min(i,j))ans++;}if(ans==n*m){cout<<ans;return 0;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]>=1&&a[i][j]<=min(n,m)){int t=a[i][j],c=min(i,j),v=a[t][t];//要想成为不动点，可以换到(t,t)~(t,m) or (t,t)~(n,t)//换过来成为不动点，要求值满足v==cif(i!=t||j!=t){if(v==c&&v==t)h=max(h,1);else if(v==c&&v!=t)h=2;else if(v!=c&&v!=t)h=max(h,1);else if(v!=c&&v==t)h=max(h,0);}for(int k=t+1;k<=m;k++){if(i!=t||j!=k){v=a[t][k];if(v==c&&v==t)h=max(h,1);else if(v==c&&v!=t)h=2;else if(v!=c&&v!=t)h=max(h,1);else if(v!=c&&v==t)h=max(h,0);}}for(int k=t+1;k<=n;k++){if(i!=k||j!=t){v=a[k][t];if(v==c&&v==t)h=max(h,1);else if(v==c&&v!=t)h=2;else if(v!=c&&v!=t)h=max(h,1);else if(v!=c&&v==t)h=max(h,0);}}}}}cout<<min(ans+h,n*m);return 0;
}

上面这张图，以10✕7矩阵为例，表示每个点要是不动点需要的值。

我们考虑一下所有增加不动点数量的交换方式。

初步思考，可能增加不动点数量的交换无非三种情况：

1. 两个非不动点->一个不动点，一个非不动点 不动点数+1
2. 两个非不动点->两个不动点 不动点数+2
3. 一个不动点，一个非不动点->两个不动点 不动点数+1

第一种情况如下图：

第二种情况如下图：

如果遇到第二种情况，可以直接断定这就是最优方案，不用再继续下去了。

第三种情况，我们细想一下，两个位置如果在“同一色块”，明显不成立，那么两个位置只能在“不同色块”，但是，这样也不成立，因为之前的不动点必然会变成非不动点，故这种情况并不存在。

也就是说，我们总共只有两种可能：

1. 两个非不动点->一个不动点，一个非不动点 不动点数+1
2. 两个非不动点->两个不动点 不动点数+2

现在我们再仔细讨论一下这种情况的代码具体实现思路。

等一下，先到这里，我要去思考一下了。

---

好了，我又回来了。首先，两种情况讨论的都是非不动点，我们需要一个高效的结构去存储非不动点的信息。

就拿示例2来说吧。

我改了一下代码，通过了88.89%。

#include<bits/stdc++.h>
using namespace std;
int ans,h;
int a[505][505];
set<int> v[505];
signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]==min(i,j))ans++;else v[min(i,j)].insert(a[i][j]);}for(int i=1;i<=min(n,m);i++){for(int e:v[i]){if(v[e].count(i)){h=2;break;}else h=1;}if(h==2)break;}cout<<ans+h;return 0;
}

---

刚又调了一下，终于过了！

#include<bits/stdc++.h>
using namespace std;
int ans,h;
int a[505][505];
set<int> v[505];
signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]==min(i,j))ans++;else v[min(i,j)].insert(a[i][j]);}for(int i=1;i<=min(n,m);i++){for(int e:v[i]){if(v[e].count(i)){h=2;break;}else if(v[e].size())h=1;}if(h==2)break;}cout<<ans+h;return 0;
}

参考：【题解】牛客周赛 Round 104_ICPC/CCPC/NOIP/NOI刷题训练题单_牛客竞赛OJ