照例x2

前两题没什么需要分析的

1341A Nastya and Rice

A.cpp
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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;

int cc[N];

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        fill(cc, cc + c + d + 1, 0);
        ++cc[max(0, (a - b) * n)];
        --cc[n * (a + b) + 1];
        int f = 0;
        for (int i = 1; i <= c + d; ++i) {
            cc[i] += cc[i - 1];
            if (i >= c - d && cc[i]) {
                f = 1;
                break;
            }
        }
        if (f) puts("Yes");
        else puts("No");
    }
    return 0;
}

1341B Nastya and Door

B.cpp
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 <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int cc[N], a[N];

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; ++i) {
            cin >> cc[i];
            a[i] = 0;
        }
        cc[n + 1] = cc[0] = INF32;
        for (int i = 1; i <= n; ++i) {
            if (cc[i] > cc[i - 1] && cc[i] > cc[i + 1]) {
                a[i] = 1;
            }
        }
        int ans = 0, tp = 0, id;
        for (int i = n; i > n + 1 - k; --i) {
            if (a[i]) ++tp;
        }
        for (int i = n + 1 - k; i > 0; --i) {
            if (ans <= tp) {
                id = i;
                ans = tp;
            }
            tp += a[i] - a[i + k - 2];
        }
        cout << ans + 1 << ' ' << id << endl;
    }
    return 0;
}

1341C Nastya and Strange Generator

（其实这题也没啥分析的）
对于$[1,x]$的一段，如果选择了一个位置$y$，那么必须将$[y,x]$填完再继续，因此将原串拆分成小段再判断就行，$O(n)$

C.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (int &i : a) cin >> i;
        int tt = 0;
        for (int i = n - 1, j; i >= 0; i = j) {
            j = i - 1;
            while (j >= 0 && a[j + 1] > a[j])
                --j;
            for (int k = j + 1; k <= i; ++k)
                b[tt++] = a[k];
        }
        if (is_sorted(b.begin(), b.end())) puts("Yes");
        else puts("No");
    }
    return 0;
}

1341D Nastya and Scoreboard

从左到右给出一些七段数码管，为$1$的位常亮，问如果恰好再添加$k$个亮的段，最大字典序的串是什么。

先通过位运算预处理每位数字，变成 $0\sim 9$ 是否可行以及需要多用的段数，然后进行背包。
$dp[i][j]$表示从后向前第$i$个数字用了$j$段是否可行，另外用一个数组保存路径，对于每位数字枚举的时候从 $0\sim 1$ 枚举，就可以保证大的数字靠左，$O(10nk)$。

D.cpp
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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;

int dp[N][N + 100];
pii to[N][N + 100];

int main() {
    int mp[10] = {0x77, 0x24, 0x5d, 0x6d, 0x2e, 0x6b, 0x7b, 0x25, 0x7f, 0x6f};

    int n, k;
    cin >> n >> k;
    vector<vector<pii>> a(n);
    string s;
    for (int i = 0, t; i < n; ++i) {
        cin >> s;
        t = 0;
        for (int j = 0; j < 7; ++j)
            t |= (s[j] - '0') << j;
        for (int j = 0; j < 10; ++j) {
            if ((t & mp[j]) == t) {
                bitset<8> aa(t ^ mp[j]);
                a[i].emplace_back(j, aa.count());
            }
        }
    }

    dp[0][0] = 1;
    for (int ii = 0; ii < n; ++ii) {
        int t = n - ii - 1;
        for (auto tp:a[t]) {
            for (int j = 0; j <= k; ++j) {
                if (!dp[ii][j])
                    continue;
                dp[ii + 1][j + tp.second] = 1;
                to[ii + 1][j + tp.second] = {j, tp.first};
            }
        }
    }

    if (!dp[n][k]) {
        cout << -1 << endl;
        return 0;
    }
    while (n) {
        cout << to[n][k].second;
        k = to[n][k].first;
        --n;
    }
    cout << endl;
    return 0;
}

1341E Nastya and Unexpected Guest

