codeforeces722 Intel Code Challenge Elimination Round (Div.1 + Div.2, combined)

終于補完這場了。

C. Destroying Array

題意：

給一個數組a，長度為n，然後給一個1~n的排列p，依次毀滅 api ，問每次毀滅後數組的最大連續子段和（當然是不能包括毀滅的位置）。

思路：

倒過來看就是每次加一個元素問最大子段和，并查集可解。

//
//  main.cpp
//  722C
//
//  Created by 翅膀 on 16/10/1.
//  Copyright © 2016年 kg20006. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <set>
using namespace std;
typedef long long ll;
int n;
ll num[];
bool vis[];
int op[];
ll as[];
ll seed[];
ll find(ll x){
    return seed[x] <= ? x : seed[x] = find(seed[x]);
}
void join(int a, int b){
    a = find(a), b = find(b);
    if(a == b) return;
    seed[a] += seed[b], seed[b] = a;
}
int main(int argc, const char * argv[]) {
    scanf("%d", &n);
    for(int i = ; i <= n; ++i) scanf("%lld", num+i);
    for(int i = ; i <= n; ++i) scanf("%d", op+i);
    ll ans = ;
    for(int i = n; i >= ; --i) {
        as[i] = ans;
        int id = op[i];
        if(vis[id-] ==  && vis[id+] == ) seed[id] = -num[id];
        else{
            if(vis[id+]) join(id, id+);
            if(vis[id-]) join(id, id-);
            seed[find(id)] -= num[id];
        }
        vis[id] = ;
        ans = max(ans, -seed[find(id)]);
    }
    for(int i = ; i <= n; ++i) printf("%lld\n", as[i]);
    return ;
}
           

D.Generating Sets

題意：

給一個集合Y，求一個集合X，集合大小相同，要求二進制下X是Y中某個元素的字首，必須一一對應，并且X中最大的元素最小。

思路：

先二分最大值，然後貪心，每個元素的字首取不超過目前二分值的盡量大的，如果有重複的就不斷減少一位，看看是不是是以元素都能找到。

//
//  main.cpp
//  722D
//
//  Created by 翅膀 on 16/10/1.
//  Copyright © 2016年 kg20006. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <set>
using namespace std;
const int N = ;
typedef long long ll;
int a[N], n;
bool ok(ll up) {
    set<int>st;
    for(int i = ; i <= n; ++i) {
        int x = a[i];
        while(x > up) x >>= ;
        while(x && st.count(x)) x >>= ;
        if(x == ) return ;
        st.insert(x);
    }
    return ;
}
void print(ll up) {
    set<int>st;
    for(int i = ; i <= n; ++i) {
        int x = a[i];
        while(x > up) x >>= ;
        while(st.count(x)) x >>= ;
        st.insert(x);
        printf("%d ", x);
    }
}
int main(int argc, const char * argv[]) {
    scanf("%d", &n);
    for(int i = ; i <= n; ++i) {
        scanf("%d", a+i);
    }
    sort(a+, a+n+);
    ll l = , r = , ans;
    while(l <= r) {
        ll mid = (l+r) >> ;
        if(ok(mid)) r = mid-, ans = mid;
        else l = mid+;
    }
    print(ans);
    return ;
}
           

E. Research Rover

題意：

從(1,1)通過最短路徑走到(n,m)，能量值為s，其中有k個特殊點，每經過一個特殊點能力值就會變成(s+1)/2，問最後能力值的期望值。

思路：

容易發現s減小的速度是很快的，最多20次就會變成1，是以我們算出經過0，1，2…20個特殊點的方案數，剩下的方案能力值都是1了。

首先考慮經過0個特殊點的方案數，就是這個題，是個很經典的容斥了，首先按經過的順序排序，如果從點a可以走到點b，那a就在b前面，然後就可以算出從（1，1）走到點（x，y）且不經過其他點的方案數，推一下就可以算出從（1，1）走到點（n，m）不經過特殊點的方案數了。

可以發現這個題就是要算恰好經過k個點的方案數，按照上面的思路來就行。

//
//  main.cpp
//  722E
//
//  Created by 翅膀 on 16/10/10.
//  Copyright © 2016年 kg20006. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = +;
ll fac[N], invfac[N];
const ll mod = +;
ll qpow(ll a, ll k) {
    ll res = ;
    while(k) {
        if(k&) res = (res*a)%mod;
        a = (a*a)%mod;
        k >>= ;
    }
    return res;
}
void init(){
    fac[] = , invfac[] = ;
    fac[] = , invfac[] = ;
    for(ll x = ; x < N; ++x){
        fac[x] = (fac[x-]*x)%mod;
        invfac[x] = qpow(fac[x], mod-);
    }
}

