青岛 外语网站建设,百度四川建设厅网站,三水建设局网站,如何向搜索引擎提交网站文章目录题意思路传送门
题意
给你nnn个长度为mmm的数组#xff0c;每个数组都有一个价值wiw_iwi#xff0c;让你选出两个数组他们没有交集且价值和最大#xff0c;如果没有输出−1-1−1。 2≤n≤1e5,1≤m≤5,1≤ai,j,wi≤1e92\le n\le 1e5,1\le m\le 5,1\le a_{i,j},w_…
文章目录题意思路传送门
题意
给你nnn个长度为mmm的数组每个数组都有一个价值wiw_iwi让你选出两个数组他们没有交集且价值和最大如果没有输出−1-1−1。
2≤n≤1e5,1≤m≤5,1≤ai,j,wi≤1e92\le n\le 1e5,1\le m\le 5,1\le a_{i,j},w_i\le 1e92≤n≤1e5,1≤m≤5,1≤ai,j,wi≤1e9
思路
看到mmm很小很容易向状压地方靠假设aaa很小那么这个题就很简单了我们将每个数组状压成一个二进制让后sosdpsosdpsosdp求一下子集最小值让后遍历即可获得答案。
但是这个题aaa高达1e91e91e9但是我们发现其最终答案是一对之间那么我们将aaa随机映射到0−150-150−15之间的某个数注意同一个数一定映射到相同数不同数可能映射到相同数我们发现这样操作后对于答案的两个数组他们都映射到不同数上的概率为0.01880.01880.0188这也是答案正确的概率虽然这个数很小但是我们运行200200200次期望概率就达到222以上了基本可以认为是正确的。
复杂度P(250∗16∗(116))P(250*16*(116))P(250∗16∗(116))
tricktricktrick遇到很大的数可以将其映射到小范围的数上进行乱搞。
#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
#pragma GCC optimize(2)
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N500010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;int n,m;
int a[N][6],w[N];
int b[N][6];
int f[121];
mt19937 rnd(time(0));
int mp[N],id[N];
vectorintv;template class T
bool read(T ret)//输入
{char c;int sgn;T bit0.1;if(cgetchar(), cEOF)return 0;while(c!- c!. (c0 || c9))cgetchar();sgn(c-)? -1:1;ret(c-)? 0:(c-0);while(cgetchar(), c0 c9)retret*10(c-0);if(c || c\n){ret*sgn;return 1;}while(cgetchar(), c0 c9)ret(c-0)*bit, bit/10;ret*sgn;return 1;
}int find(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin();
}void solve() {read(n); read(m);for(int i1;in;i) {for(int j1;jm;j) {read(a[i][j]);v.pb(a[i][j]);}read(w[i]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i1;in;i) {for(int j1;jm;j) {a[i][j]find(a[i][j]);}}srand(20000926);int ans2e97;for(int _1;_250;_) {for(int i0;iN;i) id[i]rand()%16;memset(f,0x3f,sizeof(f));for(int i1;in;i) {int state0;for(int j1;jm;j) {b[i][j]id[a[i][j]];state|1b[i][j];}f[state]min(f[state],w[i]);}int all116;for(int j0;j16;j) {for(int i0;iall;i) {if(!(ij1)) f[i|(1j)]min(f[i|(1j)],f[i]);}}for(int i0;iall;i) {int j(all-1)^i;if(f[i]!0x3f3f3f3ff[j]!0x3f3f3f3f) ansmin(ans,f[i]f[j]);}}printf(%d\n,ans2e97? -1:ans);
}int main() {LL f1,f2;f1f21;for(int i15;i15-101;i--) f1*i;for(int i1;i10;i) f2*15;printf(%.10f\n,1.0*f1/f2);int _1;while(_--) {solve();}return 0;
}
