OscarWen
喜欢到处随意折腾
算法

CSP-202104题解

发表于 2022年3月13日 更新于 2023年2月18日
字数总计：7.12k 阅读时长：24分钟

第一题：灰度直方图
签到题
按题意直接统计即可，没有难度

?
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
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 1000;
 
int n, m, l;
int h[N];
 
int main() {
    cin >> n >> m >> l;
     
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            int x;
            cin >> x;
            h[x]++;
        }
    }
     
    for (int i = 0; i < l; i ++ ) cout << h[i] << " ";
    return 0;
}

第二题：邻域均值
给出一张灰度图，通过邻域内（一个矩形范围）元素的和来判断某个像素是否位于较暗区域。使用二维前缀和来解决。

?
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
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 610;
 
int n, l, r, t;
int a[N][N], s[N][N];
int ans;
 
int main() {
    cin >> n >> l >> r >> t;
     
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            cin >> a[i][j];
        }
    }
     
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
     
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            int x1 = i - r < 1 ? 1 : i - r, y1 = j - r < 1 ? 1 : j - r;
            int x2 = i + r > n ? n : i + r, y2 = j + r > n ? n : j + r;
             
            int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            int cnt = (x2 - x1 + 1) * (y2 - y1 + 1);
            if (1.0 * sum / cnt <= t) ans++;
        }
    }
     
    cout << ans;
    return 0;
}

第三题：DHCP服务器
给了若干个IP，这些IP可以分配给主机，每个IP至多只能被一个主机占用。每个IP的状态有未分配、待分配、占用、过期，仅有位于未分配状态的IP没有占用者，待分配和占用的IP会有一个过期时间。
下面简述一下各个状态的转换规则（具体规则看题目），主机DIS报文可获得一个未分配或过期的IP，此IP的状态变为待分配，若超过期时间后会变为未分配，主机REQ报文可将待分配、占用或过期IP变为占用，设定过期时间，若超过期时间就转为过期IP。
本题的时间要求比较宽松，直接使用数组来保存IP的相关信息即可，再用一个哈希表记录主机对应占用的IP。具体就是按照题目规则来模拟。

?
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
 
using namespace std;
 
const int N = 10010;
typedef pair<int, int> PII;
 
int n, tdef, tmin, tmax;
string h;
int ip_st[N], ip_t[N];      // 0未分配 1待分配 2占用 3过期
string ip_host[N];
unordered_map<string, int> cover;
priority_queue<PII, vector<PII>, greater<PII>> alloced;
 
// 找一个没被分配的ip
int findNone(string send) {
    for (int i = 1; i <= n; i++) {
        if (ip_st[i] == 0) {
            ip_host[i] = send;
            return i;
        }
    }
    return -1;
}
 
// 找一个过期的ip
int findOutDate(string send) {
    for (int i = 1; i <= n; i++) {
        if (ip_st[i] == 3) {
            cover.erase(cover.find(ip_host[i]));
            ip_host[i] = send;
            return i;
        }
    }
    return -1;
}
 
// 提供一个IP，其进入待分配状态
void offerIP(int ip, int t, int te) {
    ip_st[ip] = 1;
    if (te == 0) ip_t[ip] = t + tdef;
    else {
        if (te < t + tmin) ip_t[ip] = t + tmin;
        else if (te > t + tmax) ip_t[ip] = t + tmax;
        else ip_t[ip] = te;
    }
    alloced.push({ip_t[ip], ip});
}
 
// 更新IP的过期状态
void updateIP(int t) {
    while (!alloced.empty()) {
        PII tt = alloced.top();
        if (tt.first <= t) {
            alloced.pop();
            if (ip_st[tt.second] == 1 && ip_t[tt.second] <= t) {
                // 待分配过期
                ip_st[tt.second] = 0;
                ip_t[tt.second] = 0;
                cover.erase(cover.find(ip_host[tt.second]));
            } else if (ip_st[tt.second] == 2 && ip_t[tt.second] <= t) {
                // 占用过期
                ip_st[tt.second] = 3;
                ip_t[tt.second] = 0;
            }
        } else break;
    }
}
 
