hnust_yangyanjun

分类

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

/ 注册

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

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

滑雪与时间胶囊

题意：有一个n个节点和m条边的图，每个节点有一个高度，路只能从一个点到一个高度不大于它的另一个点，你可以从你所经过的任何一个点出发去下一个点，求经过的点最多为多少个，且此时经过的最短路为多少？思路：prim算法中优先队列第一关键词以所到达的节点的高度降序，第二关键词以路程升序代码： #inclu...

prim

2020-05-06

0 585

换个角度思考

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

树状数组离散

2020-05-06

0 496

Symmetric Matrix

题意：求满足以下条件的n*n矩阵的个数：1.所有元素的值属于{0，1，2}；2.为对称矩阵；3.每一行的值的和为2；4对角线的值为0；结果对m取模。思路：我们知道无向图的邻接矩阵是对称的，所以将四个条件可以转化为找满足没有自环的n个节点且每个节点有且仅有二条边的无向图有多少个？我们可以知道这样的无...

数学 dp

2020-05-06

0 825

美味菜肴

题意：有n种食材，m种菜肴，每种菜肴给出所需食材和美味值和制作时间，因为每种食材以a[i]的速率变得不新鲜，求在t秒总美味值最大为多少？注意：最大总美味值可能为负。思路：贪心+01背包贪心：设二种相邻菜肴，第一种所需食材变的不新鲜的速率为w[i].a,美味值为w[i].b，制作时间为w[i].c...

贪心 dp

2020-05-04

0 917

Removal

题意：求一个n长度的序列删除m个元素后不同序列的个数，结果对1000000007取模思路：dp[i][j]为前i个元素删除j个元素序列的个数dp[i][j]=dp[i-1][j]+dp[i-1][j-1]去重：因为重复只存在于二个相同元素之间的元素全部删除后的在二个元素中删除其中一个dp[i][j...

dp

2020-05-02

0 705

子序列

题意：小美有一个由n个元素组成的序列{a1,a2,a3,...,an}，她想知道其中有多少个子序列{ap1,ap2,...,apm}(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), < 成...

2020-04-23

0 557

边的染色

题意：小团有一张n个点，m条边的无向图G，有些边上已经被标记了0或1，表示它的边权。现在你需要给剩下的边标记边权为0或1，求有几种标记的方式满足：对于G中任意一个环，里面所有边的边权的异或值为0。环的定义如下：对于任意k（k≥2）个点{a1,a2,...,ak}，若对于所有的i<...

dfs 并查集

2020-04-23

0 688

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

糖糖别胡说，我真的不是签到题目

题意：n只糖糖分为二组做游戏，排成一排，第i只糖糖有能力值bi，从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1，现在，娇姐想知道在第n秒后，...

2020-04-20

0 507

华华给月月准备礼物

https://ac.nowcoder.com/acm/problem/23049 题意：被给予n根木棍，华华需要k根，华华可以将每根木棍裁剪成若干段自己想要的长度，并丢掉多余的部分，华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。思路：二分寻找长度...

2020-04-16

1 968