강의하다
1. 분치
공통분치
즉, 모든 하위 문제에 대해 중간에 칼을 긋고 두 단락으로 나누어 구간에서mid부터 기괴한 값을 유지한다. 일반적으로 최대 접두사, 최소 접두사 등이다.중간의 교차 처리가 끝난 후에 양쪽으로 귀속하기 시작한다.전반적으로 말하면 마구잡이이다
절midmid를 초과한 답안을 처리하고 통계 귀속 해결이분
분수 계획
보통 2점은 잘 배웠는데 갑자기 귀신과 짐승이 시작되었다.
분수 계획 문제는 통계 값형이 분식 표현식의 가장 값이고 한 번 전환한 후에 유지보수에 편리한 표현식을 얻는다.
유지 보수 a[i]b[i]\frac{a[i]}{b[i]}b[i]a[i]최대 a [ i ] b [ i ] > = m i d\frac{a[i]}{b[i]}>=mid b[i]a[i]>=mid a [ i ] > = m i d ∗ b [ i ] a[i]>=mid*b[i] a[i]>=mid∗b[i] a [ i ] − m i d ∗ b [ i ] > = 0 a[i]-mid*b[i]>=0 a[i]−mid∗b[i]>=0 그래, 이거야.
그리고 막 굴기 시작할 거예요.
최소 구간 원 덮어쓰기
걸다
전체 이분
예제
2분 답안<=mid의 수는 k개가 있습니까?
하지만 그뿐만이 아닌 것 같다. 동창 블로그는 현재 명확하게 설명하는 것을 보지 못했다. 끊어라. 끊어라.
cdq분치
듣자니 정수는 왼쪽이 오른쪽에 기여하는 것을 고려하는 것이라고 하는데, 각종 결점 1결점을 처리할 수 있다.문제
너무 오묘해서 못 들었어요. 감사합니다.
점분치
점분치 효율이 우수한 것은 어쩐지 중심을 기점으로 삼았더라면 틀림없이 T를 날았을 것이다.
구간상의 분치는 중심점을 찾아 크로스컨트리 공헌 후 귀속자 문제를 처리했고 점분치의 정수도 분치에 있다. 데이터 규모를 줄이고 매번 귀속자가 나무가 되는 문제는 경계 처리에 문제가 없다.
네, 매번 중심을 경계로 처리하고 각 자수에 귀속시켜 중심을 다시 구하고 다시 계산하면 구간의 분치와 차이가 크지 않은 것 같습니다.
그것과 트리 dp 사이에는 약간의 공통성이 있다. 왜냐하면 모두 노드에서 서브 트리와의 관계를 처리하기 때문이다.그러나 일반적으로 나무형 dp의 문제는 주로 점분치로 해결할 수 있지만 점분치의 문제는 스스로 번거롭지만 나무형 dp로 해결할 수 있는 것 같다.
개인적으로 점분치라는 알고리즘은 최근에야 접촉했다. 나무 dp는 상대적으로 익숙하고 더욱 익숙하지만 점분치 숙련은 매우 중요하다.
시간 분할 치료
아까 dls에서 말씀드렸듯이 시간 분할 치료에서 추가, 삭제가 번거롭기 때문에 다른 방법으로 시간별로.타임라인에서 [l, r] 구간에 값이 있습니다.이 방법은 정말 사람을 머리가 빠지게 한다. 이 tm도 치료할 수 있겠는가?
2. 도론
- 1.최단거리 변종:
즉, 동적 삭제 사이드 삭제 최단로입니다.
동적 삭제.만약에 이 변이 가장 짧은 경로에 있지 않으면 상관하지 않고 있으면 최소 대체를 찾습니다. 단점에서 x, y,dis[1,x]+dis[x,y]+dis[y,n]로 대체를 업데이트합니까?? 보아하니 이렇게 된 것 같은데, 선생님께서 말씀하신 것을 별로 알아듣지 못한 것은 나 자신의 이해이다.근데 이거 cdq로 나눠서 하는 것 같은데.
동적 삭제점.이 점이 경로에 없는 상황은 여전히 고려할 필요가 없다.없으면 최소한의 대체를 찾는다.제목에 고리가 없는 조건이 하나 더 나오는데, 이 문제는 - 2.예1.
제목: 방향대 정권 토폴로지 그림을 정하고 ⼏줄 1에서 N까지의 경로의 길이를 구합니다<=1에서 N까지의 최단로 +K
폭력&정해:
f [x] [L] 표시 1 x 경로 길이 L 설정 f [x] 표시 1 ~ x 경로 길이 L 설정 f [x] [L] 표시 1 x 경로 길이 L f [ x ] [ L ] − > f [ f[x][L]->f[ f[x][L]−>f[ L + d i s(x, n)−d i s(1, n)<= k;L+dis(x,n)-dis(1,n)<=k 요구;L+dis(x, n)−dis(1, n)<=k 요구; d i s ( 1 , n ) < = d i s ( x , n ) + d i s ( 1 , x ) dis(1,n)<=dis(x,n)+dis(1,x) dis(1,n)<=dis(x,n)+dis(1,x) L + d i s ( x , n ) − ( d i s ( 1 , x ) + d i s ( x , n ) ) < = k L+dis(x,n)-(dis(1,x)+dis(x,n))<=k L+dis(x,n)−(dis(1,x)+dis(x,n))<=k L − d i s ( 1 , x ) < = k L-dis(1,x)<=k L−dis(1,x)<=k d i s ( 1 , x ) < = L < = d i s ( 1 , x ) + k dis(1,x)<=L<=dis(1,x)+k dis(1,x)<=L<=dis(1,x)+k 2차원 L에 대해 유효한 수치는 k+1종만 2차원 L에, 유효한 수치는 k+1종만 2차원 L에, 유효한 수치는 k+1종 그래서 f[x] [L−d i s(1,x)] 그래서 f[x] [L-dis(1,x)] 그래서 f[x] [L−dis(1,x)] (0~k) 경로 길이 dis(1,x)+v;경로 길이 dis(1,x)+v;경로 길이 dis(1,x)+v; f ( x , v ) − > f ( y , d i s ( 1 , x ) + v + w ( x , y ) − d i s ( 1 , y ) ) f(x,v)->f(y,dis(1,x)+v+w(x,y)-dis(1,y)) f(x,v)−>f(y,dis(1,x)+v+w(x,y)−dis(1,y)) f[N][d i s(1,n)...d i s(1,n)+k]f[N][dis(1,n)...dis(1,n)+k]f[N][dis(1,n)...dis(1,n)+k]- 3.최단 변종 2 (삭제):
??:
1.모든 모서리에 대해 길이 L, [sl,sr] 라인 트리 유지 보수 최소값 구하기 2.L=dis(1,x)+dis(y,n)+w - 4.삼원환 계수:
일.
1.크기점:??? 2.그림% 1개의 캡션을 편집했습니다. 정렬, 키워드(d[i], i), 각 점이 몇 번째인지 구합니다. D[x]:(x,y) 만약rank[x]y else rank[x]>rank[y]: y->x |D[x]|<=sqrt(m) 위조 코드(핵심 부분):
for 1 to x do
if (y∈D[x])res[y]=1;
for y∈D[x] do
for z∈D[y] do
ans+=res[z];
- 5.4원 링 계수
for x=1 to n // n
for y∈G[x]
for z∈D[y]
if(rank[x]
- 6.예제
제목: 당신은 지금 수열 A[1...N]가 무엇인지 알고 싶지만, 대가를 써서 정보를 얻어야 합니다. 당신은 Cost[L][R]의 값을 써서 A[L...R]의 합을 얻어서 Cost를 정하고, 최소 얼마의 대가를 치러야 A[1...N]•N<=1000,Cost[L][R]<=10^9
해:
A[l...r], 즉 S[r]-S[l-1]의 값을 알고 (S는 접두사와 수조) 매번 l-1과 r를 연결시켜 서로 밀어낼 수 있음을 나타낸다. 모든 관계를 알고 싶으면 모든 모서리를 넣고 최소 생성 트리를 한 번 만듭니다. (1번과 연결되어야 하기 때문에) prufer 시퀀스
뿌리가 없는 나무와 서열이 일일이 대응하는 관계를 나타낸다.
구조: 매번 가장 작은 잎 한 그루를 찾을 때마다 삭제한 후 그와 연결된 점을prufer 서열에 넣고 마지막에 두 점만 넣는다. prufer서열로 트리를 복원하는 절차:prufer서열이 이동한 후에 매번 하나를 찾은 후prufer서열에 나타나지 않고 이전에 표시하지 않은 가장 작은 노드를 표시하고 이 점을 표시하며 현재prufer서열의 이 점과 연결한다. 마지막으로 두 개의 도수가 충분하지 않은 점을 찾아 그들을 연결시킨다(사실은prufer서열을 만드는 과정에 따라 연결한다). 서열에 나타난 횟수 +1이 바로 이 점의 도수임을 쉽게 알 수 있다. 오로라 회로
이분도
기환을 판단하다
홀 가이드
7. 테두리 염색
8. 연습 문제
3. 문자열
KMP 문자 일치
최소 순환절을 찾습니다. (n-fail[n]도 순환절입니다. s[1]=s[n-fail[n]+1]), 즉 가장 긴 접두사입니다.
가장 작은 P를 찾아 s[i]=s[i-p]; 순순환절: n은 n-fail[n]의 배수예제
1. 각 접두사 S[1...i]에 대해 구할 문자열 S를 추가로 지정합니다. ⼏는 접두사와 같고 겹치지 않습니다. |S|<=1000000 2. m자리 숫자 문자열 S를 정하고 ⻓도가 n인 문자열 T를 구하십시오. ⾜S는 그의 문자열이 아닙니다.m<=20. n<=10^9 3. S[1...i]의 가장 ⼩ 순환절 d[i]를 지정하고 ⼀개 사전서의 가장 ⼩를 구성하는 S.|S|<=10^6 4. ⼀개의 직렬 S가 있는데 ⼀개의 우수한 분할을 정의하는 것은 ⼀개의 직렬을 AABB의 형식으로 표시하고 S의 모든 연속적인 ⼦열의 우수한 분할의 개수의 합을 구하는 것이다. |S|<=2000 5. AC 로봇접미사 배열
끊어... [울경]
n ∗ ( n + 1 ) 2 − ∑ i = 1 n − 1 h [ i ]\frac {n*(n+1)}{2}-\sum_{i=1}^{n-1} h[i] 2n∗(n+1)−∑i=1n−1h[i]
