关于 LCA 这东西太平常了 …… 这里就给出几种做法!! 倍增我相信各位 dalao 学 LCA 的时候必定第一个学的就是倍增。 倍增其实就是将暴力向上跳的过程改为跳 $2$ 的次幂。 这东西也没啥好说的,大概流程就是大力 DFS 一遍,把 $2$ 的次幂的父亲都给处理出来,然后在线搞 LCA。 ...
题解 P5788 【【模板】单调栈】
前言单调栈的模板题目,本人是手写单调栈。 单调栈首先了解一下什么是单调栈吧! 单调栈就是使栈内元素单调递增或者单调递减的栈,单调栈也只能在栈顶操作。 我们先来模拟一遍吧! 做一个比喻,比方说:有个集训队招人,一个数代表了一个选手的能力值,先进来的选手年龄会比较大,后面的选手年龄比较小,但是这个集训队 ...
题解 CF44A 【Indian Summer】
前言雾( 为什么要把它们看成两个字符串? 不就多了个空格吗? 这题目其实可以把一行当成一个字符串,反正空格又不会变化。 分析这题目其实 map 可以过,如果不知道 map 那么请自行百度。 STL大法就是好! Code#include <iostream>#include <cst ...
题解 CF977A 【Wrong Subtraction】
前言这题一看是一道模拟题,适合新手练习。 解决整数解决会稍简单一点。 首先,将n和k读入,然后k次循环 (while和for都可解决)。 然后一个判断:按照题目要求对于每一次操作,如果 n 的最后一位数字不为零,则将它减1,否则将它除以10(即删除最后一位数字)。 即可写出判断: if (n%10) ...
题解 P4136 【谁能赢呢?】
前言一开始看到这道题目的时候,以为是一道模拟,结果看数据范围,$o \big( n^2 \big)$肯定是过不了的,更何况还有神奇的多组数据。 分析于是,我就开始思考。那么在图画上模拟一遍吧! A 代表 小明 ,B 代表 小红 ,图画的可能不太好,还请各位大佬谅解,首先模拟一下 $2 \times ...
题解 P5716 【【深基3.例9】月份天数】
前言其实这题目就是一个模拟题,数组什么的都不需要,你只需要会c++基础赋值,判断,读入,输出,就可以做这题目。 至于为什么要写这篇题解,那是因为,我想让初学者更好的了解思路。 题意就是给你年份和月份,输出这一年的这一月有多少天。 还需要判闰年。 分析和解决其实很简单 1 3 5 7 8 10 12 ...