1 nagisa-kun

尚未进行身份认证

暂无相关简介

等级
TA的排名 15w+

扩展欧几里德算法+中国剩余问题+扩展中国剩余问题串联总结

扩展欧几里德算法对这算法本身认识比较一般。作用是:对于一个一次不定方程:ax+by=c,可用该算法算出x和y。这里主要说下接出来是负数的处理:大佬博客:https://blog.csdn.net/bajiu2822/article/details/102026375记住式子:D=b/gcd(a,b)(推导过程大佬博客里有)来个if,为负数的时候加上D就是了。模板题:https://...

2020-04-06 22:31:01

尺取法(滑框)专练

这部分主要是看到大佬的一篇博客,里面有几道题,都是尺取法的,所以就挖个坑没事写写。这里后面会补上总结。大佬博客:https://blog.csdn.net/lxt_lucia/article/details/81091597这里就写下我自己的感受。1、POJ 3061 Subsequence这道就是比较简单,比较普通的尺取法了,思考清楚就能过。因为所有数都是正数,所以r一直向右移动,目前的...

2020-03-29 18:13:29

HDU - 2586 How far away ? 解题报告(tarjan模板)(lca)

目录题目描述思路分析完整代码题目描述https://vjudge.net/problem/HDU-2586比较容易看懂就不说了。思路分析tarjan第一题,没什么太多要分析的关注点有以下几个:1、计算方法是将这个无根树化成以节点1为根的有根树,然后dfs出每一个点距离到节点1的距离,然后由几何关系得出答案。2、我们会先将它的所有查询都存起来进行操作,具体看代码。3、在union操...

2020-03-29 17:53:21

牛客练习赛60补题(待更新)(A、二进制 B、思维 C、DP D、拓展欧几里得算法)

目录A、大吉大利B、三角形周长和C、操作集锦D、斩杀线计算大师A、大吉大利链接:https://ac.nowcoder.com/acm/contest/4853/A一道挺普通的二进制题目,和洛谷之前做的谔运算有点像,可能还更简单一点。#include <iostream>using namespace std;typedef long long ll;ll counter...

2020-03-28 23:48:14

HDU - 2089 不要62 解题报告(数位dp)(入门题)

目录题目描述思路分析完整代码题目描述https://vjudge.net/problem/HDU-2089思路分析数位dp第一题,方法是打表+按位求ans。首先题目有点说不清楚,他求的应该是[m,n]闭区间的数字中符合条件的。先说打表,我们定义一个dp矩阵,dp[i][j]表示i位数,以j为开头数字的符合要求的数的个数。比如:我们以求[0,324]中的数字个数为例子。我们需要处理一下信...

2020-03-24 14:24:39

POJ - 1990 MooFest 解题报告(两个树状数组)

目录题目描述思路分析代码题目描述链接:https://vjudge.net/problem/POJ-1990题目有点难读,但我就是想偷个懒~思路分析这道题有点像求逆序数的那道题。首先,因为它要的两个因素(max(val)和abs(dis))里,和顺序有关的主要是max(val),那么我们就想到对它按照val进行排序:保证现在加入树中的元素的val最大。之后,就和逆序数的思路一样,加入一...

2020-03-23 15:37:07

POJ - 3321 Apple Tree 解题报告(树状数组)(dfs序)

目录题目概述思路分析题目概述链接:https://vjudge.net/problem/POJ-3321题目还是比较好懂的。给你一个树,初始状态下所有节点值都为1,输入C时,将该点从0变成1或1变成0。输入Q时,求该节点下所有节点的值的和。很容易联想到线段树或树状数组。思路分析这道题的难点在于,他所给的是一棵树,而不像之前给的是一个一维的序列,我们要做的就是对单点或区间的查询、修改。比较...

2020-03-23 15:24:56

Arab Collegiate Programming Contest 2015 K Road Network 结题报告(bfs/dfs/树形dp)

目录题目描述思路分析AC代码树形dpdfsbfs题目描述链接:https://nanti.jisuanke.com/t/44347题目还是有点难读懂的。但实际上就是求树的直径,算出不在直径上的路径的个数思路分析貌似是第一次接触树的直径。查了下方法,有三种,分别是:两次bfs两次dfs树形dp三种我都写了一次,感觉还是比较好掌握的的,以后加以熟练就是了。贴个大佬博客:https:...

2020-03-22 10:31:32

HDU - 1823 Luck and Love结题报告(二维线段树)(模板)

目录题目概述思路分析完整代码题目概述链接:https://vjudge.net/problem/HDU-1823思路分析第一道二维线段树。因为涉及到升高和活泼度两个变量,所以需要二维线段树维护。因为活泼度和缘分值都是浮点数,因为不想存浮点数,所以*10变成整数。其实二维线段树就是树套树,我们的思路就是:先把当作一个一维的线段树,先找出要更新的或者访问的节点的第一个坐标,之后再用相同的方...

2020-03-20 23:56:16

POJ - 2299 Ultra-QuickSort 解题报告(树状数组)(求逆序数)(离散化)

目录题目描述思路分析AC代码题目描述链接:https://vjudge.net/problem/POJ-2299题意:给你一组数,你能做的操作是交换两个相邻的数,令这个数列变成递增的,要求最小操作数。思路分析说实话,看到这样的题,感觉我已经本能反应地想到了逆序数了。。不知道是不是最近看了点线代的缘故。。具体分析起来是这样的:59 1 0 5 4以样例为例,我们一个一个的输入,那么...

2020-03-18 23:39:17

