正題

CF750F1
CF750F2

---

題目大意

給你一個數列，問有多少個數可以由一個單調遞增的子序列異或得到

---

解題思路

對于F1，可以用p存下得到一個數的最小值（即當前子序列前綴的最后一個數），然后直接暴力轉移

對于F2，直接暴力轉移會TLE

可以發現，該數列一定存在重復的數，而部分轉移會重復（比如前面可以轉移的后面也轉移了，但一定不會更優）

考慮更改轉移方式，先對數列進行排序，設$p_i$為得到$i$的最前位置，那么對于每次轉移，就在當前數中找第一個大于$p_i$的最小的數

時間復雜度$O(s^{2}logn)$

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 1000100 #define fs first #define sn second using namespace std; int n,x,g,w,num,now,p[N],s[N],b[N]; pair<int,int>a[N]; int main() {for(int i=1;i<=8191;++i)p[i]=10000000;scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i].fs);a[i].sn=i;}sort(a+1,a+1+n);now=1;while(now<=n){w=1;g=a[now].fs;b[w]=a[now].sn;now++;while(now<=n&&a[now].fs==g)b[++w]=a[now].sn,now++;p[g]=min(p[g],b[1]);for(int i=1;i<=8191;++i)if(p[i]<b[w])p[i^g]=min(p[i^g],b[lower_bound(b+1,b+1+w,p[i])-b]);}for(int i=1;i<=8191;++i)if(p[i]<=1000000)num++;printf("%d\n0",num+1);for(int i=1;i<=8191;++i)if(p[i]<=1000000)printf(" %d",i);return 0; }

總結

以上是生活随笔為你收集整理的Korney Korneevich and XOR（CF750F1/F2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。