Ta 分层图最短路 洛谷 - P4568

启发:

对于在图上有更多限制，相应减少数据范围的
考虑新增一些虚点表示这些信息
人称：分层图

类比：之前的带钱最短路[ABC164E] Two Currencies

都是通过在原本的图的点上新增一些点来进行完整转移

不过那是dp的写法

/*
突破口：n,m与a[i]范围都极小
并且限制条件多了金币与换算
所以考虑将金币与换算写进转移维度
bfs+“动态规划”

f[i][j]表示到i号点，持有j个银币的最小时间

两条转移，对于一个点：f[i][j]=f[i][j-v[i]]+t[i]

对于不同的两个点：f[v][j]=f[u][j+v[i]]+t[i]

每个点都来一遍宽搜，然后再从起点来一遍确定答案

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

*/

TB:CF337C
首先贪心，尽量分散得分，避免*2

实在要的放到最前面
对于要的：
设f[i]表示翻倍k次需要的
f[i]=2(f[i-1]+k)
拆开
f[i]=2f[i-1]+2k，矩阵快速幂填好递推
每一层相似
也可以退食自，fn=k(2^(n+1)-2)

Tc:CF222E
计数，考虑dp
f[i][j]+=f[i-1]k
发现每一层相似，考虑矩阵快速幂
初始全为1表示都可以转移，进来一对就把(i,j)改0
表示无法从i转移到j

TD:模拟，
对于位置确定一切确定的模拟，考虑使用
do while+
Next_pomutation(a+1,a+7)
减少常数
新用法：vector[HTML_REMOVED] s;
s=vector[HTML_REMOVED]
(a[2].size(),string(a[5].size(),’.’))
表示生成s：a[2].size行,a[5].size()列，且全部置为’.’，值得积累的两条,判断心细即可

TE：
勇敢推性质！勇敢推性质！勇敢推性质！勇敢推性质！

考虑b里面有一位x，那么x之后一定是([HTML_REMOVED]x)的形状
最大：每个(<x)以内从大往小填

实现：个人使用线段树，维护值域，当a[i]>a[i-1]，找到他前面最大的a[k]不超过a[i]，如果它和它以下的都被填完就可行，否则不可行

TF：矩阵优化，考虑方程：f[i+1][(j+w)%x]+=f[i][j]

注意到相邻两层几乎转移相似，
对于每个w，使矩阵[j][(j+w)%x]++

表示j可以转移到(j+w)%x

然后快速幂就完了

TG：光转折化成盒子翻折，枚举翻折次数，然后建系判断每个转折点是否有镜子，那些镜子被用到了要加分，也可以相似，但是建系yyds（

翻折次数枚举O(n)，暴力判断O(n)，共O(n*n)

TH:

客观上分成两个部分

思考上：f(gcd(a,b))=gcd(f(a),f(b))

feb数列还有很多性质可以辅助：
eg：
fi为广义feb，Fi为狭义Feb
若f1=a,f2=b
则fi=aFi-1+bFi-2

实际用法：
$f_(n+k)=f_(1+k)*F_(n-1)+f_(k+2)*F_(n-2)$

Σf_n=f_n+2-f_2 广义可行

扯远了，然后本题上就变为了：[l,r]内找到k个数使得他们的最大公因数最大

令res=gcd
先找理想情况，l,r都在里面：res=(r-l+1-1)/(k-1)（把l端点去掉不看）
然后动态调整
在gcd=res的情况下，即找res的倍数的个数：
r/res-(l-1)/res，
然后发现r/res在每个res恰好整除r的时候取最大
考虑类整除分块改动r/res,移动res

over

Today’s hand competition:

Tc说起，他！卡我！记忆化搜索！！！
无耻，实在无耻

状态：f[i][j]–>前i个，第i个取到j的最大值

记录i行前缀最大值：g[i][j]
i行后缀最大值h[i][j]

转移根据位置分讨
if(i&1) f[i][j]=max(g[i-1][j-1]+s[i][j])
else f[i][j]=max(h[i-1][j+1]+s[i][j])

over

Ta:
删除相邻男女：链表
选出差值最小：priority_queue
完了。
注意各种判断：要删的两边被删过吗
和细节：删过过后会产生新的吗

TB