F1. Korney Korneevich and XOR (easy version)
我们观察题意
发现我们需要找的是一个上升序列
我们回忆上升序列的状态设计
dp[i]表示第i个作为结尾最长的序列长度是多少
我们该题不需要记录长度只用记录那个数字是否存在
那我们稍微修改一个状态表示
dp[i]表示i数字作为结尾的结尾数字最小是啥
这样就可以转移了
我们考虑刷表
要是dp[j^x]<x&&dp[j]之前存在 就可以转移
最后记得因为我们自己这个数字也可以直接单独的作为结尾
dp[x]=min(dp[x],x);
还有这题的数据范围虽然是500 然后异或是不进位加法 但还是有可能到512
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
void solve() {
int n;cin>>n;
vector<int>dp(520);
for(auto &i:dp)i=INF;
for(int i=1;i<=n;i++){
int x;cin>>x;
for(int j=0;j<=512;j++){
if(dp[j]!=INF&&dp[j]<x)dp[x^j]=min(dp[x^j],x);
}
dp[x]=min(dp[x],x);
}
vector<int>ans;
for(int i=0;i<=512;i++)if(dp[i]!=INF)ans.push_back(i);
if(ans[0]!=0)ans.push_back(0), sort(all(ans));
cout<<ans.size()<<endl;
for(auto i:ans)cout<<i<<' ';cout<<endl;
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:F1,750,const,结尾,int,Div,dp,数字
From: https://www.cnblogs.com/ycllz/p/16839071.html