分类: C++

23 篇文章

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…
输入输出挂备份
备份一下自己的输入输出挂 输入输出数据量特别大的时候效果拔群 使用方法: int a; long long b; char c; string d; char str[100]; fin >> a >> b >> c >> d >> str << a << b &l…
HDU 6342 Problem K. Expression in Memories 杭电多校第四场
题意 解析题目的表达式是否合法 若合法输出合法串 不符合输出IMPOSSIBLE ?代表可以任意填写字符 输出任意满足题意答案即可 题解 根据题目进行判断 任何操作符都不能在开头和结尾 不能存在前缀零 分析?号应该填写的情况在大多数情况下应该是先填写数字 但是存在填写数字导致左边的数出现前缀零的情况,如 0?1 -> 001 这个时候只能填写任意的…
HDU 6341 Problem J. Let Sudoku Rotate 杭电多校第四场
题意 给定16 * 16 的16进制矩阵,每4 * 4为一个单元,问至少旋转几个单元可以使得整个矩阵满足数独的性质 题解 dfs + 剪枝 简单的令人发指 我当初为什么没去看这道题 AC代码 #include <iostream> #include <algorithm> #include <cstring> #…
牛客多校第五场 D.inv
链接:https://www.nowcoder.com/acm/contest/143/D 来源:牛客网 题面 Kanade has an even number n and a permutation b of all of the even numbers in [1,n] Let a denote an array [1,3,5....n-1…
Codeforces Round #501 (Div. 3) 题解
Problem A Points in Segments 题意 给你若干个区间,以及区间大小n,问你在区间$$[1,n]$$内没有被覆盖的点有哪些。 题解 乱搞,范围不大 #include <iostream> #include <algorithm> #include <cstring> #include &l…