2024-10-07 22:17 已编辑 Hogwarts School 前端工程师发布于北京

关注

题解

星星灯

引理1

对全是 $1$ 的两格操作一定没有意义，对全是 $0$ 的两格操作可以使得亮的灯的格数+2 ，对 $1$ 个 $0$ ， $1$ 个 $1$ 的两格操作可以使 $1$ 的位置发生变化（上下挪动或左右挪动）

task 1、2

此时行或列操作有一个无法使用，发现从左到右（从上到下）依次考虑所有的 $0$ ,如果有两个，直接消去，如果出现 $01$ 那么可以使用一个横操作使变成 $10$ 从而和后面的 $0$ 配对，模拟一下即可。

复杂度 $O(max(n,m))$

引理2

按照引理1的想法，我们总可以把 $0$ 先向右赶，再向下赶，那么我们发先每个位置最多一次作为竖操作的上面的方格，最多一次作为横操作的左格

task 3

考虑可以先 $2^{nm}$ 枚举哪些点做横操作，在原图上做相应操作，那么图可以用一个 $16$ 位的二进制串存下来，记出现的串的集合为 $S$

再对一张全是 $1$ 的图 $O(2^{nm})$ 的枚举哪些点做竖操作，得到的对应的二进制串为 $x$ , 看是否存在 $x \in S$ ，是的话即为 $Yes$

复杂度 $O(2^{nm+1})$

task 4

发现 $task_{3}$ 的每一行分开做完全没有影响， $O(2^n)$ 枚举每一行的操作，操作完后如果该位置仍为 $0$ 则做一个竖操作，然后处理下一行

复杂度 $O(mn2^{n})$

引理3

操作完每一行后，每一行要不剩一个 $0$ ，要么没有 $0$

task 5

依次考虑每一行，按照类似 $task_{1}$ 的从左往右做，考虑 引理3 然后从上到下把最后的 $0$ 往下赶

复杂度 $O(nm)$

引理4

因为不在乎操作次数，根据引理 $1$ 我们发现，我们总能找到方法改变偶数个 $0$ 的个数

task 6

统计 $0$ 的个数，偶数个则 $Yes$ 否则 $No$

复杂度 $O(nm)$

标程

#include <bits/stdc++.h>
using namespace std;

int const N = 2e3 + 10;
int n, m;
string s[N];

void sol() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (s[i][j] == '0') cnt++;
    if (cnt % 2 == 0) cout << "Yes" << "\n";
    else cout << "No" << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T) {
        T--;
        sol();
    }
    return 0;
}

星星路

容易发现，星星国是一棵以 $1$ 为根的树

task 1、2

考虑路径的结束点是哪个点，发现共有 $n$ 条路径，把他们对应的字符串存在来，比较 $O(n^2)$

复杂度 $O(n^2)$

task 3

此时树是一条链，考虑最长路一定字典序最大，直接输出即可

复杂度 $O(n)$

task 4、5

$task_{4}$ 是为大常数以及神奇做法的同学准备的

考虑我们每次可以扫当前点 $x$ 连接的所有点，设 $mx$ 为它可以一步走到的点里的最大字母是多少，那么考虑所有 $c_{y_i}=mx$ 的 $y_{i}$ ，那么可以把他们维护成一个可达集合 $S$ ，在当前步里选 $S$ 中的任何一个点都会拿到一个 $mx$ ，我们并不在意具体走了哪个

然后再考虑扫 $S$ 中的所有点，找出 $mx'$ ，维护新的 $S'$ ，一直这么做下去直到找出最大

复杂度 $O(n)$

标程

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int const N = 2e6 + 10;
struct stu1 {
    int y, nex;
} e[N * 2];
int n, k, lin[N], n1, cnt, a[N], m, b[N], m1;
char s[N], ans[N];

