你作為 OIer 出的最好的題有哪些？

12-29

如題。

下面幾個是我自己比較喜歡的，應該都算是腦洞很大的題目。

小Z的襪子：WC2010集訓隊出題，idea是離線處理區間詢問

最大XOR和路徑： WC2011，idea是幾何與代數中學到的線性無關和電路原理中學到的獨立迴路

與非：HNOI2012，idea是數字邏輯電路里學到的組成CPU最基本的單元是與非門

還有幾個討論遊戲中的數學模型的題目，網上沒找著，有空傳上來。

不請自來。

出的題目不多，最滿意的，沒有之一：

WC2012 memory 記憶中的水杉樹

（link：http://www.lydsy.com/JudgeOnline/problem.php?id=2584）

幾個方面：

題目本身，一直都喜歡出演算法幾何題，這個題掛著幾何的外衣，但確是個非常巧妙的演算法題，有一個相對簡單粗暴但卻需要大量編碼的在線演算法，也有一個需要思考的精巧離線做法（@莫濤感謝莫隊想到了這個做法），可以考察選手的各個方面，可以不同的角度賞析。

其次，WC2012由於命題組的失誤，memory成了當場比賽唯一一道正常的演算法題，最終效果不辱使命（也是我唯一一次完全沒出bug的命題哈哈）

最後，常州中學歷史上第一次舉辦冬令營、能把最好的題目留給在自己的母校舉辦的大賽實在是不能更美好了（全國比賽人在國外沒能參與命題）。

自己也在題目描述里刻意留了伏筆。常州中學在百年校慶整體改造前，有一片鬱鬱蔥蔥的水杉林，改建後剷出了，那片記憶只留在了教學樓電梯的相片上。那時候小，忍受不了這樣迎接時代的變化（雖然現在也挺守舊），心中一直為之唏噓不已。現在回想都快6年過去了，那時的新校舍都成了老樓，那時候的小樹苗也成了一方林蔭，我也從那時候懵懵懂懂的少年，到了現在退役許久美國求學的成年人，過著完全不同的生活。因為生活總在往前走的。也許有一天，現在的香樟樹，也會成為另一個人題面上記憶中的樟樹林吧。很幸運能把一份小的心思埋在那麼多oier的記憶里，不過對絕大多數人這也就是一道題罷了，最後留下的不過是，自己心裡對歲月的懷戀。

以前時常會想，希望能出點有趣的題，至少能發出點微弱的光亮也好……

Problem - 5510

Problem - 5891 （2016 ICPC 青島網路賽題解）

Problem - 5960 （2016 瀋陽解題報告「施工中」）

Problem - 5986 （Qingdao 2016 E Fibonacci）

Shenyang 2017 B Bridges

最小方差生成樹 - $O(nlog n)$

還有某場爛尾了的毫無意義的比賽……

然而自己怠惰了幾年對演算法競賽的熱情也早就消退了現在看看自己出的題就幼稚的像笑話一樣從來也沒有出出來什麼真的有趣的題目真是令人失望啊……

四次魔獸世界模擬賽，外加「大災變」共計16道題。

誰說出的最好的題一定是難題？

題目本身不難，尤其是前三次（NOIP難度），但是故事背景可是處心積慮寫出來的。

原題、數據、題解鏈接：

BYVoid 魔獸世界模擬賽 Stage.1

BYVoid 魔獸世界模擬賽 Stage.2

BYVoid 魔獸世界模擬賽 Stage.3

BYVoid 魔獸世界模擬賽 Stage.4

大災變 - BYVoid

天天愛跑步，Universal Online Judge

一開始更有趣一些，但是演算法被張哥哥給hack了，後來不斷迭代就出來了這題。

把離線處理用的非常妙，想出來解法後我也是被自己驚到了。感覺不足的地方是細節稍微有點多容易寫掛。

瀉藥@Lyra Blodwen @Yang Jiaqi

祝大家noip玩得開心

最好的題永遠在未來

一棵n個點的樹，每個點有顏色，一種顏色在樹上的出現次數不超過t次，求有多少條路徑滿足這條路徑上的所有點顏色互不相同。

n&<=100,000

t&<=20

矩形覆蓋+掃描線

O(ntlogn)

清華集訓2013猴子挖礦。$100$ 個點的無權有向圖，求點 $1$ 到每個點的長度不超過 $10^{15}$ 的路線中，有多少種不同的**長度**。看起來就是一個矩陣乘法，但實際上沒那麼簡單。有好幾種非常不同的解法，用上了圖論、線代和數論的知識。

