题目链接:http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=690

Problem A

题意

给一个数列,多次求数列子区间的区间积

解法

维护一个线段树,我用的是zkw线段树,做乘法的时候注意取模

另外一种解法是乘法逆元,似乎会更快一些,可是我数学太渣不会

注意:这道题非常坑,百“毒”的数据是有问题的。数据存在 $a, b > length(string)$ 的情况,这个时候输出上一次的答案就对了……

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

#define N 131072
#define MOD 9973

using namespace std;

long long ans, a[2 * N];
int n, len, s, t;
char str[N];

int main() {
    while (~ scanf("%d", &n)) {
        scanf("%s", str);
        len = strlen(str);

        memset(a, 0, sizeof(a));
        for (int i = 0; i < len; i++)
            a[i + N + 1] = str[i] - 28;

        for (int i = N - 1; i; i--)
            a[i] = a[2 * i] * a[2 * i + 1] % MOD;

        while (n--) {
            scanf("%d%d", &s, &t);
            if (s > len || t > len) {
                printf("%I64d\n", ans);
                continue ; //deal with wrong data
            }
            if (s > t) swap(s, t);
            s += N - 1; t += N + 1;
            for (ans = 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
                if (~ s & 1) ans *= a[s ^ 1];
                ans %= MOD;
                if (t & 1) ans *= a[t ^ 1];
                ans %= MOD;
            }
            printf("%I64d\n", ans);
        }
    }
    return 0;
}

Problem B

题意

$n$ 个 $1$ 组成的字符串,可以任意合并相邻的两个 $1$ 成为 $2$ ,问有多少种不同的字符串组合

例如串 $111$ 就可以变成 $12$ 和 $21$ ,加上自己,一共三种组合

再例如串 $11111$ 可以变成 $1112, 1121, 1211, 2111, 122, 212, 221$ ,加上自己,一共八种组合

解法

对于 $n=5$ ,很容易发现要计算的是 $C_5^0 + C_4^1 + C_3^2 = 1 + 4 + 3 = 8$

所以实际上 $Answer_n = C_n^0 + C_{n - 1}^1 + \cdots + C_{(n + 1) / 2}^{n / 2}$

其实最后的递推式就是 $A_1 = 1, A_2 = 2, A_n = A_{n - 1} + A_{n - 2} (n > 2)$ (就是斐波那契数列啊)

考虑到要用高精度并且完全可以打表,所以就打表呀~

代码

#!/usr/bin/env python
# encoding: utf-8

a, b = 2, 3
print '\tif (n <= 3)\n\t\tprintf("%d", n);' 
for i in range(4, 201):
    a, b = b, a + b
    print '\telse if (n == %d)\n\t\tprintf("%d");' % (i, b)

# 剩下的不用多说了吧

Problem C

题意

维护一个 可插入单词查询某前缀的单词是否存在删除某前缀的所有单词 的字典

解法

似乎就是个字母树啊,只是一般的字母树并不需要删除单词

删除某前缀时,把前缀路径上最后一个点的子树清空,然后从路径尾部开始遍历

若该点没有其他子树就清空,直到有其他子树停止遍历

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

struct TrieNode {
    struct TrieNode *children[26];
    bool isLeaf;

    TrieNode() {
        isLeaf = false;
        memset(children, 0, sizeof(children));
    }

    bool no_child() {
        for (int i = 0; i < 26; i++)
            if (children[i])
                return false;
        return true;
    }

    void insert(const char *s) {
        TrieNode *p = this;
        int len = strlen(s);
        for (int i = 0; i < len; i++) {
            if (!p->children[s[i] - 'a'])
                p->children[s[i] - 'a'] = new TrieNode();
            p = p->children[s[i] - 'a'];
        }
        p->isLeaf = true;
    }

    bool find(const char *s) {
        TrieNode *p = this;
        int len = strlen(s);
        for (int i = 0; i < len; i++)
            if (!p->children[s[i] - 'a'])
                return false;
            else p = p->children[s[i] - 'a'];
        return true;
    }

    void del_pre(const char *s);
} root, *link[40];

void TrieNode::del_pre(const char *s) {
    TrieNode *p = this;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        link[i] = p;
        if (!p->children[s[i] - 'a'])
            return ;
        else p = p->children[s[i] - 'a'];
    }
    link[len - 1]->children[s[len - 1] - 'a'] = 0;
    for (int i = len - 1; i; i--)
        if (link[i]->no_child())
            link[i - 1]->children[s[i - 1] - 'a'] = 0;
        else break ;
}

