题目链接 CCF CSP 练习地址
A 数组推导 大意 $B$ 数组是 $A$ 数组的前缀最大值。给定 $B$ 数组,求 $A$ 数组元素和的最大值与最小值。
解析 最小值:在改变处为该值,其他处为 $0$。 最大值:总是目前最大值,即和 $B$ 数组相同。
代码 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$。
代码 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)$,可以实现。
之后模拟即可,注意细节实现。
代码 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 ;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 () { 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)) ; for (int t = 0 ; t < T; ++t) { for (int i = 0 ; i < N; ++i) { I[(t + maxD - 1 ) % maxD][i] = 0 ; } 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; } } } 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)$ 被记录的情况下减少重复计算,可以通过本题。
本题可能会有卡常。
代码 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 箱根山岳险天下 待补充