CTT 2026 - Ngày 1

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 CTT 2026 - Shapez 100 (p) 3.0s 1G
2 CTT 2026 - String 100 (p) 5.0s 1G
3 CTT 2026 - Three 100 (p) 8.0s 1G

1. CTT 2026 - Shapez

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Trong một nhà máy dị hình có một công cụ gọi là bộ xoay. Mỗi lần sử dụng, bộ xoay có thể dịch vòng một xâu con nhị phân có độ dài đúng bằng \(3\): thay xyz bằng yzx hoặc zxy.

Cho hai xâu nhị phân \(s,t\) cùng độ dài \(n\). Có \(q\) truy vấn; mỗi truy vấn cho hai chỉ số \(l,r\). Hãy tìm số lần sử dụng bộ xoay ít nhất để biến \(s[l..r]\) thành \(t[l..r]\).

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên dương \(n,q\), lần lượt là độ dài của \(s,t\) và số truy vấn.
  • Dòng thứ hai chứa xâu nhị phân \(s\) có độ dài \(n\).
  • Dòng thứ ba chứa xâu nhị phân \(t\) có độ dài \(n\).
  • Mỗi dòng trong \(q\) dòng tiếp theo chứa hai số nguyên dương \(l,r\) mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in một số nguyên trên một dòng: số lần sử dụng bộ xoay ít nhất. Nếu không thể biến đổi được, in -1.

Ràng buộc

\[ 1\le n,q\le 5\cdot 10^5 \]
\[ s_i,t_i\in\{0,1\},\qquad 1\le l\le r\le n \]

Chấm điểm

Phần Điểm Giới hạn thêm
1 10 \(n,q\le 10\)
2 10 \(n,q\le 2\cdot 10^3\); tính chất A
3 25 \(n,q\le 2\cdot 10^3\)
4 20 \(n,q\le 2\cdot 10^5\)
5 10 \(n,q\le 5\cdot 10^5\); tính chất A
6 25 Không có giới hạn thêm

Tính chất A: với mọi \(1\le i\le \left\lfloor\frac{n+1}{2}\right\rfloor\), ta có \(s_{2i-1}=t_{2i-1}=0\).

Ví dụ

Ví dụ

Input 
10 5
1010111000
1111000001
1 6
3 5
4 5
1 10
8 9
Output 
3
1
-1
5
0

Đối với truy vấn đầu tiên, có thể thực hiện ba thao tác sau:

  1. Chọn đoạn \([4,6]\), thay 011 bằng 110, thu được 101110.
  2. Chọn đoạn \([2,4]\), thay 011 bằng 110, thu được 111010.
  3. Chọn đoạn \([4,6]\), thay 010 bằng 100, thu được 111100.

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.

2. CTT 2026 - String

Điểm: 100 (p) Thời gian: 5.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một xâu \(s\) có độ dài \(n\) và dãy hệ số \(f_1,f_2,\ldots,f_n\).

Một số nguyên dương \(d\) là chu kỳ của xâu con \(s[l..r]\) khi và chỉ khi \(d\le r-l+1\) và \(s_i=s_{i+d}\) với mọi \(l\le i\le r-d\).

Một số nguyên dương \(d\) là chu kỳ nguyên của \(s[l..r]\) khi và chỉ khi \(d\) là chu kỳ của xâu con này và \(d\) chia hết \(r-l+1\).

Với \(1\le l\le r\le n\), gọi giá trị của xâu con \(s[l..r]\) là

\[ w(l,r)=f_{(r-l+1)/d}, \]

trong đó \(d\) là chu kỳ nguyên nhỏ nhất của \(s[l..r]\).

Với mỗi \(1\le i\le n\), hãy tính tổng giá trị của tất cả xâu con có đầu mút phải là \(i\):

\[ \sum_{j=1}^{i} w(j,i). \]

Do kết quả có thể rất lớn, hãy in các kết quả theo modulo \(998\,244\,353\).

Dữ liệu vào

  • Dòng đầu chứa số nguyên dương \(n\).
  • Dòng thứ hai chứa xâu \(s\) gồm \(n\) chữ cái tiếng Anh viết thường.
  • Dòng thứ ba chứa \(n\) số nguyên không âm \(f_1,f_2,\ldots,f_n\).

Dữ liệu ra

In một dòng gồm \(n\) số nguyên không âm. Số thứ \(i\) là tổng giá trị của mọi xâu con có đầu mút phải là \(i\), lấy modulo \(998\,244\,353\).

