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

BZOJ 2049: [Sdoi2008]Cave 洞穴勘测

Description辉辉热衷于洞穴勘测。某天,他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测,辉辉发现这片区域由n个洞穴(分别编号为1到n)以及若干通道组成,并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来,那么这两个洞穴就是连通的,按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏,然而通道不太稳定,时常因为外界影响而发生改变,比如,根据有关仪器的监测结果,123号洞穴和127号洞穴之间有时会出现一条通道,有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的- 阅读剩余部分 -

BZOJ 1208: [HNOI2004]宠物收养所

Description最近,阿Q开了一间宠物收养所。收养所提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物,阿Q根据领养者的要求通过他自己发明的一个特殊的公式,得出该领养者希望领养的宠物的特点值a(a是一个正整数,a<2^31),而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了,宠物收养所总是会有两种情况发生:被遗弃的宠物过多或者是想要收养宠物的人太多,而宠物太少。 1. 被遗弃的宠物过多时,假若到来一个领养者,这个领养者希望领养的宠物的特点值为a,那么它将会领养一只目前未被领养的宠物- 阅读剩余部分 -

BZOJ 3223: Tyvj 1729 文艺平衡树

Description您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1Input第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n) m表示翻转操作次数接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=nOutput输出一行n个数字,表示原始序列经过m次变换后的结果Sample Input5 3 1 3 1 3 1 4Sample Output4 3 2 1 5HINTN,M<=1- 阅读剩余部分 -

BZOJ 1503: [NOI2004]郁闷的出纳员

DescriptionOIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要- 阅读剩余部分 -

【模板】Splay 模板

Splay 模板自己写的模板。#include <cstdio> const int N = 200000; struct node {int d, n, c, f, son[2];}tr[N]; int cnt, root; void up(int x) { int lc = tr[x].son[0], rc = tr[x].son[1]; tr[x].c = tr[lc].c + tr[rc].c + tr[x].n; } int type(int son) {return tr[tr[son].f].son[1] == son;} void- 阅读剩余部分 -