Thy's Blog

题目大意 给定一个序列 a1,a2,…,ana_1, a_2,\ldots, a_na1​,a2​,…,an​，首先 A 先选择至多 kkk 个数删除，然后 B 在剩下的数中选择至多 xxx 个数乘上 −1-1−1，加上剩余的数后，A 想要和尽可能大，B 想要和尽可能小。若两者都通过最佳决策，求结果为多少。 解题思路 不难看出这是一道贪心题，数组中较大的数对结果的影响更大，因此我们可以进行从大到小的排序。但是不可以想当然让两者都选择当前序列中最大的数进行操作（样例中有反例）。 仔细分析样例后不难看出，A 选择的个数不大相同，但是 B 一定是尽可能选择完最大的，这样子最后的结果才会最小化。 到这里思路就很显然了，遍历枚举一遍 A 选择的个数，把每一个结果取一个 max⁡\maxmax 即可。 你说循环求和会超时？用前缀和优化即可。 单次询问时间复杂度 O(nlog⁡n)O(n \log n)O(nlogn)。 公式详推 定义 prei=a1+a2+a3+…+aipre_i = a_1 + a_2 + a_3 + \ldots + a_iprei​=a1​+a2​+a3​+…+ai​，得出 ...

A* 算法 定义 A* 搜索算法（A*search algorithm\text{A*search algorithm}A*search algorithm）是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历（英文：Graph traversal\text{Graph traversal}Graph traversal）和最佳优先搜索算法（英文：Best-first search\text{Best-first search}Best-first search），亦是 BFS 的优化，用到了启发式搜索的思维。 启发式搜索（英文：heuristic search\text{heuristic search}heuristic search）是一种在普通搜索算法的基础上引入了启发式函数的搜索算法。 启发式函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。 过程 确定了起点 ststst 和终点 ededed，对于每个点 xxx，计算出从 ststst 开始的距离函数 ...

题目传送门 前置知识：排序 + 逆序对 题目大意 数线上有 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 ...