杂题选讲

KidA · 2023-01-09 19:53:00 · 个人记录

注：此文已永久停更

大概会记录下一些比较经典、有思维难度或者有趣的题目，也会记录算法模板，大家有时间欢迎来看看。

平常每周差不多会更一次，假期频率可能会更高些。不要催更啊qwq。

• P1596

  属于是比较经典的搜索题了。

  思路很常规，用二维字符数组存下整个地图，然后从水坑开始dfs，把搜索过的地方变成 '.' 即可，用不着 vis 数组了。

  倒是做题时还发现 void 函数 return 时并不会什么也不返回，而是返回上次搜到的点。其实是看题解才知道的

  还是贴下代码吧，免得我连dfs的模板都忘了wtcl。

  CODE

• P3372

  线段树模板1。

  话说我怎么只会刷模板啊QAQ

  把代码放这儿备忘：

  CODE

• P1531

  第一次手切线段树题，当然要纪念一下QAQ

  CODE

  基本和模板差不多，只是去掉了 \texttt{lazy tag}，然后 \text{pushup} 时改为求最大值就行了。

• P4139

  手切紫题！

  思维难度不是很大，主要是根据扩展欧拉定理：

  来进行递归求解，重点在于求 b \bmod φ(p)。

  注意这个式子仅适用于 b \geq φ(p) 的情况，但对于本题来说只要满足这种情况就够了。

  CODE

• P2197

  nim游戏模板题。

  我们知道，在nim游戏中要先手必胜，则每堆石子数的异或和（即 A_1\ \text{xor}\ A_2\ \text{xor}\ A_3\ \text{xor}\ \cdot\cdot\cdot\ \text{xor}\ A_n ）必须 \neq 0。证明可以参考《算法竞赛进阶指南》,这里就不详细说了。

  那么对于本题仅需 O(n) 求出异或和，若 \neq 0 则输出 Yes ，否则输出 No 即可。

  CODE

• P1196

  一个比较好的边带权并查集题目，就是题目背景有点长，影响读题。

  对于 get 函数，维护一个数组 dis，令 dis_x 表示 x 与 fa_x 间隔几个战舰。然后一边进行路径压缩，一边更新 dis 数组即可。

  对于 merge 函数，再维护一个数组 size，令 size_x 表示 x 所在列的战舰个数。在合并 x 与 y 所在的列后，顺便将 dis_x 更新为 size_y，然后将 size_y 更新为 size_y + size_x。

  然后其他的就和模板没什么区别了~

  CODE

• P1100

  简单位运算题。

  开始想得比较复杂，其实 n<<16 就是将低位移到了高位，n>>16 就是将高位移到了低位，两者相加就是答案了。

  位运算需要注意勤加括号。

  CODE

• P2386

  还算刑的dp，但是蒟蒻还是被卡了一个多小时。。。

  令 \text{dp}(i,j) 为把 i 个苹果放入 j 个盘子中的方案数。

  首先特判：

  • 当苹果数 \leq 1 或盘子数 = 1 时，仅有一种方案。（注意苹果数是 \leq 1）

  • 当苹果数 < 盘子数时，方案数为 \text{dp}(i,i)。

  特判完了以后就考虑两种转移路径：

  • 有盘子空着，则方案数为 \text{dp}(i,j-1);

  • 所有盘子都有苹果，则方案数为 \text{dp}(i-j,j)。

  然后就没了~

  CODE

• P2392

  我又来水dfs题了qwq。

  既然kkk能同时做两道题，那么我们就可以把每一科目分为尽量相等的两个子集。用dfs求出完成时间不小于总时间一半的其中一个子集，然后让 ans 加上它的完成时间即可（应该很好理解吧）。

  你问我的做法为什么和深基一模一样？别问，问就是我抄了深基的。。。

  CODE

