P2569 https://www.luogu.com.cn/problem/P2569

이 문제를 참고하세요.

/*단조큐로 dp 최적화

주식을 매수하는 전이 방정식에서 j는 순차적으로 열거됩니다. 주식을 매수하는 것이므로 보유한 주식은 점점 증가할 것이며,
현재의 결정이 나중에(j가 더 클 때) 사용될 수 있으므로 먼저 구해야 합니다.
마찬가지로 주식을 매도할 때 보유한 주식은 점점 줄어들고,
즉 현재의 결정이 보유한 주식 수보다 적은 상태를 사용해야 할 수 있으므로,
역순으로 열거하여 미리 처리해야 합니다.*/

https://www.luogu.com.cn/record/223728748

AT_arc098_b \(x \oplus y \oplus \cdots \oplus z \le x+y+..+z\). XOR 연산은 자리 올림이 없는 덧셈이므로, 부분적으로만 같을 수 있고 전체적으로 같지는 않습니다.

P2882 어떻게 \(O(1)\) 시간으로 \(01\) 수열의 구간 뒤집기와 실시간 쿼리를 처리할까요? 아래 \(a_i \oplus x\)가 실제 값이고, \(b)가 차분 배열이며, \(k)가 뒤집기 길이입니다. 해당 if 문은 조건 판단입니다.

bool x=0;
for(int i=1;i<=n;i++)b[i]=0;
for(int i=1;i<=n;i++){
    x^=b[i];
    if(a[i]^x){
        x^=1;
        b[i+k]^=1;
    }
}

다음 세 가지는 모두 같습니다.

• 원래 그래프에서 두 점 사이의 모든 단순 경로에서 최대 가중치의 최소값.
• 최소 신장 트리에서 두 점 사이의 단순 경로에서의 최대값.
• Kruskal 재구성 트리에서 두 점의 LCA의 가중치.

P6835 https://www.luogu.com.cn/article/icz18zjz 수식을 다시 직접 유도해보는 것을 권장합니다.

최장 공통 부분 수열(LCS) 전이 방정식.

[f_{i,j}=\max(f_{i-1,j},f_{i,j-1}) ][if(a_i==b_j)\quad f_{i,j}=\max(f_{i,j},f_{i-1,j-1}+1) ]P2516 https://www.luogu.com.cn/record/224495353

세 가지 어려운 점이 있습니다. 먼저 문제에 따라 다음과 같습니다.

1. \(a_i\)와 \(b_j\)는 모든 \(lcs(i,j)\)에 포함됩니다.

2. \(a_i\)는 모든 \(lcs(i,j)\)에 포함되지만, \(b_j\)는 모든 \(lcs(i,j)\)에 포함되지 않습니다.

3. \(a_i\)는 모든 \(lcs(i,j)\)에 포함되지 않지만, \(b_j\)는 모든 \(lcs(i,j)\)에 포함됩니다.

4. \(a_i\)와 \(b_j\)는 모두 모든 \(lcs(i,j)\)에 포함되지 않습니다.

5. 만약 \(a_i=b_j\)이면, \(f_{i,j}=f_{i-1,j-1}+1\)이 되며, 이는 경우 1에 해당합니다.

6. 만약 \(f_{i,j}=f_{i,j-1}\)이면, \(b_j\)는 모든 \(lcs(i,j)\)에 포함되지 않으며, 이는 경우 2와 4에 해당합니다.

7. 만약 \(f_{i,j}=f_{i-1,j}\)이면, \(a_i\)는 모든 \(lcs(i,j)\)에 포함되지 않으며, 이는 경우 3과 4에 해당합니다.

8. 만약 \(f_{i,j}=f_{i-1,j-1}\)이면, 이는 경우 4에 해당하며, 이때 위의 두 가지 조건도 반드시 만족해야 합니다.

• 왜 그 부분을 빼나요? 포함-배제 원리에 따라 중복 계산이 되므로 한 번 빼줍니다.
• 슬라이딩 최적화(쉽게 틀릴 수 있음). 전이가 이전 상태에서 시작하므로 첫 번째 차원 크기는 2면 충분합니다. 새 변수로 첫 번째 차원을 슬라이딩합니다.
• 초기화. 첫 번째 차원을 슬라이딩했으므로 초기화할 필요가 없습니다. 다른 경계는 최소한 하나의 방안으로 설정해야 누적할 수 있습니다.

Skip1

P2051 https://www.luogu.com.cn/problem/P2051 이러한 그리드 문제는 모두 상태 압축을 고려해야 합니다. 각 행과 열에는 최대 두 개의 포만 배치할 수 있습니다. 그리고 이 행에서 0, 1, 2개의 포를 사용한 경우를 나누기만 하면 됩니다. 큰 분류 문제일 뿐입니다. 하지만 상태 설계도 어려운 점입니다.

\(f_{i,j,k}\)는 앞 \(i)개 행에서 \(j)개 열에 1개의 말을 배치하고, \(k)개 열에 2개의 말을 배치한 방법의 수를 나타냅니다.

