Printing Without Space or NewLine

A trick of printing thing

--------------------------------------------------------

print "hello"
print "world"

The statement above print out something like this:

hello
world

Then by using comma,

print "hello",
print "world"

It will print:

hello world

The cool part is this: 

import sys
sys.stdout.write("hello")
sys.stdout.write("world")

By doing this, It will finally print out:

helloworld

From...http://codingrecipes.com/

Set

剛剛發現Set除了記錄是否出現過以外

還具有priority_queue的功用

他的begin()可以O(1)取得最佳值
（端看如何定義，通常為min值）

他的end()則可以O(1)取得最差值

他的erase()：
erase(position<iterator>)可以O(1)刪除
erase(object)則可以O(lgN)刪除

還有基本的insert(), count(), find(), size()

主要用這七個便可以在競賽中如魚得水


最後就是要如何定義最佳：

平常都是直接重載小於運算子－

bool operator<(int x, int y) return x<y;

但當你要使用的是原本就存在的type，為了避免override

可以寫成這樣－

#include<set>
struct comp{
    bool operator()(int x, int y){ return x>y; }
};
int main(){
    set<int, comp> S;
}

但寫成這樣好像更好－

#include<set>
struct comp{
    bool operator()(const int& x, const int& y)const{ return x>y; }s
};
int main(){
    set<int, comp> S;
}

接下來...

將會有28提，很不錯的網路流題目出場～～～

That's talk about Network Flow

其實我一直以為我對網路流很瞭解了，

但其實有很多東西我還不會QQ

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝從最簡單的開始

首先，有一個作法，就是不斷的流，流到不能流就停止的FF算法

要注意的是你在邊的某方向流了多少，就可以在另一個方向多流一些!!!!（就是剩餘的概念）

他的證明很神奇，但也不是什麼想不到的事情，只要你注意到一個KEY：『最小割』，『流』一定會小於等於『割』，當兩者相等時，流必為最大的，割必為最小的，也就是所謂的『最大流最小割定理』。

每次選一條可以流的路 -> O(E)＊最慘的情況下每次只增加一，而最大流是F->O(F) = O(FE)

這樣實在是太悲劇了，完全無法預知，只要流量都大到暴，時限內根本跑不完QAQ

Dinic在好久好久以前，就做了一個很棒的改進，他發現只要每次都走最短路（是指距離最短，跟邊上的流量無任何關係），就可以有很精確的複雜度了（但通常會比較小）

希望我寫的不會太爛，如果不想去了解的話，可以直接記結果，也就是每次都走最短路的話，最多只會擴充O(VE)次。所以重要的就是怎麼去找最短路。如果你感到很疑惑，走不走最短路真的有差嘛？還是那只是理論值而已，說說罷了。這裡可以附上一個非常誇張的圖：

走最短路的話，就可以避免這種愚蠢的情形發生。想要找最短路的話主要有三種方法：

1. 用BFS找：俗稱Edmonds- Karp Algorithm

這個概念很簡單，對於每次擴展都BFS一次，複雜度O(VE*E)

2. 用BFS建分層圖找：又稱Dinic Algorithm

他是先建出一個分層圖，不斷的dfs找路走，一直到沒有辦法走為止，就更新一次分層圖，並重複上述步驟。因為最長的distance是V，所以只會更新分層圖V次，複雜度O(VE+VE*V)

3. 用Relabel建分層圖找：又稱Improved Shortest Path Algorithm

先假定每個人距離T的dis都是0，接下來就開始用DFS找最短增廣路，如果你發現，某個點的距離已經不是你所想的那樣了，就把它設成他應該的樣子（這裡會用到一個概念，也就是點的距離只會增不會減，正確性在先前已證過），每次增廣O(V)＊最大距離O(V)＊某距離要查找幾次O(E)＝複雜度O(VE*V)

ISAP code:

struct edge{int t,c,r;edge(){} edge(int _t,int _c,int _r){t=_t;c=_c;r=_r;}};
vector<edge> G[N];
int s, t, n;
int iter[N], d[N], gap[N];
int dfs( int p, int flow ){
    if( p == t ) return flow;
    for( int &i=iter[p]; i<SZ(G[p]); i++ ){
        edge &e=G[p][i];
        if( e.c > 0 && d[e.t] == d[p]-1 ){
            int f = dfs( e.t, min( e.c, flow ) );
            if( f ){ e.c -= f, G[e.t][e.r].c += f; return f; }
        }
    }
    if( (--gap[d[p]]) == 0 ) d[s]=n;
    else{
        d[p]=n;
        for( int i=0; i<SZ(G[p]); i++ ) if( G[p][i].c && d[p]>d[G[p][i].t]+1 ) d[p]=d[G[p][i].t]+1;
        gap[d[p]]++; iter[p]=0;
    }
    return 0;
}
int isap(){
    for( int ret=0; d[s]<n; ret+=dfs(s,INF) );
    return ret;
}