跟jls每天一个C++小技巧（见注释）
有$n$个路口，起始在$0$终点在$n$，有$m$个安全岛（就是马路中间等红灯的地方），每个红绿灯都是以$g,r,g,r…$时长进行红绿变化的，如果有绿灯，那么就必须移动，只有经过安全岛才能转向，问能否到达$n$，能到达的最短时间。

将状态抽象，一个灯的状态有$[0,g]$种，如果在不同轮到达同一状态只有最开始是最优的。那么将状态分成$m\times (g+1)$种，进行$bfs$，由于同一轮内要先遍历完，那么用双端队处理非常方便，$O(mg)$。

E.cpp
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;
typedef long long ll;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

int main() {
    using rec = tuple<int, int, int>;

    int n, m, r, g;
    cin >> n >> m;
    vector<int> d(m);
    for (int &i : d) cin >> i;
    sort(d.begin(), d.end());
    cin >> g >> r;

    vector<vector<int>> dis(m, vector<int> (g + 1, -1));
    deque<rec> q;
    q.emplace_back(0, 0, 0);
    while (!q.empty()) {
        auto[u, t, _dis] = q.front();  //Structured Binding Declaration
        q.pop_front();
        if (dis[u][t] != -1)
            continue;
        dis[u][t] = _dis;
        if (t == g)
            q.emplace_back(u, 0, _dis + 1);
        if (u != 0 && t + d[u] - d[u - 1] <= g)
            q.emplace_front(u - 1, t + d[u] - d[u - 1], _dis);
        if (u != m - 1 && t + d[u + 1] - d[u] <= g)
            q.emplace_front(u + 1, t + d[u + 1] - d[u], _dis);
    }
    ll ans = INF64;
    for (int i = 1; i <= g; ++i) {
        if (dis[m - 1][i] != -1) {
            ans = min(ans, ll(g + r) * dis[m - 1][i] + i);
        }
    }
    if (ans == INF64)
        ans = -1;
    cout << ans << endl;
    return 0;
}

1341F Nastya and Time Machine

有一棵以$1$为根的树，记位于节点$u$，当前时刻为$t$为$(u,t)$，现在每步可以向相连的结点移动，或不移动并回到$[0,t)$的任意时间点，要求不能出现两个相同的$(u,t)$，问遍历所有节点后再回到根的路径中最小的 $max (t_1,t_2…t_k)$ 是多少。

思考一下可以想到，对于一个节点$x$，他的度数为$deg_x$，由于一定会从 $x\to$邻居一次，加上从根到$x$，那么对于$x$，$t$至少需要$deg_x$，所以答案最小为 $max (deg_1,deg_2…deg_n)$。
接下来考虑如何构造，对于节点$x$，从第一次访问它到最后一次访问它的路径要满足： $(x,t_x),(son_1,t_x+1)…(son_1,t_x),(x,t_x+1),(son_2,t_x+2)…(x,t_x+deg_x)$，此时已经得到的大致的构造方案，但可能出现访问到叶子时 $t>max (deg_1,deg_2….)$，因此进入儿子后需要检查一下当前的 $t$，确保不超过答案。
$O(n)$。

F.cpp
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;
const int N = 1e5 + 5;

int mx;
vector<pii> ans;
vector<int> g[N];

void dfs(int u, int fa, int t) {
    ans.emplace_back(u, t);
    int cur = t, res = g[u].size() - (u != 1);
    for (int v : g[u]) {
        if (v == fa)continue;
        if (cur == mx) {
            cur = t - 1 - res;
            ans.emplace_back(u, cur);
        }
        dfs(v, u, cur + 1);
        ++cur; --res;
        ans.emplace_back(u, cur);
    }
    if (u != 1 && cur != t - 1)
        ans.emplace_back(u, t - 1);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        mx = max(mx, int(g[i].size()));
    }
    dfs(1, 0, 0);
    cout << ans.size() << endl;
    for (auto i : ans)
        cout << i.first << ' ' << i.second << endl;
    return 0;
}