2개의 말을 배치할 때의 실수 포인트: 빈 칸에 열을 추가하는 경우. 이때 열이 하나 줄어들고 1개의 열이 추가됩니다. 최종적으로 열 수는 변하지 않습니다!

볼록 함수에 일차 함수를 더해도 여전히 볼록 함수입니다.

P3605 서브트리 차분 https://www.luogu.com.cn/problem/P3605

n개의 노드를 가진 트리가 주어지며, 각 노드에는 점수가 있습니다. 각 노드의 서브트리 내에서 자신보다 점수가 높은 노드의 수를 구하십시오. \(n \le 10^5\).

어떤 값보다 큰 점수를 가진 노드의 수는 명확하게 트리 배열을 통해 유지할 수 있지만, 단일 서브트리 내에서 정확하게 계산하는 것이 핵심입니다.

DFS 과정에서 트리 배열을 업데이트하면, 이는 현재까지 처리된 노드까지의 각 값이 나타난 횟수를 유지하며, 반드시 단일 서브트리는 아닙니다.

DFS 과정에서 노드는 각각 한 번씩 진입(재귀)과 퇴출(백트래킹)을 합니다. 실제로 노드에 진입할 때 해당 노드의 서브트리 정보가 아직 트리 배열에 업데이트되지 않았고, 노드를 나올 때 해당 노드의 서브트리 정보가 모두 트리 배열에 추가된 상태입니다. 따라서 이 두 시점에서의 쿼리 값의 차이가 해당 서브트리의 기여도입니다. 이러한 사고방식은 서브트리 차분이라고 합니다.

서브트리 차분 예제: https://www.luogu.com.cn/problem/P1600

popcount(a^b)=popcount(a|b)-popcount(a&b)=
popcount(a)+popcount(b)-2popcount(a&b)

https://www.luogu.com.cn/problem/P3051 https://www.luogu.com.cn/article/sb4oa22b

아주 알아두면 좋은 테크닉입니다.

환을 선으로 분할하는 것은 환을 선으로 분할하는 것입니다!

기본 문제: 선이 주어지고, 여러 선분이 주어집니다. 선분이 이 선을 완전히 덮으려면 최소 몇 개의 선분을 선택해야 합니까?

모든 후보 선분을 왼쪽 끝점 \(l_i\) 기준으로 오름차순 정렬합니다. 만약 왼쪽 끝점이 같다면, 오른쪽 끝점 \(r_i\) 기준으로 내림차순 정렬합니다.

현재 선택한 구간이 앞 x개의 점을 이미 커버했다고 가정합시다. x+1번째 점을 커버하기 위해, 왼쪽 끝점이 x+1 이하인 구간을 반드시 선택해야 합니다. 그러면 왼쪽 끝점이 x+1 이하이고 오른쪽 끝점 위치가 가장 큰 구간을 선택하면, 최대한 많은 점을 커버할 수 있으므로 최적입니다.

이때 x를 이 오른쪽 끝점 위치로 업데이트합니다. 초기에 x=0으로 설정하고, 이 과정을 반복하여 구간을 선택합니다. x=n이 될 때까지 반복합니다. 만약 한 번 구간을 선택한 후 x가 여전히 변하지 않으면, x+1번째 점을 커버할 수 없다는 것이므로 해결책이 없습니다.

각 \(1 \le i \le n\)에 대해 왼쪽 끝점이 i 이하인 모든 구간 중에서 가장 큰 오른쪽 끝점 위치를 미리 처리하면, \(O(n+k)) 시간으로 미리 처리하고, \(O(n)) 시간으로 구간을 선택할 수 있으며, 총 시간 복잡도는 \(O(n+k))입니다.

환의 경우 P6902은 분할해야 하지만, \(O(n \log n))으로 만들기 위해 배수 증가를 최적화해야 합니다. https://www.luogu.com.cn/problem/P6902

https://www.luogu.com.cn/record/225195227

배열 경계 초과 위험‌: for(int j=0;j<=vec[i].size()-1;j++) 루프에서 vec[i]가 비어 있으면 vec[i].size()-1이 부호 없는 정수의 최대값이 됩니다(왜냐하면 size()는 부호 없는 수를 반환하므로), 이로 인해 루프 조건이 비정상적이 됩니다. for(int j=0;j<=(int)vec[i].size()-1;j++)로 변경하거나 반복자를 사용하는 것이 좋습니다.

Skip2

귀여운 문제 P2519 https://www.luogu.com.cn/problem/P2519 https://www.luogu.com.cn/article/jczkipeh

하지만 겹치는 구간 수가 구간 길이를 초과하면 반드시 거짓말이 있습니다.

이것은 쉽게 이해할 수 있습니다. 구간 길이가 k라는 것은 k명의 사람이 점수가 같다는 의미이지만, 이 구간 안에 있다고 말한 사람이 k명보다 많다는 것은 명백히 거짓말입니다.

많은 파란색 문제가 귀여운 문제이며, 귀여운 문제들은 모두 호화로운 문제들입니다.

