NOIP集训-10.26总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
T1T3的暴力都挂了，就靠T2的打表拿了点分...
----------------------------------------------------------------------
Snow:SuperOjP962
考试的时候写了个费用流，准备拿60分的点的，然而只拿了30分...
费用流建图：每个点拆成入点和出点，入点指向出点，容量为这个点的访问次数限制，源点指向入点，出点指向汇点，容量
都为inf，保留原来的边（出点指向入点），容量为访问次数限制，费用为-1，其他边费用为0，最后的答案是所有点的访问
次数限制之和加上最小费用。
然而这个很慢，跑不过100分的点
100分：考虑最大流，每个点拆成入点和出点，保留原来的边（出点指向入点），容量为访问次数限制，源点连向出点，容
量为点的访问次数限制，入点连向汇点，容量为访问次数限制，最后的答案是所有点的访问次数限制之和减去最大流量。
----------------------------------------------------------------------
Game:SuperOjP963
70分给打表真是太良心了...
标算显然是数位DP，设f(i,p,j,k)表示有i位，最高位为p，是否包含7为j（0或1），对7求模为k的数个数。
转移：(设q=(k-p*(10^i)) mod 7)
f(i,7,1,k) = ∑f(i-1,0~9,0~1,q)
f(i,p,1,k) = ∑f(i-1,0~9,1,q) (p ≠ 7)
f(i,7,0,k) = 0
f(i,p,0,k) = ∑f(i-1,0~9,0,q) (p ≠ 7)
然后按位统计就好了
----------------------------------------------------------------------
Travel:SuperOjP964
大概是最简单的一道..
首先把边排序，从小到大依次添加
设f(i)表示点i的答案，l(i)表示上一次更新i的边的长度
当添加一条边(u,v,w)(它表示从u指向v，长度为w)时，若有w=f(u),那么就枚举指向u的其他边，尝试用这些边来更新v,否则
令f(v) = max{f(v),f(u)+1}并更新w(v)的值。
最后对所有f(i)取个最大值就好...
----------------------------------------------------------------------
评论 (0)
