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

CSP 202012 题解

突发奇想刷了刷去年 CSP 的题，这几年难度真是越来越高了

202012-1 期末预测之安全指数

模拟

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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef double db;

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, ans;

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        int w = read(), s = read();
        ans += w * s;
    }
    printf("%d\n", max(ans, 0));
    return 0;
}

202012-2 期末预测之最佳阈值

模拟，按y排个序，对 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef double db;

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 = 1e5 + 10;
struct Node
{
    int y, res;
    bool operator<(const Node &b) const
    {
        return y == b.y ? res < b.res : y < b.y;
    }
} a[MAXN];
int n, pre[MAXN], ans, ans1;

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i].y = read();
        a[i].res = read();
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + !a[i].res;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i].y == a[i - 1].y)
            continue;
        if (pre[i - 1] + n - i + 1 - (pre[n] - pre[i - 1]) >= ans1)
            ans = a[i].y, ans1 = pre[i - 1] + n - i + 1 - (pre[n] - pre[i - 1]);
    }
    printf("%d\n", ans);
    return 0;
}

202012-3 带配额的文件系统

大大大大大模拟，写了几个小时，半吊子 OOP，挺丑的

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
typedef double db;

class File;
class DirFile;
class OrdFile;
bool flag;

class File
{
public:
    string name;
    DirFile *fa;
    bool type;
    File(string s, DirFile *p) : name(s), fa(p) {}
    virtual ~File() = default;
};

class DirFile : public File
{
public:
    LL dirLimit, sonLimit, dirSize, sonSize;
    unordered_map<string, File *> son;
    DirFile(string s, DirFile *p) : File(s, p), dirLimit(0), sonLimit(0), dirSize(0), sonSize(0) { type = 0; }
    void add_son(DirFile *newson, LL size);
    void add_son(OrdFile *newson);
    bool get_son(const string &s) const { return son.find(s) != son.end(); }
    ~DirFile();
};

class OrdFile : public File
{
public:
    LL size;
    OrdFile(string s, DirFile *p, LL sz) : File(s, p), size(sz) { type = 1; }
    ~OrdFile() = default;
};

void DirFile::add_son(DirFile *newson, LL size)
{
    sonSize += size;
    son[newson->name] = newson;
}

void DirFile::add_son(OrdFile *newson)
{
    sonSize += newson->size;
    dirSize += newson->size;
    son[newson->name] = newson;
}

DirFile::~DirFile()
{
    for (auto &s : son)
        delete s.second;
}

DirFile *root;

void split_dir(const string dir, vector<string> &res)
{
    int loc = 1;
    while (true)
    {
        int pos = dir.find('/', loc);
        if (pos == dir.npos)
        {
            res.push_back(dir.substr(loc));
            break;
        }
        else
        {
            res.push_back(dir.substr(loc, pos - loc));
            loc = pos + 1;
        }
    }
}

bool can_create(DirFile *lastDir, const vector<string> &dir, int i, LL &size)
{
    if (i == dir.size() - 1)
    {
        if (lastDir->get_son(dir[i]))
        {
            if (!lastDir->son[dir[i]]->type)
                return false;
            else
                size -= dynamic_cast<OrdFile *>(lastDir->son[dir[i]])->size;
        }
        if (lastDir->sonLimit && lastDir->sonLimit - lastDir->sonSize < size)
            return false;
        if (lastDir->dirLimit && lastDir->dirLimit - lastDir->dirSize < size)
            return false;
        return true;
    }
    if (lastDir->get_son(dir[i]))
    {
        if (lastDir->son[dir[i]]->type)
            return false;
        if (!can_create(dynamic_cast<DirFile *>(lastDir->son[dir[i]]), dir, i + 1, size))
            return false;
    }
    if (lastDir->sonLimit && lastDir->sonLimit - lastDir->sonSize < size)
        return false;
    return true;
}

void create_file(const vector<string> &dir, LL size)
{
    DirFile *lastDir = root;
    for (int i = 0; i != dir.size(); ++i)
    {
        if (i == dir.size() - 1)
        {
            if (lastDir->get_son(dir[i]))
            {
                OrdFile *oldFile = dynamic_cast<OrdFile *>(lastDir->son[dir[i]]);
                oldFile->size += size;
                lastDir->dirSize += size;
                lastDir->sonSize += size;
            }
            else
            {
                OrdFile *newFile = new OrdFile(dir[i], lastDir, size);
                lastDir->add_son(newFile);
            }
        }
        else
        {
            if (lastDir->get_son(dir[i]))
            {
                lastDir->sonSize += size;
                lastDir = dynamic_cast<DirFile *>(lastDir->son[dir[i]]);
            }
            else
            {
                DirFile *newFile = new DirFile(dir[i], lastDir);
                lastDir->add_son(newFile, size);
                lastDir = dynamic_cast<DirFile *>(lastDir->son[dir[i]]);
            }
        }
    }
}