https://www.luogu.com.cn/problem/AT_dp_t https://www.luogu.com.cn/problem/P2467 https://www.luogu.com.cn/article/o0oht8bj https://www.luogu.com.cn/article/sg1fwhh5

전이 방정식은 모두 유사하며, 파형을 처리하는 데 사용됩니다. \(f_{i,j}\)를 앞 i개 위치를 고려했고, i번째 위치에 j번째로 작은 숫자를 채웠을 때의 총 방법 수로 설정합니다. (순열이므로 j번째로 작은 것은 이 위치에 j를 채운 것과 같습니다).

P1070 드디어 정답을 알게 되었습니다!!!

https://www.luogu.com.cn/article/5p3x7ruk

신비로운 처리: 먼저 로봇이 공장으로 전환하고 동전을 고정하는 것을 생각해야 합니다. 다음은 똑똑한 전이 변형입니다.

P6647 https://www.luogu.com.cn/record/225529688

P3188 매우 흥미로운 dp입니다.

연결 그래프의 최장 경로 찾기 방법: 위상 정렬과 dp를 사용합니다.

1. 위상 정렬을 통해 노드 처리 순서를 결정합니다.
2. \(dp_i\)를 노드 i로 끝나는 최장 경로 길이로 정의합니다.
3. 전이: \(dp_i=max(dp_j+w_{j,i})\), 모든 진입 간선 j→i에 대해.

Skip 3

P1600 https://www.luogu.com.cn/problem/P1600 .

해설: https://www.luogu.com.cn/article/nkwnx1ti .

두 구간 경로 s→lca와 lca→t를 나누어 토론하고, 관찰 가능한 조건을 유도하면 서브트리 차분으로 해결할 수 있습니다.

https://www.luogu.com.cn/record/226182410

서브트리 노드의 DFS 순서는 연속 구간을 형성하므로 직접 순회할 수 있습니다.

원방 트리의 노드 수는 2n보다 작습니다. 이는 컷 포인트의 수가 n보다 작기 때문입니다. 따라서 배열 크기를 두 배로 열어야 합니다.

오일러 경로 의사 코드.

void dfs(int now)
{
    for(int i=del[now];i<G[i].size();i=del[now])
    {
        del[now]=i+1;
        dfs(G[now][i])
    }
    st.push(now);
 }
 //여기서 del[now]는 G[now][1,2,…,del[now]-1] 
//이 모두 표시되었으며, 다음에는 G[now][del[now]]에서 시작하여 접근해야 함.

‌SPFA 알고리즘은 한 간선이 여러 번 통과되는 것을 허용하지만, Dijkstra 알고리즘은 한 간선이 여러 번 통과되는 것을 허용하지 않습니다.

CF609E: n개의 점, m개의 간선이 있고, 최소 신장 트리에서 i번째 간선(1 ≤ i ≤ m)을 반드시 포함해야 한다면, 최소 신장 트리의 가중치 합계의 최소값은 얼마입니까? 1 ≤ n ≤ 2 × 10^5, n-1 ≤ m ≤ 2 × 10^5.

최소 신장 트리를 구하고, i번째 간선을 추가하면, 그 후 하나의 순환이 발생합니다. 순환에서 가장 큰 가중치의 간선을 끊으면 됩니다. 물론 자기 자신은 끊을 수 없으므로, 원래 mst에서 u→v의 가중치가 가장 큰 간선을 끊습니다. 트리 분할을 유지하면 됩니다.

동여 최단 경로.

https://www.luogu.com.cn/problem/P3403 .

https://www.luogu.com.cn/problem/P2371 .

다점 최단 경로의 최소값을 두 점 최단 경로로 변환.

https://www.luogu.com.cn/problem/P5304 .

두 개의 집합으로 나누고, 집합 간의 점이 반드시 최소 최단 경로를 구성하지 않도록 한 후, 시작점 s가 집합 1을 연결(가중치 0), 종점 t가 집합 2를 연결, 집합 1과 2가 서로 연결합니다. 그러면 원래 문제는 s→t의 최단 경로로 변환됩니다.

핵심은 점 집합을 어떻게 나누는 것입니다. https://www.luogu.com.cn/problem/solution/P5304?page=1 .

https://www.luogu.com.cn/problem/P3199 .

ans를 가중치 방향 그래프의 모든 순환 평균값의 최소값으로 설정합니다. 임의의 방향 그래프 G에 대해, 점 s를 추가한 후.

[ans=\min_{v \in V,F_n(v)\ne \infty }\max_{0 \le k \le n-1}[\frac{F_n(v)-F_k(v)}{n-k} ] ]여기서 \(F_k(v)\)는 s→v의 정확히 k개의 간선을 지난 최단 경로(존재하지 않으면 \(\infty\))입니다.

01 분수 계획: https://blog.csdn.net/niiick/article/details/80925267 .

Skip 4

https://www.luogu.com.cn/problem/P3430 .

두 개의 배열이 주어지며, 각 배열에 동일한 숫자가 나타나지 않아야 합니다. 두 배열의 동일한 위치에 있는 숫자는 서로 교환할 수 있으며, 최소 몇 번 교환해야 이 요구 사항을 만족할까요?

