校内NOIP模拟赛题解

考点:

T1:贪心

T2:数论——组合数学、杨辉三角

T3:数据结构——分块

T1:榴莲罐头

榴莲罐头

贪心,每次都维护某个点之前的最小值就可以。

复杂度: O(n)

#include <cstdio>
#define MOD 100000007
int min(int a, int b) {return a < b ? a : b;}
int main() {
    int n, k, before_min = 214748364; scanf("%d %d", &n, &k);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int w, x; scanf("%d %d", &w, &x);
        before_min = min(before_min + k, w);
        ans = (ans + 1ll * x * before_min) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

T2:榴莲迷宫

榴莲迷宫

D(x,y)=D(x-1,y)+D(x,y-1) ,很容易想到这是一个杨辉三角

1 1 1 1 1 1 
1 2 3 4 5 6 
1 3 6 10 15 21 
1 4 10 20 35 56 
1 5 15 35 70 126 
1 6 21 56 126 252

~~根据打表可以得到,~~每次都走这条路是最优的。

1
1
1
1
1
1 6 21 56 126 252

然后可以得到一个由组合数来的表格:

C_0^0\\ C_1^0\ C_2^1\\ C_2^0\ C_3^1\ C_4^2\\ C_3^0\ C_4^1\ C_5^2\ C_6^3\\ C_4^0\ C_5^1\ C_6^2\ C_7^3\ C_8^4\\ C_5^0\ C_6^1\ C_7^2\ C_8^3\ C_9^4\ C_{10}^5

因此这条路径也就可以表示为:

n+\sum_{i=0}^mC_{n+i}^i

继续化简 \sum_{i=0}^mC_{n+i}^i ,也就是 C_n^0+C_{n+1}^1+C_{n+2}^2+...+C_{n+m}^m

由上面的表格可以得到,

C_n^0+C_{n+1}^1=C_{n+2}^1 C_{n+2}^1 C_{n+2}^2 合并就是 C_{n+3}^2 ......最后合并为 C_{n+m+1}^m

因此, \sum_{i=0}^mC_{n+i}^i=n+C_{n+m+1}^m

最后算一下 n+C_{n+m+1}^m 就可以啦。

#include <cstdio>
#include <iostream>
#define MOD 1000000007
long long qpow(long long a, long long b) {
    long long ans = 1;
    while (b > 0) {
        if (b % 2) ans = (ans * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ans % MOD;
}
long long inv(long long k) {
    return qpow(k, MOD - 2);
}
int main() {
    long long n, m; scanf("%lld %lld", &n, &m);
    if (n < m) std::swap(n, m);
    long long di = 1, cnt = 1;
    for (int i = 1; i <= n + m + 1; i++) {
        cnt = (cnt * i) % MOD;
        if (i == m) di = (di * cnt) % MOD;
        if (i == n + 1) di = (di * cnt) % MOD;
    }
    long long ans = (n + (cnt * inv(di))) % MOD;
    printf("%lld\n", ans);
    return 0;
}

T3:榴莲弹射

榴莲弹射

把整个序列分成 \sqrt{n} 块,对于每一个弹射器,都记录一下所属块(belong)、离开这个块需要多少步(cnt)、弹射出 i 所在块后第一个到达的位置(next) 。

在查询时,我们 O(\sqrt{n}) 的时间进行弹射的模拟,可以得到结果。

在修改 i 时,我们只需修改 i 所在的块,设该块区间为 [L,R] ,我们只需从修改 i L 的每个点的 cntnext 即可。

总复杂度: O(n\sqrt{n})

#include <cmath>
#include <cstdio>
#define MAXN 400001
struct nodee{
    int cnt, next, num, belong; //每个点都维护 cnt 与 next 表示有多少步跳出这个块,跳出这个块之后的下一个位置
} node[MAXN];
struct ku{
    int l, r, cnt;
}kuai[MAXN]; //存储每个块的信息
int kuai_cnt = 1, n;
int find_next(int k, int pos) {
    if (k > n) return -1;
    if (node[k].belong != pos) return k;
    node[k].next = find_next(k + node[k].num, pos);
    node[k].cnt = node[k + node[k].num].cnt + 1;
    return node[k].next;
}
 inline int cal(int x) {
 	int tmp=0;
     while(1) {
 		tmp += node[x].cnt;
 		if(!node[x].next)break;
 		x = node[x].next;
 	}
 	return tmp;
 }
int main() {
    scanf("%d", &n);
    int size_kuai = sqrt(n);
    kuai[1].l = 1;
    for (int i = 1; i <= n; i++) { //利用分块的思想,把整个分成 sqrt(n) 个块
        scanf("%d", &node[i].num);
        if (kuai[kuai_cnt].cnt >= size_kuai) {
            kuai[kuai_cnt].r = i - 1;
            kuai_cnt++; kuai[kuai_cnt].l = i;
        }
        kuai[kuai_cnt].cnt++;
        node[i].belong = kuai_cnt;
    }
    kuai[kuai_cnt].r = n;
    for (int i = 1; i <= n; i++) {
        if (node[i].next == 0) {
            node[i].next = find_next(i, node[i].belong);
            node[i].cnt = node[i + node[i].num].cnt + 1;
        }
    }
    int q; scanf("%d", &q);
    while (q--) {
        int opt; scanf("%d", &opt);
        if (opt == 1) {
            int k, ans = 0; scanf("%d", &k);
            k++;
            for (; k <= n && k != -1; k = node[k].next) {
                ans += node[k].cnt;
            }
            printf("%d\n", ans);
        } else {
            int k, p; scanf("%d %d", &k, &p);
            k++; node[k].num = p;
            for (int i = k; i >= kuai[node[k].belong].l; i--) {
                if (node[i].belong == node[i + node[i].num].belong) node[i].cnt = node[i + node[i].num].cnt + 1, node[i].next = node[i + node[i].num].next;
                else node[i].cnt = 1, node[i].next = i + node[i].num;
            }
        }
    }
    return 0;
}