char cmd[10], s[40];
int n;

int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%s%s", cmd, s);
        if (cmd[0] == 'i')
            root.insert(s);
        else if (cmd[0] == 'd')
            root.del_pre(s);
        else
            printf(root.find(s) ? "Yes\n" : "No\n");
    }
    return 0;
}

Problem D

题意

顺次给你 $n$ 个字符串,问该字符串的任意排列在之前出现过多少次

解法

似乎是所有题目里面最简单的吧,排个序扔 map 里就好了

代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

map<string, int>::iterator it;
map<string, int> m;
string s;
int n;

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    while (n--) {
        cin >> s;
        sort(s.begin(), s.end());
        it = m.find(s);
        if (it == m.end()) {
            cout << 0 << endl;
            m[s] = 1;
        } else {
            cout << (it->second) << endl;
            it->second ++;
        }
    }
    return 0;
}

Problem E

题意

依次给一些条件,问这些条件与前面哪些条件有交集

解法

似乎就是暴力,然而读入的难度比暴力本身大

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>

#define MAX 20000
#define MIN -20000

using namespace std;

map < string, pair<int, int> >::iterator it, io;
map < string, pair<int, int> > m[1100];
string ans[1100];

inline bool digital(char x) {
    return ('0' <= x && x <= '9') || x == '-';
}

inline string getvar() {
    string res = "";
    char t = getchar();
    while (t < 'a' || t > 'z')
        t = getchar();
    do {
        res += t;
        t = getchar();
    } while ('a' <= t && t <= 'z');
    ungetc(t, stdin);
    return res;
}

inline int getopt() {
    char t = getchar();
    while (t != '=' && t != '<' && t != '>')
        t = getchar();
    char x = getchar();
    if (t == '=')
        return 0;
    if (x != '=') {
        ungetc(x, stdin);
        return t == '>' ? 1 : -1;
    }
    return t == '>' ? 2 : -2;
}

inline int getint() {
    int res = 0, mul = 1;
    char t = getchar();
    while (!digital(t))
        t = getchar();
    if (t == '-') {
        mul = -1;
        t = getchar();
    }
    do {
        res *= 10;
        res += t - '0';
        t = getchar();
    } while (digital(t));
    ungetc(t, stdin);
    return mul * res;
}

inline bool getdot() {
    char t = getchar();
    while (t != ',' && t != '\r' && t != '\n' && t != EOF)
        t = getchar();
    return t == ',';
}

int main() {
    int n = getint(), opt, val;
    string var;
    char tmp[10];
    int L, R;
    for (int i = 1; i <= n; i++) {
        ans[i] = "";
        do {
            var = getvar();
            opt = getopt();
            val = getint();
            if (ans[i] == "no")
                continue ;
            it = m[i].find(var);
            if (opt == 0) L = R = val;
            if (opt == 1) L = val + 1, R = MAX;
            if (opt == 2) L = val, R = MAX;
            if (opt == -1) R = val - 1, L = MIN;
            if (opt == -2) R = val, L = MIN;
            if (it != m[i].end()) {
                if (
                    R < it->second.first ||
                    L > it->second.second
                )
                    ans[i] = "no";
                else {
                    it->second.second = min(R, it->second.second);
                    it->second.first = max(L, it->second.first);
//                    cout << "Update pair " << var << " " << it->second.first << " " << it->second.second << endl;
                }
            } else {
                m[i][var] = make_pair(L, R);
//                cout << "Insert pair " << var << " " << L << " " << R << endl;
            }
        } while (getdot());

        if (ans[i] == "no")
            continue ;

        for (int j = 1; j < i; j++) {
            if (ans[j] == "no")
                continue ;
            bool uni = false;
            for (it = m[i].begin(); it != m[i].end(); it++) {
                io = m[j].find(it->first);
                if (io != m[j].end())
                    if (
                        it->second.first > io->second.second ||
                        it->second.second < io->second.first
                    ) {
                        uni = true;
                        break ;
                    }
            }
            if (!uni) {
                sprintf(tmp, "%d", j);
                ans[i] += tmp;
                ans[i] += " ";
            }
        }
    }

    ios::sync_with_stdio(0);
    for (int i = 1; i <= n; i++)
        if (ans[i] == "" || ans[i] == "no")
            cout << "unique" << endl;
        else {
            ans[i].erase(ans[i].length() - 1);
            cout << ans[i] << endl;
        }

    return 0;
}
文章目录