[Codeforces] #417 (Div. 2)

題目連結：http://codeforces.com/contest/812

#A
一開始我題目有點看不太懂，就隨便寫一寫pretest過了，沒想到之後被hackＸＤ。
就是一題暴力題，code有點醜。

#include <iostream>
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
bool ok[5][5];
int main(){jizz
    for(int i = 1 ;i <= 4; i++ )
        for(int j = 1; j <= 4 ; j++)
            cin >> ok[i][j];
    bool flag = 0;
    for(int i = 1; i <= 4; i++){
        if(ok[i][4]){
            if(i == 1 && (ok[2][1] || ok[4][3] || ok[i][1] || ok[i][2] || ok[i][3] || ok[3][2]))
                flag = 1;
            else if(i == 2 && (ok[1][3] || ok[3][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[4][2]))
                flag = 1;
            else if(i == 3 && (ok[2][3] || ok[4][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[1][2]))
                flag = 1;
            else if(i == 4 && (ok[3][3] || ok[1][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[2][2]))
                flag = 1;
        }
    }
    flag == 1? cout << "YES" << endl : cout << "NO" << endl;
    return 0;
}

#B
pB比pC難www
dp[i][j] 存到第i層的左邊樓梯(j = 0)和右邊樓梯(j = 1)的時間。
轉移式j = 0的話就考慮前一層的右邊直接走到左邊來再往下一層走 以及 左邊往右走到燈的最右邊之後往回走去下一層。
j = 1 以此類推。
順便紀錄每一層的最左邊和最右邊分別在哪，以及哪一層之後都沒有燈泡亮。

#include <iostream>
#include <string>
#define mp make_pair
using namespace std;
typedef pair<int,int> pi;
int dp[20][2];
pi ha[20];
int main(){
    int n,m;cin >> n >> m;
    int top = -1;
    for(int i = 0 ; i < 20 ; i++)ha[i] = mp(m+1,0);
    for(int i = n-1 ; i >= 0 ; i--){
        string s;cin >> s;
        for(int j = 1 ; j <= m ; j++){
            if(s[j] == '1'){
                top = max(top,i);
                ha[i].first = min(j,ha[i].first);
                ha[i].second = max(j,ha[i].second);
            }
        }
    }
    if(top == -1){cout << '0' << endl;return 0;}
    if(top == 0){cout << ha[0].second << endl;return 0;}
    if(ha[0].first == m+1)dp[1][0] = 1;
    else dp[1][0] = ha[0].second*2+1;
    dp[1][1] = m+2;
    for(int i = 1; i <= top ; i++){
        if(i == top){
            cout << min(dp[i][0] + ha[i].second,dp[i][1] + m - ha[i].first + 1) << endl;
            return 0;
        }
        if(ha[i].first == m+1){
            dp[i+1][0] = min(dp[i][0]+1,dp[i][1]+m+2);
            dp[i+1][1] = min(dp[i][0]+m+2,dp[i][1]+1);
        }else{
            dp[i+1][0] = min(dp[i][0]+ha[i].second*2+1,dp[i][1]+m+2);
            dp[i+1][1] = min(dp[i][0]+m+2,dp[i][1]+(m-ha[i].first+1)*2+1);
        }
    }
    return 0;
}

#C
就很單純的二分搜答案(要注意long long)，結案！

#include <iostream>
#include <algorithm>
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
long long val[100005];
int n,s;
long long ok(int x){
    long long hey[100005] = {0};
    for(int i = 1 ; i <= n ; i++)
        hey[i] = (val[i] + (long long)i*(long long)x);
    sort(hey+1,hey+n+1);
    long long tmp = 0;
    for(int i = 1; i <= x; i++){
        if(tmp + hey[i] > s)return 0;
        tmp += hey[i];
    }
    return tmp;
}
int main(){jizz
    cin >> n >> s;
    for(int i = 1 ; i <= n ; i++)cin >> val[i];
    int L = 0,R = n+1;
    long long ans1 = 0,ans2 = 0;
    while((R-L) != 1){
        int M = (R+L)/2;
        ans2 = ok(M);
        if(!ans2)R = M;
        else {
            ans1 = ans2;
            L = M;
        }
    }
    cout << L << ' ' << ans1 << endl;
    return 0;
}

#D
覺得這題如果觀察出這個性質之後會變水題，但我覺得觀察出這個性質很難ＱＱ。
先從scenario requests開始。如果 a 想要 b 玩具(如果b目前沒人要，就可以直接給a)，那就必須先滿足拿 b 玩具的人的慾望，他才會把b玩具丟掉。所以我們可以把到目前為止最後想要b玩具的人連一條邊到a。因為題目表示scenario request還不會有人哭，所以最後會變成一座有向森林。
再來是query，當 a 想要 b玩具，如果把這條邊連起來會產生環，顯然就會造成矛盾導致有人哭，而會哭的人就是那些祖先有 a 的人，也就是 a 的子樹大小。反之則不會有人哭。
因此我們只要DFS那座森林，記子樹大小和DFS的時間順序。判斷時看最後想要 b 的那個人是否在 a 的子樹內就好。

#include <iostream>
#include <vector>
#include <bitset>
#define N 100000
#define PB push_back
using namespace std;
int n,m,k,q,t;
int now[N+5],in[N+5],out[N+5],sz[N+5];
vector <int> v[N+5];
bitset <N+5> is;
int DFS(int x){
    in[x] = t++;
    sz[x] = 1;
    for(int i : v[x])sz[x] += DFS(i);
    out[x] = t++;
    return sz[x];
}
int main(){
    cin >> n >> m >> k >> q;
    while(k--){
        int a,b;cin >> a >> b;
        if(now[b])v[now[b]].PB(a),is[a] = 1;
        now[b] = a;
    }
    for(int i = 1 ; i <= n ; i++)
        if(!is[i])DFS(i);
    while(q--){
        int a,b;cin >> a >> b;
        if(in[a] < in[now[b]] && out[a] > out[now[b]])cout << sz[a] << endl;
        else puts("0");
    }
    return 0;
}

#E
這題我覺得很好玩～是NIM 遊戲的變形版。
如果單純只有葉子，那就是原始的NIM遊戲，只要每個葉子上的蘋果數xor起來的值 = 0 後手有必勝的解法。但還有另外一種移動方法是將此節點的一些蘋果移到它的子節點上。
先想一下如果目前每個葉子上的蘋果樹xor起來的值 = 0 ，而我們移動了一些蘋果給葉子，這時只要把移動的那些蘋果拿走就可以保持xor值 = 0。
那如果對方不是從葉子的上一層移給葉子，而是從上上層或是上上上上上上上層移下來呢？
題目有給一個條件就是，每一片葉子到根的距離的奇偶性相同。我們先將葉子設個編號0，葉子的上奇數層的節點編號為1，上偶數層的節點為0。
如果今天所有編號為0的節點的蘋果數xor起來 = 0，這樣如果對方從編號0的節點移蘋果到編號1，我們就可以把編號1的蘋果再往下一層移到編號0來保持xor值為0。
如果從編號1往下移到編號0則以此類推，如果被移到葉子就可以直接吃掉。
因此如果一開始的樹所有編號0的xor值 = 0，則後手的那個人已經必勝，同編號的可以和同編號的節點互換，以及雖然編號不一樣但值一樣的節點也可以互換。
那如果一開始xor值 != 0，則能使編號0的xor值  = 0的互換組合個數即為答案。

#include <iostream>
#include <vector>
#define N 100005
#define PB push_back
#define endl '\n'
using namespace std;
int apple[N],p[N],leaf,t[20000005],a;
vector<int> v[N],d[2];
void DFS(int l,int x){
    d[l].PB(apple[x]);
    if(!v[x].size())leaf = l;
    for(int i : v[x])DFS(1-l,i);
}
int main(){
    int n;cin >> n;
    for(int i = 1; i <= n ; i++)cin >> apple[i];
    for(int i = 2; i <= n ; i++)cin >> a,v[a].PB(i);
    DFS(0,1);
    long long tmp = 0,ans = 0;
    for(int i : d[leaf])tmp ^= i;
    for(int i : d[1-leaf])t[i]++;
    if(!tmp)ans = (d[leaf].size()*(d[leaf].size()-1)/2 + d[1-leaf].size()*(d[1-leaf].size()-1)/2);
    for(int i : d[leaf])ans += t[tmp^i];
    cout << ans << endl;
    return 0;
}

小總結：
pB比平常的pB難了一點。
覺得pD,pE的coding 長度不高但是挺有趣的題目。