NOIP集训-10.26总结

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)取个最大值就好...
----------------------------------------------------------------------