Cyberdebut's daily record - ACGO

时间:2024-03-01 21:28:45

Cyberdebut\'s daily record

训练目标

  • 前期速切水题,尽早进入状态
  • 强化数据结构(提升码力)
  • 图论网络流(多做题)
  • 负责一部分dp,字符串

近期任务:

  • 整理板子,内容多了,就显得之前的板子杂乱臃肿了
  • 数据结构:学习KD-tree、动态主席树、权值线段树,以及点分治深入。
  • 图论:学习双连通、2-SAT、生成树计数

7/23

晚上打AGC比赛,水完签到题就挂机了,然后就去帮队友验题,
自己本来打算出一道类似hdu2189的二分图匹配,发现需要些special judge,遂放弃,出了道更水的题目。。。

7/24

下午打UESTC summer training 15div1,结果签到题罚时爆炸,两个小时后发现不需要文件读入,G题因为编译器问题一直TLE(对脸懵逼)
晚上补了一道AGC18的B题和14div1的I题(随机化大法好),然后打cf,又读错B题,酱油了一把,读错题这个问题很严重,关键时候很致命,以后还是要多多注意!!!

7/25

下午多校第一场,卡在B题,debug半天结果发现漏了一个细节,以后遇到这种情况赶紧去读题,最后和队友改最后一题的,半天也没有读入搞成功,最后跌出100名,GG。。
晚上补了昨天cf的D题,最近逐渐把晚上空闲时间腾来搞会srtp,复习之前的知识。

7/26

下午打UESTC summer training 17div1,写了C矩阵幂,开开心心去写D的高斯消元,结果板子出错,GG了半天,最后去写模拟题B,
在询问队友之后,队友建议用高斯消元去处理,我也没多想,(这点要注意在写模拟题之前一定要将思路理好,并且尽量用不复杂的代码去完成),结果最后也没调出来。。。
这一个月下来,自己的问题还是暴露的挺多的,同时也有以前会犯,但是没有注意的问题:
1.对于模拟题,不能很快想出很好的写法,再加上码力渣,最后也没调出来几个。
2.简单数据结构题不能很快想好写好,自己的熟练度还是不够好,需要多刷题。
3.代码犯错率较高,经常sb的错误调半天,以后需要写一段查一段,及时检查思考代码的正确性,要达到写完基本没有小错误的要求,
一遍写对,比不断debug能节省不少时间。

7/27

  • HDU 4737 尺取法
  • HDU 4747 线段树+二分 这题思维上的转化很重要 用线段树二分查找可以通过维护一个区间Max实现
  • bzoj 4554 缩点+二分图匹配 缩点的思想很重要
  • cf 116 C 森林dfs 其实就是求最大深度

总结:
1.数据结构在巩固基础的同时,要多做多想一些数据结构的思维题,之前这类思维题做的少,像hdu4747就没想到转化,知道转化了就是区间更新,查询的操作,显然就用线段树。
2.网络流也是多做题,掌握更多的建图套路和经典模型。
3.数据结构各种类型的强化,比如主席树,树分治,虽然学过,但是平时并没有特意去做,比赛的时候也很少遇到或者会去做这种题目,所以后面训练的时候需要有意识的强化这块。

7/28

  • cf 12B 图论+模拟
  • cf 278C floyd+并查集 跑完floyd,用并查集求联通量,这题坑在n个人都不会任何语言
  • cf 246D 图论+STL
  • cf 218C 图论+并查集
  • cf 24A 图论+dfs
  • hdu 2874 LCA+并查集 并查集维护森林,用LCA查询两点距离
    总结:
    1.今天貌似切的水题有点多,后面几天数据结构暂时还是每天做一种类型,方便总结回顾,后面感觉差不多了就做各种类型的了,最短路和生成树可以挑几道kuangbin专题里面比较好的题目做做,网络流先做夏天的风推荐的题目吧,这么说下来内容还是很多啊,任重道远!!!
    2.今天听刚参加美团codem决赛回来的校队队长说,吉利爷和别人比手敲bzoj的平衡树,不编译一遍ac,深有感触,不说以后自己能够写完数据结构不编译一遍过,但是日后自己对这方面熟练度以及代码能力的要求要尽量的向顶尖选手看齐。

