发表更新算法13 分钟读完 (大约1923个字)

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、线路j和k，可以列出他们走过圈数x和y的一个方程： \[ 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;
}

CSP 202104 题解

https://blog.xqmmcqs.com/CSP 202104 题解/

作者

xqmmcqs

发布于

2021-08-01

更新于

2023-03-29

许可协议

#

评论

目录

最新文章

分类

Your browser is out-of-date!

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

×

×