AcWing 3417. 蓝桥杯_2021省赛第一场_砝码称重

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 3417. 蓝桥杯_2021省赛第一场_砝码称重原题链接简单

作者：

nxdxml , 2021-04-19 10:58:40 , 所有人可见 , 阅读 6092

33

18

题目

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边。

算法

bitset

2021.5.4更新

首先bitset这个数据结构（蓝桥杯能看帮助文档的）

直接copy我打比赛的时候看的文档
C Bitsets
C Bitsets给程序员提供一种位集合的数据结构。Bitsets使用许多二元操作符，比如逻辑和，或等。

Constructors 创建新bitsets
Operators 比较和赋值bitsets
any() 如果有任何一个位被设置就返回true
count() 返回被设置的位的个数
flip() 反转bits中的位
none() 如果没有位被设置则返回true
reset() 清空所有位
set() 设置位
size() 返回可以容纳的位的个数
test() 返回指定位的状态
to_string() 返回bitset的字符串表示
to_ulong() 返回bitset的整数表示

一些解释

|能让状态不重
先<<再>>状态不漏
状态一定合法，>>时不合法的状态都是<0(对应重物质量<0)的，bitset不记录负的。
<<| 只放一边，>>|更新出重物边放砝码的所有状态
>>| 将一些砝码放在另一边，由于此时砝码边的所有状态都有了，在右边放一个g[i],不会出现大于g[i]的状态无法转移过来的，有人可能会认为由于g[i]不是有序的，这么干会让一些状态丢失，实则不会这样，因为所有状态的祖先都已经被更新出来，就类似<<时的s[0] = 1，顺序就无所谓了。

#include<iostream>
#include<bitset>
using namespace std;
const int N = 105, M = 100005;
int g[N], n;
bitset<M> S;
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &g[i]);
    }
    S[0] = 1;
    for(int i = 0; i < n; i ++ ){
        S |= S << g[i];
    }
    for(int i = 0; i < n; i ++ ){
        S |= S >> g[i];
    }
    cout << S.count() - 1 << endl;
    return 0;
}