2016年3月14日 星期一

[Codechef IOPC16Q][Math] Bat In Cage

原題連結
這道題....個人覺得比較傳統的數學分析。

[BZOJ 3295][操作分治] 動態逆序對

原題連結
這道題搞了我兩天左右....對於像我一樣沒有對操作分治感受深刻的人的確是比較難做的......
操作分治簡單的例子可以看這裡
code有參考過中國的大神,所以看到很像的code不要驚訝(?

2016年3月13日 星期日

[ZJ b417][莫隊] 區間眾數

原題連結
莫隊算法(Mo's algorithm)這幾年非常的紅啊~~
有很多需要複雜資料結構(LCT , 樹鏈剖分 , 持久化資料結構....) 的題目都可以用莫隊搭配樹壓平之類的技巧作到帶根號的複雜度。

2016年3月11日 星期五

[Wunder Fund Round 2016 pD][DP] Hamiltonian Spanning Tree

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月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月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

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