制作网站软件,网站建设维护公司排名,国外做游戏的视频网站有哪些问题,做网站和做app有什么不同题干#xff1a;
晨晨在纸上写了一个长度为N的非负整数序列{aiai}。对于这个序列的一个连续子序列{al,al1,…#xff0c;aral,al1,…#xff0c;ar}晨晨可以求出其中所有数异或的结果 alxoral1xor...xoraralxoral1xor...xorar其 中xor表示位异或运算#xff0c;对应C、C、…题干
晨晨在纸上写了一个长度为N的非负整数序列{aiai}。对于这个序列的一个连续子序列{al,al1,…aral,al1,…ar}晨晨可以求出其中所有数异或的结果 alxoral1xor...xoraralxoral1xor...xorar其 中xor表示位异或运算对应C、C、 Java等语言中的^运算。 小璐提出了M个询问每个询问用一个整数 xixi描述。 对于每个询问晨晨需要找到序列{aiai}的所有连续子序列求出每个子序列异或的结果找到所有的结果中与 xixi之差的绝对值最小的一个并告诉小璐相应子序列的长度。 若有多个满足条件的连续子序列则告诉小璐这些子序列中最长的长度。
Input
包含多组测试数据第一行一个正整数T表示数据组数。 每组数据共两行。 第一行包含N1个非负整数。其中第一个数为N表示序列的长度接下来N 个数依次描述序列{ aiai}中的每个数。 第二行包含M1个整数。其中第一个数为M表示询问的个数接下来M个数 xixi每个数对应题目描述中的一个询问。 保证 1 N 1001 M 100aiai 1024|xixi| 1024数据组数 100。
Output
对于每组数据输出M 1行。前M行对应晨晨M个询问的回答第M 1行为空行
Sample Input
2
2 1 1
2 0 2
3 1 2 4
3 10 5 1
Sample Output
2
13
2
1解题报告
直接记录每一个异或值下的最长长度最后二分查找输出就可以。注意并不是样例之间有空行而是每一个样例后面都输出空行时间复杂度O(T*(n^2log(n^2)mlog(n^2)))
其实这题也可以不带log。
有一个O(T*m*n^2)的做法先预处理异或和然后对于每个询问n^2暴力。这样可以过。
第二种方法是O(T*n^2)的做法不用map直接用数组然后用并查集优化一下对于每次查询就可以O1了但是实现比较复杂可能没人会写吧、、、
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
int n,m;
mapint,int mp;
int a[MAX];
int main()
{int T;cinT;while(T--) {scanf(%d,n);mp.clear();for(int i 1; in; i) scanf(%d,ai);for(int i 1; in; i) {int Xor0;for(int j i; jn; j) {Xor ^ a[j];if(mp.find(Xor) ! mp.end()) mp[Xor] max(mp[Xor],j-i1);else mp[Xor] j-i1;}}scanf(%d,m);int x;while(m--) {scanf(%d,x);auto it mp.lower_bound(x);if(it mp.end()) --it;auto itt it;if(itt ! mp.begin()) --itt;int cha1 abs(it-FF - x),cha2 abs(itt-FF - x);if(cha1 cha2) printf(%d\n,it-SS);else if(cha1 cha2) printf(%d\n,itt-SS);else printf(%d\n,max(it-SS,itt-SS));}puts();}return 0 ;
}
