202104
算是比较简单的一次，同样的分排名比以往低一些。
3. DHCP服务器
比以往简单，考试时一个小细节错了，只有 40。
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
|
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 5;
struct IP {
int sta; // 未分配 0 待分配 1 占用 2 过期 3
int del;
string owner;
}ip[N];
int n, m, t1, t2, t3;
string h;
void update_ip_sta(int tc) {
for (int i = 1; i <= n; ++i) {
if (ip[i].del && ip[i].del <= tc) {
if (ip[i].sta == 1) {
ip[i].sta = 0;
ip[i].owner = "";
ip[i].del = 0;
}
else {
ip[i].sta = 3;
ip[i].del = 0;
}
}
}
}
int get_ip_by_owner(string client) {
for (int i = 1; i <= n; ++i)
if (ip[i].owner == client)
return i;
return 0;
}
int get_ip_by_sta(int sta) {
for (int i = 1; i <= n; ++i)
if (ip[i].sta == sta)
return i;
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> t1 >> t2 >> t3 >> h;
cin >> m;
while (m--) {
int tc;
string client, server, type;
int id, te;
cin >> tc >> client >> server >> type >> id >> te;
if ((server != h && server != "*") && type != "REQ") continue;
if (type != "DIS" && type != "REQ") continue;
if ((server == "*" && type != "DIS") || (server == h && type == "DIS")) continue;
update_ip_sta(tc);
if (type == "DIS") {
int k = get_ip_by_owner(client);
if (!k) k = get_ip_by_sta(0);
if (!k) k = get_ip_by_sta(3);
if (!k) continue;
ip[k].sta = 1, ip[k].owner = client;
if (!te) ip[k].del = tc + t1;
else {
int t = te - tc;
t = max(t, t3); t = min(t, t2);
ip[k].del = tc + t;
}
cout << h << ' ' << client << ' ' << "OFR" << ' ' << k << ' ' << ip[k].del << '\n';
}
else if (type == "REQ") {
if (server != h) {
for (int i = 1; i <= n; ++i)
if (ip[i].owner == client && ip[i].sta == 1) {
ip[i].sta = 0;
ip[i].owner = "";
ip[i].del = 0;
}
continue;
}
if (!(id >= 1 && id <= n && ip[id].owner == client)) {
cout << h << ' ' << client << ' ' << "NAK" << ' ' << id << ' ' << 0 << '\n';
}
else {
ip[id].sta = 2;
if (!te) ip[id].del = tc + t1;
else {
int t = te - tc;
t = max(t, t3); t = min(t, t2);
ip[id].del = tc + t;
}
cout << h << ' ' << client << ' ' << "ACK" << ' ' << id << ' ' << ip[id].del << '\n';
}
}
}
return 0;
}
|
4. 校门外的树
题意：$n$ 个障碍物，坐标为 $a_1,a_2,\cdots,a_n$，在$[a_1,a_n]$ 间种一些树，使这些树看起来美观，树坐标在一个障碍区间构成等差数列，求出所有本质不同的美观的种树方案。
考虑 $f[n]$ 为 $[a_1,a_n]$ 方案数，则 $f[i]=\sum_{j=1}^{i-1}dp[j]*cnt(j,i)$，$cnt(j,i)$ 为 $[a_j,a_i]$ 的方案数，倒过来枚举可以避免在障碍物上的情况，用一个集合 $st$ 记录树之间的距离，预处理好因子。
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
|
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 1005, M = 1e5 + 5, MOD = 1e9 + 7;
int n;
int a[N], f[N], st[M];
vector<int> q[M];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= a[n] / 2; ++i) {
for (int j = 2 * i; j <= a[n]; j += i) {
q[j].push_back(i);
}
}
f[1] = 1;
for (int i = 1; i <= n; ++i) {
memset(st, 0, sizeof(st));
for (int j = i - 1; j >= 1; --j) {
int d = a[i] - a[j], cnt = 0;
for (int k : q[d]) {
if (!st[k]) {
cnt++;
st[k] = 1;
}
}
st[d] = 1;
f[i] = (f[i] + 1ll * f[j] * cnt) % MOD;
}
}
printf("%d\n", f[n]);
return 0;
}
|
5. 疫苗运输