停課第四天，我忘了我那時在想什么了。

A.

題意簡述：給兩個字符串s,t，求s重復n次和t重復m次后有多少位匹配。保證n|s|=m|t|

我感覺可以根據一些性質亂搞啊……但是我WA了一些。

性質1：顯然n，m與復雜度無關，我們要關心的是lcm(|s|,|t|)。

性質2：當lcm(|s|,|t|)很大時，由于gcd(|s|,|t|)=|s|*|t| / lcm(|s|,|t|)，那么gcd(|s|,|t|)，必定不大。

那么對于任意一個si，它在ti可能的匹配位置中間間隔必然是gcd(|s|,|t|)，那么只有t/gcd(|s|,|t|)( 或是lcm(|s|,|t|)/s )個(可用裴蜀定理證明)。

好的，那么現在，我們只要枚舉0到gcd(|s|,|t|)，將它們的所有對應位置逐個裝到桶里即可，但WA了QAQ。

B.

不會。

C.

題意簡述：

　　略。

二分答案的做法是顯然的，然而我只會70分 wuwu~

D.

題意簡述：

　　求一個點，使樹上所有點到它的距離總和最小。

感覺是求重心，但是不敢寫，練習了一下換根DP。 //事實上我從來沒有寫過

E.

原題，甚至我博客里都有，不表。

F.

FJOI2018 D1T1 本來是dfs裸題，后來覺得練習差分約束也不錯，就寫了一下。

轉載于:https://www.cnblogs.com/JiuPleber/p/9910100.html

總結

以上是生活随笔為你收集整理的AHS of FCGRC 停课 Day 4的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。