Coding Beans: 2016

link
You can view official tutorial here.
Here I will explain some points I consider important when trying to solve the problem.
There may be some mistakes in grammar due to my poor English QAQ.
Any correction of algorithm or grammar is welcomed.

It's not hard to find that x>y and x<y are two different problem: One is to use more tree edges as possible while the other is to use less tree edges.

2016年3月10日星期四

[TIOJ 1725][Z algorithm] Massacre at Camp Happy

原題連結
先了解一個問題：給定字串A,B，長度皆為n，要如何線性判定A和B是否只差1個字元呢？

[HDU 4605][Segment Tree] Magic Ball Game

原題連結
嗚姆....這題讓我頗開心的獲得了1A XD

[POI 21st Stage 1][Persistent Segment Tree] Couriers

原題連結
有做過第k小的同學大概對於持久化權值線段樹稍微有點感受

[TIOJ 1735] k-口吃子字串

原題連結
嗚姆....這題還算基本的趣題，我想到兩個作法。

[POI XIII Stage 1][KMP] Periods of Words

原題連結
字串的一題基礎題

2016年3月9日星期三

[POI 21st Stage 1] Couriers

原題連結

2016年3月8日星期二

[SPOJ DQUERY][BIT][Persistent Segment Tree] D-query

原題連結
這題如果沒有想到一個關鍵點的話就會很難做

[HDU 5412][ZOJ 2112][整體二分] CRB and Queries

原題連結
yee~想看對於區間第k小問題討論的同學可以戳這邊。

[TIOJ 1840][樹套樹] Coding Days

原題連結
動態區間第k小的作法基本上是這幾種：

2016年3月7日星期一

[HackerRank Weekly Challenges -- Week11][Treap] Two Array Problem

原題連結

[HDU 3007][最小覆蓋圓] Buried Memory

原題連結
嗚姆
今天來學最小覆蓋圓的隨機增量法，題目本身就是一個模板題QAQ。

2016年3月6日星期日

[III (XIV) Volga Region Open Team Student Programming Contest pB][Treap][sqrt method] Time to read

原題連結
個人很喜歡這一題
大致上，這道題的難點在於如何「快速得知某頁的顏色」還有維護「塗色」操作。

[ONTAK 2010 Day1][Treap][Disjoint Set][Heuristic Merge] Peaks

原題連結
這道題的思路其實不難，只是同時考驗對於資料結構的信心和穩定度，寫起來code量略大，還是比較麻煩的。

[Coder-Strike 2014 - Finals (online edition, Div. 1) pD][Treap] Cup Trick

原題連結
可以想像一下，要能夠快速維護他給出的所有操作我們應該要能實做哪些事情呢？

[POJ 2104][Persistent Segment Tree] K-th Number

原題連結
本題作為經典的資料結構題，解法有非常多種。
就我能力上可作的就有持久化線段樹，線段樹套平衡樹。
這些解法各自的優點和缺點都不同。

2016年3月5日星期六

