第一周，回顾下我做了些啥

Day1：杂题s：

CF1153D：

给棵树，
叶节点权值[1,k]，
其他节点为他们儿子节点权值的max/min
求根节点最大值

SOL：
考虑贪心，由于是max/min而不是加、减
所以考虑贪心的将所有叶子赋为k
然后考虑每个节点的状态：
如果是max，那么直接maxf[sons]，不用考虑重复
如果是min，考虑它实际被哪些最少影响：
1.如果底下是叶子节点，那么肯定影响
2.如果底下是min，那么是他所影响的所有min下放到叶子节点上之和
3.如果底下是max，那么是它所影响的所有min取最小影响

AT_abc164_e

题意：双权最短路
道路存在性与银币数量共同决定是否可达
通过道路和兑换银币都需要时间

切入点：n,m与每条道路需要银币数量都极小(50)
<==>银币的上限极小
<==>花一个维度来存，伪动归

dis[i][k]–>到第i个城市，且身上拥有k个银币的最少时间
两种转移：dis[i][k]=dis[i][k-c[i]]+t[i]（在这里进行转换）
dis[j][k]=dis[i][k+w[i]]+ti

n实在是太小了，每个点都这样跑一边bfs，最后再以1
为根跑一边bfs就过了，不必想最短路

最后对于每个点u，取f[u][i]最小值

Luogu P4859

dp+容斥

根据组和为n，差为k，算出要求糖果比药片能量大的恰好有多少

由于dp的性质，无论以何种方式遍历都能得到同样结果
且本体恰好实在是太难算，具有后效性
所以考虑排序ab，强制向前匹配，算”至少”
f[i][j]–>从i位置强制向前匹配，凑出j对糖果比药片能量大

r–>ai能匹配到最后的j

f[i][j]=f[i-1][j]+f[i-1][j-1]*(r[i]-j+1)

这是j组位置的选法，剩下的还可以全排列乱放

设gi–>恰好，然后f[i]=Σ(j=i->n) g[i]*c_j^i
此处注意理解：至少有i个，此时为j，那么随便从这k个里选出i个匹配，都是符合题意的

套路：ans=至少有k个的方案数-至少有k+1个的+至少有k+2个的方案数-。。。