蓝桥 和为T (状压)

简介: 蓝桥 和为T (状压)

题目描述
从一个大小为n的整数集中选取一些元素,使得它们的和等于给定的值T。每个元素限选一次,不能一个都不选。

数据规模和约定
1< =n< =22
T< =maxlongint
集合中任意元素的和都不超过long的范围

输入
第一行一个正整数n,表示整数集内元素的个数。
第二行n个整数,用空格隔开。
第三行一个整数T,表示要达到的和。
输出
输出有若干行,每行输出一组解,即所选取的数字,按照输入中的顺序排列。
若有多组解,优先输出不包含第n个整数的;若都包含或都不包含,优先输出不包含第n-1个整数的,依次类推。
最后一行输出总方案数。
样例输入
5
-7 -3 -2 5 9
0
样例输出
-3 -2 5
-7 -2 9
2

再次自闭,不过学长一讲就明白了。
用n位二进制来表示n个数选还是不选的状态,0表示不选,1表示选。然后就从0001到1111(对于这道题)开始暴力搜索所有状态。
由于二进制搜索状态时,在低三位没有达到最大时是不会标记第四位的,所以搜索顺序和题目要求的其实一样,直接暴力就可以了。
这种思路其实和next_permutation来暴力状态一样的道理。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

ll a[25];
ll n, T, ans=0;

int main(){
   
    scanf("%lld", &n);
    for (int i=0; i<n; i++)
        scanf("%lld", &a[i]);
    scanf("%lld", &T);

    ll up=1<<n;    //n位二进制最大是1<<n-1
    for (ll sta=1; sta<up; sta++){
   
        ll tmp=0;
        for (int i=0; i<n; i++){
   
            if ((sta>>i)&1){
   
                tmp += a[i];    //sta从右面数,a[]从0开始数 
            }
        }
        if (tmp==T){
   
            ans++;
            for (int i=0; i<n; i++){
   
                if ((sta>>i)&1){
   
                    printf("%d ", a[i]);
                }
            }
            printf("\n");
        } 
    } 
    printf("%d\n", ans);
    return 0;
}
相关文章
|
1月前
|
人工智能
【蓝桥】蓝桥小白入门赛8
A、签到 B、结论性排序 C、找规律+暴力 D、找规律+递推+贪心 E、找规律+贪心 F、dp
31 11
|
1月前
|
存储 人工智能 BI
【蓝桥】蓝桥小白入门赛7
A、签到 B、暴力 C、模拟 D、二进制、枚举 E、优先队列 F、二维前缀和+滑动窗口
33 9
|
1月前
【蓝桥】蓝桥小白入门赛6
A、签到 B、模拟 C、推结论+模拟 D、找规律 E、贪心+双指针 F、二分
29 6
|
3月前
|
算法 C++
小唐蓝桥的做题心得
小唐蓝桥的做题心得
|
3月前
|
存储
蓝桥备战:四元组问题(蓝桥OJ 3416)
蓝桥备战:四元组问题(蓝桥OJ 3416)
43 0
|
12月前
|
人工智能
蓝桥 包子凑数 (筛数)
蓝桥 包子凑数 (筛数)