HDU - 1394 Minimum Inversion Number 解题报告(线段树)(数学)

目录题目大意思路分析完整代码题目大意链接:https://vjudge.net/problem/HDU-1394意思就是说:给一个整数n,后面一行给出0~n-1的数的排列,可以对这个排列作一下变换:把第一个数放到最后一个数的位置生成新的排列,求在所有能生成的排列中,逆序数的最小值是多少。思路分析听说可以不用线段树?但是我看到涉及区间和查找的就先用线段树试了试。思路就是:每输入一个数,就在...

2020-03-17 22:41:13

HDU - 1166 敌兵布阵(线段树模板)

目录题目描述思路分析AC代码题目描述链接:https://vjudge.net/problem/hdu-1166思路分析由于涉及到整个区间的数据修改和查询,所以是一道线段树题目。这里主要的就是记住模板:贴个大佬博客:https://blog.csdn.net/queque_heiya/article/details/104166507然后我就偷懒吧。。AC代码#include &...

2020-03-17 21:44:09

POJ - 2528 Mayor's posters 解题报告(离散化)(线段树)

目录题目概述思路分析AC代码题目概述链接:https://vjudge.net/problem/POJ-2528大概意思就是贴广告,给出给出每个广告的边界,求全部贴完之后还有几张没有被完全遮住的。思路分析这道题是道线段树(涉及到区间更改,数据量较大)+离散化(数据较大,需要压缩树的体积)。线段树树部分和一般的线段树差不多,就是找中点,确定寻找的区间,然后递归继续搜索,直到叶子节点。离...

2020-03-16 01:10:33

HDU - 3117 Fibonacci Numbers 解题报告(数论)(矩阵快速幂)(斐波那契数通项)

之前做的题,拿出来记录一下。目录题目:思路分析ac代码题目:链接:https://vjudge.net/problem/HDU-3117思路分析因为这道题要求大于8位数的时候用省略号,因此,我们需要知道什么时候会超过8位数。自己写个程序试下,应该是到第39项(<=39)为止不需要省略号。因为,n<=39时,直接矩阵快速幂。大于39的时候,我们需要分两部分:对于后四位,我们...

2020-03-14 01:05:10

P1352 没有上司的舞会 解题报告(树形dp)

目录题目概述思路分析ac代码题目概述https://www.luogu.com.cn/problem/P1352思路分析看到上司的下属之间的关系很容易想到树形结构,那么,又和最值挂钩,那么想到的就是树形dp。那么,这里的可以进行比较的点就是:上司参加,下属就不能参加,下属参加,上司一定不能参加,因此,状态转移的时候我们就需要比较的是上司去和不去的情况,所以,我们把dp数组的第二维开为2:存...

2020-03-13 00:39:28

POJ - 3107 Godfather 解题报告(树形dp)(链式向前星)

目录题目描述思路分析AC代码题目描述链接:https://vjudge.net/problem/POJ-3107其实还是找树的重心。这道题和上一道题思路是一样的,但是写法完全不一样。为什么?接着往下看。思路分析这道题还是那个想法:求出每个点作为根节点的时候的最大子树节点数,通过dfs,分别计算出每一层的子树节点数,然后dp回去求上一层的子树节点数。但是这道题卡vector,所以需要用链式...

2020-03-10 22:39:56

POJ - 2378 Tree Cutting 解题报告

目录题目大意思路分析AC代码题目大意链接:https://vjudge.net/problem/POJ-2378情景说的有点复杂,但其实就是让你找出这棵树所有的重心节点。思路分析首先,我们了解下什么是树的重心:对于一棵n个节点无根树,若有一点,当令该点为根的时候,最大节点数最少。也可以说成:删除这个点之后,各连通块的节点数最少,则这一点就是树的重心。了解完重心的定义之后,我们再来看下...

2020-03-10 17:45:45

力扣第 179 场周赛补题报告(思维)(思维)(树形dp)(树形dp)

听说不是很难,本弱鸡就来试一试,感觉还是有所收获的。目录1374. 生成每种字符都是奇数个的字符串1375. 灯泡开关 III1376. 通知所有员工所需的时间1377. T 秒后青蛙的位置1374. 生成每种字符都是奇数个的字符串这道是思维题:我们那到一个数n,有两种情况:若他是奇数,那么直接返回n个字符组成的字符串若他是偶数,那么,我们分成一个1+一个奇数输出就行了。简单的一题目。...

2020-03-09 20:52:34

SQL学习随笔-修改表结构、插入记录

##一、修改表结构1、主要语句:ALTER [IGNORE] TABLE 表名 修改项 [,修改项]其中:加入IGNORE后,若修改后有重复关键字,则忽略此操作。没有IGNORE,则会报错。修改项为所作的操作。2、常用语句:增加列:ADD TABLE 表名 ADD 列名 类定义 [AFTER]//注意 没有BEFORE修改列类型ALTER TABLE 表名 MODIFY 列名 新类...

2020-03-09 19:24:39

力扣5339 二叉搜索子树的最大键值和 解题报告

目录题目描述思路分析ac代码题目描述链接:https://leetcode-cn.com/problems/maximum-sum-bst-in-binary-tree/给你一棵以 root 为根的 二叉树 ,请你返回 任意 二叉搜索子树的最大键值和。二叉搜索树的定义如下:任意节点的左子树中的键值都 小于 此节点的键值。任意节点的右子树中的键值都 大于 此节点的键值。任意节点的左子树...

2020-03-09 11:02:35

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。