or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
\(\Huge \text{🌱 Free Contest 131 - APPEAR}\)
🔗 Link: https://oj.vnoi.info/problem/fc131_appear
📌 Tags:
String Matching
,Precalculation
,Math
👤 Writer: @SPyofgame
👥 Contributor: @Melonade
📋 Content:
Hướng dẫn
Nhận thấy rằng việc tính toán hàm \(F(T, S_i + S_j)\) có thể được chia làm \(2\) phần:
Ta định nghĩa:
Lúc này ta có: \(\overset{n}{\underset{i = 1}{\Large \Sigma}} \overset{n}{\underset{j = 1}{\Large \Sigma}} F(T, S_i + S_j) \\= \overset{n}{\underset{i = 1}{\Large \Sigma}} \overset{n}{\underset{j = 1}{\Large \Sigma}} F(T, S_i) + \overset{n}{\underset{i = 1}{\Large \Sigma}} \overset{n}{\underset{j = 1}{\Large \Sigma}} \overset{|t|}{\underset{x = 1}{\Large \Sigma}} \left ( suff(i, x) \times pref(i, |t| - x) \right ) \\= 2n \times \overset{n}{\underset{i = 1}{\Large \Sigma}} F(T, S_i) + \overset{|t|}{\underset{x = 1}{\Large \Sigma}} \left ( \overset{n}{\underset{i = 1}{\Large \Sigma}} pref(i, x) \times \overset{n}{\underset{i = 1}{\Large \Sigma}} suff(i, |t| - x) \right ) \\= 2n \times \overset{n}{\underset{i = 1}{\Large \Sigma}} F(T, S_i) + \overset{|t|}{\underset{x = 1}{\Large \Sigma}} \LARGE \left ( \normalsize cntsuff(x) \times cntpref(|t| - x) \LARGE \right )\)
Vậy bằng việc tiền xử lí và toán, ta có thể tính kết quả đủ nhanh.
Tiếp cận
Tại Code[1]:
Đầu tiên mình sẽ viết một thuật toán trâu đơn giản: Cứ mỗi một cặp xâu \((s_i, s_j)\) thì mình nối xâu và đếm số xâu con \(t\) có trong đó.
Tại Code[2]:
Mình cần tính toán từng thàn phần một cách riêng biệt nhằm bỏ vòng for \(O(n^2)\) kia đi. Do đó mình không dùng phép nối xâu, mà tính cho từng cái một, mỗi cái ở một nửa kia.
Tại Code[3]:
Mình nhận thấy là cứ mỗi vòng for mình lại tính một phần có kết quả giống nhau, cho nên mình sẽ tiền xử lí và lưu trữ các giá trị này trước.
Tại Code[4]:
Vì vòng for trên rất phức tạp, nên mình sẽ chia làm 2 phần vòng for đơn giản. Điều này tạo điều kiện cho việc tính toán kết quả một cách đơn giản hơn.
Tại Code[5]:
Mình nhận thấy là ta lại tính đi tính lại các phần có kết quả giống nhau. Vì vậy mình lại tiền xử lí tiếp đoạn này và sử dụng toán để tính trong \(O(1)\).
Tại Code[6]:
Giờ mình chỉ cần đơn giản hóa vấn đề và rút gọn công thức .
Bài toán này cũng chỉ có thế thôi, chúc bạn một ngày vui vẻ
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →Code
SPyofgame Code [1] - Make a simple Brute-force
SPyofgame Code [2] - Calculate independently without concatenating string
SPyofgame Code [3] - Optimize Brute-forces with Precalculation
SPyofgame Code [4] - Split into two simple loops
SPyofgame Code [5] - Optimize Brute-forces with Math
SPyofgame Code [6] - Simplify The Formula
Bonus
Với \(p = |t|\) và \(q = max(|S_i|)\)
\(1.\) Giả sử \(|s_i|\) và \(|t|\) có thể rất lớn:
\(2.\) Giả sử có \(q\) truy vấn \(t_q\):