hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

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

What Goes Up Must Come Down

题意：给你一个长度为n的序列，使序列呈先升序再降序的最少操作次数为多少？每次操作可以交换相邻的两个数。思路：对于每一个数来说，它最终要么左边的数全比它小，要么右边的数全比他小，每次移动相邻两个位置，所以你只需要判断它左边比它大的数的个数和右边比它大的个数的最小值（哪边小与那边大于它的交换），用树状...

树状数组

2020-10-04

2 755

旅游

题意：有一棵n个节点的树，第一天你在s点住宿，每一天你可以浏览与它距离不超过1的节点，你不能住宿在你已经浏览过的节点，求你最多住宿几天？思路：树状dp，以s节点为根。dp[i][1/0]表示在i为根的子树中是否在i节点住宿的最大住宿次数。如果u是父节点，v是子节点。dp[u][1]= dp[v][...

树状数组

2020-08-21

1 427

华华和月月种树

题意：一开始被给予一棵只有一个编号为0、权值为0的根节点的树，有M个操作，每个操作为以下三种之一：操作1：输入格式为1 i 表示给i节点加个权值为0的子节点，编号为当前最大编号+1。操作2：输入格式为2 i a 表示给i为根的子树所有节点的权值加a。操作3：输入格式为3 i 表示输出i节点的权值。 ...

dfs 树状数组

2020-08-21

1 666

Contest

题意：有n支队伍一共参加了三场比赛。一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强（既互相觉得比对方强），(x, y), (y, x)算一组。思路：当x自己觉得比y强，y自己也觉得比x强，只有这二种情况，第一...

树状数组

2020-06-04

1 699

换个角度思考

题意：给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数思路：将所有询问按x升序排列，a序列也按升序排列，然后每次询问当前[l,r,x]之前把ai小于等于x的ai在树状数组中加入他对应的原下标（只需要对应原下标位置+1就行)，然后询问[l,r]区间有多少个数。代码： #inclu...

树状数组离散

2020-05-06

0 496