AROY - 个人主页动态 - 牛客网

发布(40) 评论刷题

2020-04-08 19:30

已编辑

长江商学院 C++

【牛客算法周周练1】题解A/C/E

https://ac.nowcoder.com/acm/contest/5086#question A 前缀和 一个数移到左边所减少的量= 增加的量为总的减少量维护前缀和，枚举下标从k~n-1,找出最少的减少量delta即可 #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e5+5; int main() { int t; scanf("%d",&t); while(t--){ int n;sca...

0 点赞评论收藏

分享

2020-04-05 23:10

已编辑

长江商学院 C++

【每日一题】树上DFS

树上DP https://ac.nowcoder.com/acm/problem/22598 题目：在以S为根的树上删掉权值和尽量小的一些边使得S和每一个叶子节点都不连通。关于树的题目真是丰富啊====树是最能体现递归的，递归是从顶向下的，转化成从底向上就变成了DP，所以“树上”的题目真是前变万化~子问题：以x为根的子树上的所有叶子和根断开的最小代价dfs转移时候选择断开与儿子的边还是断开儿子字树的边即可 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 10...

0 点赞评论收藏

分享

2020-04-05 22:11

长江商学院 C++

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

枚举优化 https://ac.nowcoder.com/acm/problem/23053这题目描述这么费劲干啥啊==''==题目：给定序列s,t,判断t是否是s的子序列思想可以参考KMP利用next数组匹配子串，我们维护一个next[i][a,b,c……z]来表示第i个字母后面的第一个a,b……字母位置；注意：比如s中有两个以上a字母，匹配时候肯定是选前面的，因为前面的如果匹配不了t，后面的就更不可能。 #include <bits/stdc++.h> using namespace std; const int maxn=1e6+5; int nex[maxn][26];...

0 点赞评论收藏

分享

2020-04-08 23:21

已编辑

长江商学院 C++

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

牛客OI周赛15-提高组https://ac.nowcoder.com/acm/contest/4912 A 环球旅行 给出一棵带边权的树。删除一条边，使分成的两棵树中较大的直径尽量小。求该直径。我自己的思路：计算直径上的每条边删除后左子树的直径l和右子树的直径r；答案就是min(所有边的max(l,r))超时，只能得50分 #include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int N=1e6+5; int n,tot,rt,dis[N],fa[N],h[N],ne[N<&lt...

0 点赞评论收藏

分享

2020-04-04 17:16

已编辑

长江商学院 C++

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

牛客OI周赛15-普及组链接：https://ac.nowcoder.com/acm/contest/4911 A A很简单不多说 #include <bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { //cout<<t; string s; cin>>s; int len =s.size(); if...

0 点赞评论收藏

分享

2020-03-31 10:34

已编辑

长江商学院 C++

【每日一题】倍增思想

题目：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)个父亲节点 因为：2^i = 2^(i-1)+2^(i-1) 【本题】 在这题中，题目说是树上的多次查询，可以联想到倍增（优化暴力查询），如果不是多次查询，倍增并不好用，因为倍增需要预处理f数组以及树的深度 定义f[u][i]为从某节点u出发往根走，购买了2^i件物品...

0 点赞评论收藏

分享

2020-05-03 14:55

已编辑

长江商学院 C++

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

https://ac.nowcoder.com/acm/problem/50528滑动窗口最大最小值 单调队列板子题 求最大值和求最小值分别维护一个单减和单增队列即可，队列内保存数组下标（方便判断是否在滑动窗口内），我这里使用deque使用 以求最大值为例： 队列的最前端是此次遍历的最大值的下标当我们遇到新的数时，将新的数和双项队列的末尾比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才停止双项队列中的所有值都要在窗口范围内 #include using namespace std; vector maxres; vector minres; void Wi...

0 点赞评论收藏

分享

2020-03-26 19:29

已编辑

长江商学院 C++

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

题目：https://ac.nowcoder.com/acm/problem/15553 统计一个数前面的连续k个数和 premax 后面最大的连续k个数和 sufmax 最后遍历一遍， ans=max(ans,preans+sufmax[i+1]); ans=max(ans,preans+premax[i-k]); 【心得】 这里写复杂了=。= 还是代码写的太少 直接前缀和就可以 sum[i]-sum[i-k]；sum[i+k-1]-sum[i-1] 我这里是用滑动窗口写的===== ...

0 点赞评论收藏

分享

2020-03-26 11:55

长江商学院 C++

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

题目：https://ac.nowcoder.com/acm/problem/13230 输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。 我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。 需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可 —————————————————————————...

0 点赞评论收藏

分享

2020-03-25 17:26

已编辑

长江商学院 C++

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

题目连接：https://ac.nowcoder.com/acm/problem/50439 【思路】 看到题目盲猜贪心，一开始是想着按val排序，每次取可以取的大值，但是涉及到容量大于限制的人数时 不容易去判断是删掉限制了我们人数的那个人扩充容量还是按现在的限制把多的人都删掉； 改为按容量排序，这道题就很容易解了； 按容量从大到小排序一遍，一次遍历，当s值变化时，把多于s的小值（使用最小堆）都拿出去，若此时堆顶的值小于当前值 && 容量为s，用当前值替换掉堆顶值。 判断s值是否变化 维护一个prevs变量即可 【心得】 做题要力争一次AC 一...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务