BZOJ 1295: [SCOI2009]最长距离

Solution可以直接求下任意两点的最短路,把障碍看做是权值为 1 的点,其他点权值为 0,这样最短路的意义就是两点间拆至少多少个障碍才能联通。之后枚举任意两个点更新答案就可以了Code#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <cmath> using namespace std; const int N = 32; int n, m, t; int a[N][N]; char s[N]- 阅读剩余部分 -

BZOJ 1084: [SCOI2005]最大子矩阵

Solution分成两种情况讨论, m = 1 非常简单就不说了。m = 2 的时候 fi[k] 表示第一行取前 i 个,第二行取前 j 个,其中取 k 个矩阵的最大值是多少。转移一下就可以了。Code#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 200; int n, m, k; int a[N], b[N]; int f[N][N][N]; int dp[N][N]; void solve1() - 阅读剩余部分 -

BZOJ 1491: [NOI2007]社交网络

Solution直接按照题意模拟就可以了,最短路用 floyd 就可以啦,还可以顺便记录下路径数。Code#include <cstdio> #include <algorithm> #include <cstring> #define long long long using namespace std; const int N = 200; int n, m; int f[N][N]; long cnt[N][N]; int main() { memset(f, 0x3f, sizeof f); scanf("- 阅读剩余部分 -

BZOJ 3039: 玉蟾宫

Solution悬线法,可以直接看论文 浅谈用极大化思想解决最大子矩形问题Code#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1001; int n, m; int a[N][N], h[N][N]; int l[N][N], r[N][N]; int L[N][N], R[N][N]; int main() { scanf("%d%d", &n, &m)- 阅读剩余部分 -

BZOJ 1202: [HNOI2005]狡猾的商人

Solution题目相当于给出几组前缀和 s[r] - s[l-1]。所以用带权并查集维护一下和根的距离就可以了。Code#include <cstdio> #include <algorithm> using namespace std; const int N = 1000; int n, m; int fa[N], dis[N]; int father(int x) { if(fa[x] == x) return x; int t = father(fa[x]); dis[x] += dis[fa[x]]; fa- 阅读剩余部分 -

BZOJ 3252: 攻略

Solution模拟赛出原题,就是这道题,正解好像是长链剖分什么的,考试时候瞎搞就差一点 AC 了,没写读入优化被卡常,写了就 A 了,BZOJ 上跑的倒是挺快的,3556ms。瞎搞的方法就是对于每个点用 set 维护一下去哪个儿子比较优,然后对于每个 k ,从 1 节点一直走最优的儿子一直走到叶节点,我们把这条路径从图中删去,然后把连到这条路径上的其他子树直接连到 1 号节点。自己想想,每次如果树随机,我们每次删路径的长度期望 $O(logn)$,再考虑一下极端情况比如链的话,只有两个叶节点,可以飞速跑出答案,如果是菊花图,每次删路径就是 $O(1)$ ,然后更新 1 号- 阅读剩余部分 -

BZOJ 3038: 上帝造题的七分钟2

Solution由于区间开根号没有可以快速合并的性质,所以如果区间更新必须一直更新到线段树叶节点,显然这样做是每次 $O(n)$ ,肯定 T 了,但是我们可以发现一个数 1e12 只需要开几次根号就会变成 1 或 0,然后他们的根号就是自己本身了,所以在线段树记录一下区间是否都是 0 和 1,如果是就不更新。DescriptionXLk觉得《上帝造题的七分钟》不太过瘾,于是有了第二部。"第一分钟,X说,要有数列,于是便给定了一个正整数数列。第二分钟,L说,要能修改,于是便有了对一段数中每个数都开平方(下取整)的操作。第三分钟,k说,要能查询,于是便有了求一段数的和的操作。第- 阅读剩余部分 -

BZOJ 4289: PA2012 Tax

Solution这题是考最短路建图,还是挺有趣的,但是我 WA 了很多次因为数组开小了和没开 long long,就让人不开心了(垃圾题面没有边权范围)。假设我们有三个点 A、B、C,其中 A 和 B 有一个权值为 v1 的边,B 和 C 有一个权值为 v2 的边,我们把 B 拆成两个点 B1,B2,其中 B1 连 A,B2 连 C,我们假设 v1 < v2,于是我们可以这样开始连边:B1 连 B2 权值为 v2 - v1B2 连 B1 权值为 0A 连 B1 权值为 v1B1 连 A 权值为 0C 连 B2 权值为 v2B2 连 C 权值为 0好好思考一下这种建图方- 阅读剩余部分 -

BZOJ 4152: [AMPPZ2014]The Captain

Solution我们可以发现如果有三个点的 x1 <= x2 <= x3,那么 x1 和 x3 两个点不需要连边,对于 y 也是同样的道理,所以排序后连边跑最短路就可以了。Code#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <set> using namespace std; const int N = 1000010; struct node {int x, y, id;}- 阅读剩余部分 -

FFT模板题:UOJ #34. 多项式乘法 & BZOJ 2179: FFT快速傅立叶

多项式乘法题目链接#include <cstdio> #include <algorithm> #include <cmath> using namespace std; const double PI = acos(-1); const int N = 2e6; struct Complex { double r, i; Complex(double r = 0, double i = 0) {this->r = r; this->i = i;} Complex operator + (Complex- 阅读剩余部分 -

BZOJ 1251: 序列终结者

SolutionSplay 基础题...Code#include <cstdio> #include <algorithm> #include <iostream> #define long long long using namespace std; long n, m; const long N = 50010; struct Node { long max, val, tag, size; bool rev; Node *ch[2], *fa; }pool[N], *null, *root; Node *ne- 阅读剩余部分 -

BZOJ 1014: [JSOI2008]火星人prefix

Solution用 Splay 维护区间 hash 值,然后每次二分长度即可。需要注意的就是这道题的哈希方式,如果想要支持合并操作,需要这么哈希:cur->hash = ls->hash + convert(cur->val) * base[ls->size] + base[ls->size+1] * rs->hash;可以发现每次是左儿子的哈希值 + 自身的值乘左儿子的大小 + 右儿子的哈希值乘上(左儿子大小+1)。这么做我们可以发现,每个数最终都会乘上比自己编号小的点数 - 1。所以树的结构不影响哈希值,就可以放心的用 splay 维- 阅读剩余部分 -

BZOJ 3196: Tyvj 1730 二逼平衡树

Solution可以用线段树套权值线段树无脑做,然而我被卡空间了,不想改了,下面的代码无法 AC,会 MLE。Code#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cmath> #include <queue> using namespace std; const int N = 51000; int n, m; int arr[N]; struct inNode { - 阅读剩余部分 -