首页 > ACM题库 > HDU-杭电 > hdu 1951 Vase collection-数论-[解题报告]C++
2013
12-26

hdu 1951 Vase collection-数论-[解题报告]C++

Vase collection

问题描述 :

Mr Cheng is a collector of old Chinese porcelain, more specifically late 15th century Feng dynasty vases. The art of vase-making at this time followed very strict artistic rules. There was a limited number of accepted styles, each defined by its shape and decoration. More specifically, there were 36 vase shapes and 36 different patterns of decoration � in all 1296 different styles.

For a collector, the obvious goal is to own a sample of each of the 1296 styles. Mr Cheng however, like so many other collectors, could never afford a complete collection, and instead concentrates on some shapes and some decorations. As symmetry between shape and decoration was one of the
main aestheathical paradigms of the Feng dynasty, Mr Cheng wants to have a full collection of all combinations of k shapes and k decorations, for as large a k as possible. However, he has discovered that determining this k for a given collection is not always trivial. This means that his collection might actually be better than he thinks. Can you help him?

输入:

On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer m <=100 , the number of vases in the collection. Then follow m lines, one per vase, each with a pair of numbers, si and di, separated by a single space, where si ( 0 < i <= 36 ) indicates the shape of Mr Cheng’s i:th vase, and di ( 0 < i <=36 ) indicates its decoration.

输出:

On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer m <=100 , the number of vases in the collection. Then follow m lines, one per vase, each with a pair of numbers, si and di, separated by a single space, where si ( 0 < i <= 36 ) indicates the shape of Mr Cheng’s i:th vase, and di ( 0 < i <=36 ) indicates its decoration.

样例输入:

2
5
11 13
23 5
17 36
11 5
23 13
2
23 15
15 23

样例输出:

2
1

题意:n个瓶子,每个瓶子有形状颜色两种属性,且这两种属性都有36个类型,告诉你这些瓶子的两种属性的类型,求最大的k满足存在k*k个瓶子,使得这些瓶子的两种属性有k个类型,且覆盖了k*k个属性组合

题解:state[a]是形状为a的覆盖的颜色的状态集(用二进制表示),state[a]&state[b]就是这两个形状都覆盖的颜色,如果这数的二进制位有大于等于2个1,就代表可以组成k=2的符合要求的答案。记录state[a]&state[b],与第三个形状进行按位与,如果有大于等于3个1,就是可以k=3…….注意别搜重了,由于m只有不超过100,所以最多也就搜10层。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int ans;
LL state[200];
int check(LL st)
{
    int cnt=0;
    for(;st;st>>=1)
        cnt+=(st&1);
    return cnt;
}
void dfs(int k,int i,LL st)
{
    if(k>=ans)
        ans=k;
    for(;i<=36;i++)
    {
        if(check(st&state[i])>=k+1)
            dfs(k+1,i+1,st&state[i]);
    }
}
int main()
{
    int n,T;
    for(scanf("%d",&T);T;T--)
    {
        scanf("%d",&n);
        ans=0;
        memset(state,0,sizeof(state));
        for(int i=0,a,b;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            state[a]|=(1LL<<b);
        }
        dfs(0,1,(1LL<<36)-1);
        printf("%d\n",ans);
    }
    return 0;
}

解题转自:http://blog.csdn.net/tmeteorj/article/details/8783574


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. [email protected]