7/29

  • loj 6006试题库 多重二分匹配 需要构造解
  • loj 6007方格取数 最大点权独立集 答案是所有方格的和减去最小的权值和 经典问题:最大点权独立集(转化为最小割问题解决) 具体参考Here
  • loj 6005最长递增子序列 最大流 拆点 按递增顺序从前往后还是从后往前建边都没问题
  • 晚上怼深度学习的论文去了,看了google的Neural Machine Translation,了解了word2vec用法。
    总结
    1.这几天先做网络流24题吧,这些题目总的来说对建图的要求还是挺高的。
    2.对于一道有意思的题目思考以及转化成经典数据结构的能力需要在做题中提升。

7/30

  • loj6001太空飞行计划 最大权闭合子图 需要构造解 实际上可以反面考虑,要收益最大,即花费最少,这样就转化成最小割模型了
  • loj6000搭配飞行员 二分图
  • 学习了最大权闭合子图
  • 看了胡伯涛的最小割论文
  • 整理了dinic的板子,之前一直用的isap的板子
  • 补了玲珑杯1149 二分+RMQ 每次取log好慢,被卡时间了
  • 继续刷机器学习论文,学到了注意力机制,强化学习模型,sequence to sequence方法,明天构造理论模型。
    总结:
    1.做了loj6006,6001这两个题,一个判断边的流量构造解,一个判断vis数组构造解
    2.板子还需要不断更新,尽量用快而好改的

7/31

  • loj 6002最小路径覆盖 题如其名 转化成二分图最大匹配问题,从而用最大流解决。 构造解的时候沿着匹配边查找
  • loj 6004餐巾计划 最小费用最大流 这题建图要想好,刚开始建错了
  • 继续整理网络流板子和知识点
  • 看了facebook的Convolutional Sequence to Sequence Learning
    总结:
    1.整个专题刷下来要总结的知识点还是很多。
    2.之前的题目这几天尽量补掉

8/1

  • cf834D dp+线段树 转移方程为\(dp[k][i] = max(dp[k-1][j]) (1<=j<i)\),这个时候考虑每层k,用线段树去维护第k层的dp值
  • loj6003 最小路径覆盖 还没有完全理解
  • luogu3355骑士共存问题 二分图最大独立集
  • 研究了一下Neural Machine Translation
    总结:
    在刷专题的同时要多去做做综合题,提升对各个专题的运用

8/2

  • 补了青岛的一道网络流 不得不说这题太坑了,取log这个技巧要会活用,正负号也要想一会,本题精度上也会卡人,比较的时候要加eps,设的不好也会轻松TLE
  • 晚上开了一套三星gym,被C题卡了。。。后面的题目也没很快切掉
  • CharCNN的原理,看了Character-Aware Neural Language Models

1.做题要更细心点
2.不是很难的题目经常会被卡住,要多转换思路

8/3

  • 补了道dfs序+线段树链接
  • 补了道矩阵幂 又更新了板子,这次不是被卡时间,是数组大小的问题导致本地RE,查了很久。。。
  • 补了道博弈论
  • C题网络流还是想好怎么建图
  • 看了Attention-Based Convolutional Neural Network for Modeling Sentence Pairs

1.板子还是要不断更新,要不然会很坑。。
2.最小割的题目经常不是一眼看破的,还是得多做题

8/4

  • 补了三道多校题,还是挺考验思维的
    总结:
    还是做题少了吧,对于多校的难题并没有完全能够独立想出来

8/5

  • 打了百度之星预选赛,搞了半天的一道01背包打印字典序最小的路径,用判断桥的方法水了一道全局最小割,不会\(n^2logn\)斐波那契堆优化
  • 学了发全局最小割,整理了下板子