void work(int x, int y) {
    e[++cnt] = (stu1) {
        y, lin[x]
    };
    lin[x] = cnt;
}
void sol() {
    int mx;
    ans[++n1] = s[1];
    a[++m] = 1;
    while (m) {
        mx = -1;
        for (int j = 1; j <= m; j++)
            for (int i = lin[a[j]]; i; i = e[i].nex) mx = max(mx, s[e[i].y] - 'a');
        if (mx == -1) break;
        for (int j = 1; j <= m; j++)
            for (int i = lin[a[j]]; i; i = e[i].nex) {
                int y = e[i].y;
                if (mx == s[e[i].y] - 'a') b[++m1] = y;
            }
        ans[++n1] = mx + 'a';
        m = m1;
        for (int i = 1; i <= m; i++) a[i] = b[i];
        m1 = 0;
    }
}
int main() {
    scanf("%d%s", &n, s + 1);
    int x, y;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        work(x, y);
    }
    sol();
    printf("%s", ans + 1);
}

星星糕

首先可以把前四个操作合并，令 $a=a+b+c+d$ ，那么只有做饭和洗盘子两种操作

引理1

因为每个人的收益相同，每个人等待的时间相同，所以按客人到达的时间从早到晚上菜一定不劣

task 1

$O(2^n)$ 枚举每个时间做什么事，然后检验是否可行与计算收益

复杂度 $O(2^n)$

task 2

留给奇思妙想的一档部分分

task 3

不需要洗盘子，那么只需要维护 $c_{1},c_{2}$ 表示：”再做一个糕点需要的时间“和“当前还有多少个糕点”，再用队列维护等待着的客人的序列，只需要记录离开时间即可，用一个变量记录当前用餐的客人什么时候停止用餐

复杂度 $O(n)$

引理2

任何时间都可以做蛋糕，但不是任何时间都能洗盘子，盘子只有一个，没盘子就不能上菜，那么贪心考虑可以洗盘子的时间一定会洗盘子

task 4

客人上了菜就会吃完，相比 $task_{3}$ 不用维护停止用餐的时间，但是需要维护 $c_{3}$ 表示当前盘子还需要多久洗好

复杂度 $O(n)$

task 5

客人不会等待，那么不需要维护客人等待队列

复杂度 $O(n)$

task 6

综合 $task_{3},task_{4},task_{5}$ 即可

复杂度 $O(n)$

标程

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int const N = 1e5 + 10;
LL ans;
int n;
int c1, c2, t1; //多少面包 面包计时器 盘子计时器
int q1[N], q2[N]; //客人队列，收益队列

int main() {
    int x, a = 0, e, f, g, h, i;
    scanf("%d", &n);
    for (int i = 0; i < 4; i++) {
        scanf("%d", &x);
        a += x;
    }
    c2 = a;
    if (!a) c1 = 1e9;
    scanf("%d%d%d%d%d", &e, &f, &g, &h, &i);
    int l1 = 1, r1 = 0, l2 = 1, r2 = 0;
    for (int j = 1; j <= n; j++) {
        if (t1 <= n && t1) {
            t1--;
        } else {
            c2--;
            if (!c2) {
                c2 = a;
                c1++;
            }
        }
        if (j % e == 0) q1[++r1] = j + f; //来人
        if (j > q1[l1] && (l1 <= r1)) l1++; //不可能同时接待多个客人
        //同时接待首先要做面包不用时间 洗盘子不用时间 那客人来了就能接待
        if ((!t1) && c1 && (l1 <= r1)) {
            q2[++r2] = j + g;
            c1--;
            l1++;
            t1 = 1e9;
        }
        if ((l2 <= r2) && (q2[l2] <= j)) ans += h, l2++, t1 = i;
    }
    printf("%lld\n", ans);
    return 0;
}

星星树

task 1

依次枚举 $a,b,c$ 选择的点的编号，从 $1$ 号点开始 $dfs(1,k)$ ，维护一个 $w$ 表示还可以回溯的次数，如果回溯则 $w--$ ，并且把当前走到的点重新挪回 $1$ 号点，对搜出来的答案去重一下即可（可以令 $x$ = $a$ 的编号+ $b$ 的编号...然后放在unordered_map 中）

