Q779’s Blog

模拟赛题讲解[11] 来自 xpp 2022-08-04 noi.ac #2731 题目描述： xpp在玩祖玛游戏，他心血来潮想根据祖玛游戏出一个题。 给一个序列 \(a_1,a_2,\dots,a_n\) ，你每次可以选择相同且相邻的三个数删除他们，如果序列中存在这样相同且相邻的三个数，xpp将不断将他们删除，xpp想知道最后序列中还剩几个数呢？ 输入格式： 第一行一个正整数 \(T(1\le T\le 10)\) 表示数据组数。 对于每组数据，第一行一个正整数 \(n\) 表示序列长度，第二行 \(n\) 个正整数表示 \(a[1\dots n]\)。 输出格式： 对于每组数据输出一行，表示答案。 输入1： 2 7 1 1 1 2 2 2 3 8 1 2 2 2 1 1 3 2 输出1： 1 2 数据规模： 对于 \(30\%\) 的数据，\(3\le n\le 10,~1\le a_i\le 10\) 对于 \(60\%\) 的数据，\(3\le n\le 10^3,~1\le a_i\le 10^3\) 对于 \(100\%\) 的数据，\(1\le a_i\le 10^...

模拟赛题讲解[10] 来自 xpp 2022-08-03 noi.ac #2723 题目描述 lzr给了xpp一个字符串 \(s\) 和一个字符串 \(t\) ，xpp想通过 \(s\) 构造出 \(t\) ，构造方式为xpp每次选择 \(s\) 的一个子序列，放到当前串的后面，xpp想知道他需要构造多少次才能构造出 \(t\) 呢？ 输入格式 第一行一个数 \(T\) 表示数据组数。 对于每组数据第一行一个字符串 \(s\) ，第二行一个字符串 \(t\) ，含义见题目描述 输出格式 每组数据输出一行表示次数。如果不能输出 \(-1\)。 输入1： 3 aabce ace abacaba aax ty yyt 输出1： 1 -1 3 数据规模： 对于 \(30\%\) 的数据， \(\texttt{字符串长度} \le 100\) 对于 \(100\%\) 的数据，\(\texttt{字符串长度} \le 10^5,~1\le T\le 10\) 题解： 暴力的解法就是遍历 \(t\) ，然后维护一个指针 \(p\) 在 \(s\) 上跳 仔细观察可以发现，如果 \(s=\tt...

CF553A Kyoya and Colored Balls 题解 题目链接：CF553A Kyoya and Colored Balls 题意： 一个袋子中有 \(n\) 个彩球，他们用 \(k\) 种不同的颜色染色。颜色被从 \(1\) 到 \(k\) 编号。同一种颜色的球看成是一样的。现在从袋中一个一个的拿出球来，直到拿完所有的球。对于所有颜色为 \(i(1 \le i \le k-1)\) 的球，他的最后一个球总是在编号比他大的球拿完之前拿完，问这样情况有多少种，答案对 \(10^9+7\) 取模。 输入单组测试数据。 第一行给出一个整数 \(k(1 \le k \le 1000)\)，表示球的种类。 接下来 \(k\) 行，每行一个整数 \(c_i\)，表示第 \(i\) 种颜色的球有 \(c_i\) 个 \((1 \le c_i \le 1000)\)。 球的总数目不超过 \(1000\)。 发烧真的无聊所以就写写题目啥的吧23333 考虑依次插入每种颜色的球，不妨设现在要插入的球颜色为 \(i\) ，有 \(x_i\) 个 设 \(n_i\) 为之前已经插入的球...

初赛复习 较为笼统而简洁的概括。 考试只要细心，不会的猜，就能过线。 IT发展历史 第一台计算机：ENIAC，1946年 应用：计算，数据储存处理，通信，辅助工作等 第一个程序员：Ada（女），有为此命名的程序语言 图灵奖（计算机），菲尔兹奖（数学），诺贝尔奖（物化生经济文学和平） ACM（美国计算机学会）IEEE（电气电子工程师学会）CCF（懂得都懂） 图灵奖由ACM设立，获得图灵奖的华人学者只有姚期智一人，名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵，是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。 计算机组成 冯诺依曼结构： 输入设备：将信息输入进计算机的是输入设备 输出设备：将计算机的信息输出给人的是输出设备 特例：触摸屏既是输入设备又是输出设备 CPU字长：32位/64位 （CPU一次能并行处理的二进制位数，一定是8的倍数） 位（Bit）：一个01 字节（Byte）：八个01 1PiB=1024TiB, 1TiB=1024GiB, 1GiB=1024KiB, 1KiB=1024Byte, 1Byte=8Bit 1Mib=1024Kib, ...

