PKU 2540 Hotter Colder [CG]

7564334    poao899    2540    Accepted    424K    0MS    G++    3998B    2010-09-02 22:09:01                         .



CG題好硬QQ不過應該是打定了XD寫起來頗有成就感(?)

看那精美的code length(望

不過   看到這題還是會想到IOI那個吧XD





題目大意：

有個房間，大小10*10

你一開始站在(0,0)，某個位置有一個熱源。

接下來每次你會移動到任意一個座標，然後會告訴你感覺Hotter還是Colder還是Same

每次移動輸出一個數字表示  "熱源可能位置"  的面積。

保證不會移動超過50次。





Sample Input：

10.0 10.0 Colder
10.0 0.0 Hotter
0.0 0.0 Colder
10.0 10.0 Hotter

Sample Output：

50.00
37.50
12.50
0.00



















===============解題報告===============


等於每次對多邊形切一條線，問面積。

測資很小所以可以每次把所有點掃過一遍。


幾個要注意的地方：

1.  判斷交點要注意等於0的狀況= =
2. 把兩個交點去修正多邊形時要注意加入的順序。
3. 注意如果重複點加入多邊形，會爆炸。




大概差不多這樣吧xD

POI - PA 2010 Round 2 Coins

翻譯:

給你n, k還有一個由R, O組成的長度n的序列。

找出區間[i, j]使得這個區間內O的個數是R的k倍，這個區間最長能多長

n, k <= 1,000,000


Sample Input:
15 3
RORROOROOROOORO



Sample Output:
8





solution:

這題跟之前USACO一題有異曲同工之感。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3274

定義f(i) = 1~i出現多少個R - (i/(k+1))

那麼會發現，若f(a) == f(b)則 [a+1, b]必為合法區間

排序 O(n lg n)或Hash O(n)就結束了。

蝴蝶作法雖然核心一樣不過細節完全不同，雖然一樣O(n lg n)

POI 11th Spies

題外話：

這題是POI XI Stage I當年第二多人寫出來的題目


最多那題沒有放在main上面QQ


當年這題 190/334 個滿分，不過我覺得這題明明沒有簡單到這種程度= =


// 好罩電波一定覺得是秒殺題


噢然後，Example裡面有一個1打成小寫L，我在想怎麼一直RE





翻譯：

BIA僱用了很多間諜，每個間諜都被下令要監視其他另一個間諜。

KB想要選一些間諜去進行絕密任務，而且他希望能委任越多間諜越好。

然而這個任務太重要了，所以他希望每個被委任的間諜都至少被一個沒有參與任務的間諜
監視。（而且目前的跟監關係不能變動。）


輸入第一行含一個數字n <= 1,000,000，表示共有n個間諜，接下來會有n行

第i+1行會有一個數字Ai，表示間諜i的跟監對象是Ai。

輸出包涵一個數字K，表示最多可以委任K個間諜並符合題目要求。



Example:
6
2
3
1
3
6
5

the correct result is:
3

===================================題解========================





保證每個點都只會有一條連出去的邊，所以每個連通塊一定是一些鍊，

然後有可能在末尾出現一個環。


對於那些鍊，有一個很明顯而且好證的貪心法就是：


1. 如果那個點入分枝度為零，不能取
2. 如果進入那個點的所有點中有任何一個沒有被取的，那麼他就可以取

然後再來處理每個環：

1. 如果那個環所有點入分枝度都是1 -> 可以取  環長/2 取高斯個點
2. 如果那個環有些點入分枝度 > 1 且有至少一個進入他的點沒被取  那他也可以取
   然後剩下的點依照跟鍊一樣的邏輯取完。


總複雜度 O(V)

COCI 2009/2010 #3 p5

標題好長XD


簡單的說

第一行有兩個數字N, C

接下來給你一條數列S  ，長度是N(<=300,000)，裡面的數字範圍是1~C(<=10,000)

第三行是一個數字M(<=10,000)表示有幾組詢問

接下來M組詢問，每組有L, R(1<=L<=R<=N)

問你閉區間[L, R]中有沒有哪個數字出現超過一半？有的話問是哪個數字？

Sample input:
10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10

Sample output:
no
yes 1
no
yes 1
no
yes 2
no
yes 3


全國賽那天晚上戰的COCI的題目(轉

小鬼當時說他會做了不知道跟官方solution一不一樣(欸

shik表示：蒙地卡羅應該會過


不過官方solution好好玩(打滾











========================solution===================


先不要考慮原題目，來想另一個遊戲：

給你一個序列S，每次可以把S裡面相異兩個數字抹掉。

直到全部都剩下同一個數字時遊戲結束

例如 12312323->312323->1323->33m 時結束。

這時紀錄兩個數 candi表示剩下的數字是什麼  count表示結束狀態多長

例如上述例子   candi=3 count=2




引理：如果有個數字出現超過length/2次，那他一定會是candi，無論過程

那麼，我們只要維護一棵seg tree就可以作到區間查詢candi了ˇ

就是分L.candi==R.candi以及L.candi!=R.candi時比兩個count大小

然後求出這個區間的candi，再去用另一棵seg tree計算他出現幾次

如果出現>length/2次就是yes  否則則是no

IOI &#39;05 Mean Sequence

這題被小乃瞬秒XD    不過其實還頗有趣的                                                                                                         .


Description:

定義一個數列S的Mean序列M:

Mi = (Si + S(i+1))/2

例如   序列1, 1, 3, 5, 15的M為: 1, 2, 4, 10



給你一個有n項的序列M，請問有多少S使得

1. S的Mean序列為M

2. S1 <= S2 <= S3 <= ... <= S(n+1)


n<= 5,000,000







Solution:

M2-M1 = (S3-S1)/2

依此，可以把奇數項和偶數項分開討論，例如範例就變成

(a), (b), (a+2), (b+4), (a+14)

再由條件2.

(a)<= (b)<= (a+2)<= (b+4)<= (a+14)

解不等式  加上a+b = 2(M1)驗證


總複雜度O(n)

IOI &#39;06 Joining Points

這題沒有Judge，所以自己寫了一個應該是可以AC的啦XD                                                                           .




很棒的題目。


Description:


Joining Points是一個獨人遊戲。

平面上有g個綠點  r個紅點   (2 <= g,r <= 50 000)

所有點都是整數座標   座標範圍是0~s (s <= 200 000 000)


保證(0,s)和(s,s)有綠點  (s,0)和(0,0)有紅點 並且任三點不共線

遊戲勝利的條件是  用g-1條線段把所有綠點連起來  用r-1條線段把所有紅點連起來

並且所有線段不交叉(共端點不算交叉)

保證一定有解  請輸出任意一種連線方案


Input

第一行: 整數g。接下來g行: 從綠點的編號1開始到g，每一行有二個以空白隔開的整數，
代表一個綠點的xi與yi 座標。第g+2行: 整數 r。接下來r行: 從紅點的編號1開始到r，
每一行有二個以空白隔開的整數，代表一個紅點的xi與yi 座標。

Output

共應輸出g-1+r-1行
每行包含兩個整數一個字元   前兩個整數代表這條線段所連接兩點編號
字元表示所連接兩點顏色


Sample Input
6
0 1000
1000 1000
203 601
449 212
620 837
708 537
8
0 0
1000 0
185 300
314 888
416 458
614 622
683 95
838 400


Sample Output
1 3 g
3 1 r
3 5 r
4 6 r
6 5 r
4 6 g
1 2 g
1 2 r
5 2 g
2 6 g
7 8 r
8 2 r



Solution:






這題目是很棒的D&C。時間複雜度：O(n lg n)


核心思想：

考慮一個三角形  v1 v2 v3 ，其中 v1,v2同色   v3異色

(1)如果中間沒有其他點    結束
(2)如果中間全部剩下的點同色    把那些點全部連到同一個頂點    結束
(3)其他：
選出一個跟v3同色的內部點vp，連v3-vp
然後對v1,v2,vp    v2,v3,vp   v3,v1,vp遞迴



很顯而易見遞迴三角形個數是和(g+r)同數量級，

如果對每個三角形O(g+r)檢查，就有了一個O((g+r)^2)算法   值55分


但是可以發現，其實對同一層    只需要合計O(g+r)的複雜度就可以
總共不會超過lg級別層，所以複雜度O(n lg n)ˇ



至於實做，我是以串列實做。










code(Judge程式，會告訴你是哪裡出錯)

http://codepad.org/rwc0RnZq

對了提一下，檢查是用Disjoint Set確定連通性，Sweep Line Algorithm檢查是否有交點




code(AC code)

http://codepad.org/q6v18QD5




testdata / solution (official)

http://olympiads.win.tue.nl/ioi/ioi2006/contest/day2/points/

IOI &#39;07 Pairs

2    75971    poao899    49440K    4656MS    G++     3.16K     2010-04-26 08:47:55                        .



Inspired by warehouse?

不過三維作法很有趣，竟然有一個n維曼哈頓轉Chebyshev distance的作法，


可惜依現在硬體技術，作用有限

事實上這兩個都有優點，可惜自由轉換僅限於1或2維

算是個遺憾吧(?

//*****************************************

#include<algorithm>
#define N 100010
#define lb(x) ((x)&-(x))
struct ele{
    int i, j, k, w, x, y, z;
    void _2get();
    void _3get();
}_ar[N];
int ar[N], front, rear;
int b, n, d, m, nmax; long long ans;
int getint(){
    int g=0; char c=getchar();
    while(c==10||c==32||c==9)c=getchar();
    while(c>='0'&&c<='9'){
        g= g*10+c-48;
        c=getchar();
    }
    return g;
}
//case 2
#define _2LEN 75010
void ele::_2get(){
    i= getint(); j= getint();
    x= i+j; y= i-j;
}
bool _2cmp(ele a, ele b){
    return a.y<b.y;
}
int _2bit[_2LEN*3];
inline int _2qry(int a){
    if(a<0) return 0;
    int ret= 0;
    while(a>0){
        ret+= _2bit[a];
        a-= lb(a);
    }
    return ret;
}
inline int _2find(int l, int r){
    return _2qry(r)-_2qry(l-1);
}
inline void _2adj(int a, int r){
    while(a<=nmax){
        _2bit[a]+= r;
        a+= lb(a);
    }
}
//case 3
#define _3LEN 76
void ele::_3get(){
    i= getint(); j= getint(); k= getint();
    w= i-j-k; x= i+j-k+m; y= i-j+k+m; z= i+j+k;
}
bool _3cmp(ele a, ele b){
    return a.w<b.w;
}
int _3bit[_3LEN*3+1][_3LEN*3+1][_3LEN*3+1];
inline int _3qry(int x, int y, int z){
    int ret= 0;
    for(int xx=x; xx>0; xx-=lb(xx))
        for(int yy=y; yy>0; yy-=lb(yy))
            for(int zz=z; zz>0; zz-=lb(zz))
                ret+= _3bit[xx][yy][zz];
    return ret;
}
inline int _3find(int lx, int ly, int lz, int rx, int ry, int rz){
    if(rx> nmax)rx= nmax;
    if(ry> nmax)ry= nmax;
    if(rz> nmax)rz= nmax;
    int ret= _3qry(rx,ry,rz);
    ret= ret- _3qry(lx-1,ry,rz)- _3qry(rx,ly-1,rz)- _3qry(rx,ry,lz-1);
    ret= ret+ _3qry(rx,ly-1,lz-1)+ _3qry(lx-1,ry,lz-1)+ _3qry(lx-1,ly-1,rz);
    ret= ret- _3qry(lx-1,ly-1,lz-1);
    return ret;
}
inline void _3adj(int x, int y, int z, int r){
    for(int xx=x; xx<=nmax; xx+=lb(xx))
        for(int yy=y; yy<=nmax; yy+=lb(yy))
            for(int zz=z; zz<=nmax; zz+=lb(zz))
                _3bit[xx][yy][zz]+= r;
}
int main(){
    b= getint(); n= getint(); d= getint(); m= getint();
    //case 1
    if(b==1){
        for(int i=0; i<n; i++) ar[i]= getint();
        std::sort(ar, ar+n);
        for(front=rear=0; rear<n; rear++){
            while(ar[front]+d< ar[rear]) front++;
            ans+= rear-front;
        }
    }
    //case 2
    else if(b==2){
        nmax= _2LEN*3;
        for(int i=0; i<n; i++) _ar[i]._2get();
        std::sort(_ar, _ar+n, _2cmp);
        for(front=rear=0; rear<n; rear++){
            while(_ar[front].y+d< _ar[rear].y){
                _2adj(_ar[front].x, -1);
                front++;
            }
            ans+= _2find(_ar[rear].x-d, _ar[rear].x+d);
            _2adj(_ar[rear].x, 1);
        }
    }
    //case 3
    else if(b==3){
        nmax= _3LEN*3;
        for(int i=0; i<n; i++) _ar[i]._3get();
        std::sort(_ar, _ar+n, _3cmp);
        for(front=rear=0; rear<n; rear++){
            while(_ar[front].w+d< _ar[rear].w){
                _3adj(_ar[front].x, _ar[front].y, _ar[front].z, -1);
                front++;
            }
            ans+= _3find(_ar[rear].x-d, _ar[rear].y-d, _ar[rear].z-d, _ar[rear].x+d, _ar[rear].y+d, _ar[rear].z+d);
            _3adj(_ar[rear].x, _ar[rear].y, _ar[rear].z, 1);
        }
    }
    printf("%I64d\n", ans);
}