題目鏈接：點擊查看

題目大意：給出一個n*m的矩陣，我們用maze[n][m]來表示每一個元素，現在我們需要選出其中 i 和 j 兩行，i 和 j 可以相同，用這兩行的元素構成一個新的數組a，構造規則為a[k]=max(maze[i][k],maze[j][k])，現在我們要使數組a中的最小值最大，請問該如何選擇 i 和 j 才能滿足條件

題目分析：讀完題目后感覺亂糟糟的，但靜下心來分析一下，要求最小值的最大值，顯然的二分，所以我們很直接的確定下來要對于數組a的最小值進行二分了，但check函數該怎么寫是我們接下來需要考慮的問題了，其實當我們確定下來了最小值之后，就相當于對原矩陣構成了一種約束條件，換句話說，原矩陣中值小于當前限制的元素，我們是無法選擇的了，不然最后構成的數組a中的最小值就無法保證為當前二分的答案了，有了這樣一個轉換后，我們就可以將原矩陣中大于當前二分的答案的位置都置為1，其余位置置為0，這樣就很自然的進行了狀態壓縮，因為每一行的元素都是綁定的，也就是對于某一行來說，我們只能選擇或者不選，這樣又是一種標準的枚舉子集，我們再看一眼數據范圍，發現m最大只有7，我們如果以枚舉子集的形式來確定 i 和 j 的話，時間復雜度最大也只有2^14，所以我們可以直接兩層for循環枚舉子集狀態，找到一種 i 和 j 的情況，滿足其能覆蓋整個子集就好了，具體實現看代碼吧，代碼寫的比較清楚了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=3e5+100;int a[N][8],vis[N],ans1,ans2,n,m;bool check(int x) {memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){int val=0;for(int j=1;j<=m;j++)if(a[i][j]>=x)val|=1<<(j-1);//狀態壓縮vis[val]=i;//標記狀態}for(int i=0;i<(1<<m);i++)//枚舉i的狀態if(vis[i])for(int j=0;j<(1<<m);j++)//枚舉j的狀態if(vis[j])if((i|j)==(1<<m)-1){ans1=vis[i];ans2=vis[j];return true;}return false; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);int l=0,r=inf;while(l<=r)//二分最小值{int mid=l+r>>1;if(check(mid))l=mid+1;elser=mid-1;}printf("%d %d\n",ans1,ans2);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1288D Minimax Problem(二分+状态压缩)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。