题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1709

题目描述

Now you are asked to measure a dose of medicine with a balance and a number of weights. Certainly it is not always achievable. So you should find out the qualities which cannot be measured from the range [1,S]. S is the total quality of all the weights.

思路

大意是给一堆砝码和一个天平,求出在$[1,S]$中不能称出的重量,S为所有砝码的重量和。

因为天平两端都可以发砝码,所以母函数是这样的。

$$\left(1+x^{A_1}+x^{\frac{1}{A_1}}\right) \left(1+x^{A_2}+x^{\frac{1}{A_2}}\right) \dots \left(1+x^{A_N}+x^{\frac{1}{A_N}}\right)$$

展开后,系数为0(即缺项)的即不能称出的重量。

AC代码

/*************************************************************************
    > File Name: 1709.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-03 Fri 23:32:32 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int _max = 100*100;

int main()
{
#ifdef Oj
    freopen("1709.in", "r", stdin);
#endif
    int c1[_max+1], c2[_max+2];
    int A[101];
    int N;
    while(cin >> N) {
        for(int i=1; i<=N; ++i)
            cin >> A[i];
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
        c1[0] = 1;
        c1[A[1]] = 1;
        int count = A[1];
        for(int i=2; i<=N; ++i) {
            count+=A[i];
            for(int j=0; j<=count; ++j)
                for(int k=0;(j+k<=count) && (k<=A[i]); k+=A[i]) {
                    c2[j+k] += c1[j];
                    c2[abs(j-k)] += c1[j]; // 注意这里有项是$\left| j-k\right|$
                }
            for(int j=0; j<=count; ++j) {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }

        int no = 0;
        for(int i=0; i<=count; ++i)
            if(c1[i] == 0)
                ++no;
        cout << no << endl;
        if(no) {
            bool flag=true;
            for(int i=0; i<=count; ++i) {
                if(c1[i] == 0) {
                    if(flag) printf("%d", i), flag=false;
                    else printf(" %d", i);
                }
            }
            puts("");
        }

    }
    return 0;
}