Thy's Blog

题目大意 给定一个数组 a。进行至多一次操作，使得 a 数组中所有元素相同。如果代价为改变元素数量，求最小代价。 思路 非常简单的贪心，对于每次修改的区间 ai∼aja_i \sim a_jai​∼aj​，可以分为以下三种情况： 如果 a1≠ana_1 \neq a_na1​=an​，那么要修改的区间一定包括这两个点之一，我们只需要选择连续区间长度最长的即可。 如果 a1=ana_1 = a_na1​=an​，那么我们只要修改除了两端连续区间的所有点。 单词询问时间复杂度为 O(n)O(n)O(n)。 AC Code 1234567891011121314151617181920212223void solve(){ int res1 = 1, res2 = 1; cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; for (int i = 2; i <= n; i ++) { if (a[i] = ...

栈 STL模板 STL 中的 stack 容器提供了一众成员函数以供调用，常见的包括但不限于如下： 创建一个栈： stack<int> stk; 修改元素： stk.push(x); 将传入的参数插入到栈顶。 stk.pop(); 将栈顶的元素弹出。 查询： stk.top(); 返回栈顶的元素。 stk.empty(); 返回栈是否为空。 stk.size(); 返回栈中元素的数量。 123456789101112// 新建两个栈 st1 和 st2std::stack<int> st1, st2;// 为 st1 装入 1st1.push(1);// 将 st1 赋值给 st2st2 = st1;// 输出 st2 的栈顶元素cout << st2.top() << endl;// 输出: 1 数组模拟 通过两个变量 stk[N] 和 top 分别模拟栈的存储和栈顶下标，从而达到实现的目的。 创建一个栈： int stk[N], top; 修改元素： stk[++ top] = x; 将传入的参数插入到栈顶。 top ...

题目大意 给定两个长度均为 nnn 的序列 A,BA,BA,B。你可以进行任意次如下操作： 选择两个正整数 i,j∈[1,n]i,j \in [1,n]i,j∈[1,n]，交换 Ai,AjA_i,A_jAi​,Aj​ ，再交换 Bi,BjB_i,B_jBi​,Bj​。 请最小化两个序列中逆序对个数之和。 解题思路 贪心方式： 先将 AAA 序列由小到大排序，将 BBB 以对应的下标重新排序，此时 AAA 和 BBB 的逆序对之和最小。 证明： 对于任意的两对元素 aia_iai​ 和 aja_jaj​，bib_ibi​ 和 bjb_jbj​，无论如何交换，他们之间对应的数永远是固定的，不难看出，每对数对于逆序对的贡献只有 000 或 111 两种，则交换两对数对于逆序对的影响有三种： 从贡献为 000 到贡献为 222。 从贡献为 222 到贡献为 000。 不变，贡献均为 111。 通俗来说，只要让每对下标 iii 和 jjj 中最多只有 111 个贡献，那么任何一对数的贡献都不会多于交换后的贡献。 那么应该如何做到呢，贪心的核心就在于排序，让 AAA 序列由 ...

解题思路 很显然的贪心题，只需要判断每一个路程耗电量的大小进行选择即可，但是这道题同样可以用 DP 做（其实思路是一样的）。 我们定义一个数组 dpdpdp 表示到第 wiw_iwi​ 时候所耗费的最小电量，由于 dpidp_idpi​ 只可以通过 dpi−1dp_{i - 1}dpi−1​ 转移而来，并且分为两种情况：一直打开或者先关机后打开。可以得到： dpi=min⁡(dpi−1+(wi−wi−1)×a,dpi−1+b)dp_i = \min(dp_i - 1 + (w_i - w_{i - 1}) \times a, dp_{i - 1} + b) dpi​=min(dpi​−1+(wi​−wi−1​)×a,dpi−1​+b) 这时候便可以愉快的写代码了。 AC Code 1234567891011121314151617181920212223242526272829303132333435363738394041// Problem: C. Sending Messages// Contest: Codeforces - Codeforces Round 920 (Div. ...

题目大意 给定一个长度为 nnn 的 010101 序列，一共三种操作： 取一只新猫并将其放入盒子中（对于 iii 中的 bi=0b_i = 0bi​=0，指定 bi=1b_i = 1bi​=1）。 从盒子中取出一只猫，让它退休（对于 iii 中的 bi=1b_i = 1bi​=1，指定 bi=0b_i = 0bi​=0）。 将一只猫从一个盒子移到另一个盒子（对于 i,ji,ji,j 中的 bi=1,bj=0b_i = 1,b_j = 0bi​=1,bj​=0，指定 bi=0,nj=1b_i = 0,n_j = 1bi​=0,nj​=1）。 要求用最小的代价将该系列转换为指定序列。 解题思路 十分明显的贪心题，既然每一种操作都是等价的，我们就要让第一种操作和第二种操作的数量尽量减少，所以我们要让第三种情况尽可能多。不难想出以这种方式的话，第一种和第三种操作之和即为两个序列中 111 的个数之差，剩下需要改变的数量即为第三种操作。 AC Code 123456789101112131415161718192021222324252627282930313233343536 ...

题目大意 给定一个序列 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// ...