题目链接：戳我（1053－1059）

Pinocchio

题目还比较好理解，每次选两个数，大数减去小数，相等则合并，其实就是求出所有数的最大公约数，然后就是直接做了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

int main() {
    int n, ans, k;
    cin >> n >> ans;
    n--;
    while (n--) {
        cin >> k;
        ans = gcd(ans, k);
    }
    cout << ans << endl;
    return 0;
}

Hanoi Tower

汉诺塔是很经典的一个东西了，但这道题还是比较有意思的。给出当前各个圆盘所在的柱子的一个序列，问你当前状态是最优移动方案里面的第几步，有可能所给状态不是最优方案里的状态，N<=31。如果对汉诺塔得递归性质理解得比较深的话应该很容易就能做出来，我是先打了一个表看看规律的。。。我们可以只考虑最大的圆盘k，如果还没有被移动过就无视，不然ans就加上2ˆ(k-1)，然后逆着递归回去，然后明显就是O(N)了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstring>

using namespace std;

int f[100] = {0}, n, ans = 0;

void sol(int k, int a, int b, int c) {
    if (k == 0) return;
    if (f[k] == c) {
        ans = -1;
        return;
    } else if (f[k] == b) {
        ans += 1 << (k-1);
        sol(k-1, c, b, a);
    } else sol(k-1, a, c, b);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> f[i];
    sol(n, 1, 2, 3);
    cout << ans << endl;
    return 0;
}

Combinations

很裸的数学题了，组合数的计算，对分式上下各个数进行质因数分解，最后统计一下，不过我好像写得比较矬，应该写得更简洁些才是啊。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>

using namespace std;

const int MN = 50010;

bool valid[MN];
int ans[MN] = {0};
int f[MN] = {0};

void getPrime(int n) {
    int tot = 0;
    memset(valid, true, sizeof(valid));
    for (int i = 2; i <= n; i++) {
        if (valid[i]) ans[++tot] = i;
        for (int j = 1; ((j <= tot) && (i*ans[j] <= n)); j++) {
            valid[i*ans[j]] = false;
            if (i % ans[j] == 0) break;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    if (m > (n/2)) m = n-m;
    getPrime(n);
    for (int i = 0; i < m; i++) {
        int t = n-i;
        if (valid[t]) {
            f[t]++;
        } else {
            int j = 0;
            while (t != 1) {
                j++;
                while (t % ans[j] == 0) {
                    f[ans[j]]++;
                    t /= ans[j];
                }
            }
        }
    }
    for (int i = 2; i <= m; i++) {
        if (valid[i]) {
            f[i]--;
        } else {
            int j = 0, t = i;
            while (t != 1) {
                j++;
                while (t % ans[j] == 0) {
                    f[ans[j]]--;
                    t /= ans[j];
                }
            }
        }
    }
    int ans = 0;
    for (int i = 2; i <= n; i++)
        if (f[i]) ans++;
    cout << ans << endl;
    return 0;
}

Computer Net

N(<=10000)点构成一颗树，要求出树的中心。由树的性质可以知道，中心必定是1 or 2个。求树的中心还有树的直径都是很经典的问题，这道题也有很多做法。我用的是两边DFS，任意选则一个点v做一遍DFS，则离v最远的那个点必定是树的直径的一个端点，然后再由得到的端点做一遍DFS，就找到了另一个端点了，记录路径，然后再找到直径的中点就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

const int MN = 10010;

vector <int> a[MN];
bool vt[MN];
int f[MN];

int n, k, l, v;

void dfs(int x, int pr, int de) {
    vt[x] = true;
    f[x] = pr;
    if (de > l) {
        l = de;
        v = x;
    }
    for (int i = 0; i < a[x].size(); i++) {
        int ch = a[x][i];
        if (vt[ch]) continue;
        dfs(ch, x, de+1);
    }
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> k;
        a[k].push_back(i);
        a[i].push_back(k);
    }
    v = l = 0;
    memset(vt, false, sizeof(vt));
    dfs(1, 0, 1);
    memset(vt, false, sizeof(vt));
    l = 0;
    dfs(v, 0, 1);
    for (int i = 1; i < l/2; i++)
        v = f[v];
    if (l % 2)
        cout << f[v] << endl;
    else
        cout << min(v, f[v]) << " " << max(v, f[v]) << endl;
    return 0;
}

Amount of Degrees

数位统计

题目大意：给出区间［X,Y］,要求算出区间内可以表示为k个不相同的b的幂的和的数字的个数。具体参见：刘聪《浅谈数位类问题》，讲的肯定比我自己说的要好TAT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;

int x, y, k, b;

int c[32][32] = {0};
int dgt[32] = {0};

void init() {
    c[0][0] = 1;
    for (int i = 1; i < 32; i++) {
        c[i][0] = c[i-1][0];
        for (int j = 1; j <= i; j++)
            c[i][j] += c[i-1][j-1] + c[i-1][j];
    }
}

int cal(int x) {
    int l = 0, ans = 0;
    while (x) {
        dgt[++l] = x % b;
        x /= b;
    }
    int mk = 0;
    for (int i = l; i > 0; i--) {
        if (dgt[i] > 1) {
            ans += c[i][k-mk];
            break;
        } else if (dgt[i] == 1) {
            if (i > k-mk) ans += c[i-1][k-mk];
            if (++mk > k) break;
        }
        if ((i == 1) && (mk == k)) ans++;
    }
    return ans;
}

int main() {
    cin >> x >> y >> k >> b;
    init();
    cout << cal(y) - cal(x-1) << endl;
    return 0;
}

Chocolate

比较那个的计算几何，我还不会写计算几何的题目，先留个坑，以后再填

//占位-_-#

Expression

题目大意：输出一个一元N次多项式的最短后缀表达式。然后有

f(x)=a_0x^n+a_{1}x^{n-1}+a_{2}x^{n-2}+......+a_{n-2}x^2+a_{n-1}x+a_n 可以化成

f(x)=(((a_nx+a_{n-1})x+a_{n-2})x+......+a_1)x+a_0

然后规律就很明显了，直接输出就行了。

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    cout << 0 << endl;
    for (int i = 0; i < n; i++) {
        cout << 'X' << endl << '*' << endl << i+1 << endl << '+' << endl;
    }
}