文章

奶牛在草地上悠闲的吃着草，因为残象已使它们目不忍视，流言已使它们耳不忍闻。如果两个奶牛的曼哈顿距离 (|x,y 坐标差|的和) 小于等于 C, 它们处在同一组。问有多少个不同的组。 思路 注意到对于一个点 P, 曼哈顿距离小于等于 c 的点组成的集合是一个斜放的正方形，不方便后续操作，我们把它转正。 阅读更多…

1. 用途 首先是有根树。 我们需要实现如从点 u 到点 v 的（最短）路径上所有点的权值+1 这种操作。 而且我们不需要频繁的求某个点的权值。 2. 实现方法 类似于前缀和的思想。 首先我们定义：val[i] 表示点 i 的标记，cal[i] 表示点 i 的权值，lca(i,j) 表示点 i 与点 阅读更多…

1. 题目 传送门=￣ω￣= 题意，给你一棵无根树，再给你一些点对。你现在可以使树上某一条边的长度变为 0，求给出的点对之间的路径中最长的那条路径最短为多长。 数据范围 30W 2. 题解 我太菜了，还要看题解才会 其实主要思路就是： 首先求出所有点对之间的路径长度，设 l[i] 为第 i 个点对之 阅读更多…

考试策略 这个里面的花，我看了一下，啊，T2 和 T3 是比较简单的原题啊，匆匆写完过了对拍，看了一下 T4，T4 有思路但是这个离散太恶心了有点思考不清楚，怕写错就打了暴力。T1 完全没思路就打了暴力。 T1 期望得分：20 实际得分：0 题目描述： 我们生活的星球对于整个宇宙来说，只不过是沧海一 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 感觉自己 noip2016 在仙游。。。 为什么这么水的题目没想出来？当时也学了组合数递推求 $C_n^k$ 先预处理出 $C_n^k\ mod\ k$的值，对于询问 n,m，求出有多少个 $C_i^j\ mod\ k(i\l 阅读更多…

1. 序言 求矩形面积并指的是给你 n 个矩形的顶点坐标（矩形的边必然平行于坐标轴），求它们所覆盖的总面积（重叠覆盖的面积只算一次覆盖）。 暴力枚举矩形的话如果 n 较大显然会超时。这时候我们就需要一种新算法：扫描线。这种算法求矩形面积并的复杂度是 nlogn 的。 2. 例题 HDU &#8211 阅读更多…

1. 题目 传送门=￣ω￣= 题目大意：给出 n 个矩形（矩形顶点左边可能为小数）1<=n<=100，求这些矩形覆盖的面积大小（多次覆盖同一个地方只算一次覆盖），即求这些矩形的面积并。含多组数据 2. 题解 首先听说数据比较水，不用线段树直接暴力数组搞也能过。 其次看到网上有一部分智障写 阅读更多…

收回我以前对某些题的评论– 这一道 tmd 才是最恶心的。 苟活者在淡红的 WA 中会依稀看见微茫的希望，真正的傻 B 会更奋然而 AC。– 某树人 耗时 4.5 个小时，手写 180 行代码，套用 5 种模板，定义 16 个数组，提交近 10 次，终于 AC… 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 这题我是查树状数组出来的。。。 然后我就当作 splay 的练手题了 蛮水的 搞个能保存每个数字出现了多少次的 splay 查 kth 就行了 也就是一边插入一遍查 kth((i+1)/2) 代码： #include <bits/stdc++.h&gt 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 首先不难想到： 设 $f[i][j][k]$为第一个字符串的前 i 个字符和第二个字符串的前 j 个字符匹配，用了 k 个子串时的方案数。 那么 $f[i][j][k]=f[i-1][j-1][k]+f[i-1][j-1][k-1]$，$f[i-1][j-1 阅读更多…