CF750F1-思维dp

题目大意:

给你一个序列，输出里面的所有递增子序列的异或和的集合.

例如：
4
4 2 2 4
输出:
4
0 2 4 6

因为有递增子序列:
0
2
4
2 4
他们的异或和的集合就是 0 2 4 6

$n\le 1e5,a_i\le 500$

题目思路:

朴素的思考:$dp(i,j)$代表前$i$个数,是否存在递增子序列的异或和为j.

但是我们需要其递增，所以贪心的让$dp(i,j)$为异或和为$j$的递增子序列的最小的可能的结尾值。

然后就可以转移了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[maxn];
int dp[513] , g[513];
int main()
{
    
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    memset(dp , 0x3f , sizeof dp);
    dp[0] = 0;
    for (int i = 1 ; i <= n ; i++){
    
        memcpy(g , dp , sizeof g);
        for (int j = 0 ; j < 512 ; j++){
    
            if (g[j] < a[i]){
    
                int k = j ^ a[i];
                dp[k] = min(g[k] , a[i]);
            }
        }
    }
    vector<int> ans;
    for (int i = 0 ; i < 512 ; i++) if (dp[i] != inf) ans.push_back(i);
    cout << ans.size() << endl;
    for (auto g : ans) cout << g << " ";
    cout << endl;
    return 0;
}