만약 두 개의 동일한 숫자가 동일한 행에 없다면, 두 숫자가 있는 열의 번호에 가중치 0의 간선을 연결하고, 그렇지 않으면 가중치 1의 간선을 연결합니다.

각 연결 요소의 점을 흑백으로 칠합니다(1 간선으로 연결된 점은 색이 반대이고, 0 간선으로 연결된 점은 색이 같습니다). 답은 각 연결 요소의 검은 점과 흰 점 수의 최소값을 더하는 것입니다.

https://www.luogu.com.cn/article/rfudqj2s .

해설이 명확하지 않은 부분이 있으므로, 여기서 그룹 내의 VainSylphid 대답에 감사드립니다. 다음은 원문입니다:

1 간선은 이 두 열 중 정확히 하나가 교환되기를 원한다는 것과 같습니다. 0 간선은 이 두 열 중 하나가 교환되면 다른 하나도 교환해야 한다는 것과 같습니다.

그러면 해당 해설 방식으로 칠하면, 동일한 색상은 전부 교환하거나 전부 교환하지 않아야 합니다.

그리고 검은색과 흰색 중 하나는 전부 교환하고, 다른 하나는 전부 교환하지 않습니다.

그러면 최소값을 취하는 것은 명백합니다.

2025.7.28-7.29 기울기 최적화 주제

오늘은 기울기 최적화 주제입니다. https://www.bilibili.com/video/BV1dKSJY5Ew5 .

P2365 https://www.luogu.com.cn/article/367gcax3

비용을 미리 계산하는 것이 매우 중요합니다. 새로운 구간의 비용이 이미 f에 중첩되어 있습니다.

https://www.luogu.com.cn/record/227393110

항을 이동하는 원칙은 다음과 같습니다:

• function(i)×function(j)를 포함하는 식을 kx로 봅니다.
• dp_i를 포함하는 항은 b의 표현식에 있어야 합니다.
• function(j)를 포함하는 항은 y의 표현식에 있어야 합니다.
• 미지수 x의 표현식이 단조 감소하면, 등식 양변에 -1을 곱하여 단조 증가로 만드는 것이 좋습니다.

간결한 기억 버전:

• 교차 항 kx.
• dp_i → b.
• fuc_j → y.

단조 큐로 볼록 껍질 점 집합을 유지하고, 작업은 세 단계로 나뉩니다:

1. 최적화 필터링을 수행할 때, 볼록 껍질에서 최적 결정 점 j를 찾습니다.
2. 최적 결정 점 j를 사용하여 dp_i를 업데이트합니다.
3. i를 결정 점으로 그래프에 추가하고 볼록 껍질을 업데이트합니다(만약 i가 dp_i의 결정 점 중 하나이면 3을 가장 앞으로 옮겨야 합니다).

Skip 5

https://www.luogu.com.cn/problem/P5677 .

좋은 문제입니다.

:::info 정렬하고, 모든 좋은 쌍을 처리합니다. 오프라인으로, 왼쪽 끝점을 기준으로 정렬하고, 현재 열거하는 r보다 작거나 같은 선계속 추가하고, l 이전의 선을 제거하면 현재 기여도입니다. :::

https://www.luogu.com.cn/record/228032569 .

P7706 https://www.luogu.com.cn/problem/P7706 .

못하겠어서 10분 동안 생각해보다가 화났습니다. 멋진 문제입니다. 사실 매우 기본적인 문제이지만, 이 테크닉을 모릅니다. https://www.luogu.com.cn/article/oj2vo7sx . 설명이 매우 명확하므로 추가 설명이 필요 없습니다.

https://www.luogu.com.cn/problem/P3792 https://www.luogu.com.cn/problem/P5278

"이중 경험", https://www.luogu.com.cn/article/itudyc23 학습 사고방식.

Luogu P5278에서, 이전 최대값(즉, 구간 내 각 요소가 마지막으로 나타난 위치의 최대값)을 유지하는 핵심 목적은 요소의 중복성을 빠르게 검색하는 것입니다. 만약 이 최대값이 구간 왼쪽 끝점보다 크거나 같다면, 적어도 하나의 요소가 구간 내에서 중복되어 나타난다는 의미입니다.

치환 순환 https://www.cnblogs.com/TTS-TTS/p/17047104.html .

• 오일러 순서 LCA 알고리즘

‌전처리 복잡도‌: \(O(n + n \log n) = O(n\log n)\).

‌쿼리 복잡도‌: \(O(1)\).

‌구현 방식‌: LCA 문제를 RMQ 문제로 변환하고, ST 표로 해결합니다.

• 배수 증가 LCA 알고리즘

‌전처리 복잡도‌: \(O(n\log n)\).

‌쿼리 복잡도‌: $O(\log n) $.

‌구현 방식‌: 각 노드의 \(2^k\) 수준 조상을 전처리하고, 배수 증가 사상을 사용하여 쿼리합니다.

