首页 > 其他分享 >Codeforces Round #750 (Div. 2) F1

Codeforces Round #750 (Div. 2) F1

时间:2022-10-29 16:56:26浏览次数:64  
标签:F1 750 const 结尾 int Div dp 数字

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

相关文章

  • Educational Codeforces Round 93 (Rated for Div. 2) D
    D.ColoredRectangles考虑数据范围显然可以n3dp我们发现dp转移时不是特别好枚举所以我们选择记忆化搜索打完你们可能会发现过不去第三个样例显然我们应该sort一遍......
  • CF1481E
    \(*\text{Defficult:}\color{Red}{2500}\)一道很有AT风格的DP。Description有\(n\)本书,每本书有一个颜色,每次操作可以将一本书移动到最右。求问使所有相同颜色......
  • CH32F103C8T6调试口Disable后的修复办法
    1.问题描述   因为软件编程,将CH32F103的debugdisable了,无法通过仿真器下载程序。   2.修复  2.1解决思路    利用厂家给的串口ISP进行下载(HU......
  • CF1394D
    所谓单调递增或单调递减,其实只用看成一条有向的链,\(b\)大的点指向\(b\)小的点即可。所以对于边\((u,v)\),假设\(b_u\neb_v\),那么这条边的方向确定。一个点对答案的......
  • Codeforces Round #827 (Div. 4) A-G
    比赛链接A题解知识点:模拟。时间复杂度\(O(1)\)空间复杂度\(O(1)\)代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;boolsolve(){......
  • CF1394C
    首先,我们关注一下“相似”是什么意思:它等价于,两个字符串中B和N的数量分别相同。显然地我们可以发现,每次操作,相当于给字符串加或减一个B或N或BN。把每个字符串中......
  • CF1675G
    首先,可以感性地发现移动小球时出现负值不会影响最终答案,只要最终方案是非负的就行了。所以,我们不妨规定,一个箱子只能从右边一个箱子拿小球,或者向右边一个箱子放小球。设......
  • 【CF1693C】Keshi in Search of AmShZ(类dijkstra)
    首先可以钦定每次只删当前点的出边。然后可以注意到,在最优策略下,我们肯定不会走回重复的点:否则意味着出现了一个环,那么我们还是需要将这个环上的某条边删掉(否则最坏情况就......
  • 【CF1537F】Figure Fixing(思维)
    题意:给一张图,每个点有一个可以为负的权值\(a_i\),一次操作可以选择一条边\((i,j)\)并让\(a_i,a_j\)同时增加任意一个可以为负的整数值,问是否存在操作方式使得所有点点......
  • Codeforces Round #826 (Div. 3) A-E
    比赛链接A题解知识点:模拟。时间复杂度\(O(n)\)空间复杂度\(O(n)\)代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;boolsolve(){......