hnust_yangyanjun

题解

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

/ 注册

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

Game of Swapping Numbers

题意：给与两个长度为n的a,b数组，你可以交换a数组中两个元素位置，你恰好进行k次操作后的最大值？思路：首先我们思考一下什么样的两个数交换后的结果会大：假如有两对数:（a1,b1），（a2,b2）原结果为abs(a1-b1)+abs(a2-b2)如果a1>b1&&a2>...

数学

2021-07-18

6 1046

环路运输来自专栏

题意：有一个n个节点的环，每一个节点有一个权值Ai,求两个节点i,j之间的Ai+Aj+dis(i,j)(i到j的距离)最大为多少？思路：单调队列首先将环转换成链，即加一段（n+1）~ (2*n),a[n+i]=a[i] (n>=i>=0)。在环上两点的距离小于等于n/2。设Ai+Aj+...

单调队列

2021-04-24

0 806

逛公园来自专栏

题意：有一个n个节点，m条有向边的图，如果从1到n的最短路为d，请你求从1到n的路线长度小于d+k的数目，答案对p取模。思路：最短路+记忆化搜索反向建图求每一个节点到n节点的最短距离。定义状态dp[i][j]为从节点i，还可以额外多走j的长度的状态到目标状态( dp[n][ji] (k>=j...

最短路记忆化搜索

2021-04-23

3 814

[JSOI2015]地铁线路来自专栏

题意：有n个站点，m条路线，每条路线使用一次要交1块钱，给出每条路线的信息，从一个站点到下一个站点的时间为1，让你求从一个站点到另一个站点的最小花费是多少，此时花费时间最大为多少？思路：最短路+拓扑+dp一看就是图论题，第一问求最小花费，如何用最短路求呢，对于每一条路线我们要创建两个虚点，一个虚点...

最短路 dp

2021-04-21

2 895

Max Flow 来自专栏

题意：有一颗n个节点的树，有k次操作，每次操作给出二个节点，然后将二个节点及二个节点之间的节点权值都加一，然后求最后树中权值最大的节点的权值为多少？思路：lca+差分：用lca求出二个节点u、v的最近公共祖先k，k的父亲节点为kp；要使u、v路经上节点权值加一则val[u]、val[v]进行加一，...

LCA 树上差分

2021-04-19

0 839

[HAOI2012]音量调节来自专栏

题意：有一个歌手要唱n首歌，每首歌在唱之前可以调节ci的音量,上调或者下调，但不能低于0或者高于maxLevel，初始音量为beginLevel，求最后一首歌音量最大为多少，如果不能满足规则，则输出-1. 思路：首先观察数据范围，我们发现n和maxLevel都不是很大，所有我们可以使用dp来写. 定...

dp

2021-04-19

4 869

Coprime Subsequences 来自专栏

题意：给你一个长度为n的序列，让你求序列的最大公约数为1的子序列数目为多少？思路：莫比乌斯反演首先统计一下该序列有什么数，个数为多少。然后求莫比乌斯函数。统计有i为因子的数有x。根据x求都有该因子的序列有 ( )个根据莫比乌斯函数判断该序列数是加上还是减去.最后得出结果. 代码： #include...

2021-03-05

1 767

Weak Memory 来自专栏

题意：给你一个n个点m条边的图，其中有k个节点是特殊的，起点s一定是特殊的，现在让你从s到t，每个特殊点可以加q点能量，经过一条边需要花费1点能量，求能从s到t时q最小为多少？（如果不能到达，输出-1）思路：求最小值，然后这值又具有单调性，所以可以二分枚举答案。然后判断这个答案行不行可以用bfs（...

二分 bfs

2021-03-03

1 802

PLEASE 来自专栏

题意：有这么一个游戏，有三个杯子，每次可以使用中间的杯子与二边的交换，求n次交换后中间杯子还是原来那个的概率为多少？思路：设原来杯子用1表示，其余二个杯子用0表示：010为初始状况第一次出现状态为：100、001第二次出现状态为：100、010、010、001第三次出现状态为：100、010、10...

数学

2021-03-01

1 593

Microtransactions (hard version) 来自专栏

题意：有i种物品，每种物品需要买k[i]个，然后商店会有m次特价出售，第j次为在di天出售第ti种物品，物品原价2元，特价1元，你每天上午可以获得一元，下午可以进行交易，求获取所有物品花费的最少时间为多少天？思路：如果第i天满足条件，则i+1天一定满足，所有二分答案.如何判断答案x是否符合：按贪心...

二分贪心

2021-02-28

1 591