lonlyn's blog
首页
时间轴
标签
分类
友链
关于
avatar
文章
18
标签
25
分类
2
首页
时间轴
标签
分类
友链
关于
目录
  1. 1. 题目链接
  2. 2. A 数组推导
    1. 2.1. 大意
    2. 2.2. 解析
    3. 2.3. 代码
  3. 3. B 非零段划分
    1. 3.1. 大意
    2. 3.2. 解析
    3. 3.3. 代码
  4. 4. C 脉冲神经网络
    1. 4.1. 大意
    2. 4.2. 解析
    3. 4.3. 代码
  5. 5. D 收集卡牌
    1. 5.1. 大意
    2. 5.2. 解析
    3. 5.3. 代码
  6. 6. E 箱根山岳险天下
第 23 次 CSP 测试
|从蒟蒻到蒟蒻的修炼
字数总计:2.2k|阅读时长: 10 分钟
|阅读量:|评论数:

题目链接

CCF CSP 练习地址

A 数组推导

大意

$B$ 数组是 $A$ 数组的前缀最大值。给定 $B$ 数组，求 $A$ 数组元素和的最大值与最小值。

解析

最小值：在改变处为该值，其他处为 $0$。
最大值：总是目前最大值，即和 $B$ 数组相同。

代码

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long
const int maxn = 100010;
int n;
int b[maxn];
ll maxv, minv;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
        maxv += b[i];
        if (b[i] != b[i-1]) minv += b[i];
    }
    printf("%lld\n%lld", maxv, minv);
    return 0;
}

B 非零段划分

大意

给定一个数组，可以选择任意一个数，将其中小于该数的值全部变为 $0$。求一种选择，让极大非零段个数最多，给出最多的个数即可。

解析

值域范围很小，考虑从小到大枚举每个选择的数，这样不用重复计算（删过的数不会再删一次）。考虑每个选择的数对答案的贡献。
对于连续相等的数可以看成一个数来看待。比如 1 2 3 3 2 1 就和 1 2 3 2 1 结果相同。我们可以预处理，让相邻的数不同。

考虑不在两端的数：

  • 若一个数比左、右的数都大，那么这个数在被删去的时候，左、右的数已经被删去，自己是一个非零段。所以对答案贡献 $-1$。
  • 若一个数比左、右的数都小，那么这个数在被删去的时候，左、右的数肯定存在，自身被删去的时候使得非零段 $+1$，对答案贡献 $1$。

考虑在两端的数：

  • 端点的数比相邻的数小，被删除时没有影响。
  • 端点的数比相邻的数大，对答案贡献 $-1$。

代码

cpp
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 500010;
const int maxm = 10010;
int n;
int a[maxn];
int f[maxm];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    int tot = 0;
    a[++tot] = a[1];
    for (int i = 2; i <= n; ++i) {
        if (a[i] == a[i-1]) continue;
        a[++tot] = a[i];
    }
    n = tot;
    for (int i = 2; i < n; ++i) {
        if (a[i] < a[i-1] && a[i] < a[i+1]) {
            ++f[a[i]];
        }
        if (a[i] > a[i-1] && a[i] > a[i+1]) {
            --f[a[i]];
        }
    }
    if (n > 1 && a[1] > a[2]) --f[a[1]];
    if (n > 1 && a[n] > a[n-1]) --f[a[n]];
    int cur = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0 && a[i-1] != 0) ++cur;
    }
    if (a[n]) ++cur;
    int ans = cur;
    for (int i = 1; i <= 10000; ++i) {
        cur += f[i];
        if (cur > ans) {
            ans = cur;
        }
    }
    printf("%d", ans);
    return 0;
}

C 脉冲神经网络

大意

给定一个 SNN，根据题意要求完成模拟即可。

解析

模拟规则大概如下：

  • 整个网格图有两种点：脉冲源和神经元。每个点之间存在有向边，即突触。
  • 在每个时刻，脉冲源可能会释放脉冲，由题目提供的 $r$ 和 myrand() 进行判断。
  • 在每个时刻，神经元按照题目要求进行对应的改变，同时根据 $v$ 值的大小，可能释放脉冲。
  • 脉冲的传递需要时间。可以看做提前发送，但直到对应时刻才会加上脉冲值。
  • 题目要求：求出最大最小值。换句话说，需要求出每个神经元在 $T$ 时刻的状态，以及每个神经元在这段区间释放脉冲的次数。

可以想到枚举时间，同时枚举时间内的每个点，进行对应的操作。维护的难点在于脉冲是有延迟的。

朴素的思路：维护每个时间点上，每个点收到的脉冲强度之和。空间复杂度 $O(NT)$ 较大。

注意到第 $3$ 组样例中，$D$ 相比第 $2$ 组样例少了很多，且两者 $N\times T$ 相等。考虑到我们只需要最终 $T$ 时刻的答案而不需要中间过程，可以使用滚动数组，复杂度降为 $O(ND)$，可以实现。

之后模拟即可，注意细节实现。

代码

cpp
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 1010;

static unsigned long nxt = 1;
/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    nxt = nxt * 1103515245 + 12345;
    return((unsigned)(nxt/65536) % 32768);
}

int N, S, P, T;
double dt;
int r[maxn];

struct Neuron {
    double v, u, a, b, c, d;
    int activate_times;
} neuron[maxn << 1];

struct Synapse {
    int s, t;
    double w;
    int D;
} synapse[maxn << 1];
vector<int> G[maxn << 1];
int maxD;

