OscarWen
喜欢到处随意折腾
算法

CSP-202109题解

发表于 2022年2月17日 更新于 2023年3月12日
字数总计：5.72k 阅读时长：20分钟

第一题：数组推导
签到题
比较简单，遍历序列B，若要让序列A的和最大，每次都取最大值即可；若要让序列A的和最小，只要序列B没上升（意味着最大值未改变）就取0，上升的话就取最大值。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int n;
int b[150];
int sum_max, sum_min;
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> b[i];
     
    for (int i = 1; i <= n; i++) {
        sum_max += b[i];
         
        if (b[i] > b[i - 1]) sum_min += b[i];
    }
    cout << sum_max << endl << sum_min;
    return 0;
}
第二题：非零段划分
大概题意是，给定一个序列A，然后让你进行一次操作，这个操作是将序列中小于p的数全部变成0，让序列A有最多的非零段。暴力做法是遍历所有的p，但是这样只能拿70分，剩余的会超时。
要做改进首先要发现一个东西，在序列A中每到一个“上坡”，即A[i+1]>A[i]时，只要p位于A[i+1]和A[i]之间，都可以产生一个非零段。注意到之后就可以开一个p的取值范围大小的差分数组，存储各个p能产生多少非零段，最后求一下前缀和就能找到合适的p。
?
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
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 5 * 1e5 + 10, M = 1e4 + 10;
 
int n;
int a[N], s[M];
int ans;
 
void add(int a, int b) {
    s[b]++, s[a + 1]--;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
     
    for (int i = 1; i <= n + 1; i ++ ) {
        if (a[i] > a[i - 1]) {
            add(a[i], a[i - 1] + 1);
        }
    }
     
    for (int i = 1; i < M; i++) {
        s[i] += s[i - 1];
        ans = max(s[i], ans);
    }
     
    cout << ans;
    return 0;
}

第三题：脉冲神经网络
大模拟
注意读清楚题目来模拟即可，用邻接表来存储，对于延时到达的脉冲，用滚动数组来存储其信息即可，可以节省很多空间，不过记得在一个单位时间后清零上一单位时间的脉冲信息。这道题目卡常非常厉害，使用scanf读入、不封装函数、不封装结构体等等，尽量节约时间。

?
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
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 1024, M = 2 * N, MOD = N - 1;
 
static unsigned long nxt = 1;
 
/* RAND_MAX assumed to be 32767 */
inline int myrand(void) {
    nxt = nxt * 1103515245 + 12345;
    return((unsigned)(nxt/65536) % 32768);
}
 
int n, s, p, t;
double dt;
 
double u[N], v[N], a[N], b[N], c[N], d[N], ik[N][N];
int sh[N];      // 神经元
double r[N];    // 脉冲源
int h[M], e[M], ne[M], idx;
double w[N];
int dl[N];       // 突触
 
inline void add(int& x, int& y, double& wi, int& di) {
    e[idx] = y, w[idx] = wi, dl[idx] = di, ne[idx] = h[x], h[x] = idx ++ ;
}
 