bool quota_file(const vector<string> &dir, const LL dsize, const LL rsize)
{
    DirFile *lastDir = root;
    for (int i = 0; i != dir.size(); ++i)
    {
        if (lastDir->get_son(dir[i]))
        {
            if (lastDir->son[dir[i]]->type)
                return false;
        }
        else
            return false;
        lastDir = dynamic_cast<DirFile *>(lastDir->son[dir[i]]);
    }
    if ((rsize && lastDir->sonSize > rsize) || (dsize && lastDir->dirSize > dsize))
        return false;
    lastDir->sonLimit = rsize;
    lastDir->dirLimit = dsize;
    return true;
}

bool delete_file(DirFile *lastDir, const vector<string> &dir, int i, LL &size)
{
    if (i == dir.size() - 1)
    {
        if (lastDir->get_son(dir[i]))
        {
            if (lastDir->son[dir[i]]->type)
            {
                size = dynamic_cast<OrdFile *>(lastDir->son[dir[i]])->size;
                lastDir->dirSize -= size;
            }
            else
                size = dynamic_cast<DirFile *>(lastDir->son[dir[i]])->sonSize;
            lastDir->sonSize -= size;
            delete lastDir->son[dir[i]];
            lastDir->son.erase(dir[i]);
            return true;
        }
        else
            return false;
    }
    if (!lastDir->get_son(dir[i]) || lastDir->son[dir[i]]->type)
        return false;
    if (delete_file(dynamic_cast<DirFile *>(lastDir->son[dir[i]]), dir, i + 1, size))
    {
        lastDir->sonSize -= size;
        return true;
    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    root = new DirFile("/", nullptr);
    while (T--)
    {
        char op[3];
        scanf("%s", op);
        if (op[0] == 'C')
        {
            string dir;
            cin >> dir;
            LL size;
            cin >> size;
            vector<string> dirList(0);
            split_dir(dir, dirList);
            if (!can_create(root, dirList, 0, size))
                puts("N");
            else
            {
                puts("Y");
                create_file(dirList, size);
            }
        }
        else if (op[0] == 'Q')
        {
            string dir;
            cin >> dir;
            LL dsize, rsize;
            cin >> dsize >> rsize;
            vector<string> dirList(0);
            if (dir.size() != 1)
                split_dir(dir, dirList);
            if (!quota_file(dirList, dsize, rsize))
                puts("N");
            else
                puts("Y");
        }
        else
        {
            string dir;
            cin >> dir;
            vector<string> dirList(0);
            split_dir(dir, dirList);
            puts("Y");
            LL temp;
            delete_file(root, dirList, 0, temp);
        }
    }
    delete root;
    return 0;
}

202012-4 食材运输

求最大值的最小值，想到二分：判断在某一个时间限制之内能不能运完所有的货。

从某一个点开始运输某一种货物的最短距离可以搜索一遍来算，是总距离-最长的支路。

然后货的种类很少，转化成状压 DP，f[j][k]表示对于前j个点，能否运输状态为k的货物。

方程有点难写，具体看代码吧，注意j要倒着遍历，原因类似 01 背包。

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

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 = 110;
int n, m, K, need[MAXN], length[MAXN][11], canTrans[MAXN];
bool f[MAXN][1<<10];
struct Edge
{
    int v, val;
};
vector<Edge> edge[MAXN];
int totalDis;

pair<int, bool> dfs(int u, int fa, int type)
{
    pair<int, bool> ret = make_pair(0, false);
    for (auto &e : edge[u])
    {
        if (e.v == fa)
            continue;
        auto result = dfs(e.v, u, type);
        if (((need[e.v] >> type) & 1) | result.second)
        {
            ret.first = max(result.first + e.val, ret.first);
            totalDis += e.val;
            ret.second = true;
        }
    }
    return ret;
}

void init()
{
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < K; ++j)
        {
            totalDis = 0;
            auto ret = dfs(i, 0, j);
            length[i][j] = totalDis * 2 - ret.first;
        }
}

