作者: Ryan

87 篇文章

HDU 6406 Taotao Picks Apples 杭电多校第八场
题意 略 题解 由于这是一个不用维护原有序列的操作,我们可以考虑维护一个ST表进行RMQ查询。 这个RMQ是用来干什么呢? 根据题目数据范围,我们知道这道题不能容忍$\mathcal O(n^2)$及以上的算法 我们必须要在$\mathcal O(nlogn)$的时间复杂度下完成所有的操作。 维护一个dp数组,$dp[cur] = dp[first…
牛客多校第七场 Problem J Sudoku Subrectangles
题解 注意 这和数独不一样,是要求子矩阵中每一行 或 每一列的字符只出现一次 这个问题坑了不少人 剩下的按照官方题解就完成 • 注意到52种字符,子矩形最多52行,52列。 • 一个5252nm的做法是显然的,可以优化到52*nm。 • 枚举上下边界(最多差52) • 当左端点确定后,右端点的范围是连续的一段,并且单调 • 扫一遍即可,可以使用位运…
牛客多校第七场 Problem C Bit Compression
题意 初始长度$2^n$的01序列,要从^&|中选择n个运算符。 • 序列长度:$(2^n)\to (2^{n-1})\to ... \to 16\to 8\to 4\to 2\to 1$。 • 问有多少个可能,使得运算后剩下的一个字符为1。 题解 事实上这道题暴力就是标准做法,但是dfs的过程一定是$3^n$的,会超出题目要求时间。我们必…
Wannafly 15 Problem A 直角三棱锥
题解 题目可以转化为插板法求解。考虑当$x + y + z <= k$时满足题意,引入一个$a$ 变成了$x + y + z + a = k$然后我们需要求的便是${k+3}\choose{3}$。 注意到题目的数据范围,可以用__int128解决问题。 AC代码 #include <iostream> #include <…
HDU 4704 Sum 欧拉降幂
题解 利用数学方法中的“隔板法”,不难知道结果就是 $\displaystyle\sum_{k=0}^{n-1}{{n-1}\choose{k}}$ 这是二项式定理的展开式。所以,这道题就转换为求解$2^{n-1} \mod (10^9+7)$ AC代码 #include <iostream> #include <algorith…
HDU 6345 子串查询
题意 对于一个字符串s 有q个询问,对于每个询问有l,r,问的是在区间$[l,r]$中字典序最小子串的个数。 题解 易证字典序最小子串一定是一个字母,于是只需要统计在[l,r]范围内最小的字母出现的次数。 由于没有更新操作,我们可以直接处理出26个字母的前缀和。 时间复杂度$\mathcal O(26 * |S|)$ 如果用离线维护查询的最大最小值…
HDU 6356 Glad You Came Problem 1007 杭电多校第五场
题意 给定长为$n$的数组,初始值均为0 执行m个操作,每次操作的行为 如原题面 题解 很多人用线段树弄过去了,但是这个非常考验模板的水平,如果常数比较大这个方法就GG了 官方题解的解法说的不是很清楚,而根据官方标程的实现方式,实际上就是一个标准的RMQ逆向的过程。 首先对于RMQ 我们要学习什么是ST表。附录:ST表 然后我们在m次操作中,把一个…
牛客多校第一场 Problem D Two Graphs
题意 n个点,m1条边的图E1,n个点,m2条边的图E2。求图E2有多少子图跟图E1同构。 题解 由于题目数据范围不大考虑暴力枚举$n!$范围的所有结果。 答案除以自同构数。 AC代码 #include <iostream> #include <cstring> #include <algorithm> #inc…