Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Các bài Div 3 Codeforces


  • Please log in to reply
Chủ đề này có 2 trả lời

#1 tritanngo99

tritanngo99

    Đại úy

  • Điều hành viên THPT
  • 1743 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng

Đã gửi 02-10-2019 - 11:28

Bài 1: [590-Div.3 -F]

Bạn được cho một xâu s chỉ chứa các kí tự thuộc 20 kí tự thường đầu tiên của kí tự Latin (‘a’,’b’,…,’t’).

Gọi s[l;r] là một xâu con của xâu s: s(l)s(l+1)...s(r). Ví dụ, xâu con của “codeforces” là “code”,”force”,”f”,”for”, còn “coder” và “top” thì không.

Bạn có thể biểu diễn các phép toán dưới đây không quá 1 lần: Chọn một xâu con bất kỳ s[l;r] và chuyển nó thành xâu nghịch đảo (nghĩa là chuyển xâu s(l)s(l+1)...s(r) thành s(r)s(r-1)...s(l)).

 

Mục tiêu của bạn là tìm ra độ dài lớn nhất của xâu con chỉ chứa các kí tự xuất hiện một lần.

Ví dụ: Các xâu “abcdef”, “arctg”,”minecraft” là những xâu mà các kí tự chỉ chứa 1 lần, trong khi đó “aba”,”aacc” là những xâu mà tồn tại 1 kí tự xuất hiện hai lần.

Đầu vào:

+ Dòng đầu tiên chứa xâu s (length(s)<=10^6) và chỉ gồm các kí tự ‘a’,’b’,…,’t’.

Đầu ra:

In ra kết quả cần tìm.

Ví dụ:

abacaba

Kết quả: 3


Yêu quê hương thương nhân loại núi sông cảm mến

Hiểu Thánh triết biết nghĩa nhân trời đất chở che


#2 tritanngo99

tritanngo99

    Đại úy

  • Điều hành viên THPT
  • 1743 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng

Đã gửi 02-10-2019 - 12:50

Bài 2: [590-Div .3-E]

Chúng tôi định nghĩa p_i(n) theo hoán vị sau: [i,1,2,…,i-1,i+1,n]. Ví dụ:

p_1(4)=[1,2,3,4];

p_2(4)=[2,1,3,4];

p_3(4)=[3,1,2,4];

p_4(4)=[4,1,2,3];

Bạn được cho một mảng x(1),x(2),…,x(m) (1<=x(i)<=n).

Gọi pos(p,val) là vị trí của phần tử val trong p. Vì vậy, pos(p_1(4),3)=3,pos(p_2(4),2)=1, pos(p_4(4),4)=1.

Chúng tôi định nghĩa :$f(p)=\sum_{i=1}^{m-1} |pos(p,x_i)-pos(p,x_{i+1})| $.

Nhiệm vụ của bạn là tính f(p_1(n)),f(p_2(n)),…,f(p_n(n)).

Đầu vào:

+ Dòng đầu tiên chứa hai số nguyên n và m(2<=n,m<=2.10^5) - số lượng phần tử trong mỗi hoán vị và số

+ Dòng thứ hai chứa m số nguyên x(1),x(2),…,x(m) (1<=x(i)<=n).

Ví dụ:

4 4

1 2 3 4

Đầu ra:

3 4 6 5

Screenshot from 2019-10-02 12-48-50.png


Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 02-10-2019 - 12:54

Yêu quê hương thương nhân loại núi sông cảm mến

Hiểu Thánh triết biết nghĩa nhân trời đất chở che


#3 tritanngo99

tritanngo99

    Đại úy

  • Điều hành viên THPT
  • 1743 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng

Đã gửi 15-10-2019 - 05:12

Bài 3 [590-Div.3-Bài D] Bạn được cho một xâu s chứa các kí tự Latin thường và q truy vấn cho xâu này.

Gọi xâu con s[l;r] của xâu s là xâu s(l)s(l+1)...s(r). Ví dụ, xâu con của “codeforces” là “code”, “force”,”f”,”for” nhưng “coder” và “top” thì không.

Có hai loại truy vấn:

+ 1 pos c (1<=p<=|s|), c là kí tự thường: Thay s(pos) với c (s(pos)=c).

+ 2 l r (1<=l<=r<=|s|): Tính số kí tự khác nhau trong xâu con s[l;r].

Đầu vào:

+ Dòng đầu tiên chứa xâu s chứa không quá 10^5 kí tự thường.

+ Dòng thứ hai chứa 1 số nguyên q(1<=q<=10^5) - số truy vấn.

+ q dòng tiếp theo . Mỗi dòng chứa câu lệnh của vấn đề. Nó đảm bảo rằng có ít nhất 1 truy vấn của loại 2.

Đầu ra:

+ Với mỗi truy vấn loại 2 in ra kết quả cho n - số kí tự khác nhau trong xâu con được yêu cầu ở mỗi truy vấn.

Ví dụ:

abacaba

5

2 1 4

1 4 b

1 5 b

2 4 6

2 1 7

Kết quả:

3

1

2


Yêu quê hương thương nhân loại núi sông cảm mến

Hiểu Thánh triết biết nghĩa nhân trời đất chở che





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh