written by pooh at 2024/09/27, 2024/10/02, 2024/10/03

這啥

パ研合宿

看起來是日本的電研合宿，看起來是巨砲日本高中生出給日本高中生的，Day 1 很像 3 天的 IOIC 會有人做出來的題目的合輯， Day 2 體感難度比 IOIC 難，Day 3 感覺比較像一半的 Day 1 一半的 Day 2，要練手速或想很快 Day 1 很好玩，Day 2 就是太神了點，Day 3 就比較有成就感，Atcoder 上有題目但沒有翻譯，所以下面我也會翻一下。

第1日「SpeedRun」

Judge : Atcoder

兩個半小時

題目

記憶體限制都是 1024 MB, 除了 pP 12s 以外都是 2s。

A - Kazuate Game (100 分)

給定一個長度為 的正整數序列 ，請判斷 中是否存在其出現次數不超過 10 的元素。


輸入都是整數

B - Cutting Circle (100 分)

在園 的圓周上，有點 按照這個順序等間隔排列。
當用通過點 的直線和通過點 的直線同時切割圓 時，圓 被分割成多少個部分？




,
輸入都是整數

C - Infinity (200 分)

給定一個長度為 的整數序列 ，你可以執行以下操作任意次(包含 0 次):
選擇相異的整數 ，並將 置換為 。
請判斷是否有可能使 的值變為 。


輸入都是整數

D - Bishop (200 分)

給定平面上兩個點 ，你可以執行下面這個操作:
選一個實數 滿足 ，將 變成 或
問你將 變 最少要花幾次操作。


輸入都是正整數

E - Thin Ice (300 分)

給一張 個點 條邊的無向連通圖，第 條邊 () 是雙向連接點 和 的，問你存不存在一個 walk 剛好經過每條邊 次。





沒有自環或重邊

F - Mean Median Construction (300 分)

給定一個 ，要求你構出一個非負整數 set 滿足

  2. 任一個子集的平均比中位數大，定義一個 個數的 set 的中位數為 (編號是 1 base，且遞增的排法)
    如果構造不出請輸出 No，不然輸出 Yes 並構解。

G - MST (Easy) (400 分)

給一個長度是 的整數陣列 ，並有一張無向圖，邊 的邊權是 ，求這張圖的最小生成樹的邊權和。


H - Winter Road (400 分)

有 個村莊和 條道路。第 條道路 () 是雙向連接村莊 和 的，無論何種情況下，通過每條道路都需要 1 分鐘。 一開始，所有的道路都覆蓋著噗機趴磚。若 ，表示噗機趴磚不會乾掉；若 ，表示噗機趴磚會在 分鐘後乾掉。 國王裝置君最初在村莊 1，並想要通過幾條道路移動到村莊 。裝置君可以在任意村莊等待，他非常謹慎，不想通過有濕的噗機趴磚的道路。請求出當裝置君在移動到村莊 時，最小化通過濕的噗機趴磚道路的時間時，所需的最小時間。 保證可以從村莊 1 經由若干條道路到達村莊 。



沒有重邊或自環
or

I - Swap and Sort (400 分)

笨 pooh 有一個長度為 的正整數序列 ，他現在要跟你玩一個遊戲，每次你都可以選一個數字 ()，然後交換 ，接著再把 ，請你給出一種選 的順序，讓你在 次操作後讓 變非嚴格遞增的。

J - Wrapping (400 分)

對於一個長度為 的正整數序列 ，定義 是一個以下操作後得到的序列:
對於 ，如果 不在 裡，將 放到 的後面。
現在問你對於給定 ，有幾個長度為 的正整數序列 滿足:

())
將答案模 998244353 輸出

K - Or Set (500 分)

給定一個正整數 與一個長度為 的非負整數序列 ，保證 ，並設定一個變數 ，初始值 ，接著我們做以下操作 ( 表示 bitwise or)，對於 ，如果 ，。

問你對於所有 種 的 permutation，有幾種最終的 的值?


L - Range Mex Sum Min (500 分)

給定一個 個數的整數序列 ，問你對於滿足以下條件的 的 permutation :
的話
最小的可能是?

其中 代表 minimum exclusive

至少存在一個滿足條件的

M - + and Xor (500 分)

給一個 ，要求你給出一個 的 permutation ，使得 最大，其中 但表 bitwise xor。

N - Chocolate Game (600 分)

Alice 跟 Bob 要玩一個吃巧克力的遊戲，給一個 的巧克力，每次可以選一刀平行或垂直地切下去，然後把切下來那一快吃掉(也就是說，如果我們把原本最左上角那一塊塗成紅色的，要把沒有那一塊的丟掉)，然後一定要留下面積大於 的巧克力，先不能做操作的就輸了。
Alice 先手。

現在有 比詢問，每筆會告訴你 ，請你回答 Alice 贏還 Bob 贏。


O - Longest Bracket Subsequence (600 分)

給一顆 個點的有根樹 (根是 1)， 代表這兩點之間有邊，然後第 個點上都有 (左括號或右括號)，然後有 筆操作詢問，第 筆，有 :
將點 的 改成
將點 的子樹內個括號全部反轉
問你 到 的路徑上的最常合法括號子字串長度

P - MST (Hard) (600 分)

給你兩個長度為 的序列 ，表示有一張 個點的完全圖，邊 的邊權是 ，問你這張圖的最小生成樹的的邊權和。



輸入都是整數

第2日「パ研杯」

Judge : Atcoder

三小時

題目

記憶體限制都是 1024 MB, 除了 pD 1s, pE 8s 以外都是 2s。

A - SpeedRun (100 分)

給一個正整數 ，問你 2023 年パ研合宿 SpeedRun 的第 名的 handle。

可以輸出個人記分板或團隊記分板的。

B - Salesman X (500 分)

給三個正整數 ，跟一顆 個點的樹， 代表上面的一條邊，規定兩組 個點的目的地 ,，Salesman Twitter 想要從點 1 出發，先走完 的每一個點(順序不定)，然後選擇一個點停留，接著從他出發走完 的所有點(順序不定)，最後走到 ，請問他走的總距離最小為多少?

Subtask :
(200 分)
(300 分) 無額外限制

C - Arithmetic Progression and … (500 分)

Bao 跟 Arual 在玩遊戲，可是他很怪，所以他把一部份拿給你玩，遊戲是這樣的，Bao 會選三個正整數會選三個非負整數 然後構造出一個等差數列 ，把他丟給 Arual， Arual 會選 個元素換掉，再把他跟泰勒斯隨機歌單一樣 shuffle，接著把結果丟給你，請你還原出一組可能的 。


輸入都是正整數

Subtask :
(200 分)
(300 分) 無額外限制

D - Many Dungeons (700 分)

巨砲施竣耀有 場 APIO 要打，每一場有 題，第 場的第 題難度是 ，因為施竣耀是策略神，所以他已經擬定好策略了。對於第 場 APIO，他會做以下的事 :

  1. 他先決定一個體力值 ，要滿足
  2. 從第一題開始做
  3. 按照 的順序，他會去做第 題，假設他現在的體力為 ，如果:
    1. ，他就會去刷牙恢復體力，把
    2. 把 變成 ，然後去做下一題
      然後因為施竣耀還有微積分作業要寫，所以他不想要花太多體力在破台上，因此他會給你一個，要求 ，然後因為一場比賽刷太多次牙有點浪費時間，所以他希望能最小化他一場比賽需要刷牙的最大次數，當然施竣耀絕頂聰明，所以他已經知道答案了，但他還是想問你，他最小的需要刷牙的最大次數是?




      輸入都是正整數

Subtask :
(200 分)
(500 分) 無額外限制

E - Is Either 1? (700 分)

桌上有 個硬幣，其中我們用 代表正面， 代表反面，因為我們很閒，所以我們想要給他下 條限制，每條限制都是 ，代表第 個硬幣是 面朝上或第 個硬幣是 面朝上，保證這些限制給妳以後一定還有一個合法的硬幣的朝上的方法。問你還有幾個限制 (意義與上面一樣) 加上後，這 個不一定相異的限制是有解的?



輸入都是正整數

F - Make it incomplete (800 分)

你有一張 個點的完全 DAG (對於任意兩點 有一條邊從 連到 ), 接著我們要做 次操作與詢問，每次的格式是 ，代表先將圖上 到 的邊刪掉，接著問妳 到 的最短距離是多少，如果不連通請輸出 -1 。




且對於所有相異
輸入都是整數。

