比赛链接
A
- 题意
- 给定 n，m
- 求第 k 大的 ∣ x y ∣ , x ∈ [ 0 , n ] , y ∈ [ 0 , m ] |xy|, \quad x \in [0, n], y \in [0, m] ∣xy∣,x∈[0,n],y∈[0,m]
- 题解
- 暴力堆搜索
#include
#include -
题意
- 记 F F F 是兔子数列的集合
- 将某个数 n 分解成兔子数列的某种表示，即求出 F F F 的某个子集 F ′ F^{\prime} F′，使集合累加值为 n， ∑ f i ∈ F ′ = n \sum_{f_i \in F ^{\prime}} = n ∑fi∈F′=n
- 求 n 的所有表示的累乘值之和，
- 例： 7 = 5 + 2 = 5 + 1 + 1 = 3 + 2 + 1 + 1 7=5+2=5+1+1=3+2+1+1 7=5+2=5+1+1=3+2+1+1
- 得： 5 ∗ 2 + 5 ∗ 1 ∗ 1 + 3 ∗ 2 ∗ 1 ∗ 1 = 21 5*2+5*1*1+3*2*1*1=21 5∗2+5∗1∗1+3∗2∗1∗1=21
-
题解
- 压维线性dp && 数学优化（离谱）
- 首先，我们默认兔子数列是从下标 1 开始的，即 f 1 = 1 , f 2 = 1 , f 3 = 2 f_1 = 1, f_2 = 1, f_3 = 2 f1=1,f2=1,f3=2
- 我们指出兔子数列的一个性质：
∑
i
=
1
n
f
i
<
3
f
n
\sum_{i = 1}^n f_i < 3f_n
∑i=1nfi<3fn
- 证明：
假设： ∑ i = 1 n f i < k f n \sum_{i = 1}^n f_i < k f_n ∑i=1nfi<kfn 成立
∴ ∑ i = 1 n + 1 f i = ∑ i = 1 n f i + f n + 1 < k f n + f n + 1 \therefore \sum_{i = 1}^{n + 1} f_i = \sum_{i = 1}^{n} f_i + f_{n + 1} < k f_n + f_{n + 1} ∴∑i=1n+1fi=∑i=1nfi+fn+1<kfn+fn+1
考察： k f n + f n + 1 < k f n + 1 kf_n + f_{n + 1} < kf_{n + 1} kfn+fn+1<kfn+1
⇔ k f n + ( 1 − k ) f n + 1 < 0 \Leftrightarrow kf_n + (1 - k)f_{n + 1} < 0 ⇔kfn+(1−k)fn+1<0
⇔ k f n + ( 1 − k ) f n + ( 1 − k ) f n − 1 < 0 \Leftrightarrow kf_n + (1 - k)f_{n} + (1-k)f_{n - 1} < 0 ⇔kfn+(1−k)fn+(1−k)fn−1<0
⇔ f n + ( 1 − k ) f n − 1 < 0 \Leftrightarrow f_n + (1 - k)f_{n - 1} < 0 ⇔fn+(1−k)fn−1<0
⇔ f n − 2 + ( 2 − k ) f n − 1 < 0 \Leftrightarrow f_{n - 2} + (2 - k)f_{n - 1} < 0 ⇔fn−2+(2−k)fn−1<0
⇔ f n − 2 < ( k − 2 ) f n − 1 \Leftrightarrow f_{n - 2} < (k - 2)f_{n - 1} ⇔fn−2<(k−2)fn−1
显然，这对 k ≥ 3 k \ge 3 k≥3 成立
∴ ∑ i = 1 n + 1 f i < 3 f n + 1 \therefore \sum_{i = 1}^{n + 1} f_i < 3f_{n + 1} ∴∑i=1n+1fi<3fn+1
那么由数学归纳法： ∑ i = 1 n + 1 f i < 3 f n + 1 , ∀ n ∈ R \sum_{i = 1}^{n + 1} f_i < 3f_{n + 1}, \quad \forall n \in R ∑i=1n+1fi<3fn+1,∀n∈R 成立
- 证明：
- 设 ( i , j ) (i,j) (i,j) 表示前 i 项（包含第 i 项）构造 j 的方案，那么 f i < j < p r e j f_i < j < pre_j fi<j<prej 时，方案才有意义。这意味着前 i 项只能转移到 j ∈ [ f i , 3 f i ) j \in [f_i, 3f_i) j∈[fi,3fi)
- 设 d p ( j ) dp(j) dp(j) 表示题目中的 W ( F ( j ) ) W(F(j)) W(F(j))，那么状态转移方程为： d p j = ∑ f i × d p i dp_j = \sum f_i \times dp_i dpj=∑fi×dpi
- 由于上述 dp 方程合法范围难以把握，所以直接枚举 i 的扩散： d p j + = f i × d p i , j ∈ [ f i , 3 f i ] dp_j += f_i \times dp_i, j \in [f_i, 3f_i] dpj+=fi×dpi,j∈[fi,3fi]
- 值得一提的是，这不就是个压维0-1 背包（队友提醒了我才反应过来）
#include
#include -
题意
- 给定主串 s，数值 k
- 求长度不小于 k 的子串在 s 中出现次数的最大值
-
题解？
- 后缀数组？
-
题意
- 给定一个序列 a 1 a_1 a1 ~ a n a_n an
- *** 作：选择相邻的两个数，删除较小的那个，并将较大的元素的数值翻倍
- 如果相等，则随机视某个数较大
- 求 *** 作 n - 1 次 *** 作后，哪些元素可能是最后剩下的那个
-
题解
- dfs/双指针 && 剪枝
- 检查每个数，用双指针模拟能否吃掉相邻的数
- 当当前值不小于最大值时，剪枝，返回 1
#include
#include - 题意
- 求 [ 0 , 1 0 n ] [0, 10^n] [0,10n] 中，能被 11 整除，或包含数码 k 的数的数量
- n ∈ 1 e 6 , k ∈ 2 e 5 n \in 1e6, k \in 2e5 n∈1e6,k∈2e5
- 题解？
- 数位 dp
-
题意
- 给定序列 a 0 a_0 a0 ~ a n a_n an，
- 求 ∑ i = 0 n ∑ j = 0 a i A ( i , j ) \sum_{i = 0}^n\sum_{j = 0}^{a_i}A(i,j) ∑i=0n∑j=0aiA(i,j)
- A ( n , m ) = { 1 , m = 0 0 , m > n n ! ( n − m ) ! , m < = n A(n, m) = \begin{cases} 1, &m = 0<= n\end{cases} , &m > n \\ \frac{n!}{(n-m)!}, &m A(n,m)=⎩⎪⎨⎪⎧1,0,(n−m)!n!,m=0m>nm<=n
题解-
数学 && 线段树
- 设 g ( x , l , r ) = ∑ i = l r A x i g(x, l, r) = \sum_{i = l}^r A_x^i g(x,l,r)=∑i=lrAxi， f ( x , y ) = s u m ( x , 0 , y ) f(x, y) = sum(x, 0, y) f(x,y)=sum(x,0,y)
- 那么问题转化：求 ∑ i = 0 n f ( i , a i ) \sum_{i = 0}^n f(i, a_i) ∑i=0nf(i,ai)
- 现在考察用最少时间获得任意的
f
(
x
,
y
)
f(x,y)
f(x,y)
我们给出两个公式： f ( x , y ) = 1 + x f ( x − 1 , y − 1 ) f(x, y) = 1 + xf(x - 1, y - 1) f(x,y)=1+xf(x−1,y−1)
f ( x , y ) = f ( x , x ) − ∏ i = x − y x i × f ( x − y − 1 , x − y − 1 ) f(x, y) = f(x, x) - \prod_{i = x - y}^x i \times f(x - y - 1, x - y - 1) f(x,y)=f(x,x)−∏i=x−yxi×f(x−y−1,x−y−1)
证明公式 2： ∵ A n m = n A n − 1 m − 1 \because A_n^m = n A_{n - 1}^{m - 1} ∵Anm=nAn−1m−1
∴ g ( x , l , r ) = x × g ( x − 1 , l − 1 , r − 1 ) \therefore g(x, l, r) = x \times g(x - 1, l - 1, r - 1) ∴g(x,l,r)=x×g(x−1,l−1,r−1)
由上述递推式得： g ( x , l , r ) = ∏ i = x − l + 1 x i × f ( x − l , r − l ) g(x, l, r) = \prod_{i=x - l + 1}^x i \times f(x - l, r - l) g(x,l,r)=∏i=x−l+1xi×f(x−l,r−l)
又 ∵ f ( x , y ) = f ( x , x ) − g ( x , y + 1 , x ) \because f(x, y) = f(x, x) - g(x, y + 1, x) ∵f(x,y)=f(x,x)−g(x,y+1,x)
∴ f ( x , y ) = f ( x , x ) − ∏ i = x − y x i × f ( x − y − 1 , x − y − 1 ) \therefore f(x, y) = f(x, x) - \prod_{i = x - y}^x i \times f(x - y - 1, x - y - 1) ∴f(x,y)=f(x,x)−∏i=x−yxi×f(x−y−1,x−y−1)
- 那么，使用公式 1 预处理所有 f ( x , x ) f(x,x) f(x,x) ，并使用线段树维护累乘值即可
#include
#include
-
G
- 题意
- 给出序列 a 1 a_1 a1 ~ a n a_n an 两人轮流 *** 作，Alice 先手Alice 可以选择一个奇数并将其分成两个正数，或者删除一个等于1的数。Bob 可以选择一个偶数并将其分成两个正数。若某个人无法移动，则输掉比赛。如果两个玩家的移动最佳，求谁是赢家。
- 题解
博弈论首先，最优决策应该是 *** 作后使自己还能剩余更多的 *** 作步骤
- 考虑 bob 分解偶数
若分解 2，则会给 alice 两步若分解非 2，则会给自己两步
- 考虑 alice 分解奇数
分解任何奇数都能给对方一步，给自己一步消除 1，则拖一回合
- 最优决策：
bob 总是最后分解 2alice 总是使偶数部分为 2，给 bob 最烂的牌那么整个过程变成：bob 尽量不分解 2，alice 拖足够多的回合。
仔细一想就能发现，两人的最优决策都是把 x 拆成 x - 2 和 2。那么统计序列中大于 2 的偶数能被分解的次数，这是 bob 的 *** 作次数；统计序列中的奇数能被分解的次数，这是 alice 的 *** 作次数。作比较即可。
#include
#include
-
H
题意-
给定一个无向图，带边权，n 个点，m 条边，没有自环
- 每次移动，其它的边权将变成 f ( x ) = 1 + x 1 − x ( m o d p ) f(x) = \frac{1 + x}{1 - x} \pmod p f(x)=1−x1+x(modp) 求从点 1 到点 n 的最短路径
题解-
我们发现边权的变化具有周期 4，那么我们考虑转化边权
- 将图中每个点复制 4 份，
- 那么从点 i 的拷贝 0 到点 j 的拷贝 1，是通过 w i , j w_{i,j} wi,j
- 那么从点 i 的拷贝 1 到点 j 的拷贝 2，是通过 f ( w i , j ) f(w_{i,j}) f(wi,j)
这样便转化成求从 1 到 n 的四个拷贝中，最短路的最小值
#include
#include
-
I
题意-
在三维空间，给出三个平面查询两点间是否被平面分隔
题解-
曲面方程 && 异侧判断
- 对于曲面方程 F ( x , y , z ) = 0 F(x, y, z) = 0 F(x,y,z)=0，若两点在同侧，则 F ( x 1 , y 1 , z 1 ) × F ( x 2 , y 2 , z 2 ) > 0 F(x_1, y_1, z_1)\times F(x_2, y_2, z_2)>0 F(x1,y1,z1)×F(x2,y2,z2)>0
#include
#include
-
J
题意-
每次查询给出一个数 n，求 n 最少能被分解成几个完全平方数的和/差
题解- 枚举 [ 1 , 1 e 5 ] [1,1e5] [1,1e5] 范围内的完全平方数，BFS 即可
#include
#include
-
K
题意-
强制在线每条线段有一个权值 *** 作 1：添加一条线段，权值为 w *** 作 2：查询区间内所有完整线段权值的最大差值
题解-
线段树套线段树第一维负责管理线段左端点，第二维负责管理线段右端点查询则查左右端点（即第一二维）都在范围内的即可
#include
#include
-
L
题意-
有三个队相互竞争。首先，以相等的概率选择两个队进行比赛。在每一轮比赛中，败队暂时离开，获胜队继续与未参加本轮比赛的三支球队中的另一支比赛。当一个队总共输掉两轮比赛时，淘汰赛结束。为了简单起见，任何两支球队都有50%的机会战胜对方。求本次淘汰赛的预期轮数。
题解-
概率论DFS
#include
#include
这套题的质量其实很高，主要考察了许多算法与数学的结合，非常考验选手算法池的广度。这次补题，我也是慢吞吞地磨蹭了 2 天才写完这些。比赛上，我可能会直接 g。我感觉到了我做题是真滴慢啊。。。。
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/1324187.html
评论列表（0条）