好运莲莲_

题解

未归档(1)

/ 注册

全部文章 / 题解（共43篇）

牛客IOI周赛23-普及组 D.小L的数列 (dp状态+枚举因子)

[原题链接](https://ac.nowcoder.com/acm/contest/11164/D) **思路：** 看到这题第一眼觉得要用些数论的知识优化，决定先写个暴力。假设dp[i]表示枚举到第i项的时候最长的好的序列长度，转移仿照LIS的n^2转移，过了80。然后就不会优化了。...

2021-03-06

0 698

牛客——求和（dfs序+树状数组）

原题链接题意：给定一棵树，有点权；两种操作，一是修改某个单点的权值，二是查询某个点为根节点的子树的点权之和。思路：dfs序后，子树都处于一个区间里，所以问题就转化成了单点修改、区间求和。用树状数组维护即可。代码： #include<bits/stdc++.h> typedef long ...

2020-11-15

2 684

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

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

2020-11-14

2 581

金字塔(区间DP+dfs序)

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

2020-11-12

1 660

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

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

2020-08-18

3 762

牛客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 1844

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

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

2020-08-16

2 1055

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

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

2020-08-05

3 678