• 【省选模拟赛】小奇的花园

    【省选模拟赛】小奇的花园

    原题:【泉七培训-刘定峰】花园【题目背景】小奇在家中的花园漫步时,总是会思考一些奇怪的问题。【问题描述】小奇的花园有n个温室,标号为1到n,温室以及以及温室间的双向道路形成一棵树。每个温室都种植着一种花,随着季节的变换,温室里的花的种类也在不断发生着变化。小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。【输入格式】第一行为两个整数n,q,表示温室的数目和操作的数目。第二行有n个整数T1...

    32015年12月19日4,397treap,STL,树套树,线段树,树链剖分
  • 【NOIP模拟赛】小奇的数列

    【NOIP模拟赛】小奇的数列

    【题目背景】小奇总是在数学课上思考奇怪的问题。 【问题描述】给定一个长度为n的数列,以及m次询问,每次给出三个数l,r和P,询问(a[l']+a[l'+1]+...+a[r'])modP的最小值。其中l<=l'<=r'<=r。 即模意义下的区间子串和最小值。 【输入格式】第一行包含两个正整数n和m,表示数列的长度和询问的个数。第二行为n个整数,为a[1]..a[n]。接下来m行,每行三个数l,r和P,代表一次询问。 【输出格式】对于...

    92015年9月13日2,140treap
  • 【bzoj3173】[Tjoi2013]最长上升子序列

    【bzoj3173】[Tjoi2013]最长上升子序列

    Description给定一个序列,初始为空。现在我们将1到N的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?Input第一行一个整数N,表示我们要将1到N插入序列中,接下是N个数字,第k个数字Xk,表示我们将k插入到位置Xk(0<=Xk<=k-1,1<=k<=N)OutputN行,第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。SampleInput3002Samp...

    62015年1月29日3,926递推与动规,treap
  • 【vijos1459】车展

    【vijos1459】车展

    描述遥控车是在是太漂亮了,韵韵的好朋友都想来参观,所以游乐园决定举办m次车展。车库里共有n辆车,从左到右依次编号为1,2,…,n,每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子:L1R1L2R2…LmRm单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。为了更加美观,展览时需要调整展台的高度,使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有...

    02015年1月25日1,778treap
  • 【bzoj2761】[JLOI2011]不重复数字

    【bzoj2761】[JLOI2011]不重复数字

    Description给出N个数,要求把其中重复的去掉,只保留第一次出现的数。例如,给出的数为1218331923654,其中2和3有重复,去除后的结果为1218319654。Input输入第一行为正整数T,表示有T组数据。接下来每组数据包括两行,第一行为正整数N,表示有N个数。第二行为要去重的N个正整数。Output对于每组数据,输出一行,为去重后剩下的数字,数字之间用一个空格隔开。SampleInput21112183319236546123456SampleOutput121831...

    22014年11月7日2,999treap,哈希表
  • 【NOIP模拟赛】魔兽争霸

    【NOIP模拟赛】魔兽争霸

    小x正在销魂地玩魔兽他正控制着死亡骑士和n个食尸鬼(编号1~n)去打猎 死亡骑士有个魔法,叫做“死亡缠绕”,可以给食尸鬼补充HP战斗过程中敌人会对食尸鬼实施攻击,食尸鬼的HP会减少 小x希望随时知道自己部队的情况,即HP值第k多的食尸鬼有多少HP,以便决定如何施放魔法请同学们帮助他:) 小x向你发出3种信号:(下划线在输入数据中表现为空格)A_i_a表示敌军向第i个食尸鬼发出了攻击,并使第i个食尸鬼损失...

    12014年10月6日1,808treap
  • 【bzoj1604】[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

    【bzoj1604】[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

    Description了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1≤N≤100000)只奶牛,你会发现她们已经结成了几个“群”.每只奶牛在吃草的时候有一个独一无二的位置坐标Xi,Yi(l≤Xi,Yi≤[1..10^9];Xi,Yi∈整数.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的:  1.两只奶牛的曼哈顿距离不超过C(1≤C≤10^9),即lXi - xil+IYi - Yil≤C.  2.两只奶牛有共同的邻居.即,存在一只奶牛k,...

    12014年9月11日3,527treap,STL
  • 【bzoj3224】Tyvj 1728 普通平衡树

    【bzoj3224】Tyvj 1728 普通平衡树

    Description您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:1.插入x数2.删除x数(若有多个相同的数,因只删除一个)3.查询x数的排名(若有多个相同的数,因输出最小的排名)4.查询排名为x的数5.求x的前驱(前驱定义为小于x,且最大的数)6.求x的后继(后继定义为大于x,且最小的数)Input第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)Output对于操作3,4,5,...

    52014年8月23日7,008treap
  • 【bzoj1483】[HNOI2009]梦幻布丁

    【bzoj1483】[HNOI2009]梦幻布丁

    DescriptionN个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.Input第一行给出N,M表示布丁的个数和好友的操作次数.第二行N个数A1,A2...An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变,其后的两个整数X,Y表示将所有颜色为X的变为Y,X可能等于Y.若第一个数字为2表示...

    12014年8月5日3,977treap,链表
  • 【bzoj3262】陌上花开

    【bzoj3262】陌上花开

    Description有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input第一行为N,K(1<=N<=100,000,1<=K<=200,000),分别表示花的数量和最大属性值。以下N行,每行三个整数...

    02014年6月19日4,656treap,树套树,树状数组
  • 【bzoj1146】[CTSC2008]网络管理Network

    【bzoj1146】[CTSC2008]网络管理Network

    DescriptionM公司是一个非常庞大的跨国公司,在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作,公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器,部门局域网内的所有机器都联向这个路由器,然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通...

  • 【bzoj2391】Cirno的忧郁

    【bzoj2391】Cirno的忧郁

    DescriptionCirno闲着无事的时候喜欢冰冻青蛙。Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形,Cirno运用自己的能力能将此多边形内所有青蛙冰冻。雾之湖生活着m只青蛙,青蛙有大有小,所以每只青蛙的价值为一个不大于10000的正整数。Cirno很想知道每次冻住的青蛙的价值总和。因为智商有限,Cirno将这个问题交给完美算术教室里的你。因为爱护动物,所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次...

    02014年6月13日2,050treap,几何
  • 【bzoj1112】[POI2008]砖块Klo

    【bzoj1112】[POI2008]砖块Klo

    DescriptionN柱砖,希望有连续K柱的高度是一样的.你可以选择以下两个动作1:从某柱砖的顶端拿一块砖出来,丢掉不要了.2:从仓库中拿出一块砖,放到另一柱.仓库无限大.现在希望用最小次数的动作完成任务.Input第一行给出N,K.(1≤k≤n≤100000),下面N行,每行代表这柱砖的高度.0≤hi≤1000000Output最小的动作次数SampleInput5339231SampleOutput2HINT原题还要求输出结束状态时,每柱砖的高度.本题略去.题解据说有很多做法,...

    32014年5月27日2,966treap
1 / 2 1 2 下一页 »