가상 트리에서, 각 파란 점은 하나의 연결 요소에 해당하며, 연결 요소 크기는 해당 파란 점의 원래 트리에서 서브트리 크기에서 파란 점의 자식 서브트리 크기를 뺀 것입니다.

Skip 6

\(G=(X,Y,E)\)가 이분 그래프이고, \(\left | X \right | \le \left | Y \right |\)라고 가정합시다. 임의의 \(W\subseteq X\)에 대해, \(V(W)\)를 G에서 W의 정점과 인접한 모든 정점의 집합으로 기록합니다. 그러면 모든 \(W\subseteq X\)에 대해 \(\left | W \right | \le \left | V(W) \right |\)가 성립할 때만, G에 대한 매칭 M이 존재하여 X의 모든 점이 매칭 점입니다

모든 정규 이분 그래프에는 완벽한 매칭이 있습니다. (정규 이분 그래프에서 모든 정점의 차수가 같습니다).

삭제 작업은 오프라인으로 역순으로 바꾸어 추가 작업으로 만들 수 있습니다.

n×m 행렬 A가 있습니다. A의 각 요소는 \([0,10^5]\)의 정수입니다. 형식적으로 다음과 같습니다.

[E_{i,j}=\sum_{1\le x\le n}\sum_{1\le y\le m}(|x-i|+|y-j|)A_{x,y} ]이제 행렬 E를 사용하여 위 조건을 만족하는 정수 행렬 A를 복원해야 합니다. 복원된 A의 각 요소는 \([0,10^{16}]\)에 속하면 됩니다.

단번 시간 복잡도는 \(O(nm)\)여야 합니다.

이렇게 멋진 문제입니다.

다음과 같이 설정합니다:

[C_i=\sum_{j=1}^{m}A_{i,j} ][E_{i,j}=\sum_{1\le x\le n}\sum_{1\le y\le m}(|x-i|+|y-j|)A_{x,y} ]이 식에서 다음과 같은 점을 알 수 있습니다:

[E_{i,j}=\sum_{x=1}^{n}\left |x-i \right |\times C_x+\sum_{x=1}^{m}\left |x-j \right |\times R_x ]더 나아가:

[E_{i-1,j}+E_{i+1,j}-2\times E_{i,j}=2\times C_i ]여기서 \(2 \le i \le n-1\).

마찬가지로 \(R_j\)를 구할 수 있습니다.

[R_j=\sum_{i=1}^{n}A_{i,j} ]즉, 결정할 수 없는 것은 \(C_1,C_n,R_1,R_m\)뿐입니다.

탐욕적 방법을 고려해봅시다. 각 \(A_{i,j}\)를 차례대로 고려하고, 직접 \(\min(R_i,C_i)\)로 설정한 후, \(R_i\)와 \(C_i\)에서 동시에 \(A_{i,j}\)를 빼 계속 진행합니다. 그러면 해결책이 있다면 이렇게 하면 반드시 음이 아닌 정수인 \(A_{i,j}\)의 해결책을 구성할 수 있습니다.

이렇게 신비로운 문제가 끝났습니다(아마도?).

:::info 여기서 n=1과 m=1인 경우를 특별히 처리해야 합니다! 이 두 경우는 다른 해결 방법으로 전환해야 합니다! :::

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,l,r) for(int i=l;i<=r;i++)
int n,m;
void solve(){
    cin>>n>>m;
    vector<vector<int> >E(n+1),A(n+1);
    vector<int>C(n+1),R(m+1);
    For(i,1,n){
        E[i].resize(m+1);
        A[i].resize(m+1);
    }
    For(i,1,n)For(j,1,m)cin>>E[i][j];
    For(i,2,n-1)C[i]=(E[i-1][1]+E[i+1][1]-2*E[i][1])/2;
    For(i,2,m-1)R[i]=(E[1][i-1]+E[1][i+1]-2*E[1][i])/2;
    if(n==1&&m==1){cout<<E[1][1]<<"\n";return ;}
    if(n==1){
        R[1]=E[1][m];
        For(i,2,m-1)R[1]-=(m-i)*R[i];
        R[m]=E[1][1];
        For(i,2,m-1)R[m]-=(i-1)*R[i];
        R[1]/=m-1,R[m]/=m-1;
        For(i,1,m)cout<<R[i]<<" ";
        cout<<"\n";
        return;
    }
    if(m==1){
        C[1]=E[n][1];
        For(i,2,n-1)C[1]-=(n-i)*C[i];
        C[n]=E[1][1];
        For(i,2,n-1)C[n]-=(i-1)*C[i];
        C[1]/=n-1,C[n]/=n-1;
        For(i,1,n)cout<<C[i]<<"\n";
        return;
    }
    int X=E[1][1];
    int Y=E[1][m];
    int Z=E[n][1];
    For(i,2,n-1){
        X-=(i-1)*C[i];
        Y-=(i-1)*C[i];
        Z-=(n-i)*C[i];
    }
    For(i,2,m-1){
        X-=(i-1)*R[i];
        Y-=(m-i)*R[i];
        Z-=(i-1)*R[i];
    }
    int W=0;
    For(i,2,m-1)W+=R[i];
    For(i,2,n-1)W-=C[i];
    W=W*(n-1)*(m-1);
    W-=(m-1)*Z-(n+m-2)*X-(n-1)*Y;
    W/=n-1,W/=2*n+2*m-4;
    C[n]=W;
    C[1]=(Z-X)/(n-1)+C[n];
    R[1]=(Y-(n-1)*C[n])/(m-1);
    R[m]=(X-(n-1)*C[n])/(m-1);
    For(i,1,n){
        For(j,1,m){
            A[i][j]=min(C[i],R[j]);
            C[i]-=A[i][j];
            R[j]-=A[i][j];
        }
    }
    For(i,1,n){
        For(j,1,m){
            cout<<A[i][j]<<" ";
        }
        cout<<"\n";  
    }
} 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}