复杂度 $O(n^3)$

task 2

对于 $k=0$ 我们只需要枚举 $a,b$ 怎么选，记点 $x$ 的子树内的 $a,b,c$ 的个数分别为 $g_{x,0},g_{x,1},g_{x,2}$ ，设当前的 $b$ 选在 $y$ 号点，答案加上 $g_{y,2}$ 即可

对于 $k=1$ ，我们枚举 $a,b$ 怎么选后， $c$ 可以任选，故加 $g_{1,2}$ ,枚举 $b,c$ 怎么选后 $a$ 可以任选，故加 $g_{1,0}$ ，但是这么统计会把 $abc$ 在一条链上的情况多次计算，故再减 $k=0$ 的答案即可

对于 $k=2$ 三个点没有任何限制，答案为 $g_{1,0}\times g_{1,1}\times g_{1,2}$

复杂度瓶颈在枚举 $a,b$ 复杂度 $O(n^2)$

task 3

根据 $task_{2}$ 考虑可以只枚举 $b$ 选在 $y$ 处，那么 $a$ 只要选在 $1-b$ 的路径上就好,记点 $x$ 到 $1$ 的路径上的 $a,b,c$ 的个数分别为 $f_{x,0},f_{x,1},f_{x,2}$ ，那么答案为：

考虑所有位 $b$ 的点 $y$

$ans=\sum_{sign_{y}='b'}f_{y,0}\times g_{y,2}$

task 4

结合 $task_{2}$ , $task_{3}$ ，记 $ab,bc$ 链的个数分别为 $v_{1},v_{2}$ ， $k=0$ 的方案数为 $sum$

则

$v_{1}=\sum _{sign_{y}='b'}f_{y,0},v_{2}=\sum _{sign_{y}='c'}f_{y,1}$

$ans=v_{1}\times g_{1,2}+v_{2}\times g_{1,0}-sum$

复杂度 $O(n)$

task 6

做法同 $task_{3}$ 的 $k=2$

复杂度 $O(n)$

task 7,8

留给写法优美的 dfs

task 9

留给根号做法/被卡常的选手

task 10

正解，即 $task_{3}+task_{4}+task_{5}$ 的糅合

标程

#include<bits/stdc++.h>
#define LL unsigned long long
using namespace std;
int const N = 1e5 + 10;
struct stu1 {
    int y, nex;
} e[N * 2];
int n, k, lin[N], cnt, c[3], f[N][3], g[N][3];
char s[N];
LL ans;
void work(int x, int y) {
    e[++cnt] = (stu1) {
        y, lin[x]
    };
    lin[x] = cnt;
}
void dfs(int x, int fa) {
    f[x][s[x] - 'a']++;
    g[x][s[x] - 'a']++;
    for (int i = lin[x]; i; i = e[i].nex) {
        int y = e[i].y;
        if (y == fa) continue;
        memcpy(f[y], f[x], sizeof(f[x]));
        dfs(y, x);
        for (int j = 0; j < 3; j++) g[x][j] += g[y][j];
    }
    LL sum = 0;
    if (s[x] == 'b') {
        sum = 1ll * f[x][0] * g[x][2];
    }
    if (k == 0) ans += sum;
    if (k == 1) {
        ans -= sum;
        if (s[x] == 'b') ans += 1ll * f[x][0] * c[2];
        if (s[x] == 'c') ans += 1ll * f[x][1] * c[0];
    }
}
int main() {
    scanf("%d%d%s", &n, &k, s + 1);
    int x, y;
    for (int i = 1; i <= n; i++) c[s[i] - 'a']++;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        work(x, y);
        work(y, x);
    }
    if (k == 2) {
        printf("%lld\n", 1ll * c[0]*c[1]*c[2]);
        return 0;
    }
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}