int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d%d%d", &n, &s, &p, &t);
    scanf("%lf", &dt);
     
    int i = 0, rn;
    while (i < n) {
        scanf("%d", &rn);
        scanf("%lf%lf%lf%lf%lf%lf", &v[i], &u[i], &a[i], &b[i], &c[i], &d[i]);
        for (int j = i + 1; j < i + rn; j++)
            v[j] = v[i], u[j] = u[i], a[j] = a[i], b[j] = b[i], c[j] = c[i], d[j] = d[i];
        i += rn;
    }
     
    for (int i = 0; i < p; i++)  scanf("%lf", &r[i]);
    int x, y, di;
    double wi;
    for (int i = 0; i < s; i++) {
        scanf("%d%d", &x, &y);
        scanf("%lf%d", &wi, &di);
        add(x, y, wi, di);
    }
     
    // 时间步模拟
    for (register int i = 1; i <= t; i++) {
        // 遍历脉冲源
        for (int j = 0; j < p; j++) {
            if (r[j] > myrand()) {
                for (int k = h[j + n]; k != -1; k = ne[k]) {
                    ik[(i + dl[k]) & MOD][e[k]] += w[k];
                }
            }
        }
         
        // 遍历神经元
        for (int j = 0; j < n; j++) {
            double old_u = u[j], old_v = v[j];
            v[j] += dt * (0.04 * old_v * old_v + 5 * old_v + 140 - old_u) + ik[i & MOD][j];
            u[j] += dt * a[j] * (b[j] * old_v - old_u);
            if (v[j] >= 30.0) {
                sh[j]++;
                for (int k = h[j]; k != -1; k = ne[k]) {
                    ik[(i + dl[k]) & MOD][e[k]] += w[k];
                }
                v[j] = c[j];
                u[j] += d[j];
            }
        }
         
        // 由于是循环使用，故记得清零
        memset(ik[i & MOD], 0, sizeof ik[i & MOD]);
    }
     
    double v_min = v[0], v_max = v[0];
    int sh_min = sh[0], sh_max = sh[0];
    for (int i = 1; i < n; i++) {
        v_min = min(v_min, v[i]);
        v_max = max(v_max, v[i]);
        sh_min = min(sh_min, sh[i]);
        sh_max = max(sh_max, sh[i]);
    }
     
    printf("%.3lf %.3lf\n", v_min, v_max);
    printf("%d %d", sh_min, sh_max);
    return 0;
}
第四题：卡牌收集 状压DP
一开始应该可以想到暴力DFS的做法，然后可以再考虑记忆化搜索，这时候就用到状态压缩，用一个16位的二进制数表示当前已经拥有的卡牌。
这里用循环来实现DP，先考虑状态的表示，dp[i][j]表示在抽第i次时已拥有的卡牌为j，二进制的j表示拥有哪些卡牌，dp[i][j]存储的就是达到这个状态的概率；再去考虑状态的计算，对于每个状态dp[i][j]，假设拥有的卡牌为c1、c2、…、ck，那么那么第i次抽卡的结果就是这k种牌的其中一种，然后对于每种抽到的牌都有两种可能：新获得的、再次获得的。根据上述就能进行状态转移的计算，遍历当前拥有的牌，每种牌分为新获得、再次获得两种情况，逐次累加概率即可，需要注意的就是如果用来计算的旧的状态已经完成了卡牌收集，那么不能转移到当前状态。
需要注意的是，官网上判断精度有点问题，要保留到10位
?
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 17, M = 1 << N;
 
int n, k;
double p[N];
double dp[N * 5][M];
int cnt[M];
double ans;
 
void cnt_card() {
    for (int i = 0; i < M; i ++ ) {
        int j = i;
        while(j) {
            j -= j & -j;
            cnt[i]++;
        }
    }
}
 
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ) cin >> p[i];
     
    for (int j = 0; j < n; j++) dp[1][1 << j] = p[j];
    cnt_card();
     
    for (int i = 2; i <= n * k; i++) {
        for (int j = 1; j < 1 << n; j++) {
             
            for (int s = 0; s < n; s++) {
                if (j & (1 << s)) {
                    if (i - 1 - cnt[j ^ (1 << s)] + cnt[j ^ (1 << s)] * k < n * k)
                        dp[i][j] += dp[i - 1][j ^ (1 << s)] * p[s];
                    if (i - 1 - cnt[j] + cnt[j] * k < n * k)
                        dp[i][j] += dp[i - 1][j] * p[s];
                }
            }
             
            if (i - cnt[j] + cnt[j] * k >= n * k) {
                ans += dp[i][j] * i;
            }
        }
    }
     
    printf("%.10lf", ans);
    return 0;
}

标签:

相关博文

2022 年 2 月
一 二 三 四 五 六 日
 123456
78910111213
14151617181920
21222324252627
28  

bgm

00:00