stupid家族练习题

admin

愚蠢的宠物
提交文件：pet(.pas/.c/.cpp)
输入文件：pet.in
输出文件：pet.out
背景
大家都知道，sheep有两只可爱的宠物（一只叫神牛，一只叫神菜）。有一天，sheep带着两只宠物到狗狗家时，这两只可爱的宠物竟然迷路了……

描述
狗狗的家因为常常遭到猫猫的攻击，所以不得不把家里前院的路修得非常复杂。狗狗家前院有N个连通的分叉结点，且只有N-1条路连接这N个节点，节点的编号是1-N（1为根节点）。sheep的宠物非常笨，他们只会向前走，不会退后（只向双亲节点走），sheep想知道他们最早什么时候会相遇（即步数最少）。


输入格式
第1行：一个正整数N，表示节点个数。
第2~N行：两个非负整数A和B，表示A是B的双亲。（保证A,B<=n）
第N+1行：两个非负整数A和B，表示两只宠物所在节点的位置。（保证A,B<=n）

输出格式
输出他们最早相遇的节点号。

样例输入
10
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
3 6
样例输出
1

数据范围
对于10%的数据，n<10^6
对于100%的数据，n<=10^6































愚蠢的组合数
提交文件：parity(.pas/.c/.cpp)
输入文件：parity.in
输出文件：parity.out

背景
最近老师教了狗狗怎么算组合数，狗狗又想到了一个问题。。。

描述
狗狗定义C(N,K)表示从N个元素中不重复地选取K个元素的方案数。
狗狗想知道的是C(N,K)的奇偶性。
当然，这个整天都老是用竖式算123456789*987654321=？的人不会让你那么让自己那么轻松，它说：“N和K都可能相当大。”
但是狗狗也犯难了，所以它就找到了你，想请你帮他解决这个问题。

输入格式
第1行：一个正整数t，表示数据的组数。
第2~2+t-1行：两个非负整数N和K。（保证k<=n）

输出格式
每一组输入，如果C(N,K)是奇数则输出1，否则输出0。

样例输入
3
1 1
1 0
2 1

样例输出
1
1
0

数据范围
对于30% 的数据，n<=10^2 t<=10^4
对于50% 的数据，n<=10^3 t<=10^5
对于100%的数据，n<=10^8 t<=10^5




愚蠢的矿工
提交文件：mining(.pas/.c/.cpp)
输入文件：mining.in
输出文件：mining.out

背景
Stupid 家族得知在HYC家的后花园里的中央花坛处,向北走3步,向西走3步,再向北走3步,向东走3步,再向北走6步,向东走3步,向南走12步,再向西走2步( - -||)就能找到宝藏的入口,而且宝藏都是藏在山里的,必须挖出来,于是Stupid家族派狗狗带领矿工队去挖宝藏.(HYC家的宝藏被狗狗挖走后有什么感想?)

描述
这个宝藏的制造者为了掩盖世人耳目,他做的宝藏是没有出口,只有入口,不少建造宝藏的人都死在里面.现在知道宝藏总共有N个分岔口,在分岔口处是有财宝的,每个宝藏点都有一个财富值.狗狗只带了M个人来,而且为了安全起见,在每个分岔口,必须至少留一个人下来,这个留下来的人可以挖宝藏(每个人只能挖一个地方的宝藏),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通.狗狗为了让他的00开心,决定要尽可能地多挖些宝藏回去.现在狗狗的圈叉电脑不在身旁,只能求救于你了,你要知道,狗狗的终身幸福就在你手上了..（狗狗ps：00，你不能就这样抛弃偶……）
输入格式
第1行：两个正整数N,M .N表示宝藏点的个数,M表示狗狗带去的人数(那是一条懒狗,他自己可不做事)。(m<=100)
第2行：N个整数,第i个整数表示第i个宝藏的财富值.(保证|wi|<maxint)
第N+2行：两个非负整数A和B，表示A通向B,当A=0,表示A是入口.（保证A,B<=n）

输出格式
输出狗狗能带回去的宝藏的价值。

样例输入
4 3
5 6 2 4
1 2
0 1
2 3
3 4
样例输出
13

数据范围
对于10%的数据，n<10
对于100%的数据，n<=1000

愚蠢的村庄
提交文件：village(.pas/.c/.cpp)
输入文件：village.in
输出文件：village.out

背景
Stupid家族的成员们生活在一个名为Stupid的村庄。
话说村里的人要喝水都得到很远很远的另一个Genius村庄打水，这并不算什么，因为Stupid村庄的村民都很勤劳不怕苦。最郁闷的是Genius村庄的村民总是无端BS我们的村民，老是问一些“1+1等于多少”的问题，害得我们答不上来。于是hyc提出要在我们自己村里建一口水井。抛开受BS的日子。

