D. The Strongest Build

布满荆棘的人生 2022-08-28 12:59 6阅读 0赞

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

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

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

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

[https://codeforces.com/contest/1574/problem/D][https_codeforces.com_contest_1574_problem_D]

题解：（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: https://codeforces.com/contest/1574/problem/D
    // Memory Limit: 256 MB
    // Time Limit: 3000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    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 slots
    		beg[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 3
    			v[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 3 10 3 1 3 12 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;
    }

[https_codeforces.com_contest_1574_problem_D]: https://codeforces.com/contest/1574/problem/D