1 条题解

  • 0
    @ 2026-4-23 16:51:56

    ::::info[无解情况]{open} 当 i[1,n],Ai>23\exists i \in [1,n],A_i>23,由于衣服只能增温,此时无解。 ::::

    发现用 20,21,22,23,24,252^0,2^1,2^2,2^3,2^4,2^51,2,4,8,16,321,2,4,8,16,32) 可以满足所有情况。

    ::::info[证明]{open} 对于有解情况,为达到 2323 度需要最多增加 63=26163=2^6-1 度。而所有在 [0,63][0,63] 中的数字都能用一个 66 位二进制表示,即 i=16bi2i\sum_{i=1}^6 b_i \cdot 2^ibi{0,1}b_i \in \{0,1\})。故 20,21,22,23,24,252^0,2^1,2^2,2^3,2^4,2^5 乘上不同系数能组合出 [0,63][0,63] 的任意值。 ::::

    故答案最多为 66,一共有 1123362311233623 种情况,可以枚举。

    检查一种方案是否合法时,可以使用背包 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]);
    

    即在原可组合方案基础上,加上所有能得到的值加 bib_i 的方案。

    return (bs & tp) == tp;
    

    判断是否满足:i[1,ans],bsi=0,tpi=1\nexists i \in [1,ans],bs_i=0,tp_i=1。 ::::

    • 1

    信息

    ID
    9656
    时间
    2000ms
    内存
    1024MiB
    难度
    9
    标签
    递交数
    23
    已通过
    3
    上传者