停课集训Day1

今天是为期9天的省选集训第一天，一大早过来就考试。我还迟到了45分钟。题目是NOI2009重庆代表队选拔赛的原题。我把它发在下面，同时您还能在我的网络硬盘里找到Word版本。不清楚此试题的版权情况，如版权所有者不希望试题被公布，请尽快联系我，我会在第一时间内删除。

中位数 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 50 100 300 1000 3600 10000 25000 55555 100000

叶子的颜色color

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。
对于每个叶结点u，定义c[u]为从根结点到u的简单路径上第一个最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。
【输入】第一行包含两个正整数m, n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，m，其中编号1，2，… ，n是叶子。以下n行每行一个0或1的整数（0表示黑色，1表示白色），依次为c[1]，c[2]，…，c[n]。以下m-1行每行两个整数a，b（1<=a < b <= m），表示结点a和b 有边相连。
【输出】仅一个数，即着色结点数的最小值。
【样例】
输入
5 3
0
1
0
1 4
2 5
4 5
3 5
输出
2
【数据规模】
数据 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 - 3 0 3
B 0 - 3 3
C 3 0 - 3
队伍 A B C 得分
A - 0 3 3
B 3 - 0 3
C 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

我来写个简单的题解，用来备忘。

中位数：记录下从1到i的，比给定数大的数字的个数big[i]，比给定数小的数字的个数small[i]。我们即要求这样的i、j组数，即big[ j ] – big[ i - 1] == small[ j ] – small[ i - 1 ]，同时i小于等于给定数所在的位置，j大于等于给定数所在的位置。上式变形得big[ j ] – small[ j ] == big[ i - 1 ] – small[ i - 1 ]。令t[ i ] = big[ i ] – small[ i ]，枚举i作为目标序列的结尾（一定要在给定数的后面），那么所有在给定数之前出现的t[ k ]的个数就是以i为结尾的符合题意的序列数。

叶子的颜色：注意题目有修改！（看上面。）树形动归。先枚举一个根，对每个点有3个状态：黑、白、无色，表示当前节点在这个状态下要满足题意需要的代价。每个叶子节点涂对应颜色的代价为1，其余为无穷大。一个节点，例如涂黑色，那么代价就是每个min(儿子涂黑色-1,儿子涂白色,儿子不涂)的和加1。如果不涂色，就是每个min(儿子涂黑色,儿子涂白色,儿子不涂)的和。到最后只要用枚举根的三个值里的最小值去更新全局答案就可以了。O(n^2)的算法会超时。实践发现任选节点作为根的答案是一样的。当然也可以进行优化，能够在枚举根的情况下优化到O(n)级别。我没有具体实践过，留给读者思考。

跳舞：二分答案，网络流。构图：讲每个男男女女都拆成两个点，喜欢和不喜欢。从源向男喜欢连一条容量为枚举答案的边，男喜欢向男不喜欢连一条容量为k的边，女不喜欢向女喜欢连一条容量为k的边，女喜欢向汇连一条为枚举答案的边。对于相互喜欢的男女，从男喜欢到女喜欢连一条为1的边，相互不喜欢的男女，从男不喜欢到女不喜欢连一条为1的边。如果最大流为枚举的n倍，那么这个答案是可行的，否则不可行。

循环赛：可以用最小表示来压缩状态，但是我不会写。如果写搜索的话，超时3个点（共25个点）。先从小到大排序，然后枚举每支队伍与其他队伍的比赛结果。一个可行性剪枝，如果当前队伍枚举完要枚举下一支的时候，如果当前队伍的分数不等于要求的分数的话，剪枝。

我总共344分，我们班有388分的大牛，只在最后一题超时3点！我的结果：第一题AC，第二题超时3个点，第三题骗分90分（今天RP暴涨了？我写了个匈牙利算法，先对相互喜欢的人做，如果有完备匹配，那么把那些匹配边删掉，再做下一次。然后把不喜欢的边加上，至多做k次。当然小数据是要搜索的！删边是绝对不行的，但是为什么能对这么多呢？），最后题搜索超4个点。

就这样，第一天过去了。

题目和数据都可以在我的网络硬盘里找到，您可以点这里直接进入本文相关的目录。