hnust_yangyanjun

分类

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

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共7篇）

Weak Memory 来自专栏

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

二分 bfs

2021-03-03

1 802

Microtransactions (hard version) 来自专栏

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

二分贪心

2021-02-28

1 591

Stressful Training

题意：有n台笔记本电脑，它们有一个初始电量ai，和每分钟耗电量bi,有一场训练需要持续k分钟，在每一分钟开始时电量不能为负，你能使用一个多大功率的充电器使其能完成训练，如果没有，则输出-1. 思路：二分枚举答案，如果一个超大的功率都不行，则说明没有，输出-1，判断一个功率是否可行，可以记录在该功率时...

二分

2020-09-29

1 633

List Of Integers

题意：给你x、p、k三个数，让你求大于x的第k个与p互素的数？思路：求出p的质因子，然后求小于等于x的与p互质的个数求出为j，题意就相当于求大于0的第k+j个与p互素的数了，二分枚举答案，求小于等于某一个数与p互质的个数使用容斥原理计算得出。代码： #include<cstdio> ...

二分容斥

2020-09-25

1 637

Alliances

题目：有n个城市，有(n-1)条道路，每条路连接两个城市，城市和道路构成了一棵n个节点的树。有k个帮派，每个帮派占领ci个城市。帮派集合称为联盟，他们控制的城市为他们占领的城市和所占领的城市二二之间的城市。有q个询问，每个询问给出一个首都和一个联盟，求首都距离联盟所控制的城市最近的距离？思路：在树...

dfs 二分 LCA

2020-07-11

1 701

[CQOI2010]扑克牌

题意：有n种牌，每种牌有ci张，还有m张万能的joker牌，每一套牌可以用一张joker牌代替任意一张牌，求最多能组成多少套牌？思路：二分求最大值，因为能组成k套牌则必能组成（k-1）套牌。是否能组成k套牌，首先我们最多用min（m,k）张万能牌，用万能牌补数目少于k的牌，最后看万能牌是否够用。 ...

二分

2020-06-10

0 569

K-th Number

题意：有一个n长度的A数组，求大于等于k的长度的连续子区间第K大的数加入B数组，求B数组第m大的数。思路：二分+尺取法代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define inf ...

二分尺取法

2020-04-21

0 517