1 条题解
-
0
::::info[无解情况]{open} 当 ,由于衣服只能增温,此时无解。 ::::
发现用 () 可以满足所有情况。
::::info[证明]{open} 对于有解情况,为达到 度需要最多增加 度。而所有在 中的数字都能用一个 位二进制表示,即 ()。故 乘上不同系数能组合出 的任意值。 ::::
故答案最多为 ,一共有 种情况,可以枚举。
检查一种方案是否合法时,可以使用背包 DP。但是
bitset实在太好用啦,我就偷个懒啦。::::success[AC 代码]
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 85; int n, ans, a[N], b[10]; bitset<N> bs, tp; bool check(){ bs.reset(); bs[0] = 1; for(int i = 1; i <= ans; ++ i) bs |= (bs << b[i]); return (bs & tp) == tp; } void dfs(int p, int l){ if(l > ans){ if(!check()) return; cout << "Yes\n" << ans << "\n"; for(int i = 1; i <= ans; ++ i) cout << b[i] << " "; exit(0); } for(int i = p; i <= a[n]; ++ i) b[l] = i, dfs(i + 1, l + 1); } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n; for(int i = 1; i <= n; ++ i) cin >> a[i], a[i] = 23 - a[i]; sort(a + 1, a + n + 1); if(a[1] < 0) return cout << "No", 0; for(int i = 1; i <= n; ++ i) tp[a[i]] = 1; for(;;++ ans) dfs(1, 1); cout << "I AK IOI"; return 0; }::::
::::info[代码中
bitset操作解释]{open}for(int i = 1; i <= ans; ++ i) bs |= (bs << b[i]);即在原可组合方案基础上,加上所有能得到的值加 的方案。
return (bs & tp) == tp;判断是否满足:。 ::::
- 1
信息
- ID
- 9656
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 9
- 标签
- 递交数
- 23
- 已通过
- 3
- 上传者