Skip 7

두 개의 스택이 있으며, 각 스택에는 n×K개의 요소가 있습니다. 여기서 숫자 1,2,...,n은 각각 정확히 K번 나타납니다.

다음과 같은 작업을 계속 수행하여 한 스택이 비워질 때까지:

• 현재 두 스택의 맨 위 요소가 같으면, 두 스택의 맨 위 요소를 모두 팝하고 1점을 얻습니다.
• 현재 두 스택의 맨 위 요소가 다르면, 한 스택의 맨 위 요소를 팝하고 점수를 얻지 않습니다.

합리적인 작업을 통해 최대 점수를 얼마나 얻을 수 있습니까?

모든 데이터에 대해, 1≤n≤10^4, 1≤K≤16이 보장됩니다.

모든 점수를 얻는 순간을 고려하고, 매칭되는 두 요소의 원래 스택에서 위치를 표시하면, 두 개의 단조 증가하는 시퀀스 x,y를 얻습니다. 여기서 a_{x_i}=b_{y_i}를 만족합니다.

반대로, 두 시퀀스가 위 요구 사항을 만족한다면, 특정 작업을 통해 점수를 얻을 수 있습니다. 따라서 목표는 조건을 만족하면서 시퀀스 길이를 최대화하는 것입니다.

모든 가능한 (x_i,y_i)를 가져와서 전순 관계 i < j를 정의합니다. (x_i,y_i) < (x_j,y_j)입니다. (여기서 작음은 두 차원 모두에서 작음을 의미합니다). 총 nK^2쌍입니다.

:::info 왜 nK^2쌍입니까? 총 n개의 숫자가 있고, 각 숫자는 첫 번째 스택에 K번, 두 번째 스택에도 K번 나타납니다. :::

가장 긴 증가 부분 수열을 찾으면 됩니다. 속지 마세요.

#include<bits/stdc++.h>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
const int N=2e5+10;
int n,k,a[N],ans;
int t[N],p[N][20],cnt[N];
inline int qry(int x){
    int res=0;
    for(;x;x-=x&(-x))res=max(res,t[x]);
    return res;
}
inline void upd(int x,int v){
    for(;x<=n*k;x+=x&(-x))t[x]=max(t[x],v);
}
int main(){
    cin>>n>>k;
    For(i,1,n*k)cin>>a[i];
    For(i,1,n*k){int x;cin>>x;p[x][++cnt[x]]=i;}
    For(i,1,n*k){
        for(int j=k;j>=1;j--){
            int res=qry(p[a[i]][j]-1)+1;
            ans=max(ans,res);
            upd(p[a[i]][j],res);
        }
    }
    cout<<ans;
    return 0;
}

Skip 8

k개의 수에서 1부터 k까지 각 값이 정확히 한 번씩 나타나는지 판단

1부터 k까지를 64비트 부호 없는 정수 p_i로 임의로 할당합니다. 각 i(1≤i≤k)에 대해 s_i를 1부터 i까지의 XOR 합으로 전처리합니다. k개 수의 가중치 XOR 합이 s_k와 같은지 판단합니다.

\(\max(p,q)-\min(p,q)=\left |p-q \right |\).

mex=i → mex ≥ i를 구합니다.

중복 없이 부분 집합을 찾기: for(int i=u;i;i=(i-1)&u)f[u]+=f[i];//i는 u의 부분 집합.

트리의 어떤 노드 u에 대해, 루트까지의 경로에서 중간 체인 수는 가벼운 간선 수보다 -1을 초과하지 않습니다.

트리의 어떤 노드 u에 대해, 루트까지의 경로에서 중간 체인 수는 O(log n)을 초과하지 않으며, 가벼운 간선 수도 O(log n)을 초과하지 않습니다.

Skip 9

길이가 n인 시퀀스 a는 0≤a_i < 2^m이고 시퀀스의 숫자는 모두 다릅니다. F(x)를 ∀a_i, a_i→a_i ⊕ x 후 시퀀스의 역순 쌍 수로 정의합니다.

이제 k번째로 작은 x를 찾아야 합니다. x_i < x_j는 F(x_i) < F(x_j)이거나, F(x_i)=F(x_j)이고 x_i < x_j일 때 정의합니다.

