主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
2022.11.19模拟赛
最后更新于 2025-07-12 14:18:47
作者
Ethanzyt
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
# noip2020 模拟赛 day1 $$ \begin{array}{|l|l|l|l|l|} \hline \text { 题目名称 } & \text { A } & \text { B } & \text { C } & \text { D } \\ \hline \text { 题目类型 } & \text { 传统型 } & \text { 传统型 } & \text { 传统型 } & \text { 传统型 } \\ \hline \text { 目录 } & \text { A } & \text { B } & \text { C } & \text{ D } \\ \hline \text { 可执行文件名 } & \text { A } & \text { B } & \text { C } & \text{ D } \\ \hline \text { 输入文件名 } & \text { A.in } & \text { B.in } & \text { C.in } & \text { D.in } \\ \hline \text { 输出文件名 } & \text { A.out } & \text { B.out } & \text { C.out } & \text { D.out }\\ \hline \text { 每个测试点时限 } & 1 \mathrm{s} & 1 \mathrm{s} & 2 \mathrm{s} & 1 \mathrm{s} \\ \hline \text { 内存限制 } & 128 \mathrm{MB} & 128 \mathrm{MB} & 256 \mathrm{MB} & 256 \mathrm{MB} \\ \hline \end{array} $$ 提交源程序文件名 $$ \begin{array}{|l|l|l|l|l|} \hline \text { 对于 C++ 语言} & \text { A.} \mathrm{cpp} & \text { B.} \mathrm{cpp} & \text { C.} \mathrm{cpp} & \text { D.} \mathrm{cpp} \\ \hline \end{array} $$ 编译选项额外添加 $$ \text{-std=c++11 -O2} $$ ## A ### 题目描述 给定长度为 $n$ 的序列 $\{a\}_{i=1}^n$ 和正整数 $k$，定义它的**桶**为序列 $\{b\}_{i=1}^n$，其中 $b_i$ 为序列 $a$ 中 $i$ 的出现次数。一次操作将序列 $a$ 变为它的桶，求 $k$ 次操作之后的序列 $a$。 ### 输入格式 第一行，两个正整数 $n,k$。 第 $i+1$ 行 $(1\le i\le n)$，一个正整数 $a_i$。 ### 输出格式 一行，$n$ 个自然数，表示 $k$ 次操作之后的序列 $a$。 ### 样例1 ``` 5 1 1 2 3 4 5 ``` ``` 1 1 1 1 1 ``` ### 样例2 ``` 1 1000000 1 ``` ``` 1 ``` ### 数据范围 **本题捆绑测试并子任务依赖** 对于所有数据，$n,k\le 10^6,a_i\le n$。 - Subtask 1 (40 分)：$nk\le 10^7$。 - Subtask 2 (60 分)：无特殊限制。 ## B ### 题目描述 给定 $n$ 个非空序列 $\{a_i\}^{l_i}_{j=1}$，定义 $f(a)$ 表示按顺序将序列 $a$ 的元素插入严格递增的[单调栈](https://oi-wiki.org/ds/monotonous-stack/)，最后得到的栈的大小。定义 $a+b$ 是将序列 $a,b$ 拼接而成的序列。求 $\sum_{i=1}^n\sum_{j=1}^{n} f(a_i+a_j)$。 如果你考试的环境没有网：$\{a_i\}_{i=1}^l$ 的单调栈大小为 $\sum_{i=1}^l \prod_{j=i+1}^{l} [a_j > a_i]$ 。 ### 输入格式 第一行，一个正整数 $n$。 第 $i+1$ 行 $(1\le i\le n)$，一个正整数 $l_i$，之后 $l_i$ 个正整数 $a_{i,j}$。 ### 输出格式 一个正整数，表示答案。 ### 样例1 ``` 2 6 1 1 4 5 1 4 2 1 9 ``` ``` 8 ``` ### 样例2 ``` 3 8 1 9 2 6 0 8 1 8 11 1 3 3 1 8 8 5 4 2 2 4 9 9 9 8 2 4 4 8 5 3 ``` ``` 28 ``` ### 数据范围 **本题捆绑测试并子任务依赖** 对于所有数据，$\sum l_i\le 10^6,a_{i,j}\le 10^9$。 - Subtask 1 (10 分)：$n\le 20,l_i\le 100$。 - Subtask 2 (20 分)：$n\le 20$。 - Subtask 3 (20 分)：$n\le 5000$。 - Subtask 4 (20 分)：$a_{i,j}\le 10$。 - Subtask 5 (30 分)：无特殊限制。 ## C 给定正整数 $n$。对于由 $1$ 到 $n$ 的正整数构成的集合的所有子集，你需要把它染成黑色或白色。 要满足限制：若 $S_1$ 和 $S_2$ 的颜色相同，则 $S_1\cup S_2$ 的颜色也应与 $S_1$ 的颜色相同。 对于每个集合，把它染黑和染白都有对应的代价。请求出总代价的最小值。 ### 输入格式 第一行一个正整数 $n$。 第二行，$2^n$ 个整数 $b_i$，第 $i$ 个数表示将第 $(i-1)$ 个集合染成黑色的代价。 第三行，$2^n$ 个整数 $w_i$，第 $i$ 个数表示将第 $(i-1)$ 个集合染成白色的代价。 （注：第 $i$ 个集合包含 $j$，当且仅当 $i$ 在二进制表示下的第 $j$ 位是 $1$。） ### 输出格式 一行一个整数表示总代价的最小值。 ### 样例 ``` 2 3 -1 4 -1 -5 9 -2 6 ``` ``` -9 ``` ### 数据范围 **本题捆绑测试并子任务依赖** 对于全部数据，$1\le n\le 20,-10^9\le b_i,w_i\le 10^9$。 * Subtask 1 (20 分): $n\le 4$。 * Subtask 2 (30 分): $n\le 15$。 * Subtask 3 (30 分): $n\le 18$。 * Subtask 4 (20 分): 无特殊限制。 ## D 给定正整数 $n$ 和两个长度均为 $n$ 的正整数序列 $a,b$。 每次你可以选择两个正整数 $x,y$（不一定不等），满足 $x,y$ 都在 $a$ 中出现过，然后将 $x$ 在 $a$ 中第一次出现的位置的值改成 $y$。 现在你要把 $a$ 变得和 $b$ 一样，请给出一种方案，或者判断无解。 你的方案使用的操作次数不应超过 $10^6$。 **注意：你不需要最小化操作次数。若有多种方案，可以给出任意一种。** ### 输入格式 第一行一个正整数 $n$。 第二行，$n$ 个整数 $a_i$。 第三行，$n$ 个整数 $b_i$。 ### 输出格式 第一行，一个字符串 $\texttt{YES}$ 或 $\texttt{NO}$。前者表示有解，后者表示无解。 若无解，则输出不应包含别的信息。 若有解，则第二行包含一个非负整数 $m$，表示你的方案的操作次数。 接下来 $m$ 行，每行两个正整数 $x,y$，表示一次操作。 ### 样例1 ``` 3 1 2 3 2 2 2 ``` ``` YES 2 1 2 3 2 ``` ### 样例2 ``` 3 1 2 3 2 3 3 ``` ``` NO ``` ### 数据范围与提示 **本题捆绑测试并子任务依赖** 对于所有数据，$1\le n\le 100,1\le a_i,b_i\le n$。 * Subtask 1 (10 分): $n\le 5$。 * Subtask 2 (40 分): 至多只有两种数在 $a$ 或 $b$ 中出现过。 * Subtask 3 (50 分): 无特殊限制。
正在渲染内容...
点赞
0
收藏
0