8/6

  • 做了几道分块打表的题目,整理了一下板子
  • hdu 4630 先把区间离线下来,然后枚举因子并且记录下前面出现的位置,树状数组记录最大值,类似题有hdu4358,明天补一下
  • 看了A_Latent_Semantic_Model_with_Convolutional-Pooling_Structure_for_Information_Retrieval_-_Report,还挺有趣的

8/7

  • 补了hdu4358
  • hdu4638 树状数组+离线 当然也可以莫队
  • hdu4622 hash+线段树 当然这题比较好的解法用后缀数组,后缀数组的做法交给队友了
  • 补了ARC080的E ST表+优队
    总结:
    1.遇到数据结构首先考虑莫队作为一种可行解法,实在想不出,大胆去写莫队的做法

8/8

  • poj 2139 枚举+floyd
  • 下午停电了,搞了半天充上电费了
  • poj 1062 把每个点等级看出最大,跑加限制的最短路,建图很有意思,没想到可以用最短路
  • 补了一道多校
  • SPOJ - COT 主席树+dfs序+LCA 没调出来,明天再搞
  • 翻github的时候看到了有人用char-RNN去学习古诗的语法与结构,搜了一篇论文看了下
    总结
    1.尽量这几天把之前学的数据结构都复习到,方法就是做题
    2.图论尽量多尝试像poj1062这种有意思的题目

8/9

  • 一场组队训练,水了两道题,疯狂debug I也没搞出来。。。
  • 做了两道队友提供的数据结构,还是挺有趣的,有一题分块没搞出来,直接大力线段树了
    1.对于构造题好像接触的有点少,中间还犯了把变量打错的sb错,要注意
    2.旧的数据结构尽量这两天都刷一遍题,然后再去学一两个新的

8/10

  • 补了之前一道主席树 SPOJ - COT 参考
  • bzoj 2597 线段树比较难想,遂用分块写了一发,然后又学习了线段树的做法
  • poj 3268 最短路
    1.该整理一下板子了,拖到现在还没有去整理
    2.今天效率有点低,数据结构内容还很多,又有新的题要补,后几天得抓紧了

8/11

  • bzoj 2243 树链剖分 刚开始还没有思路,其实维护的时候用线段树去合并 好久没写树剖了,生疏了些,如果不专门去做,平时真的很少碰到,但是区域赛说不定就考到
  • bzoj 4034 线段树+在树剖基础上的dfs序 板子上有个细节有问题,查了半天也没查出来,还是对着别人代码发现了有个细节上的问题,bzoj上的数据挺全面的。
  • 稍微更新了一下板子
  • 补了一道SEERC2014的F 一篇很好的对分块的总结 大致看了一下,学到的还挺多的,明天继续看

明日任务:
1.继续看总结
2.补掉uoj 228 神奇的线段树操作

8/12

  • 看完了总结
  • 打了百度之星初赛第一场,死磕了一道日期题,心态爆炸,结果晋级失败 以后遇到这种情况先要冷静下来,或者换换题
  • 补了uoj228
  • cf444 C 均摊线段树
  • 整理了一下数据结构模板
    明日任务:
    1.看一下这篇博客
    2.做下hdu5306

8/13

  • 看了分块思想的博客,收获也挺大的
  • 打了百度之星初赛B,成功晋级
  • 做了bzoj 3781 分块
  • 看了这篇博客 重新理解了一下主席树
  • 没来得及补掉hdu5306,明天继续

8/14

  • 组队打了一场长春ccpc,被大数的板子坑了,其他还算顺利,貌似罚时多了些
  • 整理了一下大数板子
  • 补了ccpc的数据结构,主席树nlogn的复杂度在hdu上也要跑2s,听说现场有人分块过了,类似题cf 786C,明天可以做下,对主席树理解好像还不是很深