100% 데이터에 대해, 1≤T≤10, 1≤n,∑n≤10^6, 1≤m≤30, 0≤a_i < 2^m, 1≤k≤2^m. a_i는 서로 다름이 보장됩니다.

XOR 후 비교는 비트 단위로 고려할 수 있습니다. 두 수의 가장 높은 다른 이진 비트를 L로 설정하면, 두 수의 크기 관계가 변경되는 것은 x의 L번째 비트가 1일 때입니다.

:::info 이는 L-1 비트가 같기 때문입니다. 동일한 숫자를 XOR해도 영향이 없습니다. L번째 비트는 x의 값에 관계없이 두 수가 반드시 다르므로, L 비트 이후의 값은 크기에 영향을 미치지 않습니다.

그러면 이 비트가 1일 때 크기 관계를 변경할 수 있습니다.

0 ⊕ 1=1,1⊕1=0;0 ⊕ 0=0,1⊕0=1 :::

따라서 각 이진 비트는 독립적입니다. 초기 역순 쌍 수와 각 이진 비트에 1을 XOR했을 때 역순 쌍 수의 변화량을 구해야 합니다. 전자는 병합 정렬이나 트리 배열을 통해 쉽게 구할 수 있습니다.

:::info 역순 쌍 수의 변화량은 앞 이진 비트가 같은 그룹으로 묶고, 각 그룹에서 역순 쌍 수를 구하는 것을 의미합니다. :::

후자는 높은 비트부터 낮은 비트까지 이진 비트를 열거하고, 이 비트가 다른 수에 대해 역순 쌍 수를 구합니다(0/1만), 그리고 이 비트를 기준으로 시퀀스를 두 하위 시퀀스로 나누어 각각 계속합니다. 이 부분의 시간 복잡도는 O(nm)입니다.

그다음 문제는 m개의 수에서 몇 개를 선택하여 합을 구하고, k번째로 작은 합을 찾는 것입니다. m개의 수를 두 부분으로 나누어 각 부분은 m/2개의 수를 가지고, 각 부분의 모든 선택 방법의 합을 구하고 정렬합니다. 시간 복잡도는 O(m2^{m/2})입니다.

이렇게 하면 두 시퀀스에서 각각 하나를 선택하여 조합하는 문제로 변환됩니다. 그 다음 이분 탐색 s를 수행하고, s보다 작거나 같은 합을 가지는 선택 방법의 수를 계산합니다. 여기서는 두 시퀀스에서 이중 포인터를 사용하여 스캔할 수 있습니다. 이 부분의 시간 복잡도는 O(2^{m/2} log n)입니다.

Skip 10

삭제 작업을 만나면 시간을 거꾸로 돌려 추가 작업을 수행합니다.

"두 점 u,v에 대해 두 개의 간선이 겹치지 않는 경로가 존재"와 "u,v가 동일한 간선 이중 연결 요소에 속함"은 서로 필요충분 조건입니다.

:::info Menger 정리: 무방향 그래프에서 두 다른 정점 u와 v 사이의 최대/간격이 겹치지 않는/경로 수는 u와 v를 분리하기 위해 삭제해야 하는 최소 간선 수와 같습니다. :::

문제.

간소화된 문제는 LeetCode 253이며, 다음은 간소화된 버전의 해결책입니다.

각 밴드의 공연 시간은 겹칠 수 없으며, 이는 "각 구간에 색상을 할당하고, 겹치는 구간의 색상이 달라야 함"과 동일합니다. 우리는 최소 색상 수가 필요하며, 이는 구간 그래프의 최소 색상 수입니다.

임의의 구간 집합에 대해, 최소 색상 수 = 임의 시점에서의 최대 중첩 횟수

다음은 단계입니다. 참고: 구간 포함 관계에 관계없이 이러한 알고리즘은 올바릅니다. 힙 내의 요소가 현재 사용 가능하면 나중에도 사용 가능하며, 현재 사용하는 것이 반드시 더 나쁘지 않습니다. 또한 정렬로 인해 후에 다른 영향을 미치지 않습니다. 왜냐하면 왼쪽 끝점이 같은 것들은 모두 한곳에 있고, 다음을 스캔할 때 이미 모두 큐에 들어갔기 때문입니다.

• 먼저, 구간을 왼쪽 끝점 기준으로 오름차순 정렬합니다.

• 다음으로, 최소 힙 우선 큐를 사용하여 최대 중첩 횟수를 계산합니다.

• 현재 구간 [l_i, r_i]에 대해, 먼저 힙 상단 요소(가장 일찍 끝나는 공연 종료 시간 top_r)를 확인합니다.

• 만약 top_r < l_i이면, 즉 가장 일찍 끝나는 공연이 현재 공연 시작 전에 이미 끝났으며, 겹치지 않습니다. 그러면 힙 상단 요소를 팝합니다. 해당 밴드가 현재 공연을承接할 수 있으므로 새로운 밴드가 필요하지 않습니다.