• P1309

  感觉好久没更了qwq。

  比较水的一道排序题，题解基本上都是归并。

  但可以使用归并实现的stable_sort来代替快排实现的sort。因为sort的快排在“比较”这一操作上的常数较大，而归并排序则是稳定的。详见这里。

  另外值得注意的是，题目中说每次比赛开始前和结束后均要进行一次排序，但其实每两轮比赛中间的两次排序实际上只有一次是有意义的。因此，我们仅需首先在所有比赛开始前进行一次排序，接着在每轮比赛之后进行一次排序即可。

  CODE

• P5514

  因为我们知道异或运算的结果一定小于加法运算，所以最优的分组方案就是所有数都分在一组中。

  直接 O(n) 朴素求出异或和即可。

  CODE

• P3987

  朴素算法 + 玄学卡常

  最 \texttt{navie} 的代码大家应该都会写的吧。。。

  接下来就是惊心动魄的卡常时间~

  • 快读快写

    这个没啥好说的，具体实现可见我的程序。

  • 位运算

    使用位运算代替 \times \div \bmod，能提高程序的运算效率。

    如：

    • a \times 2$ 等价于 $a << 1
    • a \div 2$ 等价于 $a >> 1
    • a \bmod 2$ 等价于 $a \space \& \space 1
    • ......

  • 循环展开

    循环展开是通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

    如这份求和的代码：

    for(int i=1;i<=n;i++) sum+=a[i];

    循环展开后就变成这样：

    int i;
    for(i=1;i<=n-5;i+=6){
       sum+=a[i];
       sum+=a[i+1];
       sum+=a[i+2];
       sum+=a[i+3];
       sum+=a[i+4];
       sum+=a[i+5];
    }
    while(n-i+1) sum[i]+=a[i],i++; //处理还没加完的部分

  • 三目运算符

    三目运算符可以代替 \texttt{if} ，来增进判断的效率。

    格式为 a?b:c，意为若 \texttt{a} 成立，则执行 \texttt{b}，否则执行 \texttt{c}。

  • 其他

    还有一些卡常小技巧：

    • 把不需要开 \texttt{long long} 的果断换成 \texttt{int}。（很重要！！！）

    • 把所有变量的定义提到最外面，并加上 \texttt{register} 前缀。

  然后就珂以愉快地 \texttt{AC} 此题啦~

  CODE

  感谢@王熙文提供的思路以及快读快写模板！

• P3383

  复习了一下埃氏筛。

  埃氏筛的流程：

  STEP1：将 1 划去；

  STEP2：将下一个未划去的数字的所有倍数划去；

  STEP3：重复STEP2、3，直到再也没有可以划去的数字。

  这样就排出了从 1 到 n 的有序质数表，对于本题，仅需对于每个询问的 x，输出质数表的第 x 项即可，时间复杂度 O(n \log \log n)，几乎接近于 O(n)，因此是能过的。

  CODE

