首页 > 代码库 > HDU 5968 异或密码
HDU 5968 异或密码
<style>p.MsoNormal { margin: 0pt; margin-bottom: .0001pt; text-align: justify; font-family: Calibri; font-size: 10.5000pt }
h1 { margin-top: 5.0000pt; margin-bottom: 5.0000pt; text-align: center; font-family: 宋体; color: rgb(26,92,200); font-weight: bold; font-size: 24.0000pt }
span.10 { font-family: "Times New Roman" }
span.15 { font-family: "Times New Roman"; color: rgb(26,92,200) }
span.16 { font-family: "Times New Roman"; color: rgb(26,92,200) }
p.pre { margin: 0pt; margin-bottom: .0001pt; text-align: left; font-family: 宋体; font-size: 12.0000pt }
span.msoIns { text-decoration: underline; color: blue }
span.msoDel { text-decoration: line-through; color: red }
table.MsoNormalTable { font-family: "Times New Roman"; font-size: 10.0000pt }
div.Section0 { }</style>
Output - 输出
HDU 5968 异或密码
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description - 题目描述
晨晨在纸上写了一个长度为N的非负整数序列{ai}。对于这个序列的一个连续子序列{al, al+1, …,ar}晨晨可以求出其中所有数异或的结果 al xor al + 1xor ... xor ar其 中xor表示位异或运算,对应C、C++、 Java等语言中的^运算。
小璐提出了M个询问,每个询问用一个整数 xi描述。
对于每个询问,晨晨需要找到序列{ai}的所有连续子序列,求出每个子序列异或的结果,找到所有的结果中与 xi之差的绝对值最小的一个,并告诉小璐相应子序列的长度。
若有多个满足条件的连续子序列,则告诉小璐这些子序列中最长的长度。
小璐提出了M个询问,每个询问用一个整数 xi描述。
对于每个询问,晨晨需要找到序列{ai}的所有连续子序列,求出每个子序列异或的结果,找到所有的结果中与 xi之差的绝对值最小的一个,并告诉小璐相应子序列的长度。
若有多个满足条件的连续子序列,则告诉小璐这些子序列中最长的长度。
Input - 输入
包含多组测试数据,第一行一个正整数T,表示数据组数。
每组数据共两行。
第一行包含N+1个非负整数。其中第一个数为N,表示序列的长度;接下来N 个数,依次描述序列{ ai}中的每个数。
第二行包含M+1个整数。其中第一个数为M,表示询问的个数;接下来M个数 xi,每个数对应题目描述中的一个询问。
保证 1 <= N <= 100,1 <= M <= 100,ai <= 1024,|xi| <= 1024,数据组数 <= 100。
每组数据共两行。
第一行包含N+1个非负整数。其中第一个数为N,表示序列的长度;接下来N 个数,依次描述序列{ ai}中的每个数。
第二行包含M+1个整数。其中第一个数为M,表示询问的个数;接下来M个数 xi,每个数对应题目描述中的一个询问。
保证 1 <= N <= 100,1 <= M <= 100,ai <= 1024,|xi| <= 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 1 3 2 1
题解
水题。
枚举所有子序列的异或值,然后花式查询即可,数据比较小,不用管时间。
输出是每组数据后面都要有额外的回车,不然会PE……
代码 C++
1 #include<cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdlib> 5 #define mx 1<<11 6 int data[105], len[mx]; 7 int main(){ 8 int t, n, m, i, j, tmp, l, r; 9 scanf("%d", &t); 10 while (t--){ 11 memset(len, 0, sizeof(len)); 12 scanf("%d", &n); 13 for (i = 0; i < n; ++i) scanf("%d", data + i); 14 for (i = 0; i < n; ++i){ 15 tmp = 0; 16 for (j = i; j < n; ++j){ 17 tmp ^= data[j]; 18 len[tmp] = std::max(len[tmp], j - i + 1); 19 } 20 } 21 scanf("%d", &m); 22 for (i = 0; i < m; ++i){ 23 scanf("%d", &tmp); l = r = -1; 24 tmp = std::max(tmp, 0); 25 for (j = tmp; j < mx; ++j) if (len[j]) break; 26 if (j < mx) l = j; 27 for (j = tmp - 1; ~j; --j) if (len[j]) break; 28 if (~j) r = j; 29 if (~(l | r)){ 30 if (abs(tmp - l) < abs(tmp - r)) printf("%d\n", len[l]); 31 else if (abs(tmp - l) > abs(tmp - r)) printf("%d\n", len[r]); 32 else printf("%d\n", std::max(len[l], len[r])); 33 } 34 else printf("%d\n", len[-1 * l * r]); 35 } 36 puts(""); 37 } 38 return 0; 39 }
HDU 5968 异或密码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。