2015
02-22

# Equivalent mass

Little Min’s family has a grocery store，and she helps her parents to weight the goods everyday. She often wants to know whether the quality of the goods they sell can be equal to the sum quality of several poise weights. Suppose there are N kinds of poise weights, but there are M pairs of them can’t be used at the same time, and we know the quality of the goods is V. The question is: can little Min exactly take K form N poise weights, and their sum quality is equal to the goods’ quality?

The first line contains an integer T, the number of test cases (T < 25). Each test case is in the following format.The first line starts with four integers N (1 <= N <= 32) denoting the number ofpoise weights and M (0 <= M <= 6),K(1<=K<=N),V(1<=V<=1000000000). The second line has N integer ai each denoting the kind poise weight’s quality(1<=i<=N,1<=ai<=1000000000).Then following M lines, each line has two integers a and b, which denoting the a-th poise weight can’t be used with the b-th poise weight at the same time(1<=a,b<=N,a!=b).

The first line contains an integer T, the number of test cases (T < 25). Each test case is in the following format.The first line starts with four integers N (1 <= N <= 32) denoting the number ofpoise weights and M (0 <= M <= 6),K(1<=K<=N),V(1<=V<=1000000000). The second line has N integer ai each denoting the kind poise weight’s quality(1<=i<=N,1<=ai<=1000000000).Then following M lines, each line has two integers a and b, which denoting the a-th poise weight can’t be used with the b-th poise weight at the same time(1<=a,b<=N,a!=b).

2
5 1 3 1000
100 200 300 500 600
2 3
5 2 3 1000
100 200 300 500 600
2 3
1 5

YES
NO

#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
map<int,int> hash[35];
int vis[35];
int n,v,k;
int flag;
int constraint;
int g[35][35];
struct node
{
int w;
int cons;
}t[35],s[35];
void dfs(int y,int x,int cur)
{
if(y>k) return;
else if(x==constraint) hash[y][cur]=1;
else
{
int tt=0;
if(s[x].cons!=-1)
{
for(int i=0;i<n;i++) if(g[x][i])
{
if(vis[i])
{
tt=1;
break;
}
}
}
if(s[x].cons==-1||!tt)
{
vis[x]=1;
dfs(y+1,x+1,cur+s[x].w);
vis[x]=0;
}
dfs(y,x+1,cur);
}
}
void dfs2(int y,int x,int cur)
{
if(y>k) return;
else if(x==n)
{
if(hash[k-y][v-cur]==1)
{
flag=1;
return;
}
}
else if(!flag)
{
dfs2(y+1,x+1,cur+s[x].w);
dfs2(y,x+1,cur);
}
}
int main()
{
int i,j;
int T;
int m;
int mark[35];
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&m,&k,&v);
for(i=0;i<n;i++)
{
scanf("%d",&t[i].w);
t[i].cons=-1;
s[i].cons=-1;
}
int cnt=0;
memset(mark,-1,sizeof(mark));
memset(g,0,sizeof(g));
for(i=0;i<m;i++)
{
int t1,t2;
int c1,c2;
scanf("%d%d",&t1,&t2);
t1--;
t2--;
if(mark[t1]==-1) mark[t1]=cnt++;
if(mark[t2]==-1) mark[t2]=cnt++;
c1=mark[t1];
c2=mark[t2];
s[c1].cons=c2;
s[c1].w=t[t1].w;
t[t1].cons=t2;
t[t2].cons=t1;
s[c2].cons=c1;
s[c2].w=t[t2].w;
g[c1][c2]=1;
g[c2][c1]=1;
}
if(cnt>n/2) constraint=cnt;
else constraint=n/2+1;
for(i=0;i<n;i++) if(t[i].cons==-1)
{
s[cnt++]=t[i];
}
for(i=0;i<=k;i++)
hash[i].clear();
memset(vis,0,sizeof(vis));
dfs(0,0,0);
flag=0;
dfs2(0,constraint,0);
if(flag) printf("YES\n");
else printf("NO\n");
}
}

1. 因为是要把从字符串s的start位到当前位在hash中重置，修改提交后能accept，但是不修改居然也能accept

2. int L[m+1][n+1];这样定义出错，这个在gcc上可以编译通过 在VS上不行 应该改为new 或者vector

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