停课集训Day2

题目是上海市NOI2008选拔赛的原题。我把它发在下面，同时您还能在我的网络硬盘里找到Word版本。不清楚此试题的版权情况，如版权所有者不希望试题被公布，请尽快联系我，我会在第一时间内删除。

循环的债务 Debt
【问题描述】
Alice、Bob和Cynthia总是为他们之间混乱的债务而烦恼，终于有一天，他们决定坐下来一起解决这个问题。不过，鉴别钞票的真伪是一件很麻烦的事情，于是他们决定要在清还债务的时候尽可能少的交换现金。
比如说，Alice欠Bob 10元，而Cynthia和他俩互不相欠。现在假设Alice只有一张50元，Bob有3张10元和10张1元，Cynthia有3张20元。一种比较直接的做法是：Alice将50元交给Bob，而Bob将他身上的钱找给Alice，这样一共就会有14张钞票被交换。但这不是最好的做法，最好的做法是：Alice把50块给Cynthia，Cynthia再把两张20给Alice，另一张20给Bob，而Bob把一张10块给C，此时只有5张钞票被交换过。
没过多久他们就发现这是一个很棘手的问题，于是他们找到了精通数学的你为他们解决这个难题。
【输入文件】
输入的第一行包括三个整数：x1、x2、x3（-1,000≤x1，x2，x3≤1,000），其中
x1代表Alice欠Bob的钱（如果x1是负数，说明Bob欠了Alice的钱）
x2代表Bob欠Cynthia的钱（如果x2是负数，说明Cynthia欠了Bob的钱）
x3代表Cynthia欠Alice的钱（如果x3是负数，说明Alice欠了Cynthia的钱）
接下来有三行，每行包括6个自然数：
a100，a50，a20，a10，a5，a1
b100，b50，b20，b10，b5，b1
c100，c50，c20，c10，c5，c1
a100表示Alice拥有的100元钞票张数，b50表示Bob拥有的50元钞票张数，以此类推。另外，我们保证有a10+a5+a1≤30，b10+b5+b1≤30，c10+c5+c1≤30，而且三人总共拥有的钞票面值总额不会超过1,000。
【输出文件】
如果债务可以还清，则输出需要交换钞票的最少张数；如果不能还清，则输出“impossible”（注意单词全部小写，输出到文件时不要加引号）。
【样例】
10 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0
输出 5
-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
输出 0
【数据规模】
对于30%的数据，x1、x2、x3 ≤ |50|。
对于100%的数据，x1、x2、x3 ≤ |1,000|。

小约翰的游戏 John
【问题描述】
小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有n堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。
小约翰相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的哥哥就聪明多了，他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。
【输入文件】
本题的输入由多组数据组成，第一行包括一个整数T，表示输入总共有T组数据（T≤500）。
每组数据的第一行包括一个整数N（N≤50），表示共有N堆石子，接下来有N个不超过5000的整数，分别表示每堆石子的数目。
【输出文件】
每组数据的输出占一行，每行输出一个单词。如果约翰能赢得比赛，则输出“John”，否则输出“Brother”，请注意单词的大小写。
【样例】
2
3
3 5 1
1
1
输出
John
Brother
【数据规模】
对于40%的数据，T ≤ 250。
对于100%的数据，T ≤ 500。

仙人图(II) Cactus
【问题描述】
如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。
举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也不是仙人图，因为它并不是连通图。
显然，仙人图上的每条边，或者是这张仙人图的桥（bridge），或者在且仅在一个简单回路里，两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1，你的任务是求出给定的仙人图的直径。
【输入文件】
输入的第一行包括两个整数n和m（1≤n≤50,000以及0≤m≤10,000）。其中n代表顶点个数，我们约定图中的顶点将从1到n编号。
接下来一共有m行。代表m条路径。每行的开始有一个整数k（2≤k≤1000），代表在这条路径上的顶点个数。接下来是k个1到n之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条连接这两个顶点的边。一条路径上可能通过一个顶点好几次，比如对于第一个样例，第一条路径从3经过8，又从8返回到了3，但是我们保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。
【输出文件】
只需输出一个数，这个数表示仙人图的直径长度。
【样例】
15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10
输出 8
10 1
10 1 2 3 4 5 6 7 8 9 10
输出 9
对第一个样例的说明：
如图，6号点和12号点的最短路径长度为8，所以这张图的直径为8。
使用Pascal语言的选手请注意：
你的程序在处理大数据的时候可能会出现栈溢出。如果需要调整栈空间的大小，可以在程序的开头填加一句：{$M 5,000,000}，其中5,000,000即指代栈空间的大小，请根据自己的程序选择适当的数值。
【数据规模】
对于30%的数据，m ≤ 50。
对于100%的数据，m ≤ 1,000。

今天的题目有点难，我还没有全部写过。下面的题解仅用来备忘，希望大牛能提供更好的题解。

循环的债务：听同学说是一个动态规划，用f[i][j]表示Alice有现金i，Bob有现金j需要的代价，然后转移，也有人用BFS过了。我只过了两个点:(

小约翰的游戏：Nim游戏的改编。我当时是画出了[3,3]为起始状态的有向图，根据ICG的定义，手算答案。与经典的Nim游戏答案比较发现，只有在所有状态都为0或1的时候出现不一向。大胆猜测，特判这种情况，居然AC了！后来有同学证明了这是正确的算法。

仙人图(II)：我写的只是裸的枚举根BFS，居然只有10分！数据不厚道，一个小一点的点都没有！这题应该是一个树形动归或者类似的题目，下午大家讨论了大半天，好像是DFS下来，根据是不是环的起点什么的采取不同的操作。求强连通分支然后缩点应该也是可以的吧，只是还是很麻烦？听说太复杂了，我也就顿时失去了写的欲望。另外，这题是欧洲某ACM比赛的原题。

题目和相关数据在这里。

停课集训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个点。

就这样，第一天过去了。

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