2018年2月

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 { - 阅读剩余部分 -

BZOJ 3110: [Zjoi2013]K大数查询

Solution线段树套线段树,外层是权值线段树,内层区间线段树。这样某个区间加一个值就变成了外层线段树单点修改,内层线段树区间加 1。询问的话,在外层线段树上二分就可以了,具体看我代码吧..需要注意开 long long,有负数需要离散化。用指针写树套树,动态开点实现起来更优雅,还不需要提前开数组...#include <cstdio> #include <algorithm> #include <vector> #include <iostream> #define long long long using namespa- 阅读剩余部分 -

BZOJ 1010: [HNOI2008]玩具装箱toy

Solution按照套路推式子就可以了...维护一个斜率递增的凸包。Code#include <cstdio> #include <algorithm> #define long long long using namespace std; const int N = 5e4 + 10; int n, c; long s[N]; long f[N]; double pow(double x) {return x * x;} long pow(long x) {return x * x;} double g(int x) {return s[x] + - 阅读剩余部分 -

奇怪的树

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; struct Node { int size, val; Node *ls, *rs; Node(int s, int v, Node *l, Node *r) { size = s, val = v, ls = l, rs = r; } bool isLeaf() {return ls == NULL;} void - 阅读剩余部分 -

BZOJ 1500: [NOI2005]维修数列

Solution这个题可以说是十分恶心了,但是并没有考太多思维方面的东西,主要考验代码能力,这道题任何一个操作单拿出来做都是比较基础的,混合到一起就比较难以调试了,需要我们理清楚代码的所有细节,我就列出一些需要注意的地方吧!需要插入两个占位的点,分别当做数列头和数列尾,他们的值应该设成 -INF 而不是零或其他值,否则求最大子序列的时候会出错,比如全是负数的数列,如果占位点的值设成零,那么最大子序列的值求出来是零,显然是错误的。注意好空节点,对于指针版是指 null 节点,对于数组版一般值 0 号节点,这些节点的值必须为 0,他们以自身为根的子树大小应该是 0,最重要的是他- 阅读剩余部分 -

BZOJ 1800: [Ahoi2009]fly 飞行棋

Solution暴力找出直径个数,然后任意两条不一样的直径都可以构成一个矩形。计算一下就好了。Code#include <cstdio> #include <algorithm> using namespace std; const int N = 50; int w[N]; int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) { int x; scanf("%d", &x); - 阅读剩余部分 -

BZOJ 2748: [HAOI2012]音量调节

Solution简单的 DPCode#include <cstdio> #include <algorithm> #include <cstring> using namespace std; int f[100][2000]; int a[100]; int main() { int n, m, mx; scanf("%d%d%d", &n, &m, &mx); for(int i=1; i<=n; i++) scanf("%d", &a[i]- 阅读剩余部分 -

BZOJ 1088: [SCOI2005]扫雷Mine

Solution如果我们已知第一个格子是否有雷,我们就可以依次计算出其他格子是否有雷。因此我们枚举一下第一个格子是否有雷,显然答案只能是 1 或 2,别忘了最后一个格子也需要检测是否合法。Code#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1e6; int f[N]; int a[N]; int main() { int n; scanf("%d", &n); - 阅读剩余部分 -

BZOJ 1059: [ZJOI2007]矩阵游戏

Solution我真是太差了,自己想不出来一看题解就懂了..因为只能交换行和列,所以同一行和列内任意两块的相对位置是不变的,据此可以获得一个推论,只要找到 n 个,横纵坐标均不同的点,就可以变换符合题意的情况。然后就可以用把行和列建立二分图,一个点如果为 1,就把对应的行和列连起来,跑一边匈牙利算法,如果所有点都被覆盖,符合题意,否则不符合题意。Code#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 5- 阅读剩余部分 -