Để làm bài này ta cần giải quyết từng yêu cầu một.

Subtask 1 (25 tests)

• Với yêu cầu tìm chiếc giày mất ta thấy rằng để có một dãy giày đúng thì tổng tất cả giày phải bằng ~0~. Hay nếu ta gọi ~x~ là chiếc giày mất ta sẽ có ~a_1 + a_2 + \dots + a_{2n-1} + x = 0~. Từ đây, ta suy ra ~x= -(a_1 + a_2 + \dots + a_{2n-1})~.

• Với yêu cầu tìm số lượng đôi giày có cùng kích cỡ với đôi giày bị lấy đi. Nếu đôi giày lấy đi là giày trái ta chỉ cần đếm số giày phải và ngược lại. Tức đếm ~-x~ xuất hiện bao nhiêu lần trong dãy.

• Với yêu cầu tìm đoạn các đôi giày được xếp đúng liên tiếp nhau có nhiều nhất. Mỗi vị trí ~i (1 \le i \le 2 \cdot n-1 )~ ta sẽ cho chạy biến ~j (i \le j \le 2 \cdot n-1 )~ Nếu a[j]+a[j+1]==0 thìcnt++ và j+=2.

Độ phức tạp ~\mathcal{O}(n^2)~.

Subtask 2 (5 tests)

• Hai yêu cầu như Subtask 1.

• Từ cách Subtask 1 ta thấy rằng nếu tại ví trí ~i~ là một đôi đúng ~(a_i+a_{i-1}=0)~ thì ta chỉ chọn được các đôi đúng ở vị trí ~0 \to i-2~. Vì thế ta suy ra công thức Quy hoạch động:

  • ~dp_i=dp_{i-2}+1~ nếu ~a_i+a_{i-1}=0~

  Và kết quả sẽ là phần tử lớn nhất trong ~dp~.

Độ phức tạp ~\mathcal{O}(n)~.

Code tham khảo của haruxne

#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i = k; i <= n; i++)
#define int long long
using namespace std;

const int N = 5e5+1;
int n, a[2*N], ans, sum, dp[2*N];

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    cin >> n;
    FOR(i,1,2*n-1) cin >> a[i], sum += a[i];
    FOR(i,1,2*n-2) if (a[i] + a[i+1]) dp[i] = 0; else dp[i] = dp[i-2] + 1;
    FOR(i,1,2*n-2) ans = max(ans, dp[i]);
    cout << -sum << ' ' << count(a+1,a+2*n,sum) << '\n' << ans;
}