描述
  Stupid村庄的村民是愚蠢的，这个村庄也是愚蠢的，他们不知道如何布置自己的村庄，所以村庄的结构很简单。我们设整个村庄处在一个坐标系的第一象限。
  而在Stupid村庄里有N座房子，这房子也是愚蠢的。它很扁，可以近似得看做一条直线；它还是平行于坐标轴的（Stupid村民是迷信的…方方正正才是美…）。
现在，要在村里建一水井，我们要使所有房子到水井的距离和最短。
设某一房子的两端点分别为（1，3），（3，3）。若水井的横坐标1〈=x〈=3， 则水井到房子的距离为 abs（水井纵坐标-1），即图中L1，否则（x〈 1 或 x 〉3），距离为min{水井到左端点的距离，水井到右端点的距离}，即图中L2。换句话说，让村民们来打水所走的距离和最短。


输入格式
输入文件village.in的第一行为一个正整数N（N〈=100）。
接下来N行输入N座房子的信息，每行为四个非负整数，分别表示房子两端点的坐标。
房子的所有坐标都为0到100间的非负整数。

输出格式
输出文件village.out有且仅有一行，为所求的最短距离（保留两位小数）。

样例输入
3
0 0 0 1
2 2 3 2
4 4 4 3  


样例输出
4.47

admin

首先给这个题定性----虽然这个题目是经典的LCA（最近公共祖先）问题，但是它是水题。
接着分析一下这个题目，“N个连通的分叉结点，且只有N-1条路连接这N个节点”保证了问题的模型是一个树，那么我们就只要求出给定的两个节点到根的路径的最近的交点就可以了，即两个节点的LCA。
经典问题当然交给经典算法。LCA问题有一个名叫Tarjan的时间复杂度仅为O（n+Q）的离线算法。很快吧？对，很快。很简单吧？对，很简单，只要一次DFS遍历加上并查集就可以轻松完成了。

Tarjan算法的过程如下：
（1）        建立仅含i点的集合S[i]
（2）        DFS遍历树，当遍历节点i时，处理所有有关子树的询问A（p，q），如果S[i]中包含节点p、q，那么A（p，q）=i，否则进入下一步
（3）        将s[i]合并到s[Father[i]]中
（S用并查集实现）（啥叫并查集?不懂就看资料。找不到资料？没事，反正你能AC这题）

但是，有必要吗？没必要！对于本题，只有一次询问，采用朴素算法就可以啦。
啥叫朴素算法？首先从节点p开始将p的祖先包括p本身作上标记，然后从q开始向上寻找，找到第一个已标记的节点就是答案拉~
你说这算法慢？是啊，但是AC就是硬道理，渐进时间复杂度小不是好！

最后说一下数据（因为sheep出数据的时候dog就不停地强调，题目越简单，数据越要阴）
有些数据，p=q
有些数据，p=root
有些数据，LCA（p、q）=p
有些数据，LCA（p、q）=root
。。。
虽然这些数据也算不上阴险，但是希望大家在Submit之前要把这些相对比较特殊的情况考虑下哦。

（这个题是sheep出的，为啥是dog写报告？因为dog比较扯。-_-b sheep原报告貌似4行）

admin

愚蠢的组合数 解题报告
预备知识
C(n, 0) = C(n, n) = 1 (n > 0;)
C(n, k) = C(n − 1, k − 1) + C(n − 1, k) (0 < k < n)

算法一
有了预备知识里面的公式，我们可以得到一个最简单的算法。
先预处理算出所有的C(n,k)。
然后再读入，输出。
但是这样会产生一个问题，当n比较大的时候，C(n,k)会超出longint的范围。
解决方法？高精度！。
由于高精度的速度限制，所以这个算法只能过30％的点。

算法二
观察题目输出，其实就是输出C(n,k)mod 2=.这样可以运用同余算术的性质。
(a + b)mod k=((a mod k)+(b mod k))mod k
（由于是mod 2，还可以写成and 1，利用位运算加速）
原式变为：
C(n, k) = (C(n − 1, k − 1) + C(n − 1, k)) mod 2 (0 < k < n)
这样好多了，可以过50％的点。

算法三
直接的递推算法还可以优化嘛？找不出了。那我们掉换思路，从规律入手。
将前面的情况全部打印出来，我们可以发现。
其实就是一个 的三角形分解为四个 的三角形，中间一个三角形全为0，
余下三个三角形继续分解。详见程序和下面的附表
这个规律比较严格的描述是这样的，设N=XaXa-1Xa-2…X1（2），K=YbYb-1Yb-2…Y1（2）
（即用二进制表示）C(n,k)为偶的充分必要条件是存在i使得Xi<Yi
这样可以通过100%的点。











