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

BZOJ 1911: [Apio2010]特别行动队

Solution斜率优化第一题,写个博客记录一下吧,首先根据题意能列出一个 $O(n^2)$ 的转移方程,其中 $s[i]$ 表示前 $i$ 个数的和。$$ f[i] = max( f[j] + a * (s[i] - s[j])^2 + b * (s[i] - s[j]) + c ) $$看一下数据范围 n 在 1e6 左右, $O(n^2)$ 肯定是超时的,考虑斜率优化。假设当前要求 $f[i]$,并且存在两个状态 $j1 < j2$ 可以转移,如果 $j2$ 更优的话,我们需要满足:$$ f[j1] + a * (s[i] - s[j1])^2 + b * (s- 阅读剩余部分 -

BZOJ 3555: [Ctsc2014]企鹅QQ

DescriptionPenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名称总是很相似的,例如Penguin1,Penguin2,Penguin3……于是小Q决定先对这种相似的情形进行统计。小Q定义,若两个账户名称是相似的,当且仅当这两个字符串等长且- 阅读剩余部分 -

BZOJ 1877: [SDOI2009]晨跑

DescriptionElaxia最近迷恋上了空手道,他为自己设定了一套健身计划,比如俯卧撑、仰卧起坐等 等,不过到目前为止,他坚持下来的只有晨跑。 现在给出一张学校附近的地图,这张地图中包含N个十字路口和M条街道,Elaxia只能从 一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校,保证寝室编号为1,学校编号为N。 Elaxia的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的路线,所以 在一个周期内,每天的晨跑路线都不会相交(在十字路口处),寝室和学校不算十字路 口。Elaxia耐力不太好,他希望在一个周期内跑- 阅读剩余部分 -

BZOJ 1040: [ZJOI2008]骑士

DescriptionZ国的骑士团是一个很有势力的组织,帮会中汇聚了来自各地的精英。他们劫富济贫,惩恶扬善,受到社会各界的赞扬。最近发生了一件可怕的事情,邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里,在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上,就像期待有一个真龙天子的降生,带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的,但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士(当然不是他自己),他是绝对不会与自己最厌恶的人一同出征的。战火绵延,人民生灵涂炭,组织起一个骑士军团加入战斗刻- 阅读剩余部分 -

BZOJ 4808: 马 / 3175: [Tjoi2013]攻击装置

Description众所周知,马后炮是中国象棋中很厉害的一招必杀技。"马走日字"。本来,如果在要去的方向有别的棋子挡住(俗称"蹩马腿"),则不允许走过去。为了简化问题,我们不考虑这一点。马跟马显然不能在一起打起来,于是rly在一天再次借来了许多许多的马在棋盘上摆了起来……但这次,他实在没兴趣算方案数了,所以他只想知道在N×M的矩形方格中摆马使其互不吃到的情况下的最多个数。但是,有一个很不幸的消息,rly由于玩得太Happy,质量本来就不好的棋盘被rly弄坏了,不过幸好只是破了其中的一些格子(即不能再放子了),问题还是可以继续解决的。Input一行,两个正整数N和M。接下来- 阅读剩余部分 -