Thy's Blog

题目传送门 前置知识：排序 + 逆序对 题目大意 数线上有 nnn 个人，第 iii 个人在点 a×ia \times ia×i，想去点 b×ib \times ib×i。对于每个人来说，a×i<b×ia \times i \lt b \times ia×i<b×i 以及所有人的起点和终点都是不同的（也就是说，所有的 2n2n2n 数 a×1,a×2,…,a×n,b×1,b×2,…,b×na \times 1, a \times 2, \dots, a \times n, b \times 1, b \times 2, \dots, b \times na×1,a×2,…,a×n,b×1,b×2,…,b×n 都是不同的）。 所有的人将以每秒 111 个单位的速度同时开始移动，直到到达终点 bib_ibi​。当两个人在同一点相遇时，他们会互相问候一次。会有多少次打招呼？ 请注意，即使一个人到达了最终点，他仍然可以向其他人打招呼。 解题思路 画图后可以看出，由于 a×i<b×ia \times i \lt b \times ia×i<b×i，所有人都在去往右边走， ...

Romantic Glasses 解题思路 题目说的很清楚了，求是否存在 LLL 和 $ R$，使 aLa_LaL​ 到 aRa_RaR​ 中奇数下标的数之和等于偶数下标的数之和，如果存在输出 Yes，否则输出 No。 方法一：前缀和 + 暴力 抛开时间复杂度（n2n ^ 2n2）不谈，在输入过程中根据下标奇偶性预处理前缀和数组，再通过双重循环判断即可。 123456for (int i = 1; i <= n; i ++) { int x; cin >> x; if (i & 1) pre[i] = pre[i - 2] + x; else pre[i] = pre[i - 2] + x; } 方法二：前缀和 + map 仔细想想不难看出，我们可以仅在一个前缀和数组上双向处理，如果 iii 为奇则加上这个数，为偶则减去这个数。此时求出的前缀和 preipre_iprei​ 就是 从 111 到 iii 之中奇数下标之和与偶数下标之和之差。如果存在 prei−1=prejpre_{i - ...

题目传送门 题目大意 给定一个只有五个字母的字符串，拆分成特定的音节并且输出。 解题思路 通过题目可以知道，两种音节分别为 CV\texttt{CV}CV 和 CVC\texttt{CVC}CVC。两种音节不同在于他们的后缀不同，如果正向搜寻，那么需要分类讨论，正难则反，因此我们可以逆序遍历求解答案。 定义一个 vector 数组，将字母和 . 加入进去，最后翻转输出即可（由于最后一个字符一定是 .，所以从第二个开始遍历） AC Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667// Problem: D. Unnatural Language Processing// Contest: Codeforces - Codeforces Round 918 (Div. 4)// URL: https://codeforces.com/contest/1915/problem/D// ...

题目传送门 题目大意 题目很简单，就是求一堆数的和是否为完全平方数，但是有几个需要注意得点： 数据最大可以到 2⋅10142 \cdot 10 ^ {14}2⋅1014，因此要开 long long。 如果使用数学函数 sqrt，在数据为 long long 的时候会出错，所以要手写平方根函数（我 WA 了好多次才发现的）。 AC Code 1234567891011121314151617181920212223242526272829303132333435363738394041// Problem: C. Can I Square?// Contest: Codeforces - Codeforces Round 918 (Div. 4)// URL: https://codeforces.com/contest/1915/problem/C// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include <bits/stdc+ ...

题目大意 爱丽丝和鲍勃想出了下面这个游戏：玩家轮流玩，从爱丽丝开始。轮到一个玩家时，他选择一种颜色 iii ，这样双方都至少有一个这种颜色的弹珠。然后玩家丢弃一个颜色为 iii 的弹珠，而对手则丢弃所有颜色为 iii 的弹珠。如果没有颜色 iii 使得双方都至少有一颗该颜色的弹珠，游戏就结束了。 游戏的得分是游戏结束时爱丽丝剩余弹珠数与鲍勃剩余弹珠数之差。换句话说，游戏的得分等于 (A−B)(A-B)(A−B) ，其中 AAA 是爱丽丝拥有的弹珠数， BBB 是游戏结束时鲍勃拥有的弹珠数。爱丽丝希望得分最大化，而鲍勃希望得分最小化。 求出得分的最大值。 解题思路 读题后不难看出这是一道博弈搜索题，数据并不大，因此我们可以直接用搜索即可。但是搜索过不了 Hard 版，因此我来讲讲贪心的思路。 双方都想要让对方的弹珠变少，可以想出第一个贪心是让双方优先选择对方弹珠数量最多的颜色减去，可以通过第一个样例，但是第二个就错了，为什么呢？因为对方的弹珠数量可能相同，此时要尽量保护好自己的弹珠数量。 细想后由此可以想出第二个贪心，每一个下标 iii 的两个权值 aia_iai​ 和 bib_ibi​ ...

题目传送门 思路 先来看一下构造要求，核心思路是围绕着第三点要求展开的： 2×∑i=1n∣ai−bi∣≤S2 \times \sum\limits_{i=1}^{n} |a_i-b_i| \leq S 2×i=1∑n​∣ai​−bi​∣≤S 由于 S=∑i=1naiS = \sum\limits_{i=1}^{n} a_{i}S=i=1∑n​ai​，我们可以先不妨设 bi≤aib_i \le a_ibi​≤ai​ 将绝对值展开，得到：对于每一个 iii，都满足 ⌊ai2⌋≤bi≤ai\left \lfloor \frac{a_i}{2} \right \rfloor \le b_i \le a_i⌊2ai​​⌋≤bi​≤ai​，同时通过二进制的性质可以得出，在范围 [⌊ai2⌋,ai]\left [ \left \lfloor \frac{a_i}{2} \right \rfloor , a_i \right ][⌊2ai​​⌋,ai​] 当中必然存在一个 2k2^k2k，因此我们只要让每一个 bib_ibi​ 都等于 2k2^k2k 即可。 那么应该如何找到这个 kkk 的大小呢？ ...

二叉搜索树 Definition 二叉搜索树（Binary Search Tree\text{Binary Search Tree}Binary Search Tree）是一种形状如二叉树的数据结构，用于快速查找和增加删除操作，它有如下几个特殊性质： 空树是二叉搜索树。 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 对于一个二叉搜索树，进行操作所花费的平均时间和这个二叉树的高度成正比。对于一个有 nnn 个结点的二叉搜索树中，这些操作的最优时间复杂度为 O(log⁡n)O(\log n)O(logn)，最坏为 O(n)O(n)O(n)​。 Define 对于一个二叉搜索树的每一个节点，都要存储以下几样东西： 左子树节点和右子树节点：l 和 r 这一个节点上存储的权值：val 表示这个节点权值出现次数的计数器：cnt 代表这个树上的大小（即子树和自己大小之和）：size 123456struct BST{ int l, ...

题目大意 给定两个长度均为 nnn 的单调不上升的序列 SSS 和 PPP，让 Si(1≤i≤n)S_{i}(1 \le i \le n)Si​(1≤i≤n) 中的每一个元素加上 Pj(1≤j≤n)P_{j}(1 \le j \le n)Pj​(1≤j≤n)，使得原 SSS 序列中的第 DDD 个数经过降序排序后的排名最靠前。 解题思路 方法一（二分查找） 通过题目不难看出，如果要使 SDS_{D}SD​ 最靠前，那么要加上 P1P_{1}P1​（因为 PPP 是降序排序的）。其次，通过贪心的思想，让比 SDS_{D}SD​ 大的所有数列都加上一个最大可以使得和小于 SD+P1S_{D} + P_{1}SD​+P1​ 的数列 PjP_{j}Pj​。 由于两个序列都满足单调性，因此我们可以使用二分的思想完成：即通过每次二分查找搜索到最优解，再使用一个 bool 数组记录下已经使用过的序列数，直到用完了第二大的 PPP 序列或者第 iii 个数直接大于 SD+P1S_{D} + P_{1}SD​+P1​ ，此时输出 i+1i + 1i+1。 此时复杂度为 O(nlog⁡n)O(n \log ...

www.luogu.com.cn 题目大意： 有一个队列，其中的每项工作 iii 都有两个值：最早可以处理的时间 tit_{i}ti​ 和处理所需要的时间 did_{i}di​，等待队列中的数量不可以超过 bbb，求出每个工作完成时间（无法完成则输出 −1-1−1）。 模拟思路 这是一道结合了队列的模拟题，自然可以使用 queue\text{queue}queue 来做，但首先我们要搞清一下几点： 如何判断当前时间点有多少件事情可以完成。 如何根据队列中的等待数判断是否可以完成。 如何计算下一个事情前的完成时间。 我们可以定义一个一维数组 bg[N]\text{bg[N]}bg[N]，其中 bgibg_{i}bgi​ 表示第 iii 个事情时最早的可以做的时间，而由于每个事情都有自己的最早可处理时间 tit_{i}ti​，因此 max⁡(bgi−1,ti)\max(bg_{i - 1}, t_{i})max(bgi−1​,ti​) 即为第 iii 个事情的实际开始时间。显然可以得出转移方程： bgi=max⁡(bgi−1+di−1,ti)bg_{i} = \max(bg ...

题目简述 www.luogu.com.cn 题目思路 这道题是很经典的动态规划题，最重要的是得出状态转移方程。 划分阶段 设定两个数组 fN,gNf_{N}, g_{N}fN​,gN​，分别表示填满前 2×i2 \times i2×i 格子的方案数以及填满前 i×2+1i \times 2+1i×2+1 格子的方案数。 答案即为 fnf_{n}fn​。 状态转移方程 1×21 \times 21×2的瓷砖的摆放方式有两种：横着摆和竖着摆。 因此第一种瓷砖的状态转移方程为： fi=fi−1+fi−2f_{i} = f_{i - 1} + f_{i - 2} fi​=fi−1​+fi−2​ 由于L型瓷砖可以进行旋转摆放，故一共有3种可能： 通过两个L型瓷砖互补摆完。 仅在1×21\times 21×2的瓷砖后继续摆放。 故第二种瓷砖的状态转移方程为： gi=gi−1+fi−1g_{i} = g_{i - 1} + f_{i - 1} gi​=gi−1​+fi−1​ 综上所述 状态转移方程为： fn=fn−1+fn−2+2×gn−2f_{n} = f_{n - 1} + f_{n ...