bool chk(int x)
{
    memset(canTrans, 0, sizeof(canTrans));
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < K; ++j)
            if (length[i][j] <= x)
                canTrans[i] |= (1 << j);
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= 1; --j)
            for (int k = 0; k < (1 << K); ++k)
                f[j][k | canTrans[i]] |= f[j - 1][k];
    return f[m][(1 << K) - 1];
}

int solve()
{
    int l = 1, r = 1e8, ans;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (chk(mid))
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    return ans;
}

int main()
{
    n = read();
    m = read();
    K = read();
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < K; ++j)
            if (read())
                need[i] |= (1 << j);
    for (int i = 1; i < n; ++i)
    {
        int u = read(), v = read(), val = read();
        edge[u].push_back((Edge){v, val});
        edge[v].push_back((Edge){u, val});
    }
    init();
    printf("%d\n", solve());
    return 0;
}

202012-5 星际旅行

线段树模板题，好几个标记，其中坐标轴变换类似维护一个模 3 的加法标记。维护的时候先维护坐标轴标记，再维护乘法标记，最后维护加法标记。

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef double db;

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 = 40010, MOD = 1e9 + 7;

int n, m;
vector<pair<int, int>> queryList;

struct Query
{
    int op, l, r;
    LL a[3];
} query[MAXN];

class SegTree
{
private:
    int lbound[MAXN << 4], rbound[MAXN << 4];
    LL sumVal[MAXN << 4][3], addVal[MAXN << 4][3], mulVal[MAXN << 4];
    int addAxis[MAXN << 4], sumAxis[MAXN << 4];
    inline int adjust_axis(int i, int o)
    {
        return (i + sumAxis[o]) % 3;
    }
    void push_down(int o)
    {
        int lc = o << 1, rc = (o << 1) | 1;
        if (addAxis[o])
        {
            addAxis[lc] = (addAxis[lc] + addAxis[o]) % 3;
            addAxis[rc] = (addAxis[rc] + addAxis[o]) % 3;
            sumAxis[lc] = (sumAxis[lc] + addAxis[o]) % 3;
            sumAxis[rc] = (sumAxis[rc] + addAxis[o]) % 3;
            addAxis[o] = 0;
        }
        if (mulVal[o] != 1)
        {
            mulVal[lc] = (mulVal[lc] * mulVal[o]) % MOD;
            mulVal[rc] = (mulVal[rc] * mulVal[o]) % MOD;
            for (int i = 0; i < 3; ++i)
            {
                addVal[lc][i] = addVal[lc][i] * mulVal[o] % MOD;
                addVal[rc][i] = addVal[rc][i] * mulVal[o] % MOD;
                sumVal[lc][i] = (sumVal[lc][i] * mulVal[o]) % MOD;
                sumVal[rc][i] = (sumVal[rc][i] * mulVal[o]) % MOD;
            }
            mulVal[o] = 1;
        }
        for (int i = 0; i < 3; ++i)
        {
            if (addVal[o][adjust_axis(i, o)])
            {
                addVal[lc][adjust_axis(i, lc)] = (addVal[lc][adjust_axis(i, lc)] + addVal[o][adjust_axis(i, o)]) % MOD;
                addVal[rc][adjust_axis(i, rc)] = (addVal[rc][adjust_axis(i, rc)] + addVal[o][adjust_axis(i, o)]) % MOD;
                sumVal[lc][adjust_axis(i, lc)] = (sumVal[lc][adjust_axis(i, lc)] + (rbound[lc] - lbound[lc] + 1) * addVal[o][adjust_axis(i, o)] % MOD) % MOD;
                sumVal[rc][adjust_axis(i, rc)] = (sumVal[rc][adjust_axis(i, rc)] + (rbound[rc] - lbound[rc] + 1) * addVal[o][adjust_axis(i, o)] % MOD) % MOD;
                addVal[o][adjust_axis(i, o)] = 0;
            }
        }
    }

public:
    struct Ans
    {
        LL sum[3];
        Ans(LL x = 0, LL y = 0, LL z = 0)
        {
            sum[0] = x;
            sum[1] = y;
            sum[2] = z;
        }
        const LL &operator[](const int &x) const
        {
            return sum[x];
        }
        LL &operator[](const int &x)
        {
            return sum[x];
        }
        Ans operator+(const Ans &b) const
        {
            return Ans((sum[0] + b[0]) % MOD, (sum[1] + b[1]) % MOD, (sum[2] + b[2]) % MOD);
        }
    };
    void build(int o, int L, int R)
    {
        int lc = o << 1, rc = (o << 1) | 1, M = (L + R) >> 1;
        mulVal[o] = 1;
        lbound[o] = queryList[L - 1].first;
        rbound[o] = queryList[R - 1].second;
        if (L == R)
            return;
        build(lc, L, M);
        build(rc, M + 1, R);
    }
    void update_val(int o, const int &queryID)
    {
        int lc = o << 1, rc = (o << 1) | 1;
        if (query[queryID].l <= lbound[o] && query[queryID].r >= rbound[o])
        {
            if (query[queryID].op == 1)
            {
                for (int i = 0; i < 3; ++i)
                {
                    addVal[o][adjust_axis(i, o)] = (addVal[o][adjust_axis(i, o)] + query[queryID].a[i]) % MOD;
                    sumVal[o][adjust_axis(i, o)] = (sumVal[o][adjust_axis(i, o)] + query[queryID].a[i] * (rbound[o] - lbound[o] + 1) % MOD) % MOD;
                }
            }
            else if (query[queryID].op == 2)
            {
                for (int i = 0; i < 3; ++i)
                {
                    addVal[o][i] = addVal[o][i] * query[queryID].a[0] % MOD;
                    sumVal[o][i] = sumVal[o][i] * query[queryID].a[0] % MOD;
                }
                mulVal[o] = mulVal[o] * query[queryID].a[0] % MOD;
            }
            else
            {
                addAxis[o] = (addAxis[o] + 1) % 3;
                sumAxis[o] = (sumAxis[o] + 1) % 3;
            }
            return;
        }
        push_down(o);
        if (query[queryID].l <= rbound[lc])
            update_val(lc, queryID);
        if (query[queryID].r >= lbound[rc])
            update_val(rc, queryID);
        for (int i = 0; i < 3; ++i)
            sumVal[o][adjust_axis(i, o)] = (sumVal[lc][adjust_axis(i, lc)] + sumVal[rc][adjust_axis(i, rc)]) % MOD;
    }
    Ans query_sum(int o, const int &queryID)
    {
        int lc = o << 1, rc = (o << 1) | 1;
        if (query[queryID].l <= lbound[o] && query[queryID].r >= rbound[o])
            return (Ans){sumVal[o][adjust_axis(0, o)], sumVal[o][adjust_axis(1, o)], sumVal[o][adjust_axis(2, o)]};
        push_down(o);
        Ans ans;
        if (query[queryID].l <= rbound[lc])
            ans = query_sum(lc, queryID);
        if (query[queryID].r >= lbound[rc])
            ans = ans + query_sum(rc, queryID);
        for (int i = 0; i < 3; ++i)
            sumVal[o][adjust_axis(i, o)] = (sumVal[lc][adjust_axis(i, lc)] + sumVal[rc][adjust_axis(i, rc)]) % MOD;
        return ans;
    }
} Tree;

