试题

2008年北京大学自主招生数学考题

/ 42 条评论

    北大自主招生的数学考题就只有5道题，考生反映“巨难无比”，考完立马就郁闷了，哇啦哇啦地哭。我收集到的信息不多，得到的消息也没有一一去证实。我把这5道题大致写一下，题目描述可能不准确，但基本意思就是这样。

1. 证明：边长为1的正五边形的对角线长为(1+√5)/2

2. 已知一个六边形AB1CA1BC1，AB1=AC1，CB1=CA1，BA1=BC1，∠A+∠B+∠C=∠A1+∠B1+∠C1。证明：三角形ABC面积为六边形的一半。

3. 某次球赛实行单循环赛制，规定赢一场得1分，输一场得0分。比赛队伍分为南方和北方，南方比北方多9支球队，且最后南方总分数是北方的9倍。求证：南方某支球队的得分最高。

4. 已知实数a1、a2、a3、b1、b2、b3满足：
a1+a2+a3 = b1+b2+b3, a1^2 + a2^2 + a3^2 = b1^2 + b2^2 + b3^2
且min{a1, a2, a3}≤min{b1, b2, b3}
证明：max{a1, a2, a3}≤max{b1, b2, b3}

5. 空间解析几何题，涉及到旋转体和光源。题目看了半天都不懂是啥意思，估计原题有附图。哪位有更准确的题目描述麻烦请在下面留言告诉我。 网上找的题目没有“圆周”两个字，怪不得半天不懂是啥意思。
立体直角坐标系xyz，在xy平面上有图形0<=y<=2-x^2，将此图形绕y轴旋转得到一个不透光的几何体V。在点P(1,0,1)处有一点光源，xy平面上有一以原点为圆心的圆，此圆的圆周上被照亮的部分长度为2π，求未被照亮的部分的长度。（感谢dd）

另据了解，清华的数学题题量较大，题目也稍微简单一些。有两道题非常有意思，我也一起写在这里。
证明：任意给定一个四面体，则至少存在一个顶点，使得过该顶点的三条棱可以构成一个三角形。
证明：以原点为对称中心、面积大于4的矩形至少覆盖除原点外的另外两个格点。

趣题：估算小数点后第三位

/ 9 条评论

    下面这道题来自今年的Virginia Tech Rigeonal数学比赛（不知道该咋翻好）。比赛时间为两个半小时，一共有7道题，这是第5题：
    找出下面这个数小数点后第三位上的数字：(2+√5)^100 * ((1+√2)^100 + (1+√2)^(-100))

    这个问题有趣的地方就是，你真的可以用一个简单的办法估算出答案来。为什么不先试试看？

    我们需要求出(2+√5)^100 * ((1+√2)^100 + (1+√2)^(-100))小数点后第三位上的数。首先，(1+√2)^(-1)就等于(√2-1)，而二项式展开后你会发现(√2 + 1)^(2n) + (√2 – 1)^(2n)总是一个整数（根号2的奇数次幂总是一正一负抵消）。同样地，((√5 + 2)^(2n) + (√5 – 2)^(2n)) * ((√2 + 1)^(2n) + (√2 – 1)^(2n))也是一个整数，于是(√5 + 2)^(2n) * ((√2 + 1)^(2n) + (√2 – 1)^(2n))和(√5 – 2)^(2n) * ((√2 + 1)^(2n) + (√2 – 1)^(2n))的小数部分是互补的（相加为1），我们可以依据后面这个数的小数部分来确定前面这个数（也即题目要求的数）的小数部分。而当n较大时，后面这个数很可能会变得非常小。事实上，当n=50时，

  (√5 – 2)^100 * ((√2 + 1)^100 + (√2 – 1)^100)
< (√5 – 2)^100 * 2((√2 + 1)^100)
< (1/4)^100 * 2((5/2)^100)
= 2(5/8)^100

    可以断定，这是一个非常非常小的数，小数点后面紧跟着的0至少有10个。这足以说明，题目里那个数的小数点后面十几位全部是9。事实上，
(2+√5)^100 * ((1+√2)^100 + (1+√2)^(-100))
= 94158733601034420664808450657998303298219601745567527892456021922994
  873597395955752869490271254871747.9999999999999999999999996186915243
  507242961564029332966750212181162222265977213142686546252118999….
    小数点后一共有24个9。

