CCF GESP 2024年6月认证 C++ 6级
题目描述
小杨想要计算由 $m$ 个小写字母组成的字符串的得分。
小杨设置了一个包含 $n$ 个正整数的计分序列 $A=[a_1,a_2,\ldots,a_n]$，如果字符串的一个子串由 $k(1\leq k \leq n)$ 个 $\texttt{abc}$ 首尾相接组成，那么能够得到分数 $a_k$，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。
例如，假设 $n=3$，字符串 $\texttt{dabcabcabcabzabc}$ 的所有可能计分方式如下：
- $\texttt{d+abc+abcabc+abz+abc}$ 或者 $\texttt{d+abcabc+abc+abz+abc}$，其中 $\texttt{d}$ 和 $\texttt{abz}$ 不计算得分，总得分为 $a_1+a_2+a_1$。
- $\texttt{d+abc+abc+abc+abz+abc}$，总得分为 $a_1+a_1+a_1+a_1$。
- $\texttt{d+abcabcabc+abz+abc}$，总得分为 $a_3+a_1$。
小杨想知道对于给定的字符串，最大总得分是多少。
输入格式
第一行包含一个正整数 $n$，代表计分序列 $A$ 的长度。
第二行包含 $n$ 个正整数，代表计分序列 $A$。
第三行包含一个正整数 $m$，代表字符串的长度。
第四行包含一个由 $m$ 个小写字母组成的字符串。
输出格式
输出一个整数，代表给定字符串的最大总得分。
样例说明
样例 1
3
3 1 2
13
dabcabcabcabz9最优的计分方式为 d+abc+abc+abc+abz，总得分为 $a_1+a_1+a_1$，共 9 分。
数据范围
对于全部数据，保证有 $1\leq n\leq 20$，$1\leq m\leq 10^5$，$1\leq a_i\leq 1000$。
题目描述
小杨有一棵包含 $n$ 个节点的二叉树，且根节点的编号为 $1$。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。
小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。
输入格式
第一行一个正整数 $n$，表示二叉树的节点数量。
第二行 $(n-1)$ 个正整数，第 $i$（$1\le i\le n-1$）个数表示编号为 $(i+1)$ 的节点的父亲节点编号，数据保证是一棵二叉树。
第三行一个长度为 $n$ 的 $\texttt{01}$ 串，从左到右第 $i$（$1\le i\le n$）位如果为 $\texttt{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。
第四行一个正整数 $q$，表示操作次数。
接下来 $q$ 行每行一个正整数 $a_i$（$1\le a_i\le n$），表示第 $i$ 次操作选择的节点编号。
输出格式
输出一行一个长度为 $n$ 的 $\texttt{01}$ 串，表示 $q$ 次操作全部完成之后每个节点的颜色。从左到右第 $i$（$1\le i\le n$） 位如果为 $\texttt{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。
样例说明
样例 1
6
3 1 1 3 4
100101
3
1
3
2010000第一次操作后，节点颜色为：011010
第二次操作后，节点颜色为：000000
第三次操作后，节点颜色为：010000
数据范围
对于全部数据，保证有 $1 \le n,q \le 10^5$。