本场比赛较简单，恭喜xcy58神仙和chengxx神仙AK（热烈祝贺）。
T1 水
这题应该不难看出求n个瓶子最少可以合并为几个瓶子就是求二进制下的n有多少个1。
然后就完了……每次增加一些瓶子，让新瓶子数在二进制一的数量下比原来的少就好。
#include<iostream>
using namespace std;
unsigned long long n,a,b,shu=0,k=0;
int main()
{
cin>>a>>b;
while(1)
{
n=a;
shu=0;
while(n!=0)
{
if(n%2==1)
{
shu++;
}
n/=2;
}
if(shu<=b)
{
cout<<k<<endl;
return 0;
}
k+=(a&-a);
a+=(a&-a);
}
return 0;
}
（没用scanf，大佬轻喷）
T2 朋友
简单并查集，模板题……
话说这题洛谷数据超级水，我故意写了好几个错的，洛谷全是满分（啊这）
直接贴代码了
#include<iostream>
using namespace std;
int z,n,m,a1,a2,a3,sz[1000005];
int h(int zz)
{
if(sz[zz]==zz)return zz;
return sz[zz]=h(sz[zz]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
sz[i]=i;
}
for(int i=0;i<m;i++)
{
cin>>a1>>a2>>a3;
if(a1==1)
{
sz[h(a2)]=h(a3);
}
else if(a1==2)
{
if(h(a2)==h(a3))
{
cout<<"Y"<<endl;
}
else
{
cout<<"N"<<endl;
}
}
}
return 0;
}
T3 托盘天平
啊这题我原来的标程写错了，导致数据错了一个点，重新翻看后发现深搜写的有点弱智……现在改对了，还能当题解……
这题觉得需要简单的讲一下，他需要用到dp和dfs，dfs有两种搜法，搜剩下的和搜去掉的，看看数据范围就能发现搜去掉的显然比搜剩下的不知道快多少……然后就爆搜求出哪些砝码被去掉了，然后是dp，dp的话用sz数组表示这个数有没有出现过，转移方程也不难，那个bl是用来加速的，从之前出现过最大的开始向下搜比从所有可能里最大的往下搜要快。然后……就完了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long a[30],bj[30],c[30],sz[4000];
long long int n,m;
long long jg=0;
long long ans=0;
long long zlzs=0;
long long bl=0;
void dp()
{
memset(sz,0,sizeof(sz));
sz[0]=1;
zlzs=0;
bl=0;
for(int i=1;i<=n;i++)
{
if(bj[i]==0)
{
for(int j=bl;j>=0;j--)
{
if(sz[j]==1&&sz[j+a[i]]==0)
{
sz[j+a[i]]=1;
zlzs++;
}
}
bl+=a[i];
}
}
jg=max(jg,zlzs);
}
void dfs(long long wz,long long shu)
{
if(shu>m)return;
if(wz==n+1)
{
if(shu==m)dp();
return;
}
dfs(wz+1,shu);
bj[wz]=1;
dfs(wz+1,shu+1);
bj[wz]=0;
return;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
dfs(1,0);
printf("%lld
",jg);
return 0;
}
T4 购物
啊这个题看看数据范围，n<=16我觉得会有一种感觉，这题不是深搜就是状压，这题是状压。
前缀和记录一下前i个商品的价格之和，便于查找，然后转移，转移的过程中求某个硬币可以买多少个商品是要用二分，要不然（在原题中）会超时。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[30],dp[100005],sz[100005],qzh[100005],zd=-99999999;
long long k,n,ans;
long long jg=0;
void cl(int shu)
{
ans=0;
for(int i=0;i<=k-1;i++)
{
if((shu>>i)%2==0)
{
ans+=a[i];
}
}
zd=max(zd,ans);
}
long long hs(long long zq,long long wz)
{
long long xwz=-1,l=wz+1,r=n-1;
while(l<=r)
{
long long mid=(l+r)/2;
if(qzh[mid]-qzh[wz]<=a[zq])
{
xwz=mid;
l=mid+1;
}else
{
r=mid-1;
}
}
return xwz;
}
int main()
{
scanf("%lld%lld",&k,&n);
for(int i=0;i<k;i++)
{
scanf("%lld",&a[i]);
}
for(int i=0;i<n;i++)
{
scanf("%lld",&sz[i]);
qzh[i]=qzh[i-1]+sz[i];
}
memset(dp,-1,sizeof(dp));
sort(a,a+k);
for(int i=0;i<(1<<k);i++)
{
for(int j=0;j<k;j++)
{
if((i>>j)%2==1)
{
dp[i]=max(dp[i],hs(j,dp[i-(1<<j)]));
}
}
}
for(int i=0;i<(1<<k);i++)
{
if(dp[i]==n-1)
{
cl(i);
}
}
if(zd!=-99999999)
{
cout<<zd<<endl;
}else
{
cout<<-1<<endl;
}
return 0;
}
为我第三题zz的标程道歉