int main() {
    // input
    scanf("%d%d%d%d", &N, &S, &P, &T);
    scanf("%lf", &dt);

    int cur = 0, rn;
    double ru, rv, ra, rb, rc, rd;
    while (cur < N) {
        scanf("%d", &rn);
        scanf("%lf%lf%lf%lf%lf%lf", &rv, &ru, &ra, &rb, &rc, &rd);
        while (rn--) {
            neuron[cur].v = rv;
            neuron[cur].u = ru;
            neuron[cur].a = ra;
            neuron[cur].b = rb;
            neuron[cur].c = rc;
            neuron[cur].d = rd;
            neuron[cur].activate_times = 0;
            ++cur;
        }
    }

    for (int i = 0; i < P; ++i) {
        scanf("%d", &r[i]);
    }

    for (int i = 0; i < S; ++i) {
        scanf("%d%d", &synapse[i].s, &synapse[i].t);
        scanf("%lf", &synapse[i].w);
        scanf("%d", &synapse[i].D);
        G[synapse[i].s].push_back(i);
        maxD = max(maxD, synapse[i].D);
    }
    ++maxD;
    vector< vector<double> > I(maxD, vector<double>(N));

    // work
    for (int t = 0; t < T; ++t) {
        // clear
        for (int i = 0; i < N; ++i) {
            I[(t + maxD - 1) % maxD][i] = 0;
        }

        // pulse source
        for (int i = 0; i < P; ++i) {
            if (r[i] > myrand()) {
                for (int j = 0; j < G[N + i].size(); ++j) {
                    Synapse tmps = synapse[G[N + i][j]];
                    I[(t + tmps.D) % maxD][tmps.t] += tmps.w; 
                }
            }
        }
        // neuron
        for (int i = 0; i < N; ++i) {
            double u = neuron[i].u, v = neuron[i].v;
            neuron[i].v = v + dt * (0.04 * v * v + 5 * v + 140 - u) + I[t % maxD][i];
            neuron[i].u = u + dt * neuron[i].a * (neuron[i].b * v - u);
            if (neuron[i].v >= 30) {
                neuron[i].v = neuron[i].c;
                neuron[i].u += neuron[i].d;
                ++neuron[i].activate_times;
                for (int j = 0; j < G[i].size(); ++j) {
                    Synapse tmps = synapse[G[i][j]];
                    I[(t + tmps.D) % maxD][tmps.t] += tmps.w;
                }
            }
        }
    }

    double minv = 1e18, maxv = -1e18;
    int mint = 1e9, maxt = 0;
    for (int i = 0; i < N; ++i) {
        if (neuron[i].v < minv) minv = neuron[i].v;
        if (neuron[i].v > maxv) maxv = neuron[i].v;
        if (mint > neuron[i].activate_times) mint = neuron[i].activate_times;
        if (maxt < neuron[i].activate_times) maxt = neuron[i].activate_times;
    }
    printf("%.3lf %.3lf\n%d %d", minv, maxv, mint, maxt);
    return 0;
}

D 收集卡牌

大意

抽卡，一共有 $n$ 张卡牌，每张卡牌每次被抽到的概率为 $p_i$。抽到重复会转化为 $1$ 个硬币，使用 $k$ 枚硬币可以兑换任何一张卡牌。问得到所有卡牌的期望抽卡次数。$1\le n\le 16,1\le k\le 5$。

解析

设 $f(i,p_c,s,j)$ 代表该状态情况下的期望抽卡数，其中 $i$ 代表目前是第 $i$ 次抽卡，$p_c$ 代表目前到达此状态的概率，$s$ 代表持有卡牌的状态，$j$ 代表目前持有的硬币数。
考虑最终答案：$f(0, 1, 0, 0)$。
考虑边界情况：卡全齐，或者持有硬币数能够兑换所有没有得到的卡牌。第二种情况其实包含了第一种情况。
考虑状态转移：设抽到的卡为 $t$，状态转移分为两种情况：

  • 抽到已有的卡，则由 $f(i+1,p_cp_t,s,j+1)$ 转移而来。
  • 抽到没有的卡，则由 $f(i+1,p_cp_t,s | 2^t, j + 1)$ 转移而来。

这样可以进行朴素的暴力求解。
考虑进行优化：对于某个特定的状态组合 $(s,j)$，在抽卡状态和持有硬币数确定的情况下，抽到所有卡片的期望步数是确定的。
不妨设 $dp(s,j)$ 代表期望，那么对于计算过程中的 $f(i,p_c,s,j)$，可以得到关系：$f(i,p_c,s,j) = dp(s,j)\times p_c$。
我们进行记忆化搜索记录 $dp(s,j)$，在 $(s,j)$ 被记录的情况下减少重复计算，可以通过本题。

本题可能会有卡常。

代码

cpp
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 20;
int n, k;
double p[maxn];
inline int calc(int s) {
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        if (s & (1 << i)) ++cur;
    }
    return cur;
}
double f[66000][90];
double dfs(int cost, double curp, int s, int card) {
    int cur = calc(s);
    if ((n - cur) * k <= card) {
        f[s][card] = cost;
        return cost * curp;
    }
    if (f[s][card] != 0) return f[s][card] * curp;
    double res = 0;
    for (int i = 0; i < n; ++i) {
        if (s & (1 << i)) {
            res += dfs(cost + 1, curp * p[i], s, card + 1);
        } else {
            res += dfs(cost + 1, curp * p[i], s | (1 << i), card);
        }
    }
    f[s][card] = res / curp;
    return res;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%lf", &p[i]);
    }
    printf("%.10lf", dfs(0, 1, 0, 0));
    return 0;
}

E 箱根山岳险天下

待补充

文章作者: lonlyn
文章链接: https://lonlyn.gitee.io/blog/2021/10/07/csp202109/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lonlyn's blog！
CSP
评论
繁