终于拿到正经分了
t1
没看
t2
这题的题面有点迷惑,读题读了很长时间,但是成功完成了转化
然后就是一个二分图匹配问题,选择dinic暴力跑一遍拿到60分
然后自己的优化思路是分治找点变成logmnlogn,自己考虑了一下发现自己好像实现不了直接找到分治中点对应的匹配数对应的结果,所以没法严格logm,所以就跑路了
事实证明跑路是相当明确的选择,因为正解是一边加边一边dinic,达成整体复杂度nm
t3
t2跑路就来做了这道题,毕竟n=2000部分直接n^2暴力dp
第二个点设置的很有引导性,在推出这个点的时候其实已经对正解有一些感觉了,毕竟正解可以看作是把第二个部分分不断连续进行而成
差点场切其实,甚至已经想出来离线下来用dp数组维护了,但是时间不够了,没打完
然后t3穿错文件了,总分100-->60
标签:师大附中,正解,t2,t3,60,D9,20231218,dp From: https://www.cnblogs.com/youlv/p/18076990/daily_2023ssdfzD9_1