阿里嘎多懒羊羊桑_

分类

未归档(1) 题解(36)

/ 注册

TA的专栏 36篇文章 2人订阅

15天大厂真题带刷Go题解

36篇文章 103人学习

全部文章（共105篇）

牛客——选点（dfs序+LIS）

牛客——选点（dfs序+LIS）原题链接思路：根据题意，选出来的子树应该满足：左子树的点的权值>右子树的点的权值>根节点的权值。对树按照根右左的顺序求dfs序，在转化后的序列里求最长上升子序列即可。代码： ///#pragma GCC optimize(3) ///#pragm...

2020-11-14

2 589

金字塔(区间DP+dfs序)

题意：给定序列表示dfs一棵树遍历得到的顺序，每次经过一个节点都输出该节点对应的字母，求有多少棵树满足此序列。思路：首先根据dfs的过程可以得到如果一棵树有n个节点的话，他的序列长度为2n-1；所以如果给出的长度为m的话，节点数量n=(m+1)/2。所以如果说给出的序列长度是偶数的话，答案一定...

2020-11-12

1 666

牛客6—— K-Bag （奇妙哈希或滑动窗口）

牛客6—— K-Bag （奇妙哈希或滑动窗口）原题链接题意：定义一个特殊序列为多个1~k的排列顺序连接起来的序列，问给出的序列是不是特殊序列的连续子串。思路：思路一来源于铭宇巨巨，思路二来源于博客首先可以知道，如果一个序列是特殊序列的连续子串，要么是序列是特殊序列的一部分，要么是一个特...

2020-08-18

3 765

牛客6—— Combination of Physics and Maths （思维）

牛客6—— Combination of Physics and Maths （思维）原题链接题意：矩形的底面积为最后一行数的和，压力为所有数的和，找一个压力/底面积（即压强）最大的可非连续子矩阵。思路：选择单列一定优于选择多列，证明：所以只需要找到每列的最大即可。代码： #pra...

2020-08-18

1 594

牛客6—— Easy Construction （思维+构造）

牛客6—— Easy Construction （思维+构造）原题链接题意：能否构造一个1~n的排列，使得对于任意的 i (1<=i<=n) ，排列都存在一个长度为i的子区间的和%n==k。思路：先考虑无解的情况，当i==n时，子区间只有一种情况，元素的和为1+2+……+n，即...

2020-08-18

1 1130

【题型总结】给区间加等差数列求值问题

【题型总结】给区间加等差数列求值问题一、前言：上一篇题型总结不知道扔哪去了，下午训练看到个很眼熟的题，感觉见过很多次了，就顺手总结下。需要会的前置知识有：差分与前缀和，树状数组基础，线段树基础二、UPC 2020年夏混合个人训练第八十场问题 B: 序列（二阶差分）题意：给定长度为n的...

2020-08-16

2 1897

牛客多校2—— Boundary （计算几何）

牛客多校2—— Boundary （计算几何）题意：给出 n 个点，需要我们选择一个经过原点的圆，使得这个圆经过尽可能多的点，输出最多可以经过多少个点思路：三点不共线的点确定一个圆 O点已经确定，O（n）枚举另一个点P，O（n）枚举第三个点，这样三点就可以确定一个圆心，每次都取圆心出现最多的...

2020-08-16

2 1068

牛客—— 红球进黑洞（线段树+位运算）

牛客—— 红球进黑洞（线段树+位运算）铭宇巨巨推荐的题！原题链接题意：给定一个序列，两种操作，一是区间求和，二是将区间里的每个数都异或x。思路：一眼就线段树，关键是怎么维护第二个操作。借助最小异或生成树的思想以及异或题的常见套路，我们可以把每个数都进行二进制拆分，用线段树分别维护每一...

2020-08-05

3 667

【牛客】小A的最短路（LCA）

【牛客】小A的最短路（LCA）原题链接题意：给定一棵树，除给定的特殊边边权为0外，其余边权均为1。求两点之间的最短距离。n为3e5 思路：题目是一棵树这个条件有点隐蔽直接进行最短路可能并不可行，考虑树上求两点距离的方法，一般就是LCA。因为存在特殊边，所以节点a和b之间的距离可能有三种...

2020-08-04

0 552

最小异或生成树

最小异或生成树一、前置知识： 1.Trie树：高效的存储和查找字符串集合的数据结构 int son[maxn][26],cnt[maxn],idx; void add(char *str){///将新的字符串插入到字典树里 int p=0,len=strlen(str); ...

2020-07-31

1 1648