Problem - F1 - Codeforces

题意：

思路：

很经典的套路

注意到ai只有500，且和子序列有关

因此设dp[j]为子序列异或和为 j 的结尾那个数的最小值

为什么要这么设计，因为要保证递增

Code：

// LUOGU_RID: 119162215
#include <bits/stdc++.h>using i64 = long long;using namespace std;const int N = 2e5 + 10;
const int M = 3e6 + 10;
const int P = 131;
const int Inf = 0x3f3f3f3f;int a[N];
int dp[N];void solve() {int n;cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i];}for (int i = 0; i <= 1000; i ++) {dp[i] = Inf;}dp[0] = 0;for (int i = 1; i <= n; i ++) {for (int j = 1000; j >= 0; j --) {if (dp[j] < a[i]) {dp[j ^ a[i]] = min(dp[j ^ a[i]], a[i]);}}}int ans = 0;for (int j = 0; j <= 1000; j ++) {if (dp[j] != Inf) ans ++;}cout << ans << "\n";for (int j = 0; j <= 1000; j ++) {if (dp[j] != Inf) cout << j << " \n" [j == 1000];}
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;while(t --) {solve();}return 0;
}