AROY

每日一题

不会DP的羸弱(1) 补题变更强(8)

/ 注册

全部文章 / 每日一题（共29篇）

[每一][EA]双指针滑窗

https://ac.nowcoder.com/acm/problem/18386双指针滑窗的基本题型了模板： while(r<n){ window.push(); dosomething; while(window 不满足条件){ ...

2020-06-18

0 732

[练习]DP-背包类

https://ac.nowcoder.com/acm/contest/5968/E选出来要买的m个物品中任意两个的位置差都大于等于k就行了。现在告诉你这n个物品排成一行之后的受欢迎程度（可能是负数），求牛牛带回去的m个物品的最大欢迎度之和。错误写法：(记录一下思考过程 int a[N]; in...

2020-06-12

0 541

[每一]DP-类似背包

https://ac.nowcoder.com/acm/problem/19158 每件武器只有三种选择：放在左边，或者放在右边，或者不放对应着也就三种状态转移，考虑背包思想dp[i][j] 表示前i个左右重量差为j的最大重量则状态转移为：不选：选：考虑质量差最大是所有武器重量总和，最小是0代...

2020-06-10

0 562

[每一]树形DP，最大独立子集

https://ac.nowcoder.com/acm/problem/15748最大独立子集：选出尽量多的点，使得任何两个节点均不相邻，输出一个最大独立集。最大独立子集 f[i][0/1]表示以i为根时最大独立点的数量，f[][0]--不住 f[][1]--住则初始值为1， v是u的儿子节点...

2020-06-08

0 813

【每一】双BFS板子

https://ac.nowcoder.com/acm/problem/23486 这题属于双BFS模板题A一个队列进行BFS B一个队列进行BFS两者同时进行BFS----B走两步 A走一步BFS过程中判断A是否走到了B走过的点（vis数组判断即可）即： while(!que[0].empty(...

2020-06-08

0 663

【每日一题】[SCOI2005]最大子矩阵 (DP)

https://ac.nowcoder.com/acm/problem/20242有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠先看 m , m 只有 1 和 2先考虑简单情况----m=1 即一维最大子矩阵状态定义:f[i][l]...

2020-06-08

1 591

【每日一题】转换为求逆序对树状数组

链接：https://ac.nowcoder.com/acm/problem/13947n支队伍一共参加了三场比赛。一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。(x, y), (y, x)算一组。 41 ...

2020-06-04

0 524

牛客练习赛63 补题

C 种水稻给你一组数，每次选一个数+1或者-1，多少次之后能够使得所有数相同---仔细想一下，要想所有数都相同的次数最小，那么这个数和其他所有数差值绝对和最小，那么这个数就是排序之后的中位数（反证法就可以证明），结论：排序之后的b[size/2]为最终相等的数。这道题加了条件：就是第i天会加1；答...

2020-05-09

0 563

【每日一题0422】二分答案

https://ac.nowcoder.com/acm/problem/14301对数列A的每个区间求第K大，并将第k大插入到B中，再求B的第M大。暴力不行咋办===那就不如反着想吧，二分枚举答案；二分一个数x，第k个数大于x的区间个数大于m-1个

2020-04-23

0 448

【每日一题0421】枚举，后缀和，思维

https://ac.nowcoder.com/acm/problem/14583题目：一共两组糖，第i只糖可以消灭掉所有排在他前面的和他不是同一组的且值小于他的数；第i秒会让前ci个值加1；问最后存活多少个糖。这个题有意思的点就是题面给你展示的是动态给前i个增加1；但实际上这个动态增加和一次性...

2020-04-22

0 492