# 電資圈接力Challange 總之是被tag了吧 雖然我只是個上不去橘的小廢物 但還是來寫一下8 原本是想用DP寫學資的排組題 但我找不到我高一的學資，所以就算ㄌ 就寫一下最近戳到的題目好惹 然後只寫一題感覺好爛，畢竟我的程度能介紹的題目都不是那種太難的題目 所以多寫個幾題好惹 //結果我寫完第一題就開始做其他事忘ㄌ寫其他題了，我就拖 ## [TIOJ 1927 同步sync](https://tioj.ck.tp.edu.tw/problems/1927) 這題我覺得滿有趣的，然後裡面的數學我真的不會，是查了才知道，也就是說我賽中肯定做不出來 但很酷，所以我還是寫寫看好了 ### 題敘 有一個長度為 $n$ 的一維棋盤，每格上均寫了一個正整數 $a_i < 10^9 + 7$ 而若 $(a_i\times a_j)^\frac{p-1}2 \equiv 1 \mod p (p = 10^9 + 7)$ 則稱點 $i,j$ 是同步的 若兩個人站在的點是同步的，則他們會一起前進一格，直到他們所在的點不再同步或是一個人走到了棋盤終點為止 接下來有 $q$ 筆詢問 每筆詢問問你兩個人分別從點 $a,b$ 開始，他們一共可以同步幾次 ### Solution :::spoiler 數學的部分 首先根據費馬小定理我們知道 $\forall n \in N, n ^ {p-1} \equiv 1 \mod p$ 然後我們可以把同步的條件改寫成 ${a_i}^\frac{p-1}2 \times {a_j}^\frac{p-1}2 \equiv 1 \mod p$ 這時候就是酷酷的事情了，我們可以證明$\forall n \in N, n^\frac{p-1}2 \equiv \pm 1 \mod p$ 我覺得可以理解成在模p下開根號，但我不會數學，所以我還是不知道他為什麼是對的 但有了這件性質之後，我們就可以好好的對他做事了 阿這個部分因為我數學太爛，所以我是去看題解，看到第一行這樣講之後才會ㄉ 但因為真的很酷，所以我想寫他w ::: ::: spoiler 後面的部分 接著可以直接對每個點求他的 $\frac{p-1}2$ 次方，由於這個值一定是 $\pm1$ 因此我們可以知道兩點同步的條件其實是兩點是否相等 所以對於每筆詢問，我們求的其實是以 $a,b$ 為起點的最大相同子字串為多少 這件事的作法應該很多（？ 總之我的作法是rolling hash之後去二分搜最大的共同子字串 這部分就很容易ㄌ，總之我笨我不會數學，但我喜歡這題 ::: [AC code](https://pastebin.com/4D7tw0i8) ## [CF 1468 pD Firecrackers](https://codeforces.com/contest/1468/problem/D) 這題其實應該滿簡單的 但大概半年多前我第一次看到這題的時候我寫不出來，然後8e7覺得我怎麼會寫不出來 但我那時候就真的很笨咩噗（現在還是很笨咩噗 總之最近在USACO Guide Silver看到這題，所以就回去把這題寫掉了 順便譴責一下為什麼自己以前寫不出這題== ### 題敘 有一個長度為 $n$ 的一維走廊，有一個歹徒在第 $a$ 格，一個警衛在第 $b$ 格 歹徒手上有 $m$ 個鞭炮 其中第 $i$ 個鞭炮會在被引燃後 $s_i$ 秒爆炸 每秒鐘會依序發生三件事 1. 歹徒可以選擇動或不動，動的話可以往左或右移動一格，但不能離開邊界。如果不動，則可以引燃一個鞭炮 2. 若鞭炮 $i$ 在$T$ 秒時被引燃，則在 $T + s_i$ 秒的這個階段鞭炮會爆炸 3. 警衛會朝歹徒前進一格，如果警衛跟歹徒在同一格，則歹徒被抓到了 而題目求歹徒在被抓到前，最多可以看到幾個鞭炮爆炸 $n,a,b,s_i \leq 10^9, m \leq 2 \times 10^5$ ### Solution :::spoiler solution 首先，可以先假設 $a < b$，如果不是的話轉一下就好 接著可以知道，能放的鞭炮量是固定的 $b - a + 1$，而歹徒一定會在第 $b - 1$ 秒被抓到 因此只要考慮一個簡單的greedy，也就是將煙火由大到小排序 並且只要這個煙火爆炸看的到就放它並進到下一秒 看不到的話就換時間更快的煙火，直到煙火沒了或一定得跑了為止 [AC Submission](https://codeforces.com/contest/1468/submission/121396606) 喔然後附上我幹過最[愚蠢的WA法](https://codeforces.com/contest/1468/submission/121396504)ㄌ 我把`a = n - a + 1; b = n - b + 1;`寫成`a = n - a + a; b = n - b + a;` 重點是還過了7組測資，他甚至是多筆測資的題目欸？？？ 害我以為我寫爛ㄌ 然後我半年前真的好笨，看來進不去選訓是活該（雖然現在再考一次大概還是進不去 ::: ## [NHDK Ten Point Round 11 pC Gunjyo與骰子](https://codeforces.com/group/H0qY3QmnOW/contest/333897/problem/C) 滿有趣ㄉ題目，總之希望NHDK可以多出一點div. 1場，有固定的中文比賽可以打還不錯XD ### 題敘 總之有三個100面骰，然後把骰出來的結果排成一列之後 可以在兩個空隙分別塞一個 + 或 * 然後問你有幾種組合方式會使最後的結果是 $n$ （不同的運算子塞法算不同的組合方式etc. 1 * 1 + 1, 1 * 1 + 1 算兩種） ### Solution :::spoiler solution 個人覺得直接看code就可以理解了 :::spoiler code :::spoiler 你確定要看嗎 :::spoiler 你要確定欸 [好啦給你看](https://drive.google.com/file/d/11KRJRWVv_a0bQON4nd3Pq3h0Msuw-BGm/view?usp=sharing)，強烈建議使用電腦打開這份檔案 想必大家都會寫這題了吧，是不是很有趣呢 只要50000多行就能AC了ㄛ 喔然後附上我[本機打表的扣的](https://www.theraleighregister.com/nhdk11benjidabiao1.html) ::: :::spoiler 欸不是 ~~這哽484其實已經不好笑了咩噗~~ 喔還有cf有檔案大小限制，所以其實根本傳不上去www 而且不止cf傳不上去，hackmd傳不上去、pastebin也傳不上去，我只好用drive XDD :::