http://codeforces.com/contest/370/problem/B
题意 ：呃，这个题我说不清楚。。。。就是有n个人，第 i 个人手里有 mi 张牌，如果，现在主人念数，念到哪张牌谁就把哪张删掉，最后谁手里没有了谁就赢，如果同时没有了，两个人都输都输出no，最重要的是Write a program that determines whether a player can win the game at the most favorable for him scenario or not.这句话，意思是说每个人都按照每个人想要的哪种方式去念牌，根据样例，第一个人手里有1张牌，是1，第二个人手里有3张牌，分别是2 4 1，第三个人手里2张牌，分别是10和11，按照第一个人想自己赢的方式念牌，应该念1，所以他没有牌了，它可以赢，而对于第二个人来讲，无论怎么念，要么1赢他输，要么两个人全输，而对于第三个人来讲，先念10再念11就可以赢。
思路：这个题，挺坑的。。。。表示交了好几遍呢。。。。这个明白点就是找子集呢，如果第 i 个人手里的牌在第 j 个人手里全有，并且还有别的牌，那么第 i 个人就可以赢，而第 i 个人一定输，所以就是判断子集包含。。。。
#include <iostream> #include <stdio.h> #include <vector> using namespace std ; bool contains(vector<int>a,vector<int>b)//b in a? {for(int i = 0 ; i < b.size() ; i++){bool in = false ;for(int j = 0 ; j < a.size() ; j++){if(a[j] == b[i])in = true ;}if(!in)return false ;}return true ; } int main() {int n ;vector<int>a[110] ;while(~scanf("%d",&n)){int m,h ;for(int i = 0 ; i < n ; i++){scanf("%d",&m) ;a[i].clear() ;for(int j = 0 ; j < m ; j++){scanf("%d",&h) ;a[i].push_back(h) ;}}int flag[110];for(int i = 0 ; i < 110 ; i++)flag[i] = 1 ;for(int i = 0 ; i < n ; i++){for(int j = 0 ; j < n ; j++){if(i==j) continue;if(contains(a[j],a[i])){flag[j] = 0 ;if(a[i].size() == a[j].size())flag[i] = 0;}}}for(int i = 0 ; i < n ; i++)if(flag[i]) cout<<"YES"<<endl;else cout<<"NO"<<endl ;}return 0 ; }
这个是二师兄写的非vector 的
#include <algorithm> #include <iostream> #include <string.h> #include <stdio.h> #include <string> #define M 10010 #define INF 1 << 30;using namespace std;int f[1010][1010]; int main() {int n, i, j, m[M], k, t;int dp[1010];memset(dp , 0 , sizeof(dp));cin >>n;for(i = 0; i < n; i++){cin >>m[i];for(j = 0; j < m[i]; j++)cin >>f[i][j];sort(f[i], f[i]+m[i]);}for(i = 0; i < n-1; i++){for(j = i+1; j < n; j++){if(m[i] >= m[j]){t = 0;for(k = 0; k < m[i]; k++){if(f[i][k] == f[j][t])t++;}if(t >= m[j])dp[i] = 1;if(m[j] == m[i] && t >= m[j])dp[j] = 1;}else{t = 0;for(k = 0; k < m[j]; k++)if(f[i][t] == f[j][k])t++;if(t >= m[i])dp[j] = 1;}}}for(i = 0; i < n; i++){if(!dp[i])cout <<"YES"<<endl;elsecout <<"NO"<<endl;}return 0; }
