- 2024-01-12P8368 [LNOI2022] 串
题面传送门首先我们可以说明,一定存在一个最优方案,使得最后一个串的右端点是\(n\)。因为如果不是\(n\),那么可以往后扩展一个,或者整体前移一位之后再往后扩展一位。然后我们可以说明,如果后缀\([i,n]\)存在一种方案使得其是最后一个,那么\([j,n](j>n)\)也存在一种方案。所以
- 2023-09-25[LNOI2022] 串
题目链接显然答案下界为\(\lfloor\frac{n}{2}\rfloor\)。采用一种对着题意模拟的策略:假设我们初始的区间为\([l,r]\),然后逐步向左平移,也就是:\([l,r],[l-1,r-2],[l-2,r-4],\dots\)直到碰到边界(平移的次数\(+1\)就等于\(m\))。显然\(l\)取\(\lfloor\frac{n}{2}\rfloor\),\(r
- 2023-05-07洛谷 P8367 - [LNOI2022] 盒(组合数学)
设\(a\)数组的前缀和为\(s_i\),\(b\)数组的前缀和为\(t_i\),那么根据模拟费用流或者贪心的思想,每一条边经过的次数即为\(|s_i-t_i|\),因此非常trivial的做法是转换贡献体,枚举每种方案下每条边被经过的次数,然后乘以\(w_i\)求和,具体来说:\[ans=\sum\limits_{i=1}^{n-1}\sum\l
- 2023-03-05luogu P8367 [LNOI2022] 盒
题面传送门比较厉害的题目。首先我们发现我们只需要计算\(i\)和\(i+1\)之间经过的货物数,也即设\(a\)的前缀和为\(Sum\),\(b\)的前缀和为\(c\),则\(i\toi+1\)
- 2023-02-03P8368 [LNOI2022] 串 题解
题目链接题目分析题目要求我们构造一个最长的\(T\)序列,我们首先从每个\(T_i\)入手,思考如何安排才能合法。容易观察到对于每个\(T_i\),合法的\(T_{i-1}\)有两种方
- 2023-01-31【题解】[LNOI2022] 盒
题目分析:我们可以对每一条边单独计算贡献,这样会发现贡献很好算:\[ans=\sum_{i=0}^{n-1}w_i\sum_{j=0}^S|j-s_i|\binom{i+j-1}{i-1}\binom{S-j+n-i-1}{n