有一年NOI冬令營的非確定機。給一個黑箱程序和輸出，求輸入。後來我自己再也沒有出出過形式上這麼有腦洞的題了。

另一年NOI冬令營的小Q運動季，提答。通過測試點的設置，引導選手思考從特殊到一般的同餘方程組解法。

NOI2012的美食節。前半部分是個費用流拆點的經典問題。不知道當時自己怎麼想到還可以一邊算一邊建圖，之前遇到的網路流題都是不改圖結構的。

現在年齡大了感覺也少有這麼有趣的腦洞了。

Crash 的文明世界：一開始只是想弄一個樹分治的題目，過了很長時間後突然發現能夠用組合數與冪級數的關係得到時間複雜度更低並且更簡單的做法。

TrickyInequality ：融合多個 trick 的組合數學題。找不到官方的題解了，附上另外一個題解。

我出過兩道idea絕妙的題目，雖然都很簡單：

1.可持久化線段樹

鏈接：[HNSDFZ #6] 可持久化線段樹

語文課上腦補出來的玩意。雖然這個思路早就家喻戶曉了。

100w，直接寫主席樹會被卡空間。

由於每一個版本是從之前的版本「衍生」出來的。所以我們只需要維護一個版本——「當前」的版本。

對於修改操作，我們在處理完這個版本之後將它還原；

對於查詢操作，直接在當前的線段樹裡面查詢；

對於衍生操作，我們遞歸下去。

正確性是顯然的，這樣我們就卡過了空間。

把上文的線段樹改成樹狀數組，就可以卡過時間。

2.樹上倍增

鏈接：樹上倍增（也許是HNSDFZ#7）

這個思路相當漂亮，在廁所裡面腦補出來的。

題意是：給定一棵樹，求多個節點的lca。

題解：阮行止：如何在 DAG 中找多個點的 LCA ?

Universal Online Judge

再也沒有過這樣有趣的想法了啊。。。

謝邀。

「LibreOJ β Round」ZQC 的樹列，順便宣傳一波 loj。

這是我們 loj 第一次 Beta Round 比賽的題，idea 是我去年 noip 前想出來的。

下方劇透預警！

這道題的要點在於 —— 不要被「特徵值最大的子序列」迷惑了，因為「特徵值最大的子序列」就是它本身！

出這個題的時候還有個小插曲，我的 std 一開始寫的是枚舉 2 ^ k 的貪心分解，然後被 lca 給 hack 了，然後我換成了反方向（k 從大到小、從小到大）枚舉，不到一個小時後又被 lca hack 了 …… 最後結論是分解的那一步只能搜索。多謝 lca 的驗題要不然 loj 第一次比賽就出大鍋（

謝邀@JCSB

祝大家UR玩的開心！

目前出的題的巔峰貌似還是前年的 Pony Round 的。。Little Pony and Lord Tirek

Problem - E - Codeforces

無論解法還是題目背景都非常滿意。。。

參考資料：

某島 - 我出過的題目

【島娘】我出過的一些題目_演講?公開課_科技_bilibili_嗶哩嗶哩

占坑，明年答(放個煙霧彈)

1、n個結點的完全圖，給定每個點v的權為w[v]，令邊(u,v)的權為|w[u]-w[v]|2，求圖的最小權哈密頓迴路。n&<=100000。

2、有n+1個點，編號0,1,...,n，從0出發，每次可以選一個整數d，然後移到和當前點編號差的絕對值等於d的點，要求在不經過重複點、不使用重複d值的情況下到達點n。給定n，求一種移動次數最多的方案。

解法留給大家思考。

雖然它看起來只是A+B problem，但它卻可以鍛煉你來寫高精度，壓位高精度，線段樹，zkw線段樹，lct，主席樹，splay，spfa，dijkstra，floyd，樹狀數組，樹剖，prim，kruskal等各種演算法的模板啊！（滑稽

1.區間所有x變成y

2.查詢區間k小值

n，m 1e5

1.區間大於x的數減x

2.區間x出現次數

n，m，值域 1e5

1.區間加

2.區間kth

n，m 1e5

1.合併兩個集合

2.回到第i個歷史狀態

3.查詢一個集合的kth

n，m 1e5

序列，每次查詢三個區間裡面，所有數（值域範圍內）出現的次數的最小值的和

n，m 1e5

其他的等掛出來再寫吧

update：話說怎麼回答的人都在說數據結構啊

我倒是要看看我至今沒A的野題究竟是哪些dalao出的。