ll C(int n, int m) {
    if(n <  || m <  || n < m) return ;
    else if(n == m) return ;
    else return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
pii p[];
inline bool cmp(const pii& a, const pii& b) {
    return a.first+a.second < b.first+b.second;
}
ll cal(pii a, pii b) {
    int x = b.first-a.first, y = b.second-a.second;
    return C(x+y, x);
}
ll dp[][];
int main(int argc, const char * argv[]) {
    init();
    int n, m, k, s;
    scanf("%d%d%d%d", &n, &m, &k, &s);
    for(int i = ; i <= k; ++i) {
        scanf("%d %d", &p[i].first, &p[i].second);
    }
    p[] = pii(, );
    p[++k] = pii(n, m);
    sort(p, p+k+, cmp);
    dp[][] = , dp[][] = cal(p[], p[]);
    for(int i = ; i <= k; ++i) {
        dp[i][] = cal(p[], p[i]);
        for(int j = ; j < i; ++j) {
            dp[i][] = (dp[i][]-dp[j][]*cal(p[j], p[i])%mod+mod)%mod;
        }
    }
    for(int i = ; i <= ; ++i) {
        for(int j = ; j <= k; ++j) {
            dp[j][i] = cal(p[], p[j]);
            for(int l = ; l < i; ++l) {
                dp[j][i] = (dp[j][i]-dp[j][l]+mod)%mod;
            }
            for(int l = ; l < j; ++l) {
                dp[j][i] = (dp[j][i]-dp[l][i]*cal(p[l], p[j])%mod+mod)%mod;
            }
        }
    }
    ll ans = , tot = cal(p[], p[k]);
    for(int i = ; i <= ; ++i, s = (s+)/) {
        ans = (ans+dp[k][i]*s%mod)%mod;
        tot = (tot-dp[k][i]+mod)%mod;
    }
    ans = (ans+tot)%mod;
    ans = ans*qpow(cal(p[], p[k]), mod-)%mod;
    printf("%lld\n", ans);
    return ;
}
           

F. Cyclic Cipher

題意：

給n個序列，一個序列内沒有重複元素，不同序列内可能有重複元素，每個序列長度<=40，每秒鐘每個序列會循環左移一次，要求算出 10100 秒内，[1,m]的答案。

一個數x在某時刻的答案為，把此時所有序列的第一個元素順序排成一個新序列，這個新序列中最長的連續x的長度。

思路：考慮對m個答案分開求，設目前要求解的數為x，那麼我們隻用關心所有x的位置，可能的答案一定是連續出現x的序列，假設i，j是答案中的兩個序列，長度為li，lj，對應x的位置為pi，pj，顯然要讓pi和pj同時出現在第一個元素，則有 pi+li∗k==pj+lj∗k ，然後有 pi−pj==lj∗k−li∗k ，兩邊同時對gcd(li,lj)取模，則有 (pi−pj)=0(modgcd(li,lj)) ，然後可以得到一個結論，兩個長度相同的序列，其pi和pj一定相同。因為序列長度<=40，是以長度相同的序列肯定是很多的，一個序列出現的數是很少的，我們就可以考慮two pointer了，過程中要保證這一段出現的x是連續的。

//
//  main.cpp
//  722F
//
//  Created by 翅膀 on 16/10/9.
//  Copyright © 2016年 kg20006. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = +;
int n, m;
struct node{
    int r, len, c;
    node(int _a = , int _b = , int _c = ) {
        r = _a, len = _b, c = _c;
    }
};
vector<node>l[N];
int pos[];
int cnt[];
int gcd[][];
int _gcd(int a, int b){ return b? _gcd(b, a%b) : a; }
// (xi+a*li) == (xj+b*lj)
// xi-xj == b*lj-a*li
// (xi-xj)%gcd(lj,li) == 0
bool add(node a) {
    if(cnt[a.len] && pos[a.len] != a.c) return ;
    for(int i = ; i <= ; ++i) {
        if(cnt[i] && (pos[i]-a.c)%gcd[i][a.len] != ) return ;
    }
    pos[a.len] = a.c;
    cnt[a.len]++;
    return ;
}
void del(node a) {
    cnt[a.len]--;
}
int solve(vector<node>& x) {
    int res = ;
    memset(pos, , sizeof(pos));
    memset(cnt, , sizeof(cnt));
    int l = , r = ;
    while(l < x.size()) {
        while(r < x.size()) {
            if(x[r].r-x[l].r != r-l) break;
            if(!add(x[r])) break;
            ++r;
        }
        res = max(res, r-l);
        if(x[r].r - x[l].r != r-l) {
            l = r;
            memset(pos, , sizeof(pos));
            memset(cnt, , sizeof(cnt));
        }
        else del(x[l++]);
    }
    return res;
}
int main(int argc, const char * argv[]) {
    for(int i = ; i < ; ++i) {
        for(int j = ; j < ; ++j) {
            gcd[i][j] = _gcd(i, j);
        }
    }
    scanf("%d%d", &n, &m);
    for(int i = ; i <= n; ++i) {
        int k;
        scanf("%d", &k);
        for(int x, j = ; j <= k; ++j) {
            scanf("%d", &x);
            l[x].emplace_back(node(i, k, j));
        }
    }
    for(int i = ; i <= m; ++i) {
        printf("%d\n", solve(l[i]));
    }
    return ;
}