【子序列DP】CF1582 F1

待我称王封你为后i 2024-03-23 18:43 113阅读 0赞

[Problem - F1 - Codeforces][]

题意：

![3c5382553d7a4b58aca13a69ceb6e942.png][]

思路：

很经典的套路

注意到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;
    }

[Problem - F1 - Codeforces]: https://codeforces.com/contest/1582/problem/F1
[3c5382553d7a4b58aca13a69ceb6e942.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f35134dd66314a69b9ce946ca13556f8.png

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关判断子序列

392. 判断子序列 > 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 > 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对

忘是亡心i/ 2024年04月03日 09:07/ 0 赞/ 138 阅读

相关【子序列DP】CF1582 F1

[Problem - F1 - Codeforces][] 题意： ![3c5382553d7a4b58aca13a69ceb6e942.png][] 思路：很经典的

待我称王封你为后i/ 2024年03月23日 18:43/ 0 赞/ 114 阅读

相关 P1582-倒水

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

太过爱你忘了你带给我的痛/ 2023年06月01日 08:52/ 0 赞/ 91 阅读

相关 Subsequence 子序列

Subsequence 191221 > 答案思路英文题翻译为中文 Title 题目： A sequence of N positive integers (

悠悠/ 2022年12月29日 09:11/ 0 赞/ 215 阅读

相关上升子序列

Problem Description 一个只包含非负整数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列\{a1,

骑猪看日落/ 2022年07月13日 01:56/ 0 赞/ 207 阅读

相关上升子序列

Problem Description 一个只包含非负整数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列\{a1,

拼搏现实的明天。/ 2022年07月12日 02:48/ 0 赞/ 271 阅读

相关 1.1 最大子序列求和

题目大意：给出一序列，求该序列的子序列和最大的子序列。下面共有四种算法：程序运行时间依次降低，最佩服的是最后的联机算法，时间已达到O(N). 注意C++中的

川长思鸟来/ 2022年06月04日 09:15/ 0 赞/ 243 阅读

相关上升子序列

Problem Description 一个只包含非负整数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列\{a1, a2,

ゞ浴缸里的玫瑰/ 2022年05月16日 01:45/ 0 赞/ 202 阅读

相关牛客OI赛制测试赛 F：子序列

[题目传送门][Link 1] 代码： include<bits/stdc++.h> using namespace std; type

╰半橙微兮°/ 2022年05月13日 23:40/ 0 赞/ 276 阅读

相关 P1582 倒水

太强了，dalao的题解 [https://www.luogu.org/blog/jingyangzhi/solution-p1582][https_www.luogu.or

秒速五厘米/ 2021年10月26日 12:32/ 0 赞/ 467 阅读