APIO 2023 - Sequence

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
C++
Điểm: 2600 (p) Thời gian: 1.5s Bộ nhớ: 2G Input: bàn phím Output: màn hình

Trong thế giới đầy mê hoặc của APIO có một học sinh trẻ tuổi và thông minh tên Alice. Alice rất thích giải những bài toán thú vị thử thách năng lực toán học. Một ngày nọ, cô bắt gặp một dãy số bí ẩn có độ dài \(N\),

\[ A[0],A[1],\ldots,A[N-1], \]

và muốn khám phá những bí mật của nó.

Trước hết, ta đưa ra một số định nghĩa. Ký hiệu

\[ W(l,r,x)=\sum_{i=l}^{r} I[A[i]=x] \]

là số lần giá trị \(x\) xuất hiện trong đoạn \(A[l],A[l+1],\ldots,A[r]\). Ở đây, \(I[P]\) bằng \(1\) nếu mệnh đề \(P\) đúng và bằng \(0\) nếu \(P\) sai.

Với một dãy số nguyên không rỗng \(B[0],B[1],\ldots,B[k-1]\), gọi \(S(\{B[0],B[1],\ldots,B[k-1]\})\) là tập các trung vị của dãy. Tập này được xác định như sau:

  1. Sắp xếp các phần tử của \(B\) theo thứ tự không giảm để thu được dãy \(C[0],C[1],\ldots,C[k-1]\).

  2. Khi đó

    \[ S(\{B[0],B[1],\ldots,B[k-1]\})= \left\{C\!\left[\left\lfloor\frac{k-1}{2}\right\rfloor\right], C\!\left[\left\lceil\frac{k-1}{2}\right\rceil\right]\right\}. \]

Ví dụ:

\[ S(\{6,3,5,4,6,2,3\})=\{4\}, \]
\[ S(\{4,2,3,1\})=\{2,3\}, \]
\[ S(\{5,4,2,4\})=\{4\}. \]

Ký hiệu \(S(l,r)\) là tập các trung vị của đoạn \(A[l],A[l+1],\ldots,A[r]\). Alice muốn tìm giá trị lớn nhất của

\[ \max_{x\in S(l,r)} W(l,r,x) \]

trên mọi cặp chỉ số \(0\le l\le r\le N-1\). Alice đã có đáp án và nhờ bạn viết chương trình để kiểm chứng đáp án đó.

Yêu cầu cài đặt

Bạn cần cài đặt hàm sau:

C++
int sequence(int N, std::vector<int> A);
  • N: độ dài của dãy A.
  • A: mảng độ dài \(N\) mô tả dãy.
  • Hàm phải trả về giá trị lớn nhất trên mọi cặp \((l,r)\) hợp lệ như đã định nghĩa ở trên.
  • Hàm được gọi đúng một lần.

Submission phải sử dụng khai báo trong sequence.h, chỉ cài đặt hàm trên và không tự cài đặt main hay đọc/ghi trực tiếp qua standard input/output.

Ví dụ

Ví dụ 1

Xét lời gọi:

C++
sequence(7, {1, 2, 3, 1, 2, 1, 3});

Hàm phải trả về \(3\).

Trong trường hợp này, \(S(0,5)=\{1,2\}\), \(W(0,5,1)=3\) và \(W(0,5,2)=2\). Vì vậy giá trị ứng với cặp \((0,5)\) là \(3\). Có thể kiểm chứng rằng đây là giá trị lớn nhất trên mọi cặp hợp lệ.

Ví dụ 2

Xét lời gọi:

C++
sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1});

Hàm phải trả về \(2\).

Ví dụ 3

Xét lời gọi:

C++
sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});

Hàm phải trả về \(3\).

Ràng buộc

  • \(1\le N\le5\times10^5\).
  • \(1\le A[i]\le N\).

Phân nhóm

Subtask Điểm Ràng buộc bổ sung
\(1\) \(11\) \(N\le100\).
\(2\) \(17\) \(N\le2\times10^3\).
\(3\) \(7\) Tồn tại \(x\) sao cho với mọi \(0\le i<x\), \(A[i]\le A[i+1]\), và với mọi \(x<i<N\), \(A[i]\le A[i-1]\).
\(4\) \(12\) \(A[i]\le3\).
\(5\) \(13\) \(W(0,N-1,A[i])\le2\) với mọi \(0\le i\le N-1\).
\(6\) \(22\) \(N\le8\times10^4\).
\(7\) \(18\) Không có ràng buộc bổ sung.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo khuôn dạng sau:

  • Dòng đầu chứa \(N\).
  • Dòng thứ hai chứa \(A[0],A[1],\ldots,A[N-1]\).

Trình chấm mẫu in trên một dòng giá trị mà hàm sequence trả về.

Phần này chỉ mô tả giao diện của trình chấm mẫu; submission vẫn phải cài đặt hàm sequence như ở trên.

Nguồn

Kho đề và dữ liệu chính thức APIO 2023, bài Sequence. Gói nguồn được phát hành theo giấy phép CC0 1.0.

Tệp

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: