D. The Strongest Build

D. The Strongest Build

给 n 个slots，每个slots 有若干个卡片，每个卡片上的数值都可以提升英雄的实力（数值已经升序排好）

告诉你，有一些卡片的序号被banned，不能使用，剩下哪些卡片可以使得英雄的实力总和最大，要求输出卡片的序号。

比如说，第i个slots 有对用三个卡片，第三个卡片被baned ，那么你选择的序号是二，因为二肯定大于等于一。

输出所有的序号，保证一定有答案。

题解：（1）二维数组如果过大，会爆内存

（2）记录一下被baned 的 卡片，用set<vector > 存，有count 函数查找。

（3）记录当前最大的卡片组合，如果被banned 那么 跟新位置，如果没有被banned ，输出。

// Problem: D. The Strongest Build
// Contest: Codeforces - Educational Codeforces Round 114 (Rated for Div. 2)
// URL: 
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor ()
int n, m;
vector<ll> a[12];
set<vector<ll>>S, q;void solve()
{scanf("%d", &n);vector<ll> beg(n+1, 0);rep(i,1,n){int tmp;scanf("%d",&tmp); a[i].resize(tmp+1);rep(j, 1, tmp)scanf("%lld", &a[i][j]);}rep(i,1,n){beg[i] = a[i].size() - 1; // sizeof slotsbeg[0] += a[i][beg[i]]; // sum of the max one}q.insert(beg); // 存了vector，vector里beg[0] 和 每个slot 的最大值// for(auto x : q)// {// for(auto y : x)// {// cout << y << " ";// }	// cout << endl;	// }scanf("%d",&m);rep(i,1,m) {vector<ll> v(n+1);rep(j,1,n) {scanf("%lld", &v[j]);// 3 2 3// 1 2 3v[0] += a[j][v[j]];// a[1][3] + a[2][2] + a[3][3]}S.insert(v);// v[1] = 14// v[2] = 13}// auto xx = *--q.end();// for(auto x : xx)// {// cout << x << endl;// }while(true){auto u = *--q.end(); // 必须是end()-1, 且有个*// u 存的是最大的q.erase(--q.end());// 把最大的删掉if(!S.count(u)) // 假如说不是被baned 那么输出（它就是最大）{rep(i,1,n) printf("%lld ",u[i]); // 注意输出的是位置return ;}int cnt = 0;rep(i,1,n) // 更新最大值, u 是最大值，而且q里没有u{if(u[i] > 1) // u是q（set<vector<ll>>）q是vec[0] 存max总和，和max值{ //为什么是u[i] > 1呢？输出的是位置, 大于1个才更新，小于等于1个不更新auto v = u;  // ！因为每次都是取同样的u，对原来最大的每个slots操作，才10个，复杂度过得去/*13 2 2 310 3 1 312 3 2 2*/--v[i]; // 位置--//cout << v[i] << endl;v[0] += a[i][v[i]] - a[i][v[i]+1]; // 更新最大值// cout << " cnt = " << cnt++ << endl;// for(auto x : v)// {// cout << x << endl;// }q.insert(v);  // 插入set中，下次再判断。}	//cout << endl;		}}
}
int main()
{solve();return 0;
}