[Codeforces Round #337 (Div. 2) pD][Segment Tree] Vika and Segments

原題連結
這題我寫的過程還是有點坎坷的

2016年3月4日星期五

[Educational Codeforces Round 3 pF][Segment Tree]Frogs and mosquitoes

原題連結
不知道為什麼一道很單純的題目不但被我弄得很複雜，而且搞了很久(?

[Codeforces Round #286 (Div. 1) pD][Disjoint Set][sqrt method] Mr. Kitayuta's Colorful Graph

原題連結
這題我提供兩個解法和兩份code，都具有相當的啟發性。

[COCI Contest #7 pE][Disjoint Set] KUGLICE

可以在這邊的Contest 7中找到題目說明和測資

2016年3月3日星期四

[Codeforces Good Bye 2014 pB][Disjoint Set] New Year Permutation

原題連結
呼呼，這是並查集專題中的一題，題目本身並不難。
先對題目和並查集的聯繫做一點說明。

[POJ 1456][Max heap or Disjoint Set] Supermarket

原題連結
唉....最近bug實在是越來越蠢了

[Codeforces Round #218 (Div. 2) pD][Disjoint Set] Vessels

原題連結
一道並查集的頗直覺的題目
難點大概就只有在有沒有想到要用Disjoint Set去做吧......
對於已經滿的vessel i ，執行 fa[i] <- findset(i+1) ，直觀上就是將每個相鄰的滿vessel連接起來，已達到快速查詢可用vessel的效果。

細節上要注意水流到地上的case要做好，不然很容易WA或是TLE。

#include<cstdio>
#define LL long long
using namespace std;
const int maxn=200000+5;
int fa[maxn],cap[maxn],cur[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {fa[i]=i;scanf("%d",cap+i);}
    fa[n]=n;
    scanf("%d",&m);
    for(int i=0,type,a,b;i<m;i++)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%d%d",&a,&b);a--;
            a=findset(a);
            for(;b && a!=n;)
            {
                if(cap[a]-cur[a]>b) cur[a]+=b,b=0;
                else // cap[a]-cur[a]<=b
                {
                    b-=cap[a]-cur[a];
                    cur[a]=cap[a];
                    fa[a]=findset(a+1);
                    a=findset(a);
                }
            }
        }
        else
        {
            scanf("%d",&a);a--;
            printf("%d\n",cur[a]);
        }
    }
}

[POJ 1182][Disjoint Set] 食物鏈

原題連結
yee~~~這是並查集非常非常經典的一道題。
顯然我1年多前看過，當時自然是沒想出來的XD，現在看就比較清晰了。

[POJ 3017][DP] Cut The Sequence

原題連結
嗚姆
個人頗喜歡這道題，大概是因為我做了蠻久的(?

[POJ 3709][DP] K-Anonymous Sequence

原題連結
關於斜率優化想了解的可以看這篇。

2016年3月2日星期三

[Codeforces Round #153 (Div. 1) pA][deque] Points on Line

原題連結
既然是pA當然要水水的XD

[POJ 3320][雙指針] Jessica's Reading Problem

原題連結

對於單調隊列、序列單調性不再多做討論，可以先做這題。

[POJ 3061][雙指針] Subsequence

原題連結
這題也是相當經典的單調性的題目

[POJ 2823][deque] Sliding Window

原題連結

這道題的時間非常......奇妙。

原本我穩穩的寫完deque想說可以一次水過。

結果竟然T了！？

[Ural 1671][Disjoint Set][Offline] Anansi's Cobweb

原題連結
在線作法的話......不知道XD，LCT大概能做(?

離線作法的話非常經典，把所有操作讀入後反過來做，這樣刪除操作就變成了加邊操作，使用并查集就能輕鬆過~~

[HDU 1512][Heap][Heuristic Merge] Monkey Kings

原題連結
懂啟發式合併之後這題就很單純了。

2016年3月1日星期二

[POJ 2431][Heap] Expedition

原題連結
出乎意料單純的一道題......

[ZJ d110][NOIP 2008 提高組][Bipartite Graph] 雙棧排序

原題連結
這題頗有趣的@@
首先想到的大概都是基於貪心的算法，我不免俗(?)的也覺得貪心蠻OK的，做完了傳上去當然是獲得WA。

2016年2月29日星期一

[POJ 1363][Stack] Rails

原題連結

[Codeforces Round #333 (Div. 1) pB][Stack] Lipshitz Sequence

原題連結

[POJ 3250][Stack] Bad Hair Day

原題連結
無聊繼續刷水題......

2016年2月28日星期日

[POJ 2559][Stack] Largest Rectangle in a Histogram

原題連結
無聊來刷刷水題......

[HOJ 136][TIOJ 1346][IOI 2007 Day2][DP] Training

原題連結
這道題也是各種折騰人......

2016年2月24日星期三

[NPSC 2009 高中組決賽][TIOJ 1690][DLX] 補習班的報名熱

原題連結

這邊不對DLX做太多的講解，只說如何建模。

[POI XI Stage II][SCC] The Tournament

原題連結

我個人非常喜歡這道題，主要是因為直到我AC前的2個小時，我都完全沒想到這題是SCC的一道題XD。
最後雖然發現了和SCC的強大關聯性，還是借用了同學的code，而且想了非常久才弄出來的......

2016年2月23日星期二

[POI XIV Stage I][TIOJ 1220][Disjoint Set] Offices(辦公室設置)

原題連結
詳細的題解可以直接參考這篇

[PA 2006 Round4][SCC] Crayfish

原題連結
這道題一開始我想的蠻歪的

2016年2月22日星期一

[Uva 315][articulation point] Network

原題連結
完全不解釋，就是一題裸的割點......
而且N才出到100，這題大概是在考你怎麼讀一行的數字吧......

[Codeforces Round #190 (Div. 1)][DP] Ciel and Gondolas

原題連結
這題的重點在於DP優化中決策點的單調性，有許多性質還是需要參考論文和證明才能懂的
有關於決策點的說明可以參考一下官方題解

2016年2月21日星期日

[Codeforces Round #313 (Div. 1) pC][DP] Gerald and Giant Chess

原題連結
本來一直往dp[i][j]=dp[i-1][j]+dp[i][j-1]去想......結果不管怎麼弄都逃離不了O(n^2)XD

最後看了codeforces上的tag寫著combinatorics!

才突然想起高中數學也有教，從(0,0)走到(n,m)的捷徑方法數是C(n+m,m)，這是解這題的其中一個關鍵

2016年2月20日星期六

[Codeforces Beta Round #23 pE][DP] Tree

好久沒更新了QQ

2016年2月13日星期六

[Codeforces 100365F][SG value] Coins Game

原題連結
相當經典的一題SG value

[Codeforces 603C][SG value] Lieges of Legendre

原題連結
這題對於SG value的新手來說還是不錯的題目，說明了遊戲題還是需要嘗試和觀察的....

2016年2月12日星期五

[POJ 2778][AC 自動機] DNA Sequence

原題連結

2016年2月5日星期五

[Uva 1449][AC自動機] Dominating Patterns

原題連結
給出字串集合A和字串B，請找出A中出現在B最多次的字串，如果次數相同則按照出現順序輸出。

2016年2月4日星期四

[Uva 1106][DP][操作分治] Machine Works

原題連結
這裡是這題完整的想法以及支持在線的作法，特地再寫一篇是因為像操作分治一類轉離線後的作法不僅code量少，時間和空間上的表現也都很優秀。

[Uva 1106][DP] Machine Works

原題連結
這道題目真是我見過最坑爹的一道題......

[POI XVIII][整體二分] Meteors

原題連結

整體二分這個科技在不想寫複雜資料結構(Persistent,Copy on write......)時還是挺好用的

2016年1月31日星期日

[SPOJ APIO10A][DP] Commando

題目連結
最單純的想法是1D/1D的DP，但是顯然不夠快。
這時候看看SPOJ的tag上寫著Convex Hull，然後就可以無恥的去做凸包優化了。

[POJ 1741][男人八題][樹分治] Tree

題目連結

不多說......就是樹分治的經典問題......在那個科技還不發達的年代還是挺難做的......

找重心，分治計算答案。最難的地方大概是答案的加減要想清楚，不然很容易完全寫錯。

啟發式合併貌似也挺快的，晚點補上code。

2016年1月29日星期五

[教學][String][Data Structure] 後綴自動機(Suffix Automaton)

==========!! Warning !!==========
此文內容皆是出自自己的理解，若有與實際情況不符之處，請以論文或是大神文章為主
==========!! Warning !!==========

後綴自動機(Suffix Automaton)大概是我見過網路上最多教學資源的資料結構了，許多大陸和外國的神人都有寫教學文，包括寫過持久化資料結構介紹的clj大神。
不過有鑒於許多教學不是為了力求邏輯通順，定義複雜繁瑣，就是講解過程中，省略許多思考步驟，導致讀起來不甚順暢。
最後我還是決定自己完整的給出一篇教學文，使用最少的定義(3個)，盡量簡化構造它和使用它的思考流程，對於重要的性質除非必須，否則說明點到即止，不加以證明。

2016年1月28日星期四

[SPOJ SUBLEX][Suffix Automaton] SUBLEX - Lexicographical Substring Search

題目連結

撇去Suffix Automaton的部份不談，這題有很多細節值得仔細探討

[Codeforces Round #146 (Div. 1)] Cyclical Quest

題目連結

題目要求在一給定字串S上求出某一字串T的所有循環字串出現幾次
(此處循環字串的意義詳見原題)

[SPOJ NSUBSTR][Suffix Automaton] NSUBSTR - Substrings

題目連結

恩....一樣是個只給O(n)方法過的字串題，倍增算法之類的只能吃土了QQ
後綴自動機的介紹請參考這裡

2016年1月27日星期三

[SPOJ LCS2][Suffix Automaton] LCS2 - Longest Common Substring II

題目連結

跟 LCS 這篇的作法非常相似，基本概念就不說了
不過寫這題的時候花了頗大量的時間釐清答案的更新順序和debug(最後的bug竟然是錯在toposort寫爛了...)

難點在於要怎麼兩兩合併計算答案，這要對後綴自動機上的狀態表示感受到一定深度才能體會(?
code中的許多assert可以幫助理解一些關鍵點和常有的bug

[SPOJ LCS][Suffix Automaton] LCS - Longest Common Substring

原題連結

Suffix Automaton(後綴自動機)的初級練習題，關於Suffix Automaton的教學和介紹網路上有很多資源，我之後也會自己補上一篇的
這題會用SAM的主要原因是SPOJ會莫名的把O(nlogn)的Suffix Array解卡掉，所以能過的大概只有後綴自動機或是O(n)後綴樹、後綴陣列的構造法吧

2016年1月26日星期二

[Codeforces 100495A][2014 KTU ACM ICPC Qualification Round][Dijkstra] Crystals

原題連結

注意到因為n很小...所以對於任何一個水晶集合都可以將狀態用一個int表示出來(點)，然後將集合的變換看成狀態的轉移(邊)

那麼本題就可以套用經典的最短路算法解決O(NlogN)，此時N=(2^n)

[Codeforces 100488M][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Construct a Permutation

原題連結

題意即構造最長排列使得LIS長度為a,LDS長度為b(Longest Decreasing Subsequence)

[Codeforces 100488K][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Two Pirates

原題連結

首先貪心顯然是要WA的，就不解釋了
困難之處在於無法知道最終兩人分別會取到什麼樣的數字集合

[Codeforces 100488C][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Lost Temple

原題連結

題意其實就是求出所有正整數對(a,b)使得a*b=k(a+b)
化簡之後可以得到(a-k)(b-k)=k^2

2016年1月25日星期一

[Codeforces 452E][MemSQL Start[c]UP 2.0 - Round 1][Suffix Array] Three strings

原題連結

首先老規矩，把三個字串用神秘的符號分隔後拼接起來，構造SuffixArray和Height陣列

相似的後綴會被排在一起，而且我們可以很快知道在SuffixArray的一群連續後綴的LCP(by H陣列)

訂閱：文章 (Atom)

2016年4月15日 星期五

2016年4月12日 星期二

2016年3月15日 星期二

2016年3月14日 星期一

2016年3月13日 星期日

2016年3月12日 星期六

2016年3月11日 星期五

2016年3月10日 星期四

2016年3月9日 星期三

2016年3月8日 星期二

2016年3月7日 星期一

2016年3月6日 星期日

2016年3月5日 星期六

2016年3月4日 星期五

2016年3月3日 星期四

2016年3月2日 星期三

2016年3月1日 星期二

2016年2月29日 星期一

2016年2月28日 星期日

2016年2月24日 星期三

2016年2月23日 星期二

2016年2月22日 星期一

2016年2月21日 星期日

2016年2月20日 星期六

2016年2月13日 星期六

2016年2月12日 星期五

2016年2月5日 星期五

2016年2月4日 星期四

2016年1月31日 星期日

2016年1月29日 星期五

2016年1月28日 星期四

2016年1月27日 星期三

2016年1月26日 星期二

2016年1月25日 星期一

2016年4月15日星期五

2016年4月12日星期二

2016年3月15日星期二

2016年3月14日星期一

2016年3月13日星期日

2016年3月12日星期六

2016年3月11日星期五

2016年3月10日星期四

2016年3月9日星期三

2016年3月8日星期二

2016年3月7日星期一

2016年3月6日星期日

2016年3月5日星期六

2016年3月4日星期五

2016年3月3日星期四

2016年3月2日星期三

2016年3月1日星期二

2016年2月29日星期一

2016年2月28日星期日

2016年2月24日星期三

2016年2月23日星期二

2016年2月22日星期一

2016年2月21日星期日

2016年2月20日星期六

2016年2月13日星期六

2016年2月12日星期五

2016年2月5日星期五

2016年2月4日星期四

2016年1月31日星期日

2016年1月29日星期五

2016年1月28日星期四

2016年1月27日星期三

2016年1月26日星期二

2016年1月25日星期一