10.01 ~ 10.03 做题记录
stripe_python · · 个人记录
由于神秘原因,之前的 blog 被覆盖了,2w 字的做题记录全没了 /ll
只留下这么点东西 /fn
【1+】XXS0103 局部函数
一个基本的刻画是,考虑相邻项
取任意拓扑序均可得到唯一的
- 设
f_{0/1,i} 为满足下列条件时,是否存在合法定向方案:-
- 仅考虑
x_0 \sim x_i 。
-
- 转移分讨
f_{0/1,i-1} \to f_{0/1,i} 是否可行,只要根据a_i,x_i 和g_i 判定。 - DP 初值为
f_{{\tt{R}},0}=1 。 - 答案为
f_{{\tt{L}},n} 。
只要记录
- 设
f_{u,v,f_0,f_1,i} 为满足下列条件的方案数:-
-
- 仅考虑
x_0 \sim x_i 。
-
- 转移枚举
x_{i+1} 的取值,可算出新的(u',v',f_0',f_1') ,转移f_{u,v,f_0,f_1,i-1} \to f_{u',v',f_0',f_1',i} 即可。 - DP 初值为
f_{0,v,0,1,0}=1 。 - 答案为
\sum\limits_{u,f_1} f_{u,0,1,f_1,n} 。
复杂度
:::::error[为啥不会做] 一个主要问题是,没想到有向链的刻画。
| 赛时略想一下先判定后计数,觉得不可做就否掉了,一直在区间 dp,自然是不可能会做的 /ll |
|---|
【1+】XXS0104 rplrprq
只有
可以用线段树套 01-Trie 维护,使用子树
考虑分析性质。对区间
- 若
\text{ctz}(a_x)<k ,则所有数\text{lowbit} 相同,等效于区间+\delta ,用标记处理即可。 - 若
\text{ctz}(a_x) \ge k ,则k 至少+1 ,直接暴力递归即可修改。
用线段树维护区间和,区间代表元,区间的
将所有节点的
:::::error[为啥不会做]
赛时被
【1+】QOJ12180 Point Divide and Conquer
正着做删点不好维护。不妨时光倒流,倒着扫
【1+】P17215 [ICPC 2017 Nanning R] The Champion
不妨设
贪心策略是,令
- 若
x=0 则f(x,y)=p^{r} 。 - 若
y=0 则f(x,y)=(1-p)^r 。 - 若
y 为偶数,令k 与1 个弱者打,剩余x-1 个强者,y-2 个弱者两两对战,一个强者打一个弱者。转移f(x,y)=p \times \left(p \times f\left(\frac{x-1}{2}+1,\dfrac{y-2}{2}\right)+(1-p) \times f\left(\dfrac{x-1}{2},\dfrac{y-2}{2}+1\right)\right) - 若
y 为奇数,令k 与1 个弱者打,剩余强弱组内部消耗,直接转移f(x,y)=p \times f\left(\dfrac{x}{2},\dfrac{y-1}{2}\right)
注意到每轮递归
【1+】QOJ12102 Hedgehog Daniyar and Algorithms
观察 可以排序,当且仅当任意逆序对和
证明 每个逆序对必须被邻项交换,必然性易得。冒泡排序的过程只交换逆序对,充分性可证。
将问题强化为,区间查询
用单调栈维护
用线段树维护
【1】CF1485F Copy or Prefix Sum
容易列得朴素 DP:
-
设
f_{i,j} 为满足下列条件的方案数:- 仅考虑
a_1 \sim a_i 。 -
- 仅考虑
-
转移枚举
a_{i+1} 的取值。- 取
b_{i+1}=a_{i+1} ,转移f_{i,j} \to f_{i+1,j+b_{i+1}} 。 - 取
b_{i+1}=\sum \limits_{k=1}^{i+1} a_k ,转移f_{i,j} \to f_{i+1,b_{i+1}} 。
注意特判转移重叠的情形。
- 取
-
DP 初值为
f_{0,0}=1 。 -
答案为
\sum \limits_{j} f_{n,j} 。
对
用哈希表维护
【2】CF626F Group Projects
将
- 设
f_{i,x,S} 为满足下列条件的合法方案数:- 仅考虑
a_1 \sim a_i 。 - 现有
x 个未确定\max 的组。 - 当前可确定的权值和为
S 。即确定部分权值和,加上待定部分-\min 的和。
- 仅考虑
- 转移
f_{i-1,x,S} \to f_{i,x',S'} ,讨论a_i 的归属:- 钦定为某个待定组的
\max ,移除待定部分,转移x \times f_{i-1,x,S} \to f_{i,x-1,S+a_i} 。 - 加入某个待定组,转移
x \times f_{i-1,x,S} \to f_{i,x,S} 。 - 新开一个确定组,转移
f_{i-1,x,S} \to f_{i,x,S} 。 - 新开一个待定组,转移
f_{i-1,x,S} \to f_{i,x+1,S-a_i} 。
- 钦定为某个待定组的
- DP 初值为
f_{0,0,0}=1 。 - 答案为
\sum \limits_{S=0}^k f_{n,0,S} 。
第三维
考虑微元贡献法
令
复杂度
:::::error[为啥不会做] 延迟钦定 dp 很快做明白了,但是不会做优化,一直在尝试搞前缀和,没见过这个差分 trick。 :::::