BestCoder Round #32

BestCoder Round #32

B題用set+讀入掛是可以卡時間過的，不過還是用HASH效率會比較高

代碼：

A：

#include 
#include 
#include 
using namespace std;

struct C {
    int a, b, id;
    void read() {
        scanf(%d%d, &a, &b);
    }
} city[105];

int n;

bool cmp(C a, C b) {
    int d1 = a.a - a.b;
    int d2 = b.a - b.b;
    if (d1 == d2) {
        if (a.b == b.b) return a.id < b.id;
        return a.b < b.b;
    } else return d1 > d2;
}

int main() {
    while (~scanf(%d, &n)) {
        for (int i = 0; i < n; i++) {
            city[i].read();
            city[i].id = i;
        }
        sort(city, city + n, cmp);
        for (int i = 0; i < n - 1; i++)
            printf(%d , city[i].id);
        printf(%d
, city[n - 1].id);
    }
    return 0;
}

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;

const int N = 1000010;

int t, n;

int a[N];
ll sum, k;

int head[N], nt[N], hn;
ll state[N];

void init() {
    hn = 0;
    memset(head, -1, sizeof(head));
}

inline int gethash(ll x) {
    return (x % 1000007 + 1000007) % 1000007;
}

void tryinsert(ll x) {
    int h = (x % 1000007 + 1000007) % 1000007;
    for (int i = head[h]; i + 1; i = nt[i]) {
        if (x == state[i]) return;
    }
    state[hn] = x;
    nt[hn] = head[h];
    head[h] = hn++;
}

bool get(ll x) {
    int h = (x % 1000007 + 1000007) % 1000007;
    for (int i = head[h]; i + 1; i = nt[i])
        if (x == state[i]) return true;
    return false;
}

bool solve() {
    init();
    sum = 0;
    tryinsert(0);
    for (int i = n, bo = 1; i >= 1; i--, bo^=1) {
        if (bo) sum += a[i]; else sum -= a[i];
        if (bo) {
            if (get(sum - k)) return true;
        } else {
            if (get(sum + k)) return true;
        }
        tryinsert(sum);
    }
    return false;
}

int main() {
    int cas = 0;
    scanf(%d, &t);
    while (t--) {
        scanf(%d%I64d, &n, &k);
        for (int i = 1; i <= n; i++)
            scanf(%d, &a[i]);
        printf(Case #%d: %s.
, ++cas, solve() ? Yes : No);
    }
    return 0;
}

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
const int N = 1002000;
const int MOD = 1000000007;

int n;
char s[N * 2];
ll f[N];

ll pow_mod(ll x, int k) {
    ll ans = 1;
    while (k) {
        if (k&1) ans = ans * x % MOD;
        x = x * x % MOD;
        k>>=1;
    }
    return ans;
}

ll invf(ll x) {
    return pow_mod(x, MOD - 2);
}

ll C(int m, int n) {
    if (m > n || m < 0 || n < 0) return 0;
    return f[n] * invf(f[m]) % MOD * invf(f[n - m]) % MOD;
}

int main() {
    f[0] = 1;
    for (int i = 1; i < N; i++)
        f[i] = f[i - 1] * i % MOD;
    while (~scanf(%d, &n)) {
        scanf(%s, s);
        if (n % 2) printf(0
);
        else {
            int len = strlen(s);
            int lt = 0, rt = 0;
            for (int i = 0; i < len; i++) {
                if (s[i] == '(') lt++;
                else if (s[i] == ')') rt++;
                if (rt > lt) break;
            }
            if (rt > lt) {
                printf(0
);
            } else {
                int p = n / 2 - rt;
                int q = n / 2 - lt;
                ll ans = ((C(q, p + q) - C(q - 1, p + q)) % MOD + MOD) % MOD;
                printf(%I64d
, ans);
            }
        }
    }
    return 0;
}

#include 
#include 
#include 
using namespace std;

typedef long long ll;

int t, n, m;
int dp[350][50005];

int main() {
    int cas = 0;
    scanf(%d, &t);
    while (t--) {
        scanf(%d%d, &n, &m);
        dp[0][0] = 1;
        int ans = 0;www.Bkjia.com
        int Max = (sqrt(8 * n + 1) - 1) / 2;
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i <= min(j, Max); i++) {
                dp[i][j] = dp[i][j - i];
                if (i) dp[i][j] = (dp[i][j] + dp[i - 1][j - i]) % m;
            }
        }
        for (int i = 0; i <= Max; i++)
            ans = (ans + dp[i][n]) % m;
        printf(Case #%d: %d
, ++cas, ans);
    }
    return 0;
}