對於ACM或者OI的問題中，有哪些方法判斷一道題是使用了什麼演算法呢？

12-31

在寫ACM題/OI題的時候，我們往往最難的問題是如何確定一個題目是使用了什麼演算法，或者如何驗證這個演算法是適合這個問題的呢？

謝邀。

能判斷用什麼演算法的前提條件是，你熟悉了這些演算法。

一般90%區域賽金以下難度的題目，以及90%NOI難度以下的題目，數據範圍透露了相當多的信息，比如僅有一個N=1000的數據範圍，那麼題目很可能是N^2或者N^2logN的複雜度，順著複雜度去推哪些演算法能匹配到這些複雜度上去，然後再去設計演算法，基本上吧，一個題的題面給了你，使用演算法的範圍就被限制的比較小了，在這裡面在確定了大致的複雜度，演算法也就基本上出來了。

另外一個小經驗是，注意題目給了哪些本來可以不給的數據範圍，比如一般情況下給你的數字都是int範圍，結果有一個題專門強調每個數字不超過100，那麼很可能複雜度跟這個100有關。

這個思路是三年前開始帶OI/ACM時候開始總結的，到現在基本能說明這個方法適合於大部分難度不那麼高的題目，很多題目看完數據一眼就猜出來做法了

首先如果你會這道題那你就不會去猜演算法了……

那麼現在假定你沒有看出這道題需要什麼演算法。

我做這種題大概有兩種辦法，看數據範圍、想一些套路。

數據範圍方面。

如果n小於500，多半是個 $O(n^3)$ ，去往floyd或者高斯消元那方面去想；

如果n是幾萬，可以考慮一下 $O(nsqrt{n}log n)$ 。

如果n是10w……這種情況是最蛋疼的，基本沒法用複雜度來猜演算法了。一個log、兩個log、一個根號都有可能。

如果n是50w，一個log沒跑了。

如果n是100w，可能是 $O(n ln n)$ 的數學題；也可能是 $O(n)$ 。（我看到的大多數單調隊列的題都是100w的？）不排除數據結構 $O(n log n)$ ，但是常數會很小。

如果n在1000w，基本可以斷定是 $O(n)$ 。

如果n再大一些，可能是 $O(sqrt{n}),O(log n),O(1)$ 。

關於套路這方面有很多可以談的。

如果題目要你數顏色，你可以去想想分塊、主席樹或樹套樹。

如果要你在樹上對某條路徑染色，你可以想想LCT。

如果要你統計整棵樹上所有路徑中滿足某個要求的路徑條數，可以想想點分治。

如果是gcd/lcm相關的問題。n==m就想想歐拉函數，n!=m就想想莫比烏斯反演。

如果數論題模數是合數，就考慮拆掉這個模數，分別計算，CRT合併。

（題外話。出題人把這麼多套路引入OI，不知道是好事還是壞事。

再不濟就看題目描述吧。

題目英文名為yist、ernd、sanrd的題目，可能是智商題、打表題、亂搞題、猜結論題。

題目描述頻繁出現John、奶牛的題目，多半是水題。

題目裡面有B君的，多半不可做。

題目裡面有由乃的，多半不可做。

如果題目名是演算法或數據結構的名字，題目描述唆使你寫這個演算法或數據結構，那這題必定是水題。正解肯定不是題目名稱那個東西。例如：【HNSDFZ2016 #6】可持久化線段樹 - 題目 - PYOJ 【HNSDFZ2017 #7】樹上倍增 - 題目 - PYOJ

總之，猜出一道題正解是啥的辦法還是很多的。主要還是看平時的知識水平的積累了。

小強和阿米巴:全場都不會的演算法

Alice and Bob: 可能是博弈論

奶牛: 可能是水題

做題少想不出怎麼答....

蟹腰。。。

三個條件

1.演算法你會，或者至少知道幹什麼的。

2.對複雜度有詳細的了解，便於估計。

3.足夠的題量。

謝邀

我覺得主要有四個途徑

1. 看題意，看能不能找到做過的類似的題或者一些關鍵線索，看問題模型能否轉化至已知問題或者看已知模型進行組合變化後是否能解題

2. 看規模，熟悉複雜度理論的話，自然知道正解該往哪些演算法靠，當然不絕對，有出題人會故意縮小範圍混淆，也有數據出問題的情況，人過得多就趕緊交暴力

3. 做實驗，一些題目可能可以通過暴力打表找到規律進而找到演算法，有想法也可以先小規模驗證

4. 抱大腿，acm里很多題目可以通過把題目交給隊友進行解決，有想法和隊友討論也更容易走出題意和演算法的誤區。賽場上oi沒法交流，不過訓練時候acm/oi都可以通過討論交流解決問題並互相促進。

要真的施行以上幾條我認為關鍵還是一要掌握基礎的演算法，二要見過較多的模型，三要做難題。所以大佬具備的特質基本是:紮實的功底，豐富的經驗，思維境界高，周圍的人腿粗。

最好的方法當然是看到一道題就想到這道題出自哪個OJ，哪個Problem Set，哪道題，然後把自己以前的代碼默寫一下就好了。

如果在題面裡面看到了由乃

請選擇寫玄學分塊，或者bitset

當然也有可能是特技平衡樹