NOIP2018普及组题解

比赛

A. 标题统计

用gets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int ans;
char s[10], ch;

int main() {
    gets(s);
    for (int i = 0; i < strlen(s); i++) {
        ch = s[i];
        if (ch >= 'A' && ch <= 'Z') ans++;
        else if (ch >= 'a' && ch <= 'z') ans++;
        else if (ch >= '0' && ch <= '9') ans++;
    }
    cout << ans << endl;
    return 0;
}

B. 龙虎斗

全开longlong！！全！！！开！！！

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, c[100005], m, p1, s1, s2, l, r;
ll ans, minn = 1e9, tmp;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    cin >> m >> p1 >> s1 >> s2;
    c[p1] += s1;
    for (ll i = 1; i < m; i++) l += c[i] * (m - i);
    for (ll i = m + 1; i <= n; i++) r += c[i] * (i - m);
    ll s = abs(l - r);
    minn = s, ans = m;
    if (l > r) {
        for (ll i = m + 1; i <= n; i++)
            if (abs(s - s2 * (i - m)) < minn) {
                minn = abs(s - s2 * (i - m)), ans = i;
            }
    } else {
        for (ll i = 1; i < m; i++)
            if (abs(s - s2 * (m - i)) <= minn) {
                minn = abs(s - s2 * (m - i)), ans = i;
            }
    }
    cout << ans << endl;
    return 0;
}

C. 摆渡车

第一次是70分——大概就是DP方程对叻但没有优化那种。

说实话这个DP真的有点晕啊！下标琢磨了半天，导致T4时间严重不够。【以后拿到题目先全部看一遍喔

记 f[i] 表示第 i 分钟刚好从一趟回来的最小等待时间，转移也可以表示成 $f[i] = \min_{i - 2m < j \leq i - m}\{f[j] + k\}$, 其中 k 是 j 在路上时等待的时间之和加上 j 回来后的等待时间之和。注意是完全背包！！所以从小往大枚举 i。还有最后答案不是 f[t[n]] 而是 f[t[n] + m - 1]!! 

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
#include <bits/stdc++.h>
using namespace std;

int n, m, t[505], f[4000005], T[4000005];
int pos = 1;

int calc(int l, int r) {
    int sum = 0;
    for (int i = l; i < r; i++) sum += (r - i) * T[i];
    return sum;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> t[i], T[t[i]]++;
    sort(t + 1, t + n + 1);
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    f[1] = 0;
    for (int i = 2; i <= t[n] + m; i++) {
        int l = max(0, i - 2 * m + 1), r = max(0, i - m);
        for (int j = l; j <= r; j++) {
            if (f[i] >= f[j] + calc(max(0, j - m + 2), max(0, i - m + 1))) {
                f[i] = f[j] + calc(max(j - m + 2, 0), max(0, i - m + 1));
            }
        }
    }
    cout << f[t[n] + m - 1] << endl;
    return 0;
}

100分明天补。

D. 对称二叉树

然而，，，暴力就好了！

为什么呢？

每一次 chk 操作，当二叉树为完全二叉树时，时间复杂度最大，为树高，即为 $log_2 n$；进行 n 次，时间复杂度为 $n log_2 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
struct point {
    int fa, l, r, w, num;
}p[N];
int n, x, y;

void upd(int x) {
    p[x].num = 1;
    if (p[x].l > 0) upd(p[x].l), p[x].num += p[p[x].l].num;
    if (p[x].r > 0) upd(p[x].r), p[x].num += p[p[x].r].num;
}

bool chk(int u, int v) {
    if (u < 0 && v < 0) return 1;
    if (u > 0 && v > 0 && p[u].w == p[v].w && chk(p[u].l, p[v].r) && chk(p[u].r, p[v].l))
        return 1;
    return 0;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i].w;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        p[i].l = x;
        if (x > 0) p[x].fa = i;
        p[i].r = y;
        if (y > 0) p[y].fa = i;
    }
    upd(1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (chk(p[i].l, p[i].r)) ans = max(ans, p[i].num);
    cout << ans << endl;
    return 0;
}