校内NOIP模拟赛题解
考点:
T1:贪心
T2:数论——组合数学、杨辉三角
T3:数据结构——分块
T1:榴莲罐头
榴莲罐头
贪心,每次都维护某个点之前的最小值就可以。
复杂度:
#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:榴莲迷宫
榴莲迷宫
由 ,很容易想到这是一个杨辉三角
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
然后可以得到一个由组合数来的表格:
因此这条路径也就可以表示为:
继续化简 ,也就是
由上面的表格可以得到,
, 与 合并就是 ......最后合并为
因此, 。
最后算一下 就可以啦。
#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:榴莲弹射
榴莲弹射
把整个序列分成 块,对于每一个弹射器,都记录一下所属块(belong
)、离开这个块需要多少步(cnt
)、弹射出 所在块后第一个到达的位置(next
) 。
在查询时,我们 的时间进行弹射的模拟,可以得到结果。
在修改 时,我们只需修改 所在的块,设该块区间为 ,我们只需从修改 到 的每个点的 cnt
和 next
即可。
总复杂度:。
#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;
}