|
中国国家集训队测试题
一、数论
1. 求解 $\sum\limits_{i=0}^{n}(-1)^i\binom{n}{i}=?$
2. 若正整数 $n$ 满足 $\dfrac{2n+1}{\sqrt{2}}$ 是整数，则 $n$ 为完全平方数。试证明之。
3. 给定正整数 $m$，分别构造函数 $f_0(x)=x$，$f_i(x)=f_{i-1}(x)+\lfloor\dfrac{x}{p^i}\rfloor$，($1\leqslant i\leqslant t=\lfloor\log_p(m)\rfloor$)，其中 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。试分析 $f_t(m)=?$ 的时间复杂度。
二、组合数学
1. 给出一张 $n$ 个点的简单无向图。若从其中任意一个点出发，恰好经过 $k$ 条边回到原点的方案数为 $f_k(n)$。试计算 $f_k(n)$ 的递推式并证明之。
2. 设 $S$ 为一包含 $n$ 个元素的集合。定义 $S$ 的排列 $P$ 的价值 $val(P)$ 为其全部 $|P|=\lfloor\sqrt{n}\rfloor$ 个连续子段的和。求 $S$ 所有排列中价值的最大值。
三、图论
1. 给出一个 $n$ 个点，$m$ 条边的无向图，保证图中每个点的度数均为偶数且 $n,m$ 同奇偶。试给出构造欧拉回路的有效算法，并分析时间复杂度。
2. 给定无向图 $G=(V,E)$ 和一个正整数 $k$。对于 $x,y\in V$，若存在一条从 $x$ 到 $y$ 的简单路径上恰好有 $k$ 个边，则称 $(x,y)$ 为 $k$ 级邻居。请设计一个时间复杂度为 $O(n(n+m)\log n)$ 的算法，对于每个 $k\geqslant 1$ 输出所有 $k$ 级邻居对的数量。
四、计算几何
1. 设 $F$ 为平面上一组点的凸包。对于 $P\in F$，记 $F_P$ 为由 $F$ 上除 $P$ 之外的点组成的集合的凸包。请设计一个几何意义明确，正确性和时空复杂度均得到保证，时间复杂度为 $O(n^2)$ 的算法，对于任意 $P\in F$ 计算 $F_P$ 的周长。
2. 给出 $n$ 个点和 $n$ 条线段，在平面上的所有点均在这些点和线段上，且线段之间没有交点。由于某些奇奇怪怪的原因，你需要计算在任意两个点之间连线所穿过的线段数量的期望值。你需要设计一个时间和空间复杂度均为 $O(n\log n)$ 的算法解决这个问题。
五、算法设计
1. 设计一个插入、查询、删除三个操作时间复杂度均为 $O(\log n)$ 的数据结构。其中插入和删除需要给出每个操作对应的键值。
2. 给出 $n$ 组不等式：$$a_1x_1+b_1x_2+\cdots+c_1x_n\leqslant d_1$$$$a_2x_1+b_2x_2+\cdots+c_2x_n\leqslant d_2$$$$\vdots$$$$a_nx_1+b_nx_2+\cdots+c_nx_n\leqslant d_n$$让你求在满足所有不等式的条件下 $\max\{x_1+x_2+\cdots+x_n\}=?$ 试设计时间复杂度为 $O(n^3)$ 的算法，其中 $a_i,b_i,c_i,d_i$ 均为整数，且 $n\leqslant 200$。
六、人工智能
1. 下棋程序可以被视为一种对抗搜索问题。对于给定的棋盘状态，程序需要在有限时间内（比如一个回合，或者一次动作）输出下一步的移动。尝试设计并实现一个对抗搜索算法，满足以下要求：（1）时空复杂度均得到保证 （2）具备较强的胜率和稳定性（可以通过与人类棋手对局的结果来评价）。
2. 请从已有的数据中学习一个人类语言的模型，并应用于自动生成文章、对话等任务。具体而言，输入是一个语料库，输出是一个可以自动生成人类语言（例如中文）的模型。请实现一种能够学习出一种语言模型的有效算法，并给出至少一个在此模型上应用的例子，展示其生成的结果。
|
