Codeforces Round #354 (Div. 2)

http://codeforces.com/contest/676

http://codeforces.com/contest/676/problem/A
http://codeforces.com/contest/676/problem/B
http://codeforces.com/contest/676/problem/C
http://codeforces.com/contest/676/problem/D
http://codeforces.com/contest/676/problem/E

上面是題目

我AC的code :
pA : http://codeforces.com/contest/676/submission/18103173
pB : http://codeforces.com/contest/676/submission/18119627
pC : http://codeforces.com/contest/676/submission/18081711
pD : http://codeforces.com/contest/676/submission/18120507
pE : http://codeforces.com/contest/676/submission/18119387

題解：

pA :
題目是說：要swap一次，讓1和n的距離最遠。

那可以想像的是說，就盡量把1和n移到最邊邊一定是最好，那如果他們本身就在最邊邊了，那就他們兩個交換就好。
實作的部分就看code吧。

pB :
題目：有n個杯子，第一層有1個......第n層有n個。我要倒水t次，每次都從第一個上倒剛好一個杯子的水量。如果溢出來，就分兩半到左右兩邊。請問到最後有多少個杯子是滿的。

那可以發現的是：n很小。於是，認真實作倒水的動作即可。可以看看code。

pC :
題目：給你一個字串，只包含a,b。請問，在換過最多k個字元後，連續字元最長是多少(可以是a或b，比如說：aaab就是3，aaabbbbba就是4)。

先有一個greedy的想法：如果某個區段是最佳解，那這個區段一定包含這k個被轉換的字元(因為越長越好嘛！)。所以說，你會發現，這k個字元最好要聚集在一起，於是乎，就可以想出一個爬行法(two pointers)的作法。
實作的部分就看看code吧！

pD :
題目：有一個n*m的房間，每個房間都有門，有各種字元代表有哪些門是開著的。當兩個房間可以彼此互通時，才可以走過去。你可以在任意時刻順時針轉90度，這個時候，所有房間的門都要轉90度。請問，sx,sy到ex,ey的最短時間(轉90度，走房間的時間都是1)。

那，我還真的不知道可以怎麼做，於是乎就跟學長、社員討論一番後。才知道可以這樣做，也算有長知識吧：就是，最多只會有四種狀態(轉四次)，所以，我就在每個狀態，可以建邊的就建邊。在不同狀態時，(x,y)一定可以到轉90度後的狀態的(x,y)。於是乎，就最多有6nm個邊，可以開心地做BFS。
實作就看看code吧。

pE :
題目：人跟AI的對決：現在有一個n次式，有些位置已知，有些位置未知。在初始狀態(全部都未知)，電腦先下，所以說，一開始的電腦和人，都只能下這些已知的位置。未知的位置可以放進任意的實數(正的、負的、0、小數)如果到最後，這個n次式可以被Q(x) = x-k整除，那就代表人類獲勝，否則電腦就贏了。

這題也是跟學長&社員討論出來的。先分兩種情況：n次式的x=0 or x!=0。
如果x!=0，那，如果有未知項，那誰先掌握最後一個數字，誰就贏了！(因為可以填任意數字)。如果沒有未知項，那你就取一個質數p，讓這條式子對p做模運算，如果=0，那代表最後的結果有可能=0，就是okay(可是經過我的測試，如果單用1e9+7 or 1e9+9 or 兩個都用，都會爛掉，於是，要多取一些)。
如果x==0，那就分常數項討論：如果常數項未知，那目前誰先下，誰就贏。如果常數項已知，判斷是不是0就好了！
實作看code吧！

第一次全部都會，好開心 ^_^

(Codeforces) 675D. Tree Construction

http://codeforces.com/problemset/problem/675/D

題意：給你n個點，依序加入二元樹。

當然不能實作，如果是一條直鏈，複雜度就爛掉了XDDD

所以說，後來我想想，發現：
加入一個值，他的祖先就是在目前的集合中  比他大的值中最小的  和  比他小的值中的最大的  的其中一個。那，我就開一棵數值線段樹是解決就好了XD

詳細就看我的code吧！也可以參考          (TOJ) 47. 1d-kd-tree          的解說

http://codeforces.com/contest/675/submission/17981375

(Codeforces)(Python) 675C. Money Transfers

http://codeforces.com/contest/675/problem/C

這題的題意：現在有n個環狀銀行，你在銀行有存錢(正值) or 欠錢(負值)。這n個銀行的錢的總和是0。每一部你都可以把任意數量的錢從一個銀行轉到鄰居銀行。求使得全部銀行的錢=0的最小步數。

我的想法：(我從當初看到題目的過程一直寫下來好了)

一開始想說，最多一定是n部(就一路轉一圈就好了)

後來想說，好想要找出某一些區段=0，使得這些區段蓋滿區間。

後來想想，如果我開前綴和，那不就前綴和一樣的區段中間不就=0！

那那那，那不就是  ( n - 出現最多的前綴和  )   XDDD

耶，AC了！

http://codeforces.com/contest/675/submission/17979231

(後記)

難得我的code寫的這們短，如果按照solution size 排序還看的到我的XDDD

(TOJ) 386 西瓜愛算術 [Python : tree]

