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 = ; i < b.size() ; i++)
{
bool in = false ;
for(int j = ; j < a.size() ; j++)
{
if(a[j] == b[i])
in = true ;
}
if(!in)
return false ;
}
return true ;
}
int main()
{
int n ;
vector<int>a[] ;
while(~scanf("%d",&n))
{
int m,h ;
for(int i = ; i < n ; i++)
{
scanf("%d",&m) ;
a[i].clear() ;
for(int j = ; j < m ; j++)
{
scanf("%d",&h) ;
a[i].push_back(h) ;
}
}
int flag[];
for(int i = ; i < ; i++)
flag[i] = ;
for(int i = ; i < n ; i++)
{
for(int j = ; j < n ; j++)
{
if(i==j) continue;
if(contains(a[j],a[i]))
{
flag[j] = ;
if(a[i].size() == a[j].size())
flag[i] = ;
}
}
}
for(int i = ; i < n ; i++)
if(flag[i]) cout<<"YES"<<endl;
else cout<<"NO"<<endl ;
}
return ;
}
这个是二师兄写的非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[][];
int main()
{
int n, i, j, m[M], k, t;
int dp[];
memset(dp , , sizeof(dp));
cin >>n;
for(i = ; i < n; i++)
{
cin >>m[i];
for(j = ; j < m[i]; j++)
cin >>f[i][j];
sort(f[i], f[i]+m[i]);
}
for(i = ; i < n-; i++)
{
for(j = i+; j < n; j++)
{
if(m[i] >= m[j])
{
t = ;
for(k = ; k < m[i]; k++)
{
if(f[i][k] == f[j][t])
t++;
}
if(t >= m[j])
dp[i] = ;
if(m[j] == m[i] && t >= m[j])
dp[j] = ;
}
else
{
t = ;
for(k = ; k < m[j]; k++)
if(f[i][t] == f[j][k])
t++;
if(t >= m[i])
dp[j] = ;
}
}
}
for(i = ; i < n; i++)
{
if(!dp[i])
cout <<"YES"<<endl;
else
cout <<"NO"<<endl;
}
return ;
}