其他-OB杂题选讲

OB_ZT

A

圆上有 (n) 个点,两两间均有边,没有三条线交于同一点。求三角形个数。

分类考虑三角形端点是否在圆周上。

B

给定 (n) 个数,求出现次数为奇数次的数(保证这样的数不超过 (10) 个)。只允许使用大约 (60)unsigned int 类型的变量。

(x ightarrow a) 使得 (forall a, a equiv k (mod p))(a) 扔桶里去,保证每个桶里异或和为 (k) ,保证扔进去概率是 (frac{1}{2}) ……我现在已经忘记当时大佬讲了什么了 QwQ ……

什么矩阵秩?大约 (96\%) 概率正确 ?校验码?真的忘了,再见。

C

给定一个多边形 (n) 个顶点在坐标系 (xOy) 中的位置。多边形质量均匀,顺时针围绕重心旋转的角速度为 ( heta) ,受重力加速度 (g) ,有一个向右初速度 (v) ,做平抛运动。保证有且仅有一个点先与 (x) 轴接触,求是哪个点。

枚举点,运动看成垂直和水平两个方向独立的运动,求二次导数,二分单调区间(或者乱搞,分成许多区间,假设每个区间就是单调的),解方程。

D

给一棵树,每次选一个点去掉,得到许多棵子树,递归下去,继续选点并去掉。求不同方案数。

相邻两点在点分树上也是父子关系,考虑两条路径组合在一起。

E

给定 (S,C) ,构造若干组 ((a_i,b_i)), 满足 (a_i,b_i in N^+) ,同时还要满足 (sum a_i b_i le S)(sum 2 cdot (a_i+b_i) le C) ,求不同方案数。

对称性可得 (a)(b) 等价,所以求小于等于的方案变成 (frac{总方案数-两侧取等的方案数}{2}) 。有两种特殊矩形辅助推状态。

原文地址:https://www.cnblogs.com/ghcred/p/10200346.html