codeforces Educational Codeforces Round 80 (Rated for Div. 2) D - Minimax Problem(状压)
程序员文章站
2022-06-04 18:15:55
...
思路:见注释
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int ans1,ans2,n,m,pos[maxn],a[maxn][9];
bool check(int x)
{
memset(pos,0,sizeof(pos));//pos记录的是状压后的值的行数位置
for(int i=1;i<=n;++i)
{
int t=0;
for(int j=1;j<=m;++j)
if(a[i][j]>=x)
t|=(1<<(j-1));//给每一行进行状压
pos[t]=i;//状压后的值可能会有重复,但我们随便记录一行就行,对ac无影响
}
// 假设最后状压后n列是这样的
// 10110(22)
// 11000(24)
// 10000(16)
// 10101(21)
// 11001(25)
// 然后你会发现第一个和最后一个相与(也就是22和25)相与后的二进制位11111(这个就表示这一列上所有的元素都满足大于x,即为答案
for(int i=0;i<(1<<m);++i)
for(int j=0;j<(1<<m);++j)
if(pos[i]&&pos[j]&&((i|j)==(1<<m)-1))
{
ans1=pos[i],ans2=pos[j];//我们不需要遍历所有n,因为发现相与后它的数值肯定不超过1<<m,结果就是1到1<<m内的数两两相与是否满足全为1(也就是(1<<m)-1)即可
return true;
}
return false;
}
int main()
{
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=1e9;
while(l<=r)//二分答案
{
int mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
printf("%d %d\n",ans1,ans2);
}
上一篇: 单链表排序----快排 & 归并排序
下一篇: 果博东方开户scc2339
推荐阅读
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
D. Sequence and Swaps(模拟+枚举) Educational Codeforces Round 99 (Rated for Div. 2)
-
Educational Codeforces Round 91 (Rated for Div. 2) D. Berserk And Fireball
-
Educational Codeforces Round 83 (Rated for Div. 2) D. Count the Arrays
-
codeforces Educational Codeforces Round 80 (Rated for Div. 2) D - Minimax Problem(状压)
-
Educational Codeforces Round 80 (Rated for Div. 2)
-
Codeforces Educational Codeforces Round 80 (Rated for Div. 2) E - Messenger Simulator(树状数组+思维)
-
Educational Codeforces Round 63 (Rated for Div. 2)-D
-
Educational Codeforces Round 80 (Rated for Div. 2) 题解
-
Educational Codeforces Round 93 (Rated for Div. 2) A~D