Table of Content

9-21
今天上午做了三题:
Run 最小生成树+倍增,可能是倍增写错了,爆零,需要继续调试。后来发现倍增确实写错了,但是没有再次调试这道题。
Nim 涉及到博弈论,不会做。正解是奇数行的亦或值是否为1
Toy 应该是树形dp,我写了暴力。正解是选或不选这个点,如果不选这个点,子节点就必须有选的
下午:
Sequence 正解是O(n)算法,我只想到了O(n^2)的模拟算法,需要进一步研究。
Word 涉及到高深的技术和kmp字符串匹配,没有想到怎么做
Car 一开始模仿八皇后写了搜索算法,时间复杂度略高,后来改成了状压dp,因为有一个状态被遗漏了,WA,后来该上了,应该能AC。
9-22
今天到noi.ac上打比赛,只拿到了60分暴力分。
第一题,count 组合数学题,for I = 1..n+1 do ans[i] = C(n+1, i) – C(L+R, I – 1)。调试的时候,由于组合数复杂度太高而T,后来由于模后数相减没有调整为正数,卡了好久。还要背过逆元递推式,并进行阶乘的预处理,O(n)
第二题,delete,首先是DP,60分,研究DP的转移状态,得到二维偏序问题,sort后做LIS即可,O(nlogn)
第三题,涉及到树剖,没有研究。

另外研究了昨天的LCA问题,洛谷上LCA如果用倍增法,不用读入优化会T,而ST表求RMQ则不会T,昨天T1需要求额外的信息,就不能用ST表来做了

9-23
今天考了几道题,isbn、connect和drive
Isbn水过了。
Connect 爆了0,后来研究发现,是printf输出符号打错了,lf达成了ld。修改后只有45分,调整模拟退火算法的参数后75.查看题解,发现正解是枚举+最大生成树。
照题解修改程序后发现是95分,后来查出,是循环内使用es数组数据,而sort改变了es数组的顺序,进而有一组数据没有通过。谨以记之。
第三题是图上dp,实际上也可以不建图,常数略大而已。写的时候有一点小问题,gdb调了半天,发现时复制样例输入的时候复制错了,程序本身没有问题。
9-24
今天上午做了:
Toy: dp+斜率优化。考试的时候看错了题意,写了贪心,没有得分。下午和晚上学习了斜率优化,打算配合相关的题目练习一下。
Fence:据说是要用单调队列计算对答案的贡献。没有研究。
Sequence: 据说要用单调队列优化,或者是某种奇怪的贪心。
Apple dp+优化(离散化+排序)

9-25
上午做了dp优化系列2,以为是有两道题以为是贪心,结果是错误的。
第一题garden非常诡异,当时搜索没有写出来,就放弃了。题意是,只能是长条和矩形,这样才能保证距离是曼哈顿距离
第二题写了搜索,可能剪枝剪得太厉害了,只过了样例。正解是m=2时的答案最大,按照l, r排序后,用单调栈维护状态、更新答案。
第三道题是某种贪心、也使用单调栈维护。
第四题是某种dp,和编辑距离有关,我写了搜索,搜到了小部分的分。后来在推dp方程,没有推出来。
另外提交答案的时候,输出搞错了,要注意一下。
晚上研究了树链剖分,被某种有坑的文章坑了好久。

9-26
今天没有考试,研究了一些零散的dp题,在洛谷上做了一些,感觉不是很熟练,需要进一步练习

9-27
今天考试内容是图论,二分图匹配。
城堡守卫,当时写了搜索,A1W1T8,应该是搜索剪枝厉害了,正解是每行设置一个编号,遇到墙则断开,然后每列这么处理,同时又可以站立的格子,则把当前格子所属的行列编号连边,进行二分图匹配或网络流。
序列变换,距离公式是还上距离,当时写了搜索。正解是裸的二分图匹配,从大到小开始匹配,匹配时从小到大,如果不能完全匹配则No Answer,完全匹配则输出匹配内容。
机器调度,考场上写了spfa+map的最短路问题,同时将问题简化,认为调度时只能依次处理,骗到了70分。正解是modA和modB连边,直接二分图匹配。
导弹,第一题是求同时满足三维的最长上升子序列,直接连边求最长路即可,spfa会被卡一个点,记忆化dfs可以过,第二题是求小路径覆盖问题,根据公式 最小路径覆盖=点数-最大匹配,套用匈牙利算法解决。预处理需要o(n^2),由于没有时间限制,所以每次必须遍历所有的点。似乎可以排序后遍历一部分,常数会小很多,但没必要。

Leave a Reply

Your email address will not be published. Required fields are marked *