Thy's Blog

题目传送门 题目大意 题目很简单，就是求一堆数的和是否为完全平方数，但是有几个需要注意得点： 数据最大可以到 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 的大小呢？ ...

二叉搜索树 www.luogu.com.cn 定义 二叉搜索树（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)。 操作过程 定义 对于一个二叉搜索树的每一个节点，都要存储以下几样东西： 左子树节点和右子树节点：l 和 r 这一个节点上存储的权值：val 表示这个节点权值出现次数的计数器：cnt 代表这个树上的大小（即子树和自己大小之和）：size 123456struct BST{ ...

题目大意 给定两个长度均为 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 ...

题目简述 www.luogu.com.cn 给出一个 n×mn \times mn×m 的二维数组，求出最长的一条滑坡，使得这条滑坡的高度会依次减少。 解题思路 原始DFS 这是一道 DFS\text{DFS}DFS 搜索题，同样也可以使用 DP\text{DP}DP 来做。 这里用DFS。 可以先双重循环这个二维数组上的每个点，在每个点上进行周围四个点的搜索（同时也要注意边界条件）。 可以设定两个偏移数组如下。 1int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; 1234567891011121314151617int dfs(int x, int y){ if (s[x][y]) return s[x][y]; s[x][y] = 1; for (int i = 0; i <= 3; i++) { int xx = dx[i] + x; int yy = dy[i] + y; if (xx & ...

www.luogu.com.cn 基本思路 深度优先搜索（DFS） 由于题目数据很小（6≤n≤136 \le n \le 136≤n≤13），我们可以采用打表深度优先搜索的方式完成这道题。 定义四个布尔数组分别表示表格的行，列，两个对角线上是否有旗子存在。 如图所示。 抽象代码如下↓ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <bits/stdc++.h>using namespace std;const int N = 50;//常量记得开大一点int n, sum, a[N], b[N], c[N], d[N];// n:网格大小 sum:方案总数// a,b,c,d数组分别代表行，列，左下到右上的对角线，左上到右下的对角线void dfs(int i) // 核心代码{ if (i > n) // 判断是否到达边界 { if (sum <= 2) / ...

使用 scanf / printf 在默认情况下，std::cin/std::cout 是极为迟缓的读入/输出方式，而 scanf/printf 比 std::cin/std::cout 快得多。 然而有的时候使用scanf/printf进行输入输出十分繁琐，因此我们可以采取取消同步流的方式直接使用std::cin/cout。 取消同步流传输 std::ios::sync_with_stdio(false)可以用来关闭stdio的兼容并解除std::cin和std::cout的绑定，从而达到较快的输入和输出。 但是在这样做之后要注意不能同时使用 std::cin 和 scanf，也不能同时使用 std::cout 和 printf，但是可以同时使用 std::cin 和 printf，也可以同时使用 scanf 和 std::cout。 std::cin.tie(0),cout.tie(0)可以用来解除std::cin和std::cout之间的绑定，从而进一步优化输入和输出。 但是要注意使用了这个以后不能再使用std::cout << endl原因在于endl不仅有换行的功 ...