선형 기 설명
2802 단어 탐욕의 책략
1.선형 기:
몇몇 수의 선형 기 는 한 그룹의 수 a1,a2,...ana1,a2,...an 인 데 그 중에서 axax 의 가장 높 은 11 은 xx 위 에 있다.
선형 기 에서 원소 xorxor 를 통 해 나 오 는 수의 값 영역 은 원래 의 숫자 xorxor 에서 나 오 는 값 영역 과 같 습 니 다.
2.선형 기의 구조 법:
각 수의 pp 를 높 은 위치 에서 낮은 위치 로 쓸 고 xx 위 가 11 일 때 ax 가 존재 하지 않 으 면 ax=pax=p 를 스 캔 하고 이 수의 스 캔 을 끝 냅 니 다.그렇지 않 으 면 p=pp=p 를 끝 냅 니 다. xorxor ax。ax。
3.조회:
선형 기반 으로 이 그룹의 xorxor 에서 나 오 는 최대 치 를 구하 십시오.높 은 곳 에서 낮은 곳 으로 axax 를 쓸 고 다른 곳 이나 위의 axax 가 답 을 크게 만 들 면 다른 곳 이나 다른 곳 입 니 다.
4.판단:
선형 기반 으로 하나의 숫자 가 xorxor 에 의 해 나 올 수 있 는 지 를 구 합 니 다.높 은 곳 에서 낮은 곳 까지 이 수 는 각각 11 의 위치 xx 입 니 다.이 수 를 상이 하거나 상 axax(주의 하거나 후 이 수 를 1 로 하 는 위치 와 원수 가 다 릅 니 다)로 바 꾸 면 최종 적 으로 00 으로 바 뀌 면 이 또는 출 수 있 습 니 다.당연히 특 판 00 이 필요 하 다.예:(11111,10001)(11111,10001)의 선형 기 는 a5=11111a 5=11111,a4=01110a 4=01110 a 4=01111 로 1111111111 이 xorxor 에 의 해 나 올 수 있 는 지,1111111111111 xorxor a5a 5=0=0 을 판단 하려 면 이 수 는 나중에 11 의 위치 가 없 었 고 최종 결 과 는 00 으로 1111111111111111 이 xorxor 에 의 해 나 올 수 있 음 을 나타 낸다.
개인 적 으로 선형 기 에 대한 이 해 를 이야기 하 다.
많은 경우 에 이 또는 연산 과 최 치 를 구하 기만 하면 선형 기 를 사용 할 수 있다.선형 기 는 매우 좋 은 성질 이 많다.예 를 들 어 여러 개의 수가 있 으 면 우 리 는 이런 수의 선형 기 를 구성 할 수 있다.그러면 이 선형 기 는 서로 xorxor 를 통 해 원래 의 수 는 서로 xorxor 가 구성 할 수 있 는 모든 수 를 구성 할 수 있다.그래서 판단 의 시간 과 횟수 를 크게 줄 일 수 있다.이 동시에 선형 기반 의 어떠한 비 빈 부분 집합 도 xorxor 와 0 으로 만 들 지 않 고 증명 도 간단 하 며 반증 법 은 설명 할 수 있다.이 성질 은 많은 문제 에서 알고리즘 의 합 법성 을 확보 할 수 있다.예 를 들 어 BZOJ 2460 BZOJ 2460 이다.
구조 적 인 방법 은 욕심 처럼 크 고 작은 것 부터 높 은 것 을 보장 하 는 것 이 더 크다.이해 하기 도 쉽 고.바로 이 몇 줄 의 코드 입 니 다.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
for ( int i=1;i<=n;i++) { for ( int j=62;j>=0;j--) { if (!(a[i]>>j)) continue ; // if (!p[j]) { p[j]=a[i]; break ; } // a[i]^=p[j]; } } N 개 수 를 가장 큰 수의 바 이 너 리 숫자 만큼 많은 숫자 로 바 꿀 수 있 는데 이것 이 바로 선형 기의 우수한 점 이다.
조회 하면 욕심 도 있 습 니 다.ansans 를 더 크게 만 들 수 있다 면 이 사람의 기 xorxor 를 ansans 에 넣 으 세 요.
1 for(int i=62;i>=0;i--) if((ans^p[i])>ans) ans=ans^p[i];//선형 기 에서 최대 치 를 얻다
이것 이 바로 선형 기의 기본 용법 과 개인의 이해 이다.
좋은 웹페이지 즐겨찾기
