POJ 1742 Coins-白红宇

POJ 1742 Coins

阅读量：2125 次

发布时间：2019-04-30

本文共 1257 字，大约阅读时间需要 4 分钟。

题意

给出N个硬币和数量，求一共可以组合成几种情况

AC

bitset
用二进制的下标表示和，最后1的个数表示种类数
优化：用二次方移动加快速度
例如：

移动7次（需要4次）

1.0000 0000 1

2.0000 0001 1 移动1，剩余6

3.0000 0111 1 移动2，剩余4

4.0111 1111 1 移动4，剩余0

移动10次（需要5次）

1.0000 0000 0000 1

2.0000 0000 0001 1 移动1，剩余9

3.0000 0000 0111 1 移动2，剩余7

4.0000 0111 1111 1 移动4，剩余3

剩余3

0011 1111 1111 1 移动3，剩余0

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define N 1000015#define P pair
            
             #define ll long long#define mk(a, b) make_pair(a, b)#define mem(a, b) memset(a, b, sizeof(a))using namespace std;bitset<100005> a;int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif int n, m; while (cin >> n >> m, n + m) { a.reset(); vector
              v(n); for (int i = 0; i < n; ++i) { cin >> v[i].first; } for (int i = 0; i < n; ++i) { cin >> v[i].second; } a[0] = 1; // for (int i = 0; i < n; ++i) { // for (int j = 1; j <= v[i].second; ++j) { // a |= a << (v[i].first); // } // } for (int i = 0; i < n; ++i) { // 每次移动2的次方，这样可以加快速度 log for (int j = 1; j <= v[i].second; j <<= 1) { v[i].second -= j; a |= a << (j * v[i].first); } a |= a << (v[i].second * v[i].first); } int ans = 0; for (int i = 1; i <= m; ++i) { if (a[i] == 1) ans++; } cout << ans << endl; } return 0;}