8/15

  • bzoj 1050 图论
  • bzoj 1066 最大流
  • cf 786 C 主席树
  • 补了cf 839E
    总结:
    1.多校的题目貌似欠了好几场了,明天开始补吧
    2.队友补的数据结构优化dp自己也可以顺便写写

8/16

  • 下午一场组队训练,运气好一点,会做的题目自己也熟悉,最后结果还行
  • 补掉了SGU 286 最小环覆盖
    明日任务:
    1.补多校的题目
    2.补下今天组队训练的I题

8/17

  • 状压dp: uva 11825 枚举子集+分组背包 poj 3254 状压计数
  • 补了昨天的I题 最短路+完全背包
  • bzoj 4759 树状数组
    总结:
    貌似对稍微综合点的题还是不能很快就能思路,需要多练练这种题

8/18

  • 下午打了百度之星复赛,貌似有两道原题,水了过去。。
  • 补了之前百度之星初赛第二场的B,暴力过的,貌似我的板子连1s都不用,时限还给了10s

8/19

  • 打了ccpc网络赛,延续了电科一贯的出题风格,不是有原题就是有结论题,题目难度差别还挺大的,后面就基本挂机了。。。
  • 补了之前总结里的一道 bzoj1878 离线+数组数组
  • 补了cf840 B 貌似对这种题目的不能很快思考出来

8/20

  • 白天去看熊猫了,晚上才回来,有点累,也没怎么写题,只是大概看了看之前的题目,队友晚上推荐几个,明天补补

8/21

  • 补了hihocoder 1554和1555
  • 补了之前PNRPC的C题最小割
  • bzoj3996 转化一下变成最小割
  • 写了下ccpc网络赛的矩阵+线段树
    总结:
    有些题目转化成最小割模型确实挺巧妙的,还是要多积累,要不然还是很难想到

8/22

  • cf 817 D 单调栈
  • 补掉了之前16年四川省赛 scu 4442 最小割
  • 看了昨晚的cf教育场G题,貌似要高斯消元,找了资料看了看,感觉还是有些难度,暂时鸽了
  • 补了多校#10 hdu 6162 树链剖分+线段树
  • 多校#10 hdu 6166 最短路

8/23

  • 下午组队训练,结果还可以
  • 晚上写了发昨天多校02主席树的做法,大概理解了今天的K,明天打算写一发
    总结:
    差不多一个月单独训练还是有些进步的,但是还是有些问题,比如对于一些中档题目的顺藤摸瓜型的逻辑思考有所欠缺,对于不是经典的dp和变形的dp需要多做题。

8/24

  • 补了南阳的K
  • bzoj 1083 最小生成树
  • UESTC 360 Another LCIS 线段树+区间合并
  • poj2828 线段树 补的之前看到博客里面推荐的题目

8/25

  • 补了多校第10场的 1008 ,写了发1011
  • 针对树形dp解决最大独立集和最小点覆盖这类的,看了这篇博客,并且做了几道题,整理了一下
  • 水了下昨天的cf

8/26

  • poj 3659 最小支配集
  • poj 2886 线段树
  • bzoj 2163 最大流 bzoj 4472 树形dp

8/27

  • 写了几道夏天的风推荐网络流的题目,博客
  • 写了两道之前看的关于线段树合并的博客里面推荐的题目

8/28

  • 补掉了多校第八场的1001
  • 回顾了一下扫描线+线段树,做了几道简单题,明天把今天的I做一下

8/29

  • 补掉昨天I题
  • 补掉之前的一道三星gym的最短路
  • cf 474 F 线段树
  • hdu 5023 poj2227线段树+位运算

8/30

  • 下午做了套15年沈阳,出题人出的final规格的题目,结果数据水了,导致暴力出奇迹,而且有些简单题因为题目和顺序问题隐藏着,榜被带歪了,最后L费用差一点,没有想通怎么判断不存在的情况,然后GG
  • 补掉了今天的L费用流
  • 补了之前多校的hdu 6180 贪心 hdu 6170 dp hdu 6168 模拟