NOI2009重庆代表队选拔赛

NOI2009重庆代表队选拔赛

试题一览

题目名称	中位数	叶子的颜色	跳舞	循环赛
题目代号	median	color	dance	Match
时间限制	2秒	2秒	2秒	2秒
内存限制	512M	512M	512M	512M
评分测试点	10	10	10	25
最高得分	100	100	100	100
题目类型	传统	传统	传统	传统

中位数

Median

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

【输入】

第一行为两个正整数n和b，第二行为1~n的排列。

【输出】

输出一个整数，既中位数为b的连续子序列个数。

【样例】

输入	输出
5 4 1 2 3 4 5	2
6 3 1 2 4 5 6 3	1
7 4 5 7 2 4 3 1 6	4

第三个样例解释：{4}，{7，2，4}，{5，7，2，4，3}和{5，7，2，4，3，1，6}。

【数据规模】

编号	1	2	3	4	5	6	7	8	9	10
N	10	0	100	300	1000	3600	10000	25000	55555	100000

叶子的颜色

Color

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。

对于每个叶结点u，定义c[u]为从根结点到u的简单路径上最后一个有色结点的烟丝。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

【输入】

第一行包含两个正整数m，n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，n是叶子。以下n行每行一个0或1的(责海内果树表示黑色，1表示白色)，依次为c[1],c[2]，…，c[n]。以下m-1行每行两个整数a，b（1<=a<b<=m），表示结点a和b有边相连。

【输出】

仅一个数，既着色结点数的最小值。

【样例】

输入

输出

5 3

1 4

2 5

4 5

3 5

【数据规模】

数据	1	2	3	4	5	6	7	8	9	10
m	10	50	100	200	400	1000	4000	8000	10000	10000
n	5	23	50	98	197	498	2044	4004	5021	4996

跳舞

Dance

一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。

有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。

给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

【输入】

第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为“Y”当且仅当男孩i和女孩j相互喜欢。

【输出】

仅一个数，即舞曲数目的最大值。

【样例】

输入	输出
3 0 YYY YYY YYY	3
3 0 YYY YYN YNY	2
2 0 YN YN	0
2 1 YN YN	1

【数据规模】

数据	1	2	3	4	5	6	7	8	9	10
N	1	3	5	8	10	40	40	50	50	50
k	1	2	2	1	4	0	14	10	20	30

循环赛

Match

N支队伍打比赛，每两支队伍恰好比赛一场。平局时各得1分，而有胜负时胜者3分，负者0分。

假设三支队伍得分分别为3，3，3，则可能有两种情况：

队伍	A B C 得分
A B C	- 3 0 3 0 - 3 3 3 0 - 3
队伍	A B C 得分
A B C	- 0 3 3 3 - 0 3 0 3 - 3

给出n支队伍的最终得分（即所有比赛均已结束），统计有多少种可能的分数表。

【输入】

第一行包含一个正整数n，队伍的个数。第二行包含n个非负整数，即每支队伍的得分。

【输出】

输出仅一行，即可能的分数表树木。保证至少存在一个可能的分数表。

【样例】

输入	输出
3 3 3 3	2
2 0 3	1
3 4 1 2	1
6 5 6 7 7 8 8	121

【数据规模】

数据	1	2~3	4~6	7~12	13~19	20~25
n	3	4	5	6	7	8