子希

分类

ACM动态规划(4) ACM花里胡哨(1) c++(4) Dijkstra(5) javafx开发(1) java学习(1) oj几何(1) oj贪心(7) oj递归(5) stl练习题(6) 动态规划(2) 单调栈(4) 图论最小生成树(6) 图论-网络流(1) 图论最短路(8) 图论（杂）(5) 字典树(2) 字符串(8) 并查集(14) 思维题(23) 数据结构实现(2) 数据结构实验(2) 数论(1) 暴力(1) 暴力搜索(26) 有趣的数学题(1) 未归档(2) 树状数组(6) 模拟(3) 每日一题(1) 离散数学实验(5) 算法设计与分析题库(15) 线段树(10) 网络比赛(6) 题解(43)

/ 注册

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

算法周周练

8篇文章 758人学习

codeforces题解

10篇文章 766人学习

牛客日常竞赛

15篇文章 900人学习

牛客每日一题

13篇文章 983人学习

全部文章（共232篇）

Fast Food(DP)

题意：给你n个饭店在横坐标轴上的位置，要你在这些饭店旁边建立k个仓库，使得所有饭店到最近的仓库距离之和最短，要你输出这个值。思路：这个题可以认为是管道问题的扩展版本，也可以认为是矩阵链乘的变种。定义dp[ i ] [ j ]:表示一共i个仓库在[1, j] 这些饭店的最短距离和转移方程：d...

2020-05-21

0 475

P1106删除问题(单调栈)

思路：单调栈维护一个递增序列，需要处理一些小细节，比说前导0等等，具体思路写在代码上了。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 10; char s[maxn]; void s...

2020-05-21

0 479

树(DP or 组合数学)

题目描述： shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。输入描述: 第一行两个整数n，k代表点数和颜色数；接下来n-1行，每行两个整数x,y表示x与y之间...

2020-05-21

0 500

LCA最近公共祖先详解

最近公共祖先LCA(lowest common ancestor) 在图论和计算机科学中，最近公共祖先（英语：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和...

2020-05-21

0 1116

Borrow Classroom(LCA最近公共祖先)

题目描述每年的BNU校赛都会有两次赛前培训，为此就需要去借教室，由于SK同学忙于出题，这个事情就由小Q同学来跑腿。SK同学准备从宿舍出发，把借教室的单子交给小Q同学让他拿去教务处盖章，但是何老师突然发现SK同学好像借错教室了，想抢在借教室的单子被送到教务处之前拦截下来。现在把校园抽象成一棵...

2020-05-21

0 441

D - RGB Triplets(前缀和+思维)

题意很好懂，就是一个长度为n的序列，s[i] 只可能是r,g,b，要你要满足就 j - i != k - j,并且s[i],s[j],s[k]两两不相同，并且i < j < k，的个数有多少个。思路：暴力O(n^3)模拟一遍铁超时，j - i != k - j 一开始一直在观察这个式...

2020-05-21

0 583

Codeforces Round #635 (Div. 2)(ABCD题解) 来自专栏

题意：给你三个区间，要你在这三个区间选三条边使得它成为一个三角形。思路：签到题，直接输出一个等腰三角形，b,c,c即可。时间复杂度O(1) 代码： #include<bits/stdc++.h> using namespace std; typedef long long int...

2020-05-21

0 659

E2. Three Blocks Palindrome (hard version)(枚举+思维+前缀和)

题目大意：给你一个长度为n的序列，要你找出形如aba这样的回文，其中a,b 可以等于0，并且最多只能出现两个不同字符。思路：注意到字符很少，只有200，可以从这里下手，先把[1,200]每个字符的前缀和求出来，再把相同字符的位置存起来，然后枚举200个数，再枚举每个数的长度的一半，然后在当前枚...

2020-05-21

0 425

人人都是好朋友(离散化 + 并查集)

思路：并查集基本操作了。。。c为1的先把他们并到同一个集合中，然后再检查c=0的情况，如果他们在同一个集合c又等于0说明矛盾。做这题的时候，出现好多小问题(上次写并查集是去年)，首先因为输入量很大，cin会超时，要用scanf，其次因为每次读入两个点所以maxn需要开两倍。就这个两个坑。另外注意到b...

2020-05-21

0 901

建设道路(前缀和优化)

思路：我觉得这个题目有点意思。。。。用一个简单的数学公式展开可以将O(n^2)降到O(n)实属牛皮。 sum1是ai的前缀和，sum2是ai ^ 2的前缀和 <mstyle displaystyle="true" scri...

2020-05-21

0 357