int main()
{
    n = read();
    m = read();
    vector<int> nodeList;
    nodeList.push_back(1);
    nodeList.push_back(n);
    for (int i = 1; i <= m; ++i)
    {
        query[i].op = read();
        query[i].l = read();
        query[i].r = read();
        if (query[i].op == 1)
        {
            for (int j = 0; j < 3; ++j)
                query[i].a[j] = read();
        }
        else if (query[i].op == 2)
            query[i].a[0] = read();
        nodeList.push_back(query[i].l);
        nodeList.push_back(query[i].r);
    }
    sort(nodeList.begin(), nodeList.end());
    nodeList.resize(unique(nodeList.begin(), nodeList.end()) - nodeList.begin());
    for (int i = 0; i < nodeList.size(); ++i)
    {
        if (i != 0)
            if (nodeList[i - 1] < nodeList[i] - 1)
                queryList.emplace_back(nodeList[i - 1] + 1, nodeList[i] - 1);
        queryList.emplace_back(nodeList[i], nodeList[i]);
    }
    Tree.build(1, 1, queryList.size());
    for (int i = 1; i <= m; ++i)
    {
        if (query[i].op <= 3)
            Tree.update_val(1, i);
        else
        {
            auto ans = Tree.query_sum(1, i);
            printf("%lld\n", ((ans[0] * ans[0] % MOD + ans[1] * ans[1] % MOD) % MOD + ans[2] * ans[2] % MOD) % MOD);
        }
    }
    return 0;
}

要是我去年考这套题恐怕要完犊子

CSP 202012 题解

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

作者

xqmmcqs

发布于

2021-03-19

更新于

2023-03-29

许可协议

#

评论

目录

最新文章

分类

Your browser is out-of-date!

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

×

×