• P1130

  令 $f[i][j]$ 表示走到第 $i$ 行第 $j$ 列时所取得的最小价值。考虑两种不同情况下的转移路径： - 若当前在第 $1$ 行，则 $f[i][j]$ 就可能由 $f[m][j-1]$（上一列的最后一个）与 $f[i][j-1]$（上一列的第一个）转移过来。在这两种当中取最小值并加上这个位置的原价值就得到了 $f[i][j]$。 - 若当前不在第一行，则 $f[i][j]$ 就可能由 $f[i][j-1]$（它左边的）与 $f[i-1][j-1]$（它左上方的）转移过来。同样在这两种当中取最小值并加上这个位置的原价值就得到了 $f[i][j]$。 分析完以后，这道题就变得非常简单了。 最后还有一些坑点： - 注意 $dp$ 顺序，大循环是列，小循环是行。 - 最终结果并非为 $f[m][n]$，应该是最后一列的所有值取 $\min$。 - 读入是要先读入列数 $n$，再读入行数 $m$。 [***CODE***](https://www.luogu.com.cn/paste/m0qrnljz)

• T246517

  考虑 dp，令 f[i][j] 表示前 i 枚硬币，能否凑出 j 元。

  预处理时将每一枚硬币都存入 b 数组中，并算出硬币总额，记作 m。

  分两类情况讨论：

  • 特殊情况：若 j-b[i]=0（即只要用一枚 b[i] 即可凑出 j 元），或 f[i-1][j]=0（即用 i-1 枚硬币便可凑出 j 元），则 f[i][j]=true。

  • 一般情况：若 j-b[i]>0 且 f[i-1][j-b[i]]，则 f[i][j]=true

  最后，仅需看最后一行有几个 1 即可。

  CODE

• P8815

  鸽子XOF终于开始补CSP的题了

  考虑分治计算表达式。首先找出第一层优先级最高的运算符号，分别递归左右两边进行计算，直到左/右半边只有数字就回溯。每一层的值都是它左右半边的值做这一层运算符操作所得的结果。

  如何计算短路？可以计算出左半边结果后，若 ans=1 且符号为 \mid，则构成了或短路；若 ans=0 且符号为 \And，则构成了与短路。

  为了优化时间复杂度，可以对字符串进行预处理，算出对于每个位置与其同层且离它最近的运算符。这将计算时的复杂度降至 O(n)。

  CODE

• P1144

  基础最短路问题，考虑使用 \text{BFS} 进行解决。

  因为边权均为 1，所以每个结点的最短路就是它在 \text{BFS} 中的深度。如果恰好有一个节点的深度是当前节点的深度 -1，则当前节点的最短路条数即为它上一层节点的最短路条数 +1。

  于是在用 \text{BFS} 遍历图的过程中用 dep 和 cnt 数组分别记录当前节点的深度与最短路条数即可。

  CODE

• P7075

  恶心的模拟题o_o，需要极强的计算能力&思维能力，调了我整整一晚上。

  显然数据范围不能够支持你一天一天地累加计算，因此我们考虑采用另一种方法。

  我们可以算出，格里高利历每 400 年有 146097 天，儒略历每 4 年有 1461 天。（别问我怎么算出来的）

  据此，我们便可先预处理格里高利历前 400 年每天的年月日（方便以后确定月份与日期），分别将日期、月份与年份存入 day、mon 与 yea 数组中。

  接着在主体部分，先判断历法（r \le 2299160 为儒略历，否则为格里高利历），若为格里高利历，则先让起始日期变为 1200 年（r - 2159351），算出当前日期距离起始日期有多少年（year = r \div 146097 \times 400 + 1200），再求出除去这些年后还剩多少天（r \bmod year）。

  对于儒略历，则也是一样，先算出当前日期距离起始日期（4712）有多少年（year = r \div 1461 \times 4 - 4712），再求出除去这些年后还剩多少天（r \bmod year）。

  因为日期与月份具有周期性，今天的日期与月份和若干年前是一样的。所以利用这个性质，可以得知当前日期的日期与月份就是 day[r] 与 mon[r]（注意是 \bmod 以后的 r）。

  我们规定：公元后第 x 年为 x 年，公元前第 x 年为 1 - x 年。因此，我们还要判断当前日期是在公元前还是公元后。若 yea[r]（\bmod 以后的 r）+ \space year \ge 0，说明是公元后；否则是公元前。

  需要注意的是，这道题读入最好用scanf，不仅速度快，还支持格式化输出；同时记得把 146097、1461 等这样的数字保存为常量，这样随取随用更方便。

  CODE

• P1807

  注意遍历前需将 $\texttt{d}$ 数组设为 $-1$。 [***CODE***](https://www.luogu.com.cn/paste/l4ckaqcc)

• P1434

  普通 \text{DFS} \ + 记忆化搜索。

  对于每个点进行 \text{DFS}，每次向四个方向搜索，同时更新最长路即可。

  CODE