Ràng buộc

\[ 1\le n\le 10^6,\qquad 0\le f_i\le 10^9 \]

Mỗi ký tự \(s_i\) là một chữ cái tiếng Anh viết thường.

Chấm điểm

Ký hiệu \([P]\) bằng \(1\) nếu mệnh đề \(P\) đúng và bằng \(0\) nếu \(P\) sai.

Phần Điểm Giới hạn thêm
1 10 \(n\le 100\)
2 15 \(n\le 5\cdot 10^3\)
3 25 \(n\le 2\cdot 10^5\); tính chất A
4 10 \(n\le 2\cdot 10^5\); tính chất B
5 20 \(n\le 2\cdot 10^5\)
6 20 \(n\le 10^6\)

Tính chất A: \(f_i=[2\mid i]\) với mọi \(1\le i\le n\).

Tính chất B: tồn tại số nguyên dương \(k\) sao cho \(f_i=[k\mid i]\) với mọi \(1\le i\le n\).

Ví dụ

Ví dụ

Input 
8
babaaabb
0 1 1 0 0 0 0 0
Output 
0 0 0 1 1 2 0 1

Các xâu con có giá trị khác \(0\) là:

  • \(s[1..4]=\) baba: chu kỳ nguyên nhỏ nhất là \(2\), giá trị bằng \(1\).
  • \(s[4..5]=\) aa: chu kỳ nguyên nhỏ nhất là \(1\), giá trị bằng \(1\).
  • \(s[4..6]=\) aaa: chu kỳ nguyên nhỏ nhất là \(1\), giá trị bằng \(1\).
  • \(s[5..6]=\) aa: chu kỳ nguyên nhỏ nhất là \(1\), giá trị bằng \(1\).
  • \(s[7..8]=\) bb: chu kỳ nguyên nhỏ nhất là \(1\), giá trị bằng \(1\).

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.

3. CTT 2026 - Three

Điểm: 100 (p) Thời gian: 8.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có \(n\) ô, được đánh số từ \(0\) đến \(n-1\). Ban đầu, mọi ô đều màu trắng.

Ta thực hiện ba lần tô màu. Lần thứ \(i\) (\(1\le i\le 3\)) cho hai số \(a_i,b_i\) thỏa mãn \(0\le b_i<a_i\), rồi tô đen mọi ô \(x\) thỏa mãn

\[ x\bmod a_i=b_i. \]

Sau ba lần tô, hãy đếm số đoạn khác nhau \([l,r]\) thỏa mãn \(0\le l\le r<n\) mà tất cả các ô từ \(l\) đến \(r\) vẫn màu trắng. Do kết quả có thể rất lớn, hãy in kết quả theo modulo \(998\,244\,353\).

Dữ liệu vào

  • Dòng đầu chứa số nguyên dương \(n\).
  • Dòng thứ \(i+1\) (\(1\le i\le 3\)) chứa hai số nguyên không âm \(a_i,b_i\).

Dữ liệu ra

In một số nguyên không âm: số đoạn thỏa mãn, lấy modulo \(998\,244\,353\).

Ràng buộc

\[ 1\le n\le 10^{13} \]
\[ 0\le b_i<a_i\le 2n\qquad (1\le i\le 3) \]

Chấm điểm

Phần Điểm Giới hạn thêm
1 5 \(n\le 10^6\)
2 25 \(n\le 10^{13}\); \(a_3>b_3\ge n\)
3 5 \(n\le 10^{13}\); \(\lfloor n/a_1\rfloor,\lfloor n/a_2\rfloor\le 10^5\)
4 5 \(n\le 10^{13}\); \(\lfloor n/a_1\rfloor\le 10^5\)
5 20 \(n\le 10^{13}\); \(a_1,a_2,a_3\le 10^3\)
6 40 Không có giới hạn thêm

Trong từng phần:

  • Giải đúng mọi dữ liệu mà \(a_1,a_2,a_3\) đôi một nguyên tố cùng nhau nhận được \(60\%\) số điểm của phần đó.
  • Giải đúng mọi dữ liệu nhận được \(100\%\) số điểm của phần đó.

Ví dụ

Ví dụ 1

Input 
10
5 3
7 0
7 1
Output 
8

Ví dụ 2

Input 
1000000
114514 114
114514 810
200000 5
Output 
136032633

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.