Astar(百度之星程序设计竞赛, 简称坑爹之星)2016还没有结束, 但是并没有onsite的机会。 不过好在拿了一件T-shirt(前500), 觉得这次比赛还是有很多地方需要总结的, 包括题目 & 一些人生经验 :-)

回顾一下题目:

资格赛: (题目链接 :http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=690) 资格赛是任意AC一道进入下一轮, 结果AC了四道

1001 差分之后除法取模, 考察逆模。 扩展欧几里得求出逆模, 除法取模变成乘法取模, 注意取逆模的时候可能得到一个负的值x, (x+mod)%mod处理一下

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100010;
const int MOD = 9973;

int mod[N];
string s;

void extend_gcd(int a, int b, int &x, int &y, int &d) {
    if(!b) {
        d = a;
        x = 1; y = 0;
    }
    else {
        extend_gcd(b, a%b, y, x, d);
        y -= x*(a/b);
    }
}

int main() {
    int n, l, r;
    while(~scanf("%d", &n)) {
        cin >> s;

        mod[0] = 1;
        for(int i = 0; i < s.length(); ++i) {
            mod[i+1] = mod[i] * (s[i] - 28) % MOD;
        }

        for(int i = 0; i < n; ++i) {
            scanf("%d %d", &l, &r);
            if(l == 1) {
                printf("%d\n", mod[r]);
            }
            else {
                int x, y, d;
                extend_gcd(mod[l-1], MOD, x, y, d);
                x = x * (mod[r])/d;
                if(x < 0) {
                    x += (-x / MOD + 1) * MOD;
                }
                x %= MOD;
                printf("%d\n", x);
            }
        }
    }
    return 0;
}

1002 简单递推题, 本质上就是求Fibnacci数列, 但是需要高精度加法

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
const int N = 201;

int dp[N][N];

void solve() {
    memset(dp, 0, sizeof(dp));
    dp[1][0] = 1, dp[2][0] = 2;
    for(int i = 3; i < N; ++i) {
        int d = 0;
        for(int j = 0; j < N-1; ++j) {
            int res = dp[i-1][j] + dp[i-2][j] + d;
            dp[i][j] = res % 10;
            d = res / 10;
        }
    }
}

int main() {
    int n;
    solve();

    while(~scanf("%d", &n)) {
        int idx = N - 1;
        for(; dp[n][idx] == 0; --idx) ;
        for(int i = idx; i >= 0; --i) {
            printf("%d", dp[n][i]);
        }
        puts("");
    }
    return 0;
}

1003 字典树, 稍微有点trick, 交了好几发。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;

struct trie {
    int val;
    trie *next[26];
    trie() {
        val = 0;
        for(int i = 0; i < 26; ++i) {
            next[i] = NULL;
        }
    }
};
trie *root;

void insert(trie *root, char *word) {
    int idx = 0;
    trie *p = root;

    while(word[idx]) {
        int v = word[idx] - 'a';
        if(p->next[v] == NULL) {
            trie *q = new trie;
            p->next[v] = q;
        }
        p = p->next[v], ++idx;
        p->val++;
    }
}

bool query(trie *root, char *word) {
    trie *p = root;
    int idx = 0;
    while(word[idx]) {
        int v = word[idx] - 'a';
        if(p->next[v] == NULL || p->next[v]->val < 1) {
            return false;
        }
        p = p->next[v], ++idx;
    }
    return true;
}

void delete_(trie *root, char *prefix) {
    trie *p = root;
    int idx = 0;
    while(*(prefix+idx)) {
        int v = *(prefix+idx) - 'a';
        if(p->next[v] == NULL || p->next[v]->val < 1) {
            return ;
        }
        p = p->next[v], ++idx;
    }

    int cnt = p->val;
    p = root, idx = 0;
    while(*(prefix + idx)) {
        int v = *(prefix + idx) - 'a';
        p->next[v]->val -= cnt;
        p = p->next[v], ++idx;
    }
    for(int i = 0; i < 26; ++i) {
        p->next[i] = NULL;
    }
}

int main() {
    int n;
    char op[10], word[41];
    scanf("%d", &n);

    root = new trie;
    for(int i = 0; i < n; ++i) {
        scanf("%s %s", op, word);
        switch(op[0]) {
            case 'i':
                insert(root, word);
                break;
            case 's':
                if(query(root, word)) {
                    cout << "Yes" << endl;
                }
                else {
                    cout << "No" << endl;
                }
                break;
            case 'd':
                delete_(root, word);
                break;
            default:
                break;
        }
    }
    return 0;
}

1004 $\Gamma(n) = (n-1)!\quad\forall n\in\mathbb N$

相似文章


最近发表的文章

全部文章

评论区

comments powered by Disqus 回到顶部