CSP 202104 题解

这次T3 T4都很简单,可惜没有把握住。

202104-1 灰度直方图

桶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int n, m, L;
int ans[300];
int main()
{
cin >> n >> m >> L;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
int x;
cin >> x;
ans[x]++;
}
for (int i = 0; i < L; ++i)
cout << ans[i] << ' ';
return 0;
}

202104-2 邻域均值

二维前缀和。

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 <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;

inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
return x * f;
}

int n, L, r, t, a[610][610], pre[610][610];
int main()
{
n = read();
L = read();
r = read();
t = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
a[i][j] = read();
pre[i][j] = pre[i][j - 1] + a[i][j];
}
for (int j = 1; j <= n; ++j)
for (int i = 1; i <= n; ++i)
pre[i][j] += pre[i - 1][j];
int ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
int x1 = max(1, i - r) - 1, x2 = min(n, i + r);
int y1 = max(1, j - r) - 1, y2 = min(n, j + r);
int cnt = (y2 - y1) * (x2 - x1);
int tot = pre[x2][y2] + pre[x1][y1] - pre[x1][y2] - pre[x2][y1];
if ((double)tot / cnt <= t)
++ans;
}
printf("%d\n", ans);
return 0;
}

202104-3 DHCP服务器

按题意模拟即可,调几个STL。我这代码中有一部分STL没有啥用。

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <iostream>
using namespace std;

inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
return x * f;
}

int N, Tdef, Tmax, Tmin, n;
string H;
int main()
{
N = read();
Tdef = read();
Tmax = read();
Tmin = read();
cin >> H;
n = read();
vector<int> ippool(N + 1); // 1 undis 2 tobedis 3 used 4 dated
vector<string> iphost(N + 1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> liveq;
vector<int> ipttl(N + 1);
set<int> undis, tobedis, used, dated;
unordered_map<string, int> mp;
for (int i = 1; i <= N; ++i)
undis.insert(i), ippool[i] = 1;
while (n--)
{
int t = read();
while (!liveq.empty() && liveq.top().first <= t)
{
int tip = liveq.top().second, thisttl = liveq.top().first;
liveq.pop();
if (thisttl != ipttl[tip])
continue;
if (ippool[tip] == 2)
{
ippool[tip] = 1;
tobedis.erase(tip);
undis.insert(tip);
mp[iphost[tip]] = 0;
iphost[tip].clear();
}
else if (ippool[tip] == 3)
{
ippool[tip] = 4;
used.erase(tip);
dated.insert(tip);
}
ipttl[tip] = 0;
}
string sender, recver, type;
cin >> sender >> recver >> type;
int ip = read(), ttl = read();
if (!(recver == H || recver == "*") && type != "REQ")
continue;
if (type != "REQ" && type != "DIS")
continue;
if (recver == "*" && type != "DIS" || recver == H && type == "DIS")
continue;
if (type == "DIS")
{
int sendip;
if (mp[sender])
{
sendip = mp[sender];
if (ippool[sendip] == 2)
tobedis.erase(sendip);
else if (ippool[sendip] == 3)
used.erase(sendip);
else if (ippool[sendip] == 4)
dated.erase(sendip);
}
else if (!undis.empty())
{
sendip = *(undis.begin());
undis.erase(sendip);
}
else if (!dated.empty())
{
sendip = *(dated.begin());
mp[iphost[sendip]] = 0;
dated.erase(sendip);
}
else
continue;
ippool[sendip] = 2;
iphost[sendip] = sender;
mp[sender] = sendip;
tobedis.insert(sendip);
int sendttl;
if (!ttl)
sendttl = t + Tdef;
else
sendttl = max(t + Tmin, min(ttl, t + Tmax));
liveq.push(make_pair(sendttl, sendip));
ipttl[sendip] = sendttl;
cout << H << ' ' << sender << " OFR " << sendip << ' ' << sendttl << endl;
}
else
{
if (recver != H)
{
int tip = mp[sender];
if (tip)
{
if (ippool[tip] == 2)
{
ippool[tip] = 1;
iphost[tip].clear();
tobedis.erase(tip);
undis.insert(tip);
mp[sender] = 0;
ipttl[tip] = 0;
}
}
continue;
}
if (!(ip >= 1 && ip <= N && iphost[ip] == sender))
{
cout << H << ' ' << sender << " NAK " << ip << " 0" << endl;
continue;
}
if (ippool[ip] == 2)
{
ippool[ip] = 3;
tobedis.erase(ip);
used.insert(ip);
}
else if (ippool[ip] == 4)
{
ippool[ip] = 3;
dated.erase(ip);
used.insert(ip);
}
int sendttl;
if (!ttl)
sendttl = t + Tdef;
else
sendttl = max(t + Tmin, min(ttl, t + Tmax));
liveq.push(make_pair(sendttl, ip));
ipttl[ip] = sendttl;
cout << H << ' ' << sender << " ACK " << ip << ' ' << sendttl << endl;
}
}
return 0;
}

202104-4 校门外的树

60分的转移很好想,f[i]表示前i个树的方案,可以\(O(n^3)\)​预处理出来之后转移。

优化成\(O(n^2\log n)\)​​的话,需要观察出性质,如果内层循环倒着走的话,如果一个间隔出现过,则之后以这个间隔为因子的间隔都不能再出现了。所以首先预处理出\(10^5\)​​内每个数的因子,之后用一个集合维护一下每个间隔是否出现即可。

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
typedef long long LL;
using namespace std;

inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
return x * f;
}

