AROY

分类

不会DP的羸弱(1) 每日一题(29) 补题变更强(8)

/ 注册

全部文章（共38篇）

【每日一题】字符串枚举优化

枚举优化 https://ac.nowcoder.com/acm/problem/23053这题目描述这么费劲干啥啊==''==题目：给定序列s,t,判断t是否是s的子序列思想可以参考KMP利用next数组匹配子串，我们维护一个next[i][a,b,c……z]来表示第i个字母后面的第一个a,b…...

2020-04-05

0 572

【牛客OI周赛15-提高组】题解[补题A]

牛客OI周赛15-提高组https://ac.nowcoder.com/acm/contest/4912 A 环球旅行给出一棵带边权的树。删除一条边，使分成的两棵树中较大的直径尽量小。求该直径。我自己的思路：计算直径上的每条边删除后左子树的直径l和右子树的直径r；答案就是min(所有边的max(...

2020-04-05

0 508

【牛客OI周赛15-普及组】补题

牛客OI周赛15-普及组链接：https://ac.nowcoder.com/acm/contest/4911 A A很简单不多说 #include <bits/stdc++.h> using namespace std; int main() { int t; sca...

2020-04-04

2 530

【每日一题】倍增思想

题目：https://ac.nowcoder.com/acm/problem/13331 【倍增思想】倍增经典递推公式：f[u][i]=f[f[u][i−1]][i−1] 即： u的第2^i个父亲节点是 u的第2^(i-1)个父亲的节点的第2^(i-1)个父亲节点 ...

2020-03-31

2 708

【每日一题】单调队列、滑动窗口最大最小值

https://ac.nowcoder.com/acm/problem/50528滑动窗口最大最小值单调队列板子题求最大值和求最小值分别维护一个单减和单增队列即可，队列内保存数组下标（方便判断是否在滑动窗口内），我这里使用deque使用以求最大值为例：队列的最前端是此次遍历的最大值的下标当...

2020-03-29

1 935

【每日一题】前缀和、滑动窗口

题目：https://ac.nowcoder.com/acm/problem/15553 统计一个数前面的连续k个数和 premax 后面最大的连续k个数和 sufmax 最后遍历一遍， ans=max(ans,preans+sufmax[i+1]); ...

2020-03-26

0 998

【每日一题】合并回文子串、区间DP

题目：https://ac.nowcoder.com/acm/problem/13230 输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"ab...

2020-03-26

0 508

【每日一题】贪心、滑动窗口

题目连接：https://ac.nowcoder.com/acm/problem/50439 【思路】看到题目盲猜贪心，一开始是想着按val排序，每次取可以取的大值，但是涉及到容量大于限制的人数时不容易去判断是删掉限制了我们人数的那个人扩充容量还是按现在的限制把多的人都删掉；改为按...

2020-03-25

0 598