本文来源：http://www.cut-the-knot.org/arithmetic/PowersOf10.shtml

07年NOIp提高组题目内容概述

/ 23 条评论

    NOIp越来越水了，题目还没大家的模拟赛出得好。我感觉从来没有这么垃圾的题目，一二题完全是送分题，三题估计多数人都会，只有四题或许会难住一些人。本来还想写题解的……算了，不用写了，节约点时间赶我的高数作业。

第一题：count 统计数字
    输入一个数n(n<=200000)和n个自然数（每个数都不超过1.5*10^9），请统计出这些自然数各自出现的次数，按顺序从小到大输出。输入数据保证不相同的数不超过10000个。

样例输入：
8
2
4
2
4
5
100
2
100
样例输出：
2 3
4 2
5 1
100 2

第二题：expand 字符串的展开
    我们可以用减号对连续字母或数字进行缩写，于是字符串a-dha3-68就可以展开为abcdha34568。
    输入三个参数p1,p2,p3，再输入一个仅由数字、小写字母和减号组成的字符串（长度不超过100），请按参数展开此字符串
    各个参数的意义如下：

  • 参数p1=1 -> 所有填充的字母都写成小写；
  • 参数p1=2 -> 所有填充的字母都写成大写；
  • 参数p1=3 -> 所有填充的字母和数字都用星号代替；
  • 参数p2=k -> 同一个填充字符连续写k遍；
  • 参数p3=1 -> 顺序填充；
  • 参数p3=2 -> 逆序填充。

    另外，如果减号两边的字符一个是数字一个是字母，或者减号右边的ASCII码没左边的大，则该处不变

样例输入1：
1 2 1
abcs-w1234-9s-4zz
样例输出1：
abcsttuuvvw1234556677889s-4zz

样例输入2：
2 3 2
a-d-d
样例输出2：
aCCCBBBd-d

样例输入3：
3 4 2
di-jkstra2-6
样例输出3：
dijkstra2************6

第三题：game 矩阵取数游戏
    一个n行m列的矩阵，每次你需要按要求取出n个数，m次正好将所有数取完。每取出一个数你都会有一个得分，请求出最终的得分最大是多少。
    每一次取数的要求：每一行中恰好取一个数，且只能取剩下的数中最左边或最右边位置上的数
    每取一个数的得分：所取数的数值乘以2^i，i表示这是第i轮取数。
    矩阵中的数为不超过100的自然数，1<=n,m<=80

样例输入：
2 3
1 2 3
3 4 2
样例输出：
82
样例说明：
1*2+2*2 + 2*4+3*4 + 3*8+4*8 = 82

第四题：core 树网的核
    树上的任两点间都有唯一路径。定义某一点到树上某一路径的距离为该点到路径上所有点的路径长度中的最小值。定义树中某条路径的“偏心距”为所有其它点到此路径的距离的最大值。定义树的直径为树的最长路径（可能不唯一）。给出一个有n个节点的无根树，请找出某个直径上的一段长度不超过s的路径（可能退化为一个点），使它的偏心距最小。请输出这个最小偏心距的值。
    题目已经告诉你如下定理：树的所有直径的中点必然重合（这个中点可能在某条边上）。其实这个结论很显然嘛，因为如果中点不重合的话必然可以找到一条更长的路。
    5<=n<=300，0<=s<=1000，边权是不超过1000的正整数

只是大致读了一下题目，若有写错的地方请指正
感谢huyue第一时间发布题目照片

Google面试题中的两道趣题

/ 44 条评论

看看下面两道题，它的解答非常简单，即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来？一小时？一分钟？一秒钟？

1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。

2. 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。

Solution:
1. 遍历链表，给每个元素赋一个0到1之间的随机数作为权重（像Treap一样），最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍，然后从后往前再扫一遍。也就是说，线性时间构造两个新数组，P[i]=A[1]*A[2]*…*A[i]，Q[i]=A[n]*A[n-1]*…*A[i]。于是，B[i]=P[i-1]*Q[i+1]。

突然想到，给别人(MM?)介绍信息学时，用这两道题当例子挺合适的。