const int MOD = 1e9 + 7;
int n, a[1010], f[1010];
vector<int> factor[100010];
set<int> s;

int cal(int l, int r)
{
int ans = 0;
for (const auto &i : factor[r - l])
{
if (s.find(i) == s.end())
{
if (i != r - l)
++ans;
s.insert(i);
}
}
return ans;
}

int main()
{
n = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int i = 1; i <= 100000; ++i)
{
int t = sqrt(i);
for (int j = 1; j <= t; ++j)
if (i % j == 0)
{
factor[i].push_back(j);
if (j * j != i)
factor[i].push_back(i / j);
}
}
f[1] = 1;
for (int i = 2; i <= n; ++i)
{
s.clear();
for (int j = i - 1; j; --j)
f[i] = ((LL)cal(a[j], a[i]) * f[j] % MOD + f[i]) % MOD;
}
printf("%d\n", f[n]);
return 0;
}

202104-5 疫苗运输

将一条线路化为一个点,点之间如果能在某个站相遇则连边,边的权值要用exgcd求出特解,再算出通解:

b[i]表示第i条线路走一圈花费的时间,pre[i][j]表示第j条线路第一次到达第i个站点的时刻。

对于站点i、线路jk,可以列出他们走过圈数xy的一个方程: \[ b_j\cdot x + pre_{i,j} = b_k\cdot y + pre_{i,k} \] 移项,设\(a=b_j, b=b_k, c=|pre_{i,j}-pre_{i,k}|, d=\gcd(b_j,b_k)\)​​​,用exgcd求解: \[ a\cdot x+b\cdot y=d \] 得特解\(x_0\)\(y_0\),注意由于exgcd的系数全部要求是非负整数,所以求出解之后要看情况调整\(x_0\)或者\(y_0\)的符号。

