D. The Strongest Build二叉堆，map乱搞

D. The Strongest Build二叉堆，map乱搞

Link
题意：
给定n个序列，要从每个序列选出一个数，价值为选出来的总和，然后有m个限制，代表m个序列不能用，求最大值 n < = 10 ∑ c i < = 2 e 5 m < = 2 e 5 n<=10 sum~ci<=2e5~m<=2e5 n<=10∑ ci<=2e5 m<=2e5
思路：
一开始想着类似于n路尺取，也就是先把所有最大值放进堆里，然后每次尺取花费最小的，然后会发现会漏掉某些情况。正解是暴力bfs，因为m<=2e5也就是我们最多从最后搜2e5+1次就可以搜到最优解，考虑n<=10我们可以用map记录vector，每次剪枝，如果搜索过就不要再搜该值。复杂度 O ( m ∗ 10 ∗ l o g ( 10 ) ∗ 10 ) O(m*10*log(10)*10) O(m∗10∗log(10)∗10)，还好给的三秒，但貌似哈希能优化到掉一个n？

//#pragma GCC target("avx")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
// created by myq
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef pair<int,int> pii;
const int N = 400010;
const int mod=1e9+7,mod2=1e9+9;
inline int read()
{int res=0;int f=1;char c=getchar();while(c>'9' ||c<'0'){if(c=='-')	f=-1;c=getchar();}while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+c-'0';}return res;}
ll a[N];	
vector<int>v[N];
map<vector<int>,int>mp;
typedef pair<int,vector<int>>	piv;
const int bas=13331;
const int bas2=233333;
int p[11];
int p1[11];
struct node{int a;int b;int c;bool operator<(const node&w)const{return a>w.a;}
};int main()
{ios::sync_with_stdio(0);int _;
//	cin>>_;_=1;while(_--){int n;cin>>n;for(int i=0;i<n;i++){int k;cin>>k;while(k--){int x;cin>>x;v[i].push_back(x);}}int m;cin>>m;while(m--){ll tt=0;ll tt2=0;vector<int>v;for(int i=1;i<=n;i++){int x;cin>>x;x--;v.push_back(x);}mp[v]=true;}vector<int>dd;int ans=0;map<vector<int>,int>st;for(int i=0;i<n;i++){dd.push_back((int)v[i].size()-1);ans+=v[i].back();//return 0;}	priority_queue<piv>q;q.push({ans,dd});st[dd]=true;while(q.size()){auto tt&#p();q.pop();
//			for(auto j:tt.y)
//			cout<<j<<" ";
//			cout<<endl;
//			cout<<tt.x<<"qwq"<<endl; if(!mp.count(tt.y))	{dd=tt.y;break;}int now=tt.x;auto vv=tt.y;for(int i=1;i<=n;i++){if(vv[i-1]>=1){now-=v[i-1][vv[i-1]];vv[i-1]--;unt(vv)){vv[i-1]++;now+=v[i-1][vv[i-1]];continue;}now+=v[i-1][vv[i-1]];
//					cout<<now<<endl;q.push({now,vv});now-=v[i-1][vv[i-1]];st[vv]=1;vv[i-1]++;now+=v[i-1][vv[i-1]];}}}for(auto j:dd)cout<<j+1<<" ";cout<<"n";} return 0;}
/**
3
3 1 2 3
3 1 2 3
3 1 2 3
21
2 2 1
3 3 1
2 3 1
3 2 1
3 1 1
3 1 3
2 2 2
3 2 3
3 3 2
2 2 3
2 1 1
1 3 2
2 3 3
1 1 3
1 2 1
1 3 1
1 1 1
1 3 3
2 1 3
1 1 2
3 3 3
**/