http://sprout.tw/oj/pro/386/

主要想法就是如果遇到括號，就一直遞迴下去

Python班完了再放到codepad上XDDD

http://sprout.tw/oj/chal/53947/

def get_pivot( s ):    
    cnt = 0
    for i in range( 3 , len( s ) ):
        if s[ i ] == '(':
            cnt += 1
        elif s[ i ] == ')':
            cnt -= 1
        elif cnt == 0 and s[ i ] == ' ':
            return i
    return -123456789;
        

def f(s) :
    #print("in " + s);
    t = get_pivot(s);
    #print("t = "+str(t));
    a=0;
    b=0;
    if (s[t-1] == ')') :
        tmpt=t-1;
        check=1;
        while (s[tmpt]!='(') or check!=0:
            tmpt-=1;
            if (s[tmpt]==')') :
                check+=1;
            elif (s[tmpt]=='(') :
                check-=1
        a = f(s[tmpt:t])
    else :
        tmpt=t-1;
        tmp=[];
        while (s[tmpt]!=' ') :
            tmp.append(s[tmpt]);
            tmpt-=1;
        a=0;
        for i in range(len(tmp)-1,-1,-1) :
            a=a*10 + int(tmp[i]);
            
    if (s[t+1] == '(') :
        tmpt=t+1;
        check=1;
        while (s[tmpt]!=')') or check!=0:
            tmpt+=1;
            if (s[tmpt]==')') :
                check-=1;
            elif (s[tmpt]=='(') :
                check+=1;
        b = f(s[t+1:tmpt+1])
    else :
        tmpt=t+1;
        tmp=[];
        while (s[tmpt]!=')') :
            tmp.append(s[tmpt]);
            tmpt+=1;
        b=0;
        for i in range(0,len(tmp)) :
            b=b*10 + int(tmp[i]);
            
    #print(s + " : a=" + str(a) +" b= "+str(b));
            
    if s[1]=='+' :
        return a+b;
    elif s[1]=='-' :
        return a-b;
    elif s[1]=='*' :
        return a*b;
    elif s[1]=='/' :
        return a//b;
        
    

n=int(input());
for i in range(0,n) :
    s=input()
    tmp=get_pivot(s)
    
    if tmp==-123456789:
        print(s);
    else :
        if (s[0]!='(') :
            s = "(" + s + ")";
        print(f(s));

(Codeforces) 672D. Robin Hood

http://codeforces.com/contest/672/problem/D

這題的大意是說我總共有n個人，每個人都有Cn塊錢。

每天，Robin Hood 會從最有錢的拿走1塊錢，然後在把這一塊錢拿給目前狀態中錢最少的那個人(比如說，3個人分別有3,3,3，會先變成3,3,2，再變成3,3,3)

現在總共有k天，求出過了這k天後，(最有錢-最沒錢)的值

我的想法：最有錢&最沒錢都可以二分搜，就OK啦~~，小心溢位

http://codeforces.com/contest/672/submission/17888095

(TOJ) 157 [rolling hash]

http://sprout.tw/oj/pro/157/

一定要用rolling hash!!!

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

int a[2][1000001];
int w[101];
int v[101];

int main () {
int T;
scanf("%d",&T);
while (T--) {
int n,m;
scanf("%d %d",&n,&m);
for (int x=1;n>=x;x++) scanf("%d %d",&w[x],&v[x]);
memset(a,0,sizeof(a));
for (int x=1;n>=x;x++) {
for (int y=1;m>=y;y++) {
if (y - w[x] < 0) a[1][y] = a[0][y];
else a[1][y] = max(a[0][y],a[0][y-w[x]] + v[x]);
}
for (int y=1;m>=y;y++) a[0][y] = a[1][y];
}
printf("%d\n",a[1][m]);
}
}

Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition)

http://codeforces.com/contest/673

題目在上面

我AC的code ：
pA : http://codeforces.com/contest/673/submission/17781398
pB : http://codeforces.com/contest/673/submission/17784269
pC : http://codeforces.com/contest/673/submission/17786886
pD : http://codeforces.com/contest/673/submission/17789145

我的Rating  : 1288 --> 1522  ， 從pupil(學生) --> specialist

題解：

pA :
尋找第一個兩個相鄰數字差>=15的數字，輸出該數字+15即可

pB :
遇到兩個是similar的problem，那我們一定可以知道：數字大要在div. 1，數字小的要在div. 2，如果沒有發生矛盾的情況，那我們再繼續找所有的題目中，div. 2題號最大的 imax 和div. 1題目標號最小的 jmin ，如果 imax > jmin ==> 矛盾。如果沒有矛盾，那在[imax+1 , jmin-1] 的區間的數字中，可以任意切割成兩個連續部分，再稍微處理一下，即是解答！

pC :
認真O(N^2)一番。就是說，你要記錄每個數字出現的次數，對於現在的答案最大的數字id出現num次，如果有一個新的數字i更新後剛好出現num次，則判斷id > i，如果是，更新答案！

pD :
如果n==4 || k<=n，輸出-1(不可能)
要不然，就直接看我的code的想法(還跟jury一樣XDDD)
有點懶的解釋