网页设计 网站,网页制作中级证书,产品如何在网上推广,深圳市住房和建设局正题
CF750F1 CF750F2 题目大意
给你一个数列#xff0c;问有多少个数可以由一个单调递增的子序列异或得到 解题思路
对于F1#xff0c;可以用p存下得到一个数的最小值#xff08;即当前子序列前缀的最后一个数#xff09;#xff0c;然后直接暴力转移
对于F2#xf…正题
CF750F1 CF750F2 题目大意
给你一个数列问有多少个数可以由一个单调递增的子序列异或得到 解题思路
对于F1可以用p存下得到一个数的最小值即当前子序列前缀的最后一个数然后直接暴力转移
对于F2直接暴力转移会TLE
可以发现该数列一定存在重复的数而部分转移会重复比如前面可以转移的后面也转移了但一定不会更优
考虑更改转移方式先对数列进行排序设pip_ipi为得到iii的最前位置那么对于每次转移就在当前数中找第一个大于pip_ipi的最小的数
时间复杂度O(s2logn)O(s^2\ log\ n)O(s2 log n) code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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];
pairint,inta[N];
int main()
{for(int i1;i8191;i)p[i]10000000;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i].fs);a[i].sni;}sort(a1,a1n);now1;while(nown){w1;ga[now].fs;b[w]a[now].sn;now;while(nowna[now].fsg)b[w]a[now].sn,now;p[g]min(p[g],b[1]);for(int i1;i8191;i)if(p[i]b[w])p[i^g]min(p[i^g],b[lower_bound(b1,b1w,p[i])-b]);}for(int i1;i8191;i)if(p[i]1000000)num;printf(%d\n0,num1);for(int i1;i8191;i)if(p[i]1000000)printf( %d,i);return 0;
}