CF852B Neural Network country 题解 题目链接：CF852B Neural Network country 题意： 给定一个包含一个出发点 \(s\) ，终止点 \(t\) 以及 \(L\) 层 \(V_1,V_2,\dots,V_L\) ，每层都包含 \(N\) 个顶点的带边权有向分层图。从出发点 \(s\) 到第一层 \(V_1\) 中每个顶点都有一条带权边，从最后一层 \(V_L\) 到终止点 \(t\) 中每个顶点也都有一条带权边。对于所有 \(1\le i<L\) ，第 \(i\) 层的每个顶点到第 \(i+1\) 层中的每个顶点都会连有一条带权有向边，且第 \(i\) 层的每个顶点连出的边权完全相同，并且任意相邻两层之间所连边权完全相同。可以参照样例解释中链接内图示结合样例帮助理解。 现给出该分层图，你需要计算有多少种从 \(s\) 走到 \(t\) 的路径，使得路径上经过边权值和能被 \(M\) 整除？由于答案可能过大，你需要将答案对 \(10^9+7\) 取模后输出。 对于 \(100\%\) 的数据，\(1\le N\le 1...

CF691E Xor-sequences 题解 题目链接：CF691E Xor-sequences 题意：给定大小为 \(n\) 的集合 \(\{a_1,\dots,a_n\}\)，从集合中选择 \(k\) 个数组成一个序列 \(x_1 , \dots , x_k\) (可以重复选择)，使得序列满足 \(x_i\) 与 \(x_i +1\) 异或的二进制中 \(1\) 的个数是 \(3\) 的倍数 问长度为 \(k\) 的满足条件的序列的种数，答案对 \(10^9 + 7\)取模。 \(1\le n\le 100,~1\le k,a_i \le 10^{18}\) 设 \(f_{i,j}\) 表示序列长度为 \(i\) 且最后一个数为 \(a_j\) 时的方案数，则 \[ f_{0,j}=1 \\\\f_{i,j}=\sum_{1\le k \le n}f_{i-1,k}\times g_{k,j} \] 其中 \(g_{k,j}\) 表示 \(\left[3 \mid (a_k \oplus a_j)_{\texttt{ 2进制下1的数量}}\right]\) 可以发现这个...

Atcoder Educational DP Contest R Walk 题解 题目链接：Atcoder Educational DP Contest R Walk 题意： 给一张 \(N\) 个结点的有向简单图，给出邻接矩阵 \(A\) ，求长度为 \(K\) 的路径条数，答案对 \(10^9+7\) 取模。 \(1 \le N \le 50,1\le K \le 10^{18}\) ， \(a_{i,j}\) is 0 or 1 ，\(a_{i,i}=0\) 设 \(f_{k,i,j}\) 表示 \(i\) 到 \(j\) 路径长为 \(k\) 的方案数，则 \[ f_{k,i,j}=\sum_{(s,j) \in E} f_{k-1,i,s} \] 之所以不从 \(k-t\) 转移，而从 \(k-1\) 转移，是因为可能存在重复计数 比如这张图 就可能重复计数 上面的式子可以进一步化简 \[ f_{k,i,j} = \sum_{1\le s \le n} f_{k-1,i,s}\times A_{s,j} \] 这个形式是不是很熟悉？ \[ f^{0}_{i,j} ...

OI数学总结-基础公式&结论 施工中，咕咕咕… \(A(n) = 1 + \dfrac{1}{\sqrt{2}}+\dfrac{1}{\sqrt{3}}+\dots+\dfrac{1}{\sqrt{n}}\) ，积分逼近有 \(A(n) = \Theta(\sqrt{n})\) \(B(n) = 1+\sqrt{2}+\sqrt{3}+\dots\sqrt{n}\) ，积分逼近有 \(B(n) = \Theta(n\sqrt{n})\) 调和级数求和 \(C(n) = 1 + \dfrac{1}{2}+\dfrac{1}{3}+\dots+\dfrac{1}{n}\) ，积分逼近有 \(C(n) = \Theta(\ln n)\) 著名的巴塞尔问题，证明 \[ \displaystyle \zeta(2)= \sum_{n = 1}^{\infty} \frac{1}{n^2} =\lim_{n \to +\infty}\left( 1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\right)=\frac{\pi^2...

线性代数-矩阵 施工中，咕咕咕…. 矩阵乘法 1. 矩阵乘法的定义 矩阵乘法的定义 \[ (AB)_{i,j}=\sum_{k=1}^{m}A_{i,k}B_{k,j}\quad i\in[1,n],j\in[1,p] \] 一个 \(n \times m\) 的矩阵和 \(m\times p\) 的矩阵相乘，答案为一个 \(n \times p\) 的矩阵 注意，矩阵乘法没有叉乘的定义，因为叉乘通常是指在向量空间中的一种运算 列向量可以右乘矩阵（左乘需要转置为行向量），且乘积不一定相等：\(Mv \not\Leftrightarrow v^{\top}M\) 2. 快速手算 矩阵乘法的计算方法有很多种，这里提供两种方法。 第一种是传统的逆时针旋转右侧矩阵，可以在这里看动画演示。 第二种是 Roundgod 老师告诉我们的方法，如下 例： \[ \begin{bmatrix}1&2\\3&4\\\end{bmatrix} \times \begin{bmatrix}5&6\\7&8\\\end{bmatrix} \] 第一行： \[ \begin{...

ABC156E Roaming 题解 题目链接：ABC156E Roaming 题意： 翻译来自我们模拟赛，可能和原题有区别 输入两个数字 \(n,k\) ，初始时有 \(n\) 个盒子，每个盒子中都装着一个小球，\(n\) 个小球之间不可区分。现在你要进行下列操作恰好 \(k\) 次 选择任意一个盒子中的一个小球，将它放到一个不同的盒子中 你需要算出在 \(k\) 次操作之后，小球的不同的摆放方式有多少种，答案对 \(10^9+7\) 取模。两种摆放小球的方式被认为是不同的，当且仅当存在某一个盒子在两种摆放方式中放了不同个数的小球。 \(3 \le n \le 10^5,~2 \le k \le 10^9\) Roundgod老师：这道题需要很好的观察能力 注意到 \(k \ge n-1\) 时方案数等于 \(n-1\) 的方案数 因为至多 \(n-1\) 步就可以摆出所有的情况，例如 5,0,0,0,0 只要 \(4\) 步 而步数是可以浪费的，比如本来要把 \(1\) 的一个球移到 \(2\) ， 可以先移到 \(3\) 再移到 \(2\) ，这样就浪费了一步，这样...

ABC167E Colorful Blocks 题解 题目链接：ABC167E Colorful Blocks 题意： 翻译从我们模拟赛搬过来的，稍微有些不一样。 有 \(n\) 个小球按照编号为 \(1−n\) 从左至右放成一排，你现在要给每个小球染上 \(1−m\) 中的颜色，并且满足至多存在 \(k\) 对相邻位置上小球的颜色相同。 你需要输出一共有多少种不同的给小球染色的方案，两种染色方案被认为是不同的当且仅当两种方案中存在一个小球被染上了不同的颜色。由于答案可能过大，你需要对 \(998244353\) 取模后输出。 \(1 \le n,m \le 2\times 10^5,~0\le 0 \le n-1\) 简单组合数学。考虑 \(k\) 对相邻的情况， 其实就是在前 \(n-1\) 个球中选 \(k\) 个和它右边的合并 因此答案就是 \[ \sum_{i=0}^{k} m \times(m-1)^{n-i-1}\times \dbinom{n-1}{i} \] 前面的 \(m \times(m-1)^{n-i-1}\) 可能比较难理解 其实就是一个经典模型： ...

模拟赛题讲解[9] 来自 Roundgod 2022-07-29 noi.ac #2693 原题来自 ABC172E NEQ 问题描述： 给定 \(n,m\)，你需要计算满足以下条件的数组对 \(A=[a_1,a_2,\dots,a_n]\) 和 \(B=[b_1,b_2,\dots,b_n]\) 的个数: 对于所有 \(1\leq i\leq n\) ，都有 \(1\leq a_i\leq m\) 以及 \(1\leq b_i\leq m\). 对于所有 \(1\leq i\leq n\) ，都有 \(a_i\neq b_i\). 对于所有的 \(1\leq i\lt j\leq n\) ，都有 \(a_i\neq a_j\) 且 \(b_i\neq b_j\). 由于答案可能过大，你需要输出答案对 \(10^9+7\)取模后的值。 输入格式： 输入第一行包含一个整数 \(t(1\leq t\leq 10)\) ，表示数据的组数。 对于每组测试数据，输入为一行，包含两个整数 \(n,m\)。 输出格式： 对于每组测试数据，在一行中输出一个整数，表示答案。 输入1： 2 2 ...