一只橘橘猫

分类

coderforces(20) dp动态规划(3) icpc(8) KMP算法(3) leetcode(1) STL(1) 人工智能(2) 优先队列(1) 图论(3) 字符串(5) 搜索(2) 数学(4) 日记(1) 最短路(3) 未归档(29) 杭电多校(7) 牛客多校(11) 牛客寒假训练营2020(6) 牛客练习赛(8) 线段树树状数组(2) 贪心(4) 题解(25)

/ 注册

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

acm菜鸡日常

20篇文章 2407人学习

7篇文章 1156人学习

0篇文章 0人学习

全部文章（共149篇）

[每日一题]4.2 Shortest Path 来自专栏

题意：给出一棵有偶数的节点的树，将其分成n/2对点，并且要求n/2对点的路径之和最小涉及知识点：思维/树上dfs 思路：树上任意两点间的距离是唯一的，题目又要求路径之和最小，所以选择两个节点，要么是父节点和其孩子节点，要么是父节点的两个孩子节点，还有一种情况是多了一个孩子节点，那么肯定要先加上...

2020-04-02

1 873

最近公共祖先（LCA）来自专栏

学习算法——最近公共祖先算法介绍：LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科例题：洛谷-LCA模板题模板代码： #include <bits/stdc++.h> ...

2020-04-01

2 747

[每日一题]4.1 月月查华华的手机来自专栏

涉及知识点：字符串匹配题意：给出母串 s，给出 m 次询问，每次询问给出的子串 si 是否是 s 的子序列思路：如果直接考虑双重for循环比较会超时，看着是道字典树的题，但是没写过字典树，就写了个递推思路的代码，设 nex[ i ][ j ] 表示第 i 个位置的字母后第一个 j + 'a'...

2020-04-01

5 1056

同余最短路来自专栏

题目一般风格：原题目网址：https://www.luogu.com.cn/problem/P2371 模板代码: #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn ...

2020-03-30

1 831

[每日一题] 3.30滑动窗口来自专栏

涉及知识点：队列/双指针做法：我看大佬们都是写的优先队列，我这里讲一下deque（双端队列）的解法吧，原理都是一样，首先先看一下deque的写法： deque<int> q;//定义双端队列 q.push_front(x);//队列头部插入元素x q.push_back(x);//队...

2020-03-29

0 749

[牛客练习赛60] ABCD 来自专栏

A: 涉及知识点：位运算解法： &运算对应的二进制运算，如果第i个数的二进制第k位为1，那么它可以和其余所有二进制第k位为1的每一个数产生(1<<i)的贡献(当然也包括它本身)，所以统计二进制第k位为1的个数，最后加一下时间复杂度： O(nlogn) 代码： #...

2020-03-28

2 681

[每日一题]3.26 数学考试来自专栏

涉及知识点：前缀和 solution：题目要求的是两段不连续长度为k的连续区间和先求一遍前缀和，然后记录第i个位置的前缀和的较大值以及后缀的较大值，最后遍历一遍答案可能为负数，记得初始化为-inf std： #include <bits/stdc++.h> using namespa...

2020-03-26

1 838

[每日一题]3.25 合并回文子串来自专栏

涉及知识点：区间dp solution：划重点：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。大多数区间dp的模板都长这样子： for(int len = 1; len <= n; len++){ f...

2020-03-26

7 986

[每日一题]3.24 tokitsukaze and Soldier 来自专栏

题目网址：https://ac.nowcoder.com/acm/problem/50439 涉及知识点：优先队列/贪心做法：每个士兵都有战力Vi和一个限制Si，我们先按照每个士兵的Si从大到小进行排序然后我们根据排好序的士兵遍历因为士兵的Si从大到小，所以遍历的过程中，当前遍历的士...

2020-03-24

2 1351

UCF Local Programming Contest 2012 补题记录 - 闫志强 - 2020.3.5

比赛主页：https://www.jisuanke.com/contest/7332 A. Wall Street Monopoly: solution: 涉及知识点：区间dp 划重点：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解...

2020-03-05

3 722