중 남 oj 1216: 이 또는 최대 치 데이터 구조
8562 단어 데이터 구조
Time Limit: 2 Sec
Memory Limit: 128 MB
Submit: 98
Solved: 29 [
Submit ][
Status ][
Web Board ]
Description
몇 개의 수 를 정 해서 이 두 수의 차이 나 값 이 가장 큰 값 을 구하 세 요.
Input
첫 번 째 행위 숫자 개수 n, 1 < = n < = 10 ^ 5.다음 n 줄 마다 32 자리 기호 가 마이너스 정수 가 아 닙 니 다.
Output
임의의 두 수의 최대 이 또는 값
Sample Input
3
3
7
9Sample Output
14HINT
이 문제 에서 나 는 약간의 새로운 지식 을 배 웠 다.
사전 트 리 를 써 본 적 이 없다.이 문 제 는 01 사전 나 무 를 사용한다.
트 리 구축, 트 리 dp 와 같 습 니 다. 모두 트 리 입 니 다.
생각:
폭력 은 시간 을 초과 할 수 있다.
사전 트 리, 01 사전 트 리.
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4
5 typedef struct
6 {
7 int a[2];
8 int num;
9 }Tril;
10 Tril f[100010<<5];
11 int root,ans;
12
13 void insert(int x,int u,int num)
14 {
15 int i,k;
16 for(i=num;i>=0;i--)
17 {
18 k=(1<<i&x)?1:0;
19 if(f[u].a[k]==-1)
20 f[u].a[k]=root++;
21 u=f[u].a[k];
22 }
23 f[u].num=x;
24 }
25 void query(int x,int u,int num)
26 {
27 int i,j,k;
28 for(i=num;i>=0;i--)
29 {
30 k=(1<<i&x)?0:1;
31 if(f[u].a[k]!=-1)
32 u=f[u].a[k];
33 else
34 u=f[u].a[k^1];
35 }
36 j=f[u].num^x;
37 if(j>ans)
38 ans=j;
39 }
40 int main()
41 {
42 int n,i,x;
43 while(scanf("%d",&n)>0)
44 {
45 memset(f,-1,sizeof(Tril)*((n+1)<<5));
46 ans=0;
47 root=1;
48 for(i=1;i<=n;i++)
49 {
50 scanf("%d",&x);
51 insert(x,0,31);
52 query(x,0,31);
53 }
54 printf("%d
",ans);
55 }
56 return 0;
57 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