Subtask :
(200 分)
(600 分) 無額外限制

G - Reducing x K (800 分)

給一個長度為 的非負整數序列 ，進行以下操作 次:
挑一個還是正的元素 ，把他換成一個滿足 的
問你 次操作後的 有幾種可能性? 將答案對 998244353 取模。

Subtask :
(200 分)
(400 分)
(200 分) 無額外限制

H - Two PCities (800 分)

每個人都想要有兩個 PCC，所以我們有一棵 個點的樹， 代表樹上有一條邊連接這兩個點 ，以及一張很酷的圖，圖上 有邊若且為若在樹上 的距離大於等於 ，接著有 比詢問，問你 在圖上的距離是多少，如果不連通輸出 -1




輸入都是正整數

Subtask :
(300 分)
(500 分) 無額外限制

第3日「Teamwork」

Judge : Atcoder

三小時

題目

記憶體限制都是 1024 MB, 時限都是 2s。

都是 100 分。

A - ABC

給你一個長度為 的字串 ，其中每個字元都是 A, B, C 其中一個。問你在做以下操作 次後，有幾種最終的字串，將答案模 998244353 輸出。
選一個滿足 的
如果 ，在中間插入一個一樣的字元。
如果 ，在中間插入一個跟 相異且是 A, B, C 其中一個的字元。


B - AND

給你一個長度為 () 的非負整數序列 ，定義 為經過以下操作讓整個序列都變 所需要的最小操作次數，如果做不到的話是 :
每次選一個元素 ，並挑一個他相鄰的元素 ( = 1)，讓 ( 表示 bitwise and)。

現在給一個長度為 的正整數序列 ，與 比詢問 ，請你輸出 。




C - DEC

Alice 跟 Bob 找 Arual, Bao, Chris 當莊家要玩一個遊戲，一開始 Arual 有 元、Bao 有 元、Chris 有 元，Alice 跟 Bob 會輪流做下面兩個操作其中一個 (Alice 先):
從 Arual 跟 Bao 手上各搶 元送給被暈的人
從 Bao 跟 Chris 手上各搶 元送給被暈的人
( 要是一個正整數)
先不能操作的就輸了。
現在你知道 Alice 跟 Bob 都絕頂聰明，所以有 比詢問，給你 ，請你回答誰會贏。


D - GCD

請構造出一個長度為 30，每個數小於 的正整數陣列，使每個區間的 gcd 相異。

E - MEX

給你 ，問你有幾個長度為 ，每個值都在 到 的非負整數數列，滿足:
定義 的一個長度為 的數列是嚴格遞增的，其中 表示 minimum excluded


F - MEX2

給一個長度為 的非負整數數列 與一個目標 ，問你有幾個 的區間的 是 K，其中 表示 minimum excluded。


G - MOD

本題包含 筆測試，每筆要回答下列問題:
有一個長度為 的非負整數序列 ，初始值都是 ，接著給兩個長度為 的正整數序列 ，問你每次執行下列操作 :
選一個 ，將 , 。
問你在執行若干次操作後，能不能讓 的每項元素都滿足 。






H - ROT

給一個非空字串 ，與一個非負整數 ，定義 是將 向右旋轉 步後的字串 (也就是說，將 最尾端的字元移到前面這個動作執行 次)，定義對於兩個字串 , 是有幾個 滿足 且 的字典序比 小。

現在給你兩個長度皆為 的字串 ，叫你處理 個詢問。
Query 1 : 給 ，問 ( 表示這兩者間的子字串)
Query 2 : 給 ，如果 ，將 ，若 ，將




是個小寫英文字母

I - TREE

給一個 個點的定根樹， 是跟，對於 ， 的父節點是 ，保證 。

對於一個 的 permutation ，我們說他的 cost 是以下流程的最後的 ，定義 一開始是 0 ，接著對於 如果點 在 的子樹內， 就將 。

請輸出對於所有可能的 最小的 cost。



J - XOR

給 比詢問，每筆給你 ，問你對於 set 的所有 subset 的 xor 有幾種可能的結果。


心得

總結就是有趣的題目真的很多，然後三天的性質也不太一樣， Day 1 就是手速賽，Day 2 是給思考破台的人的地方，Day 3 基本上就是 ICPC，寫的蠻爽的。

之後如果補完題了再寫題解。