原方程的通解为: \[ \left\{\begin{align*} x&=x_0\cdot \frac cd+\frac bd\cdot t \\ y&=y_0\cdot \frac cd+\frac ad\cdot t \end{align*}\right. \] 转化为实际的时刻,得: \[ \left\{\begin{align*} t_1=(x_0\cdot \frac cd+\frac bd\cdot t)\cdot a+pre_{i,j} \\ t_2=(y_0\cdot \frac cd+\frac ad\cdot t)\cdot b+pre_{i,k} \end{align*}\right. \] 即: \[ \left\{\begin{align*} t_1=\frac {ab}d\cdot t+x_0\cdot \frac {ac}d+pre_{i,j} \\ t_2=\frac {ab}d\cdot t+y_0\cdot \frac {bc}d+pre_{i,k} \end{align*}\right. \] 边的权值中记录\(t\)之前的系数和常数项。

dis[i]表示第i条线路最早得到疫苗的时刻,可以用dijkstra算法求出各点的dis[i],只是这里边权是可变的,松弛操作时需要根据dis[u]和边权更新dis[v]的值。

最后根据dis[i]求出原图中各点最早拿到疫苗的时刻即可。

最后一个数据可能卡long long,我的代码只能拿95分,改了好久没改出来,遂放弃。

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
typedef long long LL;
using namespace std;

inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
return x * f;
}

const int MAXN = 510;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int pass[MAXN][MAXN], passtime[MAXN][MAXN], pre[MAXN][MAXN];
LL b[MAXN], dis[MAXN], g[MAXN][MAXN];
struct Edge
{
int v;
LL x, a;
};
vector<Edge> e[MAXN];
bool vis[MAXN];

LL exgcd(LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
LL d = exgcd(b, a % b, x, y);
LL t = x;
x = y;
y = t - a / b * y;
return d;
}

LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}

void dijkstra()
{
for (int i = 1; i <= m; ++i)
{
int u;
LL mn = INF;
for (int j = 1; j <= m; ++j)
{
if (vis[j])
continue;
if (dis[j] < mn)
{
u = j;
mn = dis[j];
}
}
vis[u] = true;
for (const auto &j : e[u])
{
if (vis[j.v])
continue;
LL val = ceil((double)(dis[u] - j.x) / j.a) * j.a + j.x;
if (val < dis[j.v])
dis[j.v] = val;
}
}
}

int main()
{
n = read();
m = read();
memset(pre, -1, sizeof(pre));
for (int i = 1; i <= m; ++i)
{
int t = read();
pre[0][i] = 0;
for (int j = 1; j <= t; ++j)
{
pass[i][j] = read();
passtime[i][j] = read();
pre[pass[i][j]][i] = pre[pass[i][j - 1]][i] + passtime[i][j - 1];
b[i] += passtime[i][j];
}
}
for (int j = 1; j <= m; ++j)
for (int k = j + 1; k <= m; ++k)
g[j][k] = gcd(b[j], b[k]);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (pre[i][j] == -1)
continue;
for (int k = j + 1; k <= m; ++k)
{
if (pre[i][k] == -1)
continue;
LL d = g[j][k];
if (abs(pre[i][j] - pre[i][k]) % d)
continue;
LL x, y;
exgcd(b[j], b[k], x, y);
if (pre[i][j] - pre[i][k] > 0)
x = -x;
else
y = -y;
e[j].push_back((Edge){k, x * abs(pre[i][j] - pre[i][k]) / d * b[j] + pre[i][j], b[k] / d * b[j]});
e[k].push_back((Edge){j, y * abs(pre[i][j] - pre[i][k]) / d * b[k] + pre[i][k], b[j] / d * b[k]});
}
}
}
for (int i = 1; i <= m; ++i)
{
if (pre[1][i] == -1)
dis[i] = INF;
else
dis[i] = pre[1][i];
}
dijkstra();
for (int i = 2; i <= n; ++i)
{
LL ans = INF;
for (int j = 1; j <= m; ++j)
{
if (pre[i][j] == -1)
continue;
LL val = dis[j] / b[j] * b[j] + pre[i][j];
if (val < dis[j])
val += b[j];
ans = min(ans, val);
}
if (ans == INF)
puts("inf");
else
printf("%lld\n", ans);
}
return 0;
}
作者

xqmmcqs

发布于

2021-08-01

更新于

2021-08-01

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×