• 현재 구간의 오른쪽 끝점 r_i를 힙에 추가하여 새로운 진행 중인 공연을 나타냅니다. 만약 힙 크기가 증가하면, 더 많은 밴드가 필요할 수 있습니다.

• 힙 크기는 현재 동시에 진행 중인 공연 수이며, 이는 이 시점에 필요한 밴드 수이며, 최대값이 답입니다.

이 문제로 돌아갑시다.

특정 시간 구간에서 밴드 수를 어떻게 구하는지 고려해봅시다. 왼쪽에서 오른쪽으로 순차적으로 탐욕적으로 하는 것이 맞습니다. 현재 상속할 수 있다면 반드시 상속하는 것이 더 좋으며, 현재 힙에 있는 오른쪽 끝점을 기록합니다. 가장 왼쪽에 있는 것이 l ≤ 이라면 팝하고 r을 추가하며 비용은 0입니다. 그렇지 않으면 r을 직접 추가하며 비용은 1입니다.

각 시간 구간의 커버 횟수 t_i를 고려해봅시다. 위 분석에 따르면 답은 max t_i입니다.

직접 dp t_i를 설정하고, t_0 = t_{n+1} = 0으로 설정합니다. 시퀀스 t가 유효한 것은 |t_{i+1}-t_i| ≤ 1일 때입니다.

또한 t_i가 몇 개의 구간 집합에 해당하는지 고려해야 합니다. t_i = t_{i+1}인 경우, i에 의해 커버되는 각 구간에 대해, 변경되지 않거나; 가장 왼쪽에 있는 구간의 왼쪽 끝점이 i에서 끝나고, 동시에 i+1에서 새로운 구간이 시작됩니다. 총 2가지 방안입니다.

k = ∑i[t_i ≠ 0 ∧ t_i = t_{i+1}]를 기록하면, 기여도는 2^k입니다. 여기서 방안은 다른 위치에 대한 영향이 독립적입니다. 인접 위치의 매핑만 고려하면 되므로 기여도는 2입니다. 다른 경우의 매핑은 모두 유일합니다.

유효한 구간 집합과 |t_{i+1}-t_i| ≤ 1을 만족하는 커버 횟수 시퀀스 t는 일대일 대응 관계이며, 시퀀스에서 인접 위치 t_i와 t_{i+1}의 관계는 i에서 i+1까지의 구간의 증감(해당 구간의 시작 또는 끝)을 직접 결정하며, 인접 위치의 t만으로 구간 집합의 구조를 유일하게 결정하고 기여도를 계산할 수 있으며, 비인접 위치를 고려할 필요가 없습니다.

단순 dp를 수행하며, O(n^3)입니다.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
const int p=998244353;
int n;
/*최대 k개의 밴드를 사용할 때의 유효한 집합 수를 계산하는 동적 계획
충돌의 정의:
두 공연의 시간 구간이 겹칩니다.
끝점에서 겹치는 것을 포함합니다*/ 
ll dp(int k){
    /*f[i]는 모든 시간 구간을 고려한 후,
	선택된 공연 중 최대 충돌 깊이가 i인 유효한 집합 수
	f[i]는 선택된 공연들이 서로 완전히 겹치지 않는 집합을 통계합니다.
	예를 들어 [1,2], [3,4], [5,6]과 같은 시간 구간,
	임의의 두 개도 겹치지 않으며, 동시에 진행되는 공연은 최대 1개뿐입니다*/
    vector<ll>f(n+1),g(n+1);
    f[0]=1;
    For(i,0,n-1){
        fill(g.begin(),g.end(),0);
        For(j,0,k){
            /*1번 경우: 현재 시간 구간을 선택하지 않음 
			또는 선택했지만 충돌 깊이를 증가시키지 않음
			(j=0일 때 충돌 없음*/
            g[j]=(g[j]+f[j]*(j?2:1))%p;
            //2번 경우: 깊이 j+1에서 j로 전이
            if(j+1<=k){
                g[j]=(g[j]+f[j+1])%p;
            }
            //3번 경우: 깊이 j-1에서 j로 전이
            if(j-1>=0){
                g[j]=(g[j]+f[j-1])%p;
            }
        }
        swap(f,g);
		//새 상태가 이전 상태가 되고, 이전 상태는 직접 덮어씁니다
    }
    //최대 k개의 밴드를 사용한 유효한 집합 총수를 반환
    return (f[0]+f[1])%p;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    For(k,1,n)cout<<dp(k)<<" ";
    return 0;
}

tarjan 알고리즘은 다음을 알려줍니다: 만약 y가 x의 자식 노드이고 low(y)≥dfn(x)라면, x는 컷 포인트입니다. 만약 루트 x가 두 개 이상의 서브트리를 가지면, x는 컷 포인트입니다.

차분 제약 조건을 사용하여 최장 경로를 구하면, 하한 제약 조건이 있는 경우 사전 순으로 최소 해결책을 얻습니다.

하나의 경로의 lca가 다른 경로에 있으면, 두 경로는 교차하며, 그렇지 않으면 교차하지 않습니다.