C题:
题意是给你一个无向图,保证无重边,无自环,在每一条边上放一个domino,而且保证对于任意一个点,其边上放的domino的该点一侧的点数相同,然后问你图中能放的domino的最大数量。
思路:
当n<=6时,每一点所连的边的数量最大为5,而domino的点的数量是可以满足的,所以可以保证每条边都能放一个。
n=7时,必然会有一个点的号码和另一个点相同,所以可以枚举所有可能相同的点的,然后减去重复的边,即可,同时找到最小数量的重边,用m减去即可。
代码:
#include <bits/stdc++.h>
using namespace std;
bool vis[8][8];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int a,b,minn=100;
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
vis[a][b]=1;
vis[b][a]=1;
}
if(n<=6)
{
printf("%d\n",m);
continue;
}
for(int i=1;i<=7;i++)
{
for(int j=i+1;j<=7;j++)
{
int cnt=0;
for(int k=1;k<=7;k++)
{
if(vis[i][k]&&vis[j][k])
cnt++;
}
minn=min(minn,cnt);
}
}
printf("%d\n",m-minn);
}
}
D:
想到思路就很简单。题目中x比y优越的要求是,他们所属的集合中只有x会y不会的算法。因此两个人要在同一个集合中,必须满足不存在只有一个人会的算法。
所以,可以先处理出,a[i]出现次数>=2的a[i],用num数组保存起来,那么数组里a[i]值属于num数组的人可以在同一个集合中。
然后,遍历所有的人,找出a[i]值是num数组中a[i]值子集的人,可以保证会他们不会算法的人必定大于1,那么他们也可以加入。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[7050],b[7050];
bool vis[7050];
map<ll,ll>mp1;
map<ll,ll>mp2;
vector<ll>num;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
mp1.clear();
mp2.clear();
num.clear();
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
mp1[a[i]]++;
if(mp1[a[i]]>=2&&(!mp2[a[i]]))
{
num.push_back(a[i]);
mp2[a[i]]=1;
}
}
for(int j=1;j<=n;j++)
scanf("%lld",&b[j]);
ll ans=0;
for(int i=0;i<num.size();i++)
{
for(int j=1;j<=n;j++)
{
if((num[i]|a[j])==num[i]&&!vis[j])
{
ans+=b[j];
vis[j]=1;
}
}
}
printf("%lld\n",ans);
}
return 0;
}