附表：ｎ＝32的情况（注：为了整齐0写成00，1写成11）
11
1111
110011
11111111
1100000011
111100001111
11001100110011
1111111111111111
110000000000000011
11110000000000001111
1100110000000000110011
111111110000000011111111
11000000110000001100000011
1111000011110000111100001111
110011001100110011001100110011
11111111111111111111111111111111
1100000000000000000000000000000011
111100000000000000000000000000001111
11001100000000000000000000000000110011
1111111100000000000000000000000011111111
110000001100000000000000000000001100000011
11110000111100000000000000000000111100001111
1100110011001100000000000000000011001100110011
111111111111111100000000000000001111111111111111
11000000000000001100000000000000110000000000000011
1111000000000000111100000000000011110000000000001111
110011000000000011001100000000001100110000000000110011
11111111000000001111111100000000111111110000000011111111
1100000011000000110000001100000011000000110000001100000011
111100001111000011110000111100001111000011110000111100001111
11001100110011001100110011001100110011001100110011001100110011
1111111111111111111111111111111111111111111111111111111111111111
110000000000000000000000000000000000000000000000000000000000000011

admin

题目分析:
这道题的模型就是典型的树型DP.不知道大家是否看懂了题目,出题人蛤蟆本人觉得题意是清楚的,给了几位大牛们看了,都能理解题意.如果确实看不懂的也不要埋怨,NOIP2006提高组的第三题,就是一个典型,为了备战NOIP,请各位选手锻炼一下自己的阅读能力.
然后就从题目分析,题目中有句话说: 任意两点间有且只有一条路可通,也就是说这是一棵树,一棵以入口为根的树,这样数据结构就搞定了. ”每个人只能挖一个地方的宝藏”这句话说明每个人只能覆盖一个结点,那么M个就最多能覆盖M个结点.而且这M个点连成的也是一棵树.而且这棵树的所有结点的权和必须最大.这样一来我们最容易想到的就是动态规划.

算法分析:
题目中没准确说明这是一棵二叉树,所以这个宝藏应该是一棵多叉树.由于” 在每个分岔口,必须至少留一个人下来”这句话,说明要取一个点的子结点,就必须先取这个点.而取了这个点,总的M个人就会变成M-1个人,我们用f(i,j)表示取j个人到了第i个结点能够取到的最优值.f(0,m)就是答案.
但是如果直接DP一棵多叉树,是有问题的,(出题人太水,不会).所以我就先把多叉树转化为二叉树,按照左儿子右兄弟转化.就把一棵多叉树转化成二叉树了.然后这个问题就变得非常极其十分简单了.
方程:f(i,j):=max{max{f(tree[i].l,k)+f(tree[i].r,j-1-k)}(0<=k<=j-1),f(tree[i].r,j)}

数据分析:
数据给定的规模是N<=1000,M<=100,DP的时间复杂度和空间复杂度都是没问题的.一开始输入的一棵树,应该怎样存储?应该N<=1000,所以直接用邻接表是没问题,但如果N<=10000呢?(其实出题人本来是想出N<=10000,M<=100的,就算这样DP的时间复杂也不会有问题,但一开始多叉树的存储就可能会出问题)如果N=10000,那普通的邻接表显然会空间溢出,这里介绍一种压缩邻接表的存储方法,压缩邻接表就是一个一维的数据,外加一个N大的数组作标记,标记第i个结点从哪位开始,a[i+1]-1就是第i个结点结束的位置,这样空间就可以压缩了.10000个点都没问题.
大家看题时要看清,每个点的财富值是|wi|<maxint,也就是说会有负值出现.看不清也没什么大问题!
这次的比赛由于是针对普及组的,(我也没能力出能针对提高组的题)所以数据有点弱,有20分的数据是送的,这两个数据一个全是1,一个全是-1.还有第一个数据是N<10的小数据.希望大家不要BS我出了这道水题.
(蛤蟆第一次写解题报告,不足之处多多包涵).

admin

话说考试答疑的时候，有牛提出：‘题目里的哪个图应该是（3，1），（3，3） 而非 （1，3），（3，3）’；更有牛认为“样例中，若井建在（3，2），所得的距离比样例更小。”
看到这里言论，我深感遗憾，想必，这些同学的数学基本功不够扎实，不是对直角坐标系不够熟悉，就是没有掌握直角坐标系里两点间距离计算的基本方法。希望相关同学回家好好补数学。不要应此吃了亏。
再切入正题：
得分情况：
100分 ：13人； （不会都是交USACO的程序吧=.=）
80分  ：1人；
50分  ：4人


题意很简单。直观地想到搜索。由于坐标范围为【0，100】，搜整点的话复杂度是完全允许的。但显然，只搜整点是不够的，事实证明只搜整点与正确结果相差很大，那么，要考虑实点。注意到输出只要求保留两位，我们再搜过整点之后，答案所需的实点就在最优的整点附近。，所以我们可以先枚举依次整点，取前K优的整点（事实证明：取K=6，可以AC），再搜索这些点附近的实点(小数点后两位)，就可以得到一个近似最优解(显然这不是完全最优，但对于保留小数足够了。)
上述为本人程序解法，但事实上，本题为USACO原题（我事先也不知道-.-，但这题也确实不是我原创的）可以参考USACO题解的解法。
谢谢。