int main() {
    cin >> n >> tdef >> tmax >> tmin >> h;
 
    int m;
    cin >> m;
    string send, rec, type;
    int t, ip, te;
    while (m -- ) {
        cin >> t >> send >> rec >> type >> ip >> te;
        updateIP(t);
         
        // 接收方不是本机
        if (rec != "*" && rec != h && type == "DIS") continue;
        // 不是DIS却用*
        if (rec == "*" && type != "DIS") continue;
        // 是DIS却没用*
        if (rec == h && type == "DIS") continue;
         
        if (type == "DIS") {
            auto p = cover.find(send);
            if (p != cover.end()) {
                ip = (*p).second;
                offerIP(ip, t, te);
                cout << h << " " << send << " OFR " << ip << " " << ip_t[ip] << endl;
            } else {
                ip = findNone(send);
                if (ip == -1) ip = findOutDate(send);
                if (ip != -1) {
                    offerIP(ip, t, te);
                    cover[send] = ip;
                    cout << h << " " << send << " OFR " << ip << " " << ip_t[ip] << endl;
                }
            }
        } else if (type == "REQ") {
            auto p = cover.find(send);
            if (rec != h) {
                // 接收方不是本机
                if (p != cover.end()) {
                    ip = (*p).second;
                    if (ip_st[ip] == 1) {
                        ip_t[ip] = 0;
                        ip_st[ip] = 0;
                        cover.erase(p);
                    }
                }
            } else {
                // 接收方是本机
                if (p != cover.end() && (*p).second == ip) {
                    offerIP(ip, t, te);
                    ip_st[ip] = 2;
                    alloced.push({ip_t[ip], ip});
                    cout << h << " " << send << " ACK " << ip << " " << ip_t[ip] << endl;
                } else cout << h << " " << send << " NAK " << ip << " 0" << endl;
            }
             
        }
    }
    return 0;
}

第四题：校门外的树
数轴上有若干障碍，障碍上不能种树，然后种若干树使其美观，一个区间美观的定义是：整个区间所有东西（包含障碍和树）的坐标形成等差数列，或者区间分为两部分分别美观。需要求种树美观的方案总数。
这种方案数的问题，可以考虑DP。
首先考虑状态的表示，dp[i]表示在前i个障碍里种树的美观方案集合，存储的属性是方案数量。之所以这样考虑是因为这个问题属于选择问题（类似背包问题），要选择种树位置让区间变完美，在实际做题时如果在后续分析时发现条件不足还可以增加状态表示数组的维度。
再考虑状态的计算，将集合（前i个障碍里美观种树集合）划分，由于一个美观区间可以由若干美观子区间组成，所以可划分为最后最后一个美观子区间起始为i-1、i-2、…、0，共i个子集。
对于每个子集，设最后一个美观区间长度为d，设最后一个美观区间起始点为j，计算出d的约数数量，剔除之前已经出现的约数，再利用乘法原理可算出这个子集的方案数。进一步考虑这样的划分是不重不漏的，显然不会遗漏，然后因为在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
44
45
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int N = 1010, M = 1e5, MOD = 1e9 + 7;
typedef long long LL;
 
int n;
int a[N];
int dp[N];
bool st[M];
vector<int> p[M + 5];
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
     
    for (int i = 1; i < M; i++)
        for (int j = i * 2; j <= M; j += i)
            p[j].push_back(i);
     
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        memset(st, 0, sizeof st);
        for (int j = i - 1; j >= 0; j--) {
            int d = a[i] - a[j];
            int cnt = 0;
             
            for (int k : p[d]) {
                if (!st[k]) {
                    st[k] = 1;
                    cnt++;
                }
            }
            st[d] = 1;
            dp[i] = (dp[i] + (LL)dp[j] * cnt) % MOD;
        }
    }
     
    cout << dp[n];
    return 0;
}

标签:

相关博文

2022 年 3 月
一 二 三 四 五 六 日
 123456
78910111213
14151617181920
21222324252627
28293031  

bgm

00:00