互联网站备案登记表,深圳网络优化,网站设计深圳哪家强?,搜狗网址大全下载安装传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你nnn个长度为mmm的数组#xff0c;选出两个来#xff0c;让他们每一位取maxmaxmax构成新数组bbb#xff0c;让后最大化bbb的最小值。
思路#xff1a;
看到m8m8m8#xff0c;也就是每个数组长度为…传送门
文章目录题意思路题意
给你nnn个长度为mmm的数组选出两个来让他们每一位取maxmaxmax构成新数组bbb让后最大化bbb的最小值。
思路
看到m8m8m8也就是每个数组长度为mmm很容易想到状压。由于要最大化最小值我们不妨二分这个最小值让后将nnn个数组状压成一个二进制midmidmid的位置为111否则为000。这个时候我们只需要找出两个数使其取或后[0,m−1][0,m-1][0,m−1]的每一位都是111即可。 我们发现只需要记录一下当前状态对应的编号让后28∗282^{8}*2^{8}28∗28枚举状态让后判断(i∣j)(1m)−1(i|j)(1m)-1(i∣j)(1m)−1即可。 复杂度O(max(nm,22m)∗log(1e9))O(max(nm,2^{2m})*log(1e9))O(max(nm,22m)∗log(1e9)) 如果mmm很大怎么办有没有更好的方法呢当然是有的。 假设我们知道了状态110101110101110101那么我们只需要看一下是否存在001010001010001010即可。而这个状态有可能是某个状态的子集我们不能对于每数都将其子集暴力的加入这样复杂度会爆掉的看到大佬有一个好的方法来递推求子集。我们从(1m)−1(1m)-1(1m)−1开始记为nownownow让后遍历[0,m−1][0,m-1][0,m−1]记为jjj看一下now∣(1j)now|(1j)now∣(1j)是否存在存在的话就说明他是now∣(1j)now|(1j)now∣(1j)的一个子集就直接继承now∣(1j)now|(1j)now∣(1j)的信息即可。这样递推的复杂度为2m∗m2^m*m2m∗m显然更加的优秀。
复杂度O(max(nm,2m∗m)∗log(1e9))O(max(nm,2^{m}*m)*log(1e9))O(max(nm,2m∗m)∗log(1e9))
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N][10];
int id[1010],ans1,ans2;
bool flag;bool check(int mid)
{memset(id,0,sizeof(id));for(int i0;in;i){int now0;for(int j0;jm;j)if(a[i][j]mid) now(1j);id[now]i1;}int tot(1m);for(int itot-1;i0;i--)for(int j0;jm;j)if(id[i|(1j)])id[i]id[i|(1j)];for(int itot-1;i0;i--)if(id[i]id[i^(tot-1)]){ans1id[i];ans2id[i^(tot-1)];return true;}return false;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i0;in;i) for(int j0;jm;j) scanf(%d,a[i][j]);int l0,r1e9,ans;while(lr){int midlr1;if(check(mid)) lmid1;else rmid-1;}printf(%d %d\n,ans1,ans2);return 0;
}
/**/
复杂度O(max(nm,22m)∗log(1e9))O(max(nm,2^{2m})*log(1e9))O(max(nm,22m)∗log(1e9))
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N][10];
int id[1010],ans1,ans2;
bool flag;bool check(int mid)
{memset(id,0,sizeof(id));for(int i0;in;i){int now0;for(int j0;jm;j)if(a[i][j]mid) now(1j);id[now]i1;}for(int i0;i(1m);i)for(int j0;j(1m);j)if(id[i]id[j](i|j)((1m)-1)){ans1id[i],ans2id[j];return true;}return false;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i0;in;i) for(int j0;jm;j) scanf(%d,a[i][j]);int l0,r1e9,ans;while(lr){int midlr1;if(check(mid)) lmid1;else rmid-1;}printf(%d %d\n,ans1,ans2);return 0;
}
/**/
