2018年1月

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。接下来- 阅读剩余部分 -

BZOJ 1303: [CQOI2009]中位数图

Description给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。Input第一行为两个正整数n和b ,第二行为1~n 的排列。Output输出一个整数,即中位数为b的连续子序列个数。Sample Input7 4 5 7 2 4 3 1 6 Sample Output4HINT第三个样例解释:{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}N<=100000Solution利用前缀和的思想,把大于 b 的看做 1,小于 b 的看做 -1,等于 b 的看- 阅读剩余部分 -

BZOJ 1087: [SCOI2005]互不侵犯King

Description在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。Input只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)Output方案数。Sample Input3 2Sample Output16 有 16 种Solution简单的状态压缩DP,设 DPi[k] 表示前 i 行放 j 个且最后一行的状态为 k,转移显然。别忘了开 long longCode#include <cstdio>- 阅读剩余部分 -

BZOJ 1692: [Usaco2007 Dec]队列变换

DescriptionFJ打算带他的N(1 <= N <= 30,000)头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中,每个参赛者都必须让他的奶牛排成一列,然后领她们从裁判席前依次走过。 今年,竞赛委员会在接受队伍报名时,采用了一种新的登记规则:他们把所有队伍中奶牛名字的首字母取出,按它们对应奶牛在队伍中的次序排成一列(比如说,如果FJ带去的奶牛依次为Bessie、Sylvia、Dora,登记人员就把这支队伍登记为BSD)。登记结束后,组委会将所有队伍的登记名称按字典序升序排列,就得到了他们的出场顺序。 FJ最近有一大堆事情,因此他不打算在这个比赛上- 阅读剩余部分 -

BZOJ 1031: [JSOI2007]字符加密Cipher

Description喜欢钻研问题的JS同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。例如下图,可以读作:JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0把它们按照字符串的大小排序:07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是突然想出来的,那就^^)。但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?Inpu- 阅读剩余部分 -

BZOJ 1750: [Usaco2005 qua]Apple Catching

Description奶牛爱苹果是一个鲜为人知的事实。农夫约翰在他的田地里有两棵苹果树(方便地编号为1和2),每棵都装满了苹果。贝西在树上时不能接触到苹果,因此必须等待它们落下。但是,自从苹果在地上撞伤(而且没有人想吃苹果)时,她一定要将它们抓在空中。贝茜是一个快速食用的人,所以她吃的苹果只需要几秒钟就能吃掉。每一分钟,两棵苹果树中的一棵掉落一个苹果。如果贝西站在一棵落下的树下,就可以抓到一个苹果。而贝茜可以在两棵树之间快速行走(不到一分钟),她可以随时站在一棵树下。而且,奶牛不会得到很多锻炼,所以她不愿意无休止地在树木之间来回走动(因此错过了一些苹果)。T(1 <=- 阅读剩余部分 -

BZOJ 1901: Zju2112 Dynamic Rankings

Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。Input第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令每行的格式是下面两种格式中的一种。 Q i j k 或者 C- 阅读剩余部分 -

BZOJ 2631: tree

Description一棵n个点的树,每个点的初始权值为1。对于这棵树有q个操作,每个操作为以下四种操作之一:u v c:将u到v的路径上的点的权值都加上自然数c;u1 v1 u2 v2:将树中原有的边(u1,v1)删除,加入一条新边(u2,v2),保证操作完之后仍然是一棵树;u v c:将u到v的路径上的点的权值都乘上自然数c;/ u v:询问u到v的路径上的点的权值和,求出答案对于51061的余数。Input第一行两个整数n,q接下来n-1行每行两个正整数u,v,描述这棵树接下来q行,每行描述一个操作Output对于每个/对应的答案输出一行Sample Input3 2- 阅读剩余部分 -

BZOJ 3282: Tree

Description给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1:后接两个整数(x,y),代表连接x到y,若x到Y已经联通则无需连接。2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。3:后接两个整数(x,y),代表将点X上的权值变成Y。Input第1行两个整数,分别为N和M,代表点数和操作数。第2行到第N+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。第N+2行到第N+M+1行,- 阅读剩余部分 -