题解 洛谷 U327217 寻找千泷の小翼龙
2023-08-18 996 字 6 分钟

题解 洛谷 U327217 寻找千泷の小翼龙

题解 洛谷 U327217 寻找千泷の小翼龙本题题面 原题（本题由该题数据加强而来）：USACO Training 6.1.1 Postal VansTiring of their idyllic fields, the cows have moved to a new suburb. The suburb is a rectangular grid of streets with a post office at its Northwest corner. It has four avenues running East-West and $n(1\le n\le 10^{18})$ str
题解 AT_arc132_a Permutation Grid
2023-08-18 568 字 3 分钟

题解 AT_arc132_a Permutation Grid

题解 AT_arc132_a Permutation Grid简要题意：给定两个数列 $R$ 和 $C$ ，$R$ 和 $C$ 内均有 $n$ 个元素，要求根据 $R$ 和 $C$ 对一个 $n\times n$ 的矩阵进行染色，使得第 $i$ 行有 $R_i$ 个黑色块，第 $j$ 列有 $C_j$ 个黑色块。最后，$R$ 和 $C$ 均为 $1-n$ 的一个排列。 反思分析：有个伸臂和一个神犇在赛时没有看到最后一个条件导致两个人想出了各种各样复杂又奇葩的做法，我不说是谁 有了排列那这不成水题了，我们以样例为例（这什么话）把它按顺序重新排列一下，就会变成这样（我们用$W$表示白色，$B$表
题解 洛谷 P1045 [NOIP2003 普及组] 麦森数
2023-08-18 598 字 3 分钟

题解 洛谷 P1045 [NOIP2003 普及组] 麦森数

题解 洛谷 P1045 [NOIP2003 普及组] 麦森数简要题意：给定一个数$p$，求$2^p$-1的位数和后500位的值，其中$p\in [1\times10^3,3.1\times10^6]$。 策略分析：我们可以将这个问题分为两步来处理，第一步求出位数，第二步求后$500$位 求出位数：首先有一个非常平凡的结论：$10^k$的位数为$k+1$。那么一个$10^k$的数的位数也等于$lg10^k$，设$n =2^p$，因为不存在最后一位为$0$的$2^p$的数，所以$2^p-1$的位数一定与$2^p$的位数相同。我们希望能够将$10^k$所具有的性质应用在$2^p$中，设$1
题解 BNDS OJ 1575 哈夫曼
2023-08-18 804 字 4 分钟

题解 BNDS OJ 1575 哈夫曼

题解 BNDS OJ 1575 哈夫曼前置芝士：哈夫曼树 简要题意：给定一个仅包含小写字母的字符序列，要求输出这个序列的哈夫曼编码 分析/求解：哈夫曼建树时要求每次配对权值最小的两个儿子，它们配对所产生的父亲也要重新与其它的树进行比较，所以我们很容易可以想到通过优先队列来维护当前所有的树，具体细节见代码 AC代码：12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
题解 CF1413D Shurikens
2023-08-18 762 字 4 分钟

题解 CF1413D Shurikens

题解 CF1413D Shurikens简要题意给定一个 $n$ 和 $2n$ 个操作，第一种操作 “+” 表示从 $1$ ~ $n$ 中选择一个数插入序列，第二种操作 “ - $x$” 表示从当前序列中删除 $x$ 且 $x$ 为当前序列里的最小值，根据给出的操作来推断将数插入序列的合法顺序。 策略分析不合法情况不合法的情况有两种。第一种是当在连续取出的两个值中，后取出的值比前取出的值小，因为每次必须取出序列里最小的值，所以这种情况显然是不符合要求的。第二种情况是取出的操作数比放入的操作数多，这样显然也是不合法的。 如何处理合法情况我们看到这种有进有出的结构能够想到什么，怎么才能反转操作呢？
题解 洛谷 CF958E1 Guard Duty (easy)
2023-08-18 301 字 2 分钟

题解 洛谷 CF958E1 Guard Duty (easy)

题解 CF958E1 Guard Duty (easy)这是一道诈骗题简要题意给你 $n$ 个 $R$ 点和 $m$ 个 $B$ 点，现在给你这些点的坐标，问能否在这两类点间连线来构造出一种情况使得一个线段两边分别是 $R$ 和 $B$。 策略分析不合法情况当 $n\ne m$ 时，我们顺次连接 $R$ 和 $B$，先不考虑相交不相交，发现连到最后要么 $R$ 和 $R$ 相连，要么 $B$ 和 $B$ 相连，一定不合法。 合法情况当 $n=m$ 时，答案一定合法 正确性证明我们设有点 $R_1,R_2,B_1,B_2$，那么我们加上边 $(R_1,B_1),(R_2,B_1),(R
题解 洛谷 P3514 [POI2011] LIZ-Lollipop
2023-08-18 971 字 5 分钟

题解 洛谷 P3514 [POI2011] LIZ-Lollipop

P3514 [POI2011] LIZ-Lollipop简要题意给定一个只有 $1$ 和 $2$ 的序列，给出 $m$ 次询问，每次询问给出一个数 $k$，查询序列中有没有一个子串和为 $k$，如果有则输出区间两端点，如果没有输出 NIE。 策略分析本题最重要的条件就是该序列中只含有 $1$ 和 $2$，因为这个条件，我们就可以得到下面这个性质：若 $k$ 可以被表示，则 $k-2$ 也一定可以被表示。这个性质很容易被证明。我们很容易发现，一个区间的两端点有三种情况，全为 $1$，全为 $2$ 以及一边 $1$ 一边 $2$。那么当两边存在 $2$ 时，只需要减掉这个 $2$ 即可；如果是两个