斜率優化

今天多虧了J睿的福，我很清楚的了解了斜率優化的基礎，

並自己透過概念，想出一套錯誤的演算法，再經J睿的修正，得出這個算法的正確形象

感謝最愛J!NN的J1SS睿～～～>//////<

他並不是很難，看到下面這個基本的斜率優化code就知道了，精神不過五行。

//By momo
#include<cstdio>
int s[100010],dq[100010],f,e,r,L,R,x,y,t,n,k,i;
bool crs( int a,int b,int c ){
    return 1ll*(s[b]-s[a])*(c-b)>1ll*(s[c]-s[b])*(b-a);
}
int main(){
    scanf("%d",&t);
    while( t-- ){
        scanf("%d%d\n",&n,&k);
        for( s[0]=f=e=y=0,i=x=1; i<=n;i++) r=getchar(),s[i]=s[i-1]+r-'0';
        for( i=k; i<=n; i++ ){
            while( f<e-1 && crs(dq[e-2],dq[e-1],i-k) ) e--; dq[e++]=i-k;
            while( f<e-1 && !crs(dq[f],dq[f+1],i) ) f++;
            if( 1ll*y*(i-dq[f])<1ll*x*(s[i]-s[dq[f]]) 
             || 1ll*y*(i-dq[f])==1ll*x*(s[i]-s[dq[f]]) && i-dq[f]<R-L )
                x=i-dq[f], y=s[i]-s[dq[f]], L=dq[f], R=i;
        }
        printf("%d %d\n",L+1,R);
    }
}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝今天就快速進入正題，code已附上

他基本上用來解的題目是這樣子的－Q:給一個序列（有N個值），問長度大於等於K的最大平均和?

預先操作為將序列轉成sum[i]序列（就是由a0+...+ai），題目也轉成在座標平面上（x為i值，y為sum[i]值），選出兩點使(sum[i]-sum[j])/(i-j)的值最大（其中i-j+1>=K），也就是斜率最大（故稱為斜率優化）

naive作法：枚舉i並枚舉他的j，O(n^2)，爛作法-3-

這時，你重新的看一下你想要做的事情：

你其實想要做的是對於所有的i，要從K限制以下的點中，找出一點，使i節點與那一個點的斜率最大。

而從幾何上看來，即為一個圍起來的凸多邊形，而在 此多邊形 外的點，要與其中的所有點有最大斜率or最小斜率時，其必出現在端點上（線性規劃的精隨）。

（pf: 一個不是端點的點，代表在一個距離為e的圓（或半圓）內必存在另一個也在此多邊形中的點，若此點有最大斜率，則在此點指向i的向量順時針轉180度的範圍內移動e，皆可使斜率變大（反之則斜率變小），故唯有某一端點才會有最大斜率）

這時你就得到一個較快速的方法，求出前面的凸包，一個一個枚舉，而你又可以知道上半部的凸包並不是最大的（反而是最小的），原因如同上面的證明，所以你只需要記錄下凸包即可，但複雜度仍為O(n^2)。（下凸包定義：斜率遞增，且不會有點在此函數下方）

再多想一下你想要找的是什麼：

你發現了其實你要找的是一個切點－定義為與i形成的直線『斜率最大』的點－，經過一些直覺的猜想與證明，你知道這個切點與i形成的直線斜率要介於這個切點與兩個邊所形成的直線斜率之間，把它做切塊后，你可以很清楚的看到這樣的點只有一個，除非是在邊上（如圖所示），而且每個點與i形成的斜率會呈現遞增再遞減的趨勢。

{性質：斜率會是遞增再遞減，而切點則是使與i形成的斜率介於兩個邊所形成的直線斜率之間，且唯一}

pf:先證遞減，同理可證遞增

pf:再證當斜率介於這個切點與兩個邊所形成的直線斜率之間，則斜率比兩邊都還要大

這時你就可以用一個二分搜的方法求出切點，演算法複雜度：O(nlgn)，但這並不是最好的，因為再多看一下我放的第二張圖，你會發現當你做到某一切點時，前面的點都可以刪掉了，因為若之後的點會把前方的點當做切點時，他的斜率必介於兩個邊的斜率之間，而且邊的斜率遞增，所以這個斜率一定會小於現在做到的斜率，故你也不需要去看前面的點了。加上這個單調性優化，複雜度變成了O(n)。

tohtml.com

#include<stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    printf("%d\n",n);
}

想要code直接color的話，可以去http://tohtml.com，他會自動把code轉成html，並上色～