NIRVANA

Problem

【SCOI2007】组队

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

Description

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

Input

第一行四个数$N,A,B,C$。
下接$N$行每行两个数描述一个球员的$height$和$speed$。

Output

最多候选球员数目。

Problem

最假女选手

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

Description

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

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

Input

第一行一个整数$N$表示序列长度
第二行$N$个整数$A_i$表示初始序列
第三行一个整数$M$表示操作个数
接下来$M$行，每行三或四个整数，第一个整数$Tp$表示操作类型，接下来$L,R,X$或$L,R$表述操作数

Output

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

Problem

【HNOI2008】神奇的国度

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

Description

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

Input

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

Output

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

Problem

【SCOI2008】斜堆

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

Description

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

• 当$H$为空或者$X$小于$H$的根结点时X变为新的树根，而原来的树根（如果有的话）变为$X$的左儿子。
• 当$X$大于$H$的根结点时，$H$根结点的两棵子树交换，而$X$（递归）插入到交换后的左子树中。

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

Input

第一行包含一个整数$n$。
第二行包含$n$个整数$d_1,d_2,\cdots,d_n$，$d_i<100$表示$i$是$d_i$的左儿子，$d_i\ge100$表示$i$是$d_i-100$的右儿子。
显然$0$总是根，所以输入中不含$d_0$。

Output

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

Problem

YY的GCD

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

Description

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

Input

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

Output

$T$行，每行一个整数表示第$i$组数据的结果。

Problem

【HAOI2007】覆盖问题

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

Description

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

Input

第一行有一个正整数$N$，表示有多少棵树。
接下来有$N$行，第$i+1$行有$2$个整数$X_i,Y_i$，表示第$i$棵树的坐标，保证不会有$2$个树的坐标相同。

Output

一行，输出最小的$L$值。

Problem

小猴打架

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

Description

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

Input

一个整数$N$，$N\le10^6$

Output

一行，方案数$\mod{9999991}$。

Problem

【JSOI2007】合金

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

Description

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

Input

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

Output

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

Problem

【ZJOI2007】Hide捉迷藏

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

Description

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

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

Input

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

Output

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

Problem

【SCOI2007】压缩

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

Description

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

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

Input

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为$n$。

Output

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