Problem

【SCOI2007】组队

Time  Limit:  3  Sec\mathrm{Time\;Limit:\;3\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

NBANBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为minVmin_V,身高最矮的球员高度为minHmin_H,那么这支球队的所有队员都应该满足:A×(heightminH)+B×(speedminV)CA\times(height-min_H)+B\times(speed-min_V)\le C。其中AAB,CB,C为给定的经验值。这个式子很容易理解,如果一个球队的球员速度和身高差距太大,会造成配合的不协调。 请问作为球队管理层的你,在NN名选秀球员中,最多能有多少名符合条件的候选球员。

Input

第一行四个数N,A,B,CN,A,B,C
下接NN行每行两个数描述一个球员的heightheightspeedspeed

Output

最多候选球员数目。

Read more »

Problem

最假女选手

Time  Limit:  50  Sec\mathrm{Time\;Limit:\;50\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

在刚刚结束的水题嘉年华的压轴节目放水大赛中,wyywyy\mathrm{wyywyy}如愿以偿的得到了最假女选手的奖项。但是作为主办人的C_SUNSHINE\mathrm{C\_SUNSHINE}为了证明wyywyy\mathrm{wyywyy}确实在放水,决定出一道基础题考察wyywyy\mathrm{wyywyy}的姿势水平。给定一个长度为NN序列,编号从11NN。要求支持下面几种操作:

  1. 给一个区间[L,R][L,R]加上一个数xx
  2. 把一个区间[L,R][L,R]里小于xx的数变成xx
  3. 把一个区间[L,R][L,R]里大于xx的数变成xx
  4. 求区间[L,R][L,R]的和
  5. 求区间[L,R][L,R]的最大值
  6. 求区间[L,R][L,R]的最小值

Input

第一行一个整数NN表示序列长度
第二行NN个整数AiA_i表示初始序列
第三行一个整数MM表示操作个数
接下来MM行,每行三或四个整数,第一个整数TpTp表示操作类型,接下来L,R,XL,R,XL,RL,R表述操作数

Output

对于每个4,5,64,5,6类型的操作,输出一行一个整数表示答案

Read more »

Problem

【HNOI2008】神奇的国度

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

KK国是一个热衷三角形的国度,连人的交往也只喜欢三角原则。他们认为三角关系:即A,BA,B相互认识,B,CB,C相互认识,C,AC,A相互认识,是简洁高效的。
为了巩固三角关系,KK国禁止四边关系,五边关系等等的存在。所谓NN边关系,是指NN个人A1,A2AnA_1,A_2\cdots A_n之间仅存在NN对认识关系:(A1,A2)(A2,A3)(An,A1)(A_1,A_2)(A_2,A_3)\cdots(A_n,A_1),而没有其它认识关系。比如四边关系指A,B,C,DA,B,C,D四个人 (A,B)(A,B)(B,C)(B,C)(C,D)(C,D)(D,A)(D,A)相互认识,而(A,C)(A,C)(B,D)(B,D)不认识。
全民比赛时,为了防止做弊,规定任意一对相互认识的人不得在一队。国王想知道,最少可以分多少支队。

Input

第一行两个整数N,MN,M。表示有NN个人,MM对认识关系。
接下来MM行每行输入一对朋友。

Output

输出一个整数,最少可以分多少队。

Read more »

Problem

【SCOI2008】斜堆

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

斜堆(skew  heap)\mathrm{(skew\;heap)}是一种常用的数据结构。它也是二叉树,且满足与二叉堆相同的堆性质:每个非根结点的值都比它父亲大。因此在整棵斜堆中,根的值最小。但斜堆不必是平衡的,每个结点的左右儿子的大小关系也没有任何规定。在本题中,斜堆中各个元素的值均不相同。
在斜堆HH中插入新元素XX的过程是递归进行的:

  • HH为空或者XX小于HH的根结点时X变为新的树根,而原来的树根(如果有的话)变为XX的左儿子。
  • XX大于HH的根结点时,HH根结点的两棵子树交换,而XX(递归)插入到交换后的左子树中。

给出一棵斜堆,包含值为0n0\sim n的结点各一次。求一个结点序列,使得该斜堆可以通过在空树中依次插入这些结点得到。
如果答案不惟一,输出字典序最小的解。输入保证有解。

Input

第一行包含一个整数nn
第二行包含nn个整数d1,d2,,dnd_1,d_2,\cdots,d_ndi<100d_i<100表示iidid_i的左儿子,di100d_i\ge100表示iidi100d_i-100的右儿子。
显然00总是根,所以输入中不含d0d_0

Output

仅一行,包含n+1n+1整数,即字典序最小的插入序列。

Read more »

Problem

YY的GCD

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}

Description

神犇YY\mathrm{YY}虐完数论后给傻叉kAc\mathrm{傻叉kAc}出了一题:
给定N,MN,M,求1xN,  1yM1\le x\le N,\;1\le y\le Mgcd(x,y)\gcd(x, y)为质数的(x,y)(x, y)有多少对
kAc\mathrm{kAc}这种傻叉\mathrm{傻叉}必然不会了,于是向你来请教。
多组输入。

Input

第一行一个整数TT表述数据组数。
接下来TT行,每行两个正整数,表示N,MN,M

Output

TT行,每行一个整数表示第ii组数据的结果。

Read more »

Problem

【HAOI2007】覆盖问题

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

某人在山上种了NN棵小树苗。冬天来了,温度急速下降,小树苗脆弱得不堪一击,于是树主人想用一些塑料薄膜把这些小树遮盖起来,经过一番长久的思考,他决定用33L×LL\times L的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系,设第ii棵小树的坐标为(Xi,Yi)(X_i,Y_i)33L×LL\times L的正方形的边要求平行与坐标轴,一个点如果在正方形的边界上,也算作被覆盖。当然,我们希望塑料薄膜面积越小越好,即求L最小值。

Input

第一行有一个正整数NN,表示有多少棵树。
接下来有NN行,第i+1i+1行有22个整数Xi,YiX_i,Y_i,表示第ii棵树的坐标,保证不会有22个树的坐标相同。

Output

一行,输出最小的LL值。

Read more »

Problem

小猴打架

Time  Limit:  5  Sec\mathrm{Time\;Limit:\;5\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

一开始森林里面有NN只互不相识的小猴子,它们经常打架,但打架的双方都必须不是好朋友。每次打完架后,打架的双方以及它们的好朋友就会互相认识,成为好朋友。经过N1N-1次打架之后,整个森林的小猴都会成为好朋友。 现在的问题是,总共有多少种不同的打架过程。 比如当N=3N=3时,就有{12,13}\lbrace1-2,1-3\rbrace {12,23}\lbrace1-2,2-3\rbrace {13,12}\lbrace1-3,1-2\rbrace {13,23}\lbrace1-3,2-3\rbrace {23,12}\lbrace2-3,1-2\rbrace {23,13}\lbrace2-3,1-3\rbrace六种不同的打架过程。

Input

一个整数NNN106N\le10^6

Output

一行,方案数mod9999991\mod{9999991}

Read more »

Problem

【JSOI2007】合金

Time  Limit:  4  Sec\mathrm{Time\;Limit:\;4\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。 现在,用户给出了nn种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料,并且使用这些原材料可以加工出用户需要的所有种类的合金。

Input

第一行两个整数mmnn(m,n500)(m,n\le500),分别表示原材料种数和用户需要的合金种数。第22m+1m+1行,每行三个实数a,b,c(a,b,c0a+b+c=1)a,b,c(a,b,c\ge0且a+b+c=1),分别表示铁铝锡在一种原材料中所占的比重。第m+2m+2m+n+1m+n+1行,每行三个实数a,b,c(a,b,c0a+b+c=1)a,b,c(a,b,c\ge0且a+b+c=1),分别表示铁铝锡在一种用户需要的合金中所占的比重。

Output

一个整数,表示最少需要的原材料种数。若无解,则输出1–1

Read more »

Problem

【ZJOI2007】Hide捉迷藏

Time  Limit:  40  Sec\mathrm{Time\;Limit:\;40\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

捉迷藏Jiajia\mathrm{Jiajia}Wind\mathrm{Wind}是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia\mathrm{Jiajia}Wind\mathrm{Wind}和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由NN个屋子和N1N-1条双向走廊组成,这N1N-1条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的,孩子们负责躲藏,Jiajia\mathrm{Jiajia}负责找,而Wind\mathrm{Wind}负责操纵这NN个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia\mathrm{Jiajia}希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。
我们将以如下形式定义每一种操作:

  • C(hange)  i\mathrm{C(hange)}\;i :改变第ii个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。
  • G(ame)\mathrm{G(ame)} :开始一次游戏,查询最远的两个关灯房间的距离。

Input

第一行包含一个整数NN,表示房间的个数,房间将被编号为1,2,3N1,2,3\cdots N的整数。接下来N1N-1行每行两个整数a,ba,b,表示房间aa与房间bb之间有一条走廊相连。接下来一行包含一个整数QQ,表示操作次数。接着QQ行,每行一个操作,如上文所示。

Output

对于每一个操作G(ame)\mathrm{G(ame)},输出一个非负整数,表示最远的两个关灯房间的距离。
若只有一个房间是关着灯的,输出00;若所有房间的灯都开着,输出1-1

Read more »

Problem

【SCOI2007】压缩

Time  Limit:  1  Sec\mathrm{Time\;Limit:\;1\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以(但不必)包含大写字母R\mathrm{R}M\mathrm{M},其中M\mathrm{M}标记重复串的开始,R\mathrm{R}重复从上一个M\mathrm{M}(如果当前位置左边没有M\mathrm{M},则从串的开始算起)开始的解压结果(称为缓冲串)。 bcdcdcdcd\mathrm{bcdcdcdcd}可以压缩为bMcdRR\mathrm{bMcdRR},下面是解压缩的过程:

另一个例子是abcabcdabcabcdxyxyz\mathrm{abcabcdabcabcdxyxyz}可以被压缩为abcRdRMxyRz\mathrm{abcRdRMxyRz}

Input

输入仅一行,包含待压缩字符串,仅包含小写字母,长度为nn

Output

输出仅一行,即压缩后字符串的最短长度。

Read more »