不忘初心
时刻前行

和 wyc 一起打的 = =

150 pts,A 10 pts,B 40 pts,C 100 pts,rk 9

题目 pdf

A 补票

一条铁路,从第 i 个站台到 i + 1 个站台的权值为 a[i]m 次询问,每次给出 x, y, p, q,代表你有从 pq 的车票,求至少还要购买多少元的车票使得你能从 pq

前缀和


脑筋急转弯题

前缀和维护,一定要判断如果两条线段不相交的情况

时间复杂度 O(n + m)

#include <bits/stdc++.h>
#define DEBUG(x) cerr << #x << " = " << x << '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 10;
int n, m, a[maxn];
ll sum[maxn];
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i - 1];
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) { int x, y, p, q; // p, q 持有,x, y 目标
        scanf("%d %d %d %d", &x, &y, &p, &q);
        int ans1 = sum[y] - sum[x], ans2 = 0;
        if (p > x) ans2 += sum[p] - sum[x];
        if (y > q) ans2 += sum[y] - sum[q];
        printf("%d\n", min(ans2, ans1));
    }
    return 0;
}

B 换铺

从一个节点 i 走到 j (j > i) 的花费为 a(j - i) * (j - i) ^ 3,求 1n 的最小花费路径,要求走过不超过 p 条边

线性 DP


抽象成一张图后,DP 即可,每次枚举终点,枚举走到该点的步数,枚举从哪个点走来(由于规定了只能从 j < i 走来所以维护非常方便)

时间复杂度 O(n^2p),数据随机,所以可过

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
int n, p;
ll f[maxn][maxn], a[maxn], ans = 0x7fffffff;
int main() {
    scanf("%d %d", &n, &p);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] *= i * i * i;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) {
        f[i][1] = a[i - 1];`
        for (int j = 2; j <= min(p, i - 1); ++j) {
            for (int k = i - 1; k >= j; --k) {
                f[i][j] = min(f[i][j], f[k][j - 1] + a[i - k]);
            }
        }
    }
    for (int i = 1; i <= p; ++i) ans = min(ans, f[n][i]);
    printf("%d\n", ans);
    return 0;
}

更优的做法(由 llf 提出)

事实上我们可以发现,i 向前跳时步长不会太大,即在第 3 层循环中,k 很小时是不优的

具体的来讲,对于每一步,我们都想让其跨越的步长尽量地短

而又有 p 的限制,那么步长的范围就一定在 [1, \big \lceil \frac{n}{p} \big \rceil *4]

具体还得请教 llf

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
int n, p;
ll f[maxn][maxn], a[maxn], ans = 0x7fffffff;
int main() {
    scanf("%d %d", &n, &p);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] *= i * i * i;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) {
        f[i][1] = a[i - 1];
        for (int j = 2; j <= min(p, i - 1); ++j) {
            for (int k = i - 1; k >= j; --k) {
                f[i][j] = min(f[i][j], f[k][j - 1] + a[i - k]);
            }
        }
    }
    for (int i = 1; i <= p; ++i) ans = min(ans, f[n][i]);
    printf("%d\n", ans);
    return 0;
}

C 铁轨

有一个长度为 n 的序列,对于元素 i \not = n 都有一条边连向 i + 1,初始每个边颜色都是一种颜色,有 m 次操作,共两种,分别是:

  1. 给出 x,将 [1, x] 之间的所有边染成一种新的颜色
  2. 给出 x, y,求在 [x, y] 任选一个点,在这个点之前的所有边的颜色种类的期望

线段树


线段树直接维护答案

记在第 i 个站台之前有 val(i) 个数,则答案即为

\frac{1}{y - x + 1} \sum_{i = x}^y val(i)

对于线段树上的节点 i 代表 l, r,维护 \sum_{i = l}^r val(i)

则更改操作即为,将 [1, x] 置为 0,再将 [x + 1, n] 加上 1 - val(x + 1)

时间复杂度 O(m \log n)

#include <bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
using namespace std;
const int maxn = 100000 + 10;
int n, m;

struct segementtree { int val, cover, add; } t[maxn << 2];
void pushup(int k) { t[k].val = t[ls(k)].val + t[rs(k)].val; }
void pushdown(int k, int l, int r) {
    if (t[k].cover) {
        t[ls(k)].cover = true, t[ls(k)].val = 0, t[ls(k)].add = 0;
        t[rs(k)].cover = true, t[rs(k)].val = 0, t[rs(k)].add = 0;
        t[k].cover = false;
    }
    int mid = (l + r) >> 1;
    t[ls(k)].add += t[k].add, t[rs(k)].add += t[k].add;
    t[ls(k)].val += (mid - l + 1) * t[k].add, t[rs(k)].val += (r - mid) * t[k].add;
    t[k].add = 0;
}
int getval(int k, int l, int r, int tgt) {
    if (l == r) return t[k].val;
    pushdown(k, l, r);
    int mid = (l + r) >> 1;
    if (tgt <= mid) return getval(ls(k), l, mid, tgt);
    else return getval(rs(k), mid + 1, r, tgt);
}
void cover(int k, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) { t[k].val = 0, t[k].add = 0, t[k].cover = true; return ; }
    pushdown(k, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) cover(ls(k), l, mid, ql, qr);
    if (qr > mid) cover(rs(k), mid + 1, r, ql, qr);
    pushup(k);
}
void modify(int k, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) { t[k].val += (r - l + 1) * val, t[k].add += val; return ; }
    pushdown(k, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) modify(ls(k), l, mid, ql, qr, val);
    if (qr > mid) modify(rs(k), mid + 1, r, ql, qr, val);
    pushup(k);
}
int query(int k, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return t[k].val;
    pushdown(k, l, r);
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res += query(ls(k), l, mid, ql, qr);
    if (qr > mid) res += query(rs(k), mid + 1, r, ql, qr);
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) { int opt;
        scanf("%d", &opt);
        if (!opt) { int x;
            scanf("%d", &x);
            int tmp = getval(1, 1, n, x + 1);
            cover(1, 1, n, 1, x), modify(1, 1, n, x + 1, n, 1 - tmp);
        } else { int x, y;
            scanf("%d %d", &x, &y);
            printf("%.4lf\n", ((double)query(1, 1, n, x, y) / (double)(y - x + 1)));
        }
    }
    return 0;
}

做的好的地方

  • 最后一题切出来了(虽然与 wyc 交流了)
  • 对拍对出了问题

做的不好的地方

  • A 题只有 10 分,这种题就是考的细心,简单题更要细心,尤其是这种难度的模拟赛

  • B 题貌似记搜写成了爆搜 = =,题做少了

OI-前缀和 OI-数据结构-线段树

CSP 初赛复习笔记
上一篇 «
treap 学习笔记
» 下一篇
© 2019 - 2020 bwt's blog.
...... visits · ...... visitors