一年计划 From 2018.6.28 To 2019.7.30
引言
现在是2018年6月28日20:48
突发奇想做一个一年计划
明年的现在 不知道是在为NOI拼命的努力 还是已经滚回去奋战 准备高考
努力一年
希望有一个满意的结果
Day1 2018.6.28
bzoj 2282 [Sdoi2011]消防
21:00 开题
21:30 胡乱猜了一个结论 开始码
22:00 TLE了
22:08 通过
就是猜想选择的路径一定属于直径的一部分 感觉很对
某位巨佬的证明:
因为离树上任意一点最远的点一定是直径的端点，所以我们选择的路径要与直径相交上才会产生最优解，
至于为什么整条路径都在直径上最优，
我们不妨假设现在有一棵树，
将直径上的一个点作为我们要选的路径上的一点，
我们要以这个点为中心扩展出一条路径，
离这个点最远的点一定是直径的端点，当前的最大值就是这个长度。
这时如果我们选的一条边不在直径上，并不会更新这个最大值，
这样即使不能继续在直径上延长，也对答案没有贡献
看起来很有道理的样子
把直径拎出来 然后整棵树就变成了一条长长的线加伸出去的一堆树枝
知道了这些 就二分答案(好像two-pointers也可以 而且更快)
预处理li,ri,disti
li表示当前点及其左侧所有点到当前点的距离的最大值
ri表示当前点及其右侧所有点到当前点的距离的最大值
disti表示当前点连出去的子树中所有点到当前点的距离的最大值
对于当前答案ans 找到最大的i满足li≤ans 最小的j满足ri≤ans
如果i~j中所有点的dist均≤ans 并且i到j的距离≤s 那么可行 否则不可行
TLE的原因是 有零边 这样的话找直径的时候一直当前点求上一个点我用的方法是找u 满足dis(u)+len(u,v)=dist(v)
如果len(u,v)=0 会死循环 所以必须记录下每个点是从哪里来的
bzoj 3571 [Wc2010]重建计划
22:28 开题
22:44 感觉点分治+线段树可以做
22:46 看了题解 发现必须O(n)处理点分治中的每一层 而且还需要预处理root 出题人真的是......
23:40 码累了 休息一会儿
23:56 接着码
00:28 码完了 一遍过了样例 感觉非常高兴 提交到洛谷上 ... 0分 睡觉去... 明天再调...
Day2 2018.6.29
今天出了一些小问题 就不记录了
讲起来真是惭愧呢 才第二天就中断了...
再说下去我都不好意思了 那就这样吧
Day3 2018.6.30
只能从晚上开始记录了 之前又忙了一些事情
poj 1739 Tony's Tour
19:45 开题
20:00 研究陈丹琦论文 基于连通性状态压缩的动态规划问题
21:03 看完了论文和kuangbin的插头dp板子之后准备开始写
21:52 过掉了
这算是插头dp的模板题了吧
有一个trick就是在最后加两行 就可以了变成回路了 就和论文里那道题一样了
*..
...
->
..
...
..
...
强制从左下角到右下角
然后就是插头dp了 根据kuangbin的模板大致是这样的
struct HASHMAP{
//手写哈希
...
} hm[2];
void decode(int *code,int m,long long st){
//将st解码成code数组 大小为m
...
}
long long encode(int *code,int m){
//将code数组压缩成st 一般采用2的幂次进制 因为位运算既方便又快 m依旧是大小
...
}
void shift(int *code,int m){
//将code移动一位 因为假如到了一行的边界我们需要把数组的最后一项扔掉 第一项存上新的状态 其余状态右移
...
}
void dpblank(int i,int j,int cur){
//对于没有障碍的格子的dp
//用类似bfs的dp以减少状态数
for(int k=0;k<hm[cur].size;k++){
decode(code,m,hm[cur].state[k]);
if(){
...
hm[cur^1].push(encode(code,m),nwans);
}
else if(){
...
hm[cur^1].push(encode(code,m),nwans);
}
...
//分类讨论转移
}
}
void dpblock(int i,int j,int cur){
//跟dpblank差不多 状态转移一般比较简单
...
}
void init(){
//读入 并且找到ex, ey表示最后一个不是障碍的格子 这个格子比较特殊 需要在转移的时候特殊考虑
...
}
void solve(){
int cur=0;
hm[cur].init();
hm[cur].push(0,1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
hm[cur^1].init();
if(mp[i][j]) dpblank(i,j,cur);
else dpblock(i,j,cur);
cur^=1;
}
long long ans=0;
for(int i=0;i<hm[cur].size;i++)
ans+=hm[cur].f[i];
cout<<ans<<endl;
}
大概就是这样了
(突然感觉markdown编辑器的c++配色比我的代码编辑器的配色好看多了...)
bzoj 2734 [HNOI2012]集合选数
22:23 开题
22:50 看了一眼题解
23:03 看了第二眼题解 大概会做了
23:13 被逼着去睡觉... 好像以后都得早睡早(晚?)起了...
Day3 2018.7.1
不知不觉6月就过去了...
bzoj 2734 [HNOI2012]集合选数
08:57 过掉了
这题是一个比较神的状压dp
首先把所有数列成一些数表
1, 3, 9,... \\ 2, 6,18,...\\ 4,12,36,...\\ ...
就是每个数是它上面的数的两倍 它左边的数的三倍
然后把所有既不是2的倍数也不是3的倍数的数放在左上角 列出一堆这样的数表
每个数表最多17行11列
然后题目的要求就是 选一些数 使得没有两个数相邻(上下相邻对应着2x 左右相邻对应着3x)
我们一个个数表去考虑 两个数表之间互不影响 所以最后把每个数表的答案乘起来就好了
对于一个数表 令f[i][st]表示当前选完了第i行, 第i行的状态是st的方案数
那么枚举两行的状态 判断是否可行(就是没有上下相邻、左右相邻) 然后就可以转移了
但是这样状态会有点多 可以先把没有左右相邻的状态预处理出来 然后只判断有没有上下相邻 就可以了通过这道题啦
bzoj 2436 [Noi2011]Noi嘉年华
09:19 开题
09:33 看题解
10:24 过了
这题好难啊
其实也不是很难 就是把几个dp揉到了一起 感觉起来变得好难
因为时间的具体数值对安排活动没什么影响，可以先离散化时间
需要知道第i个活动LiRi必须举办，活动较少的嘉年华活动数量的最大值，可以转化为(i=1Li)(j=RiT)的活动必须在同一个嘉年华举办的答案
设f[i][j]表示i~j的活动在同一个嘉年华举办的答案，需要几个辅助的状态
设pre[i][j]表示时间1~i，有j个活动在A举行，B活动数的最大值，
suf[i][j]表示后缀，状态定义类似pre
num[i][j]表示i~j的活动数量
pre[i][j]=max(pre[k][j]+num[k+1][i],pre[k][j-num[k+1][i]])
suf 类似
于是得
f[i][j]=max(min(k+l,pre[i-1][k]+num[i][j]+suf[j+1][l]))
直接暴力转移是O(n^4)的
可以发现，当k增加时，l单调不升
可以优化到O(n^3)
poj 3567 Cactus Reloaded
这好像是第一轮NewTrain的最后一题了
剩下的都是感觉没法做的了
10:28 开题
11:01 试着开始写
11:30 成功wa掉 感觉自己的做法有问题 但又不知道哪里有问题...
13:55 看题解(怎么还是要看题解啊...%>_<%)
15:27 暂时放弃这道题 大概看懂了题解 以后再写
然后参加了一个什么"正睿OI2018暑期普转提集训热身赛"
具体过程就不说了
反正是个信心赛一样的东西 题目比较容易
Day4 2018.7.2
早上先把那个什么信心赛打完了 接着又有一个对我这个蒟蒻来说比较难的比赛 做到了下午还是一题不会。。。
晚上出去吃饭 又上了一个奇妙的语文课 感觉一天啥都没干。。。效率极低。。。
Day5 2018.7.3
今天好像是休息
但是昨天也没干事感觉很虚...
这个一年计划的第一个星期算是虎头蛇尾?
早上去我妈工作的学校里 下午去了一个农庄 人生第一次钓鱼... 钓了一条小的一条大的 一共6斤 很有成就感
本来以为晚上得上课 匆忙赶回家 连饭都没吃 结果老师那边停电了...%>_<% 于是晚上就只好做题了
准备把各种算法梳理一遍 查漏补缺
堆
- NOIP2004 合并果子
每次选两个最小的数加起来 加到答案里 然后把他们的和放入堆中 做n-1次 - NOI2015 荷马史诗
k进制的哈夫曼编码 注意要求最长的编码长度最短 我们要记录每个单词的已经被合并的次数
每次选的时候 如果有多个频率相同的词汇 优先选被合并次数少的 这样更优(显然)
然后我们需要总个数mod k-1 余1 如果n不满足这个条件 可以加一些出现次数为0的单词 不影响结果 - [国家集训队]种树
经典问题 还是一个环 所以更方便做 不用考虑边界
去一个最大值 把两边的数加起来减去它 把它和它两边的数从堆中删除(开一个map记录被删除次数) 压入两边的数的和与他的差
链表+堆+map 类似的问题还有好几题 不过感觉以后不会再出现了吧 都考烂掉了... - [POI2005]SAM-Toy Cars
经典问题? 一开始我以为每次从架子上拿的时候把当前pick出来的剩余玩的次数最少的拿掉
事实上应该把pick出来的下次出现位置最远的拿掉 因为出现的越远 如果不拿掉 对答案的贡献越大(占了一个位置)
我们要使得答案尽量小 就要把远的拿掉
我还是太naive了
由于一个a[i]打成了i 我调了10分钟而且看了数据... 好菜啊...
做完了这四题以后我惊讶的发现 全部是贪心+堆 所以是不是贪心的题大部分都可以用堆维护呢
并查集
- [NOI2008]假面舞会
想出来后感觉不是并查集啊 然后翻了一下题解 果然跟并查集没什么关系...
果然是假面舞会 真**假... - [APIO2008]免费道路
这题比较简单
首先优先加边长为1的边求一棵最小生成树 找到其中加的边长为0的边 这些边标记一下 必须得加入生成树中
如果这些边的数量>k 那么直接无解
然后把所有边长为0的边拉出来求一下最小生成树(森林) 因为不完整所以求出来的东西并不一定连通 不过没关系 算出这时被选入的边的数量
如果这些边的数量<k 那么同样无解(全加进去也不够)
然后就是肯定有解的情况了
首先标记上的边加入生成树中 然后再在剩下的边长为0的边里面选k-已加入数量的边加入生成树
然后在所有边长为1的边 继续求生成树 这时候得到的生成树就是满足条件的一棵生成树了
哈希
找了几道在大神博客上分类为hash的题,发现全部要与其他算法一起使用 好像没什么只用哈希的题
树状数组/线段树
做了[kuangbin带你飞]的线段树专题中的一些题目
基础的线段树不成问题 但是有一些trick的题目就看不出来....(；′⌒`)
Day6 2018.7.4
今天还是先写线段树的题目
然后下午浪了一会+上课
晚上试图做SDOI2017 R1D1
具体过程不赘述
感觉题目不算太难 第三题比较简单 连我都会做
第一题推了几张草稿纸结果发现中间有一步错了 只好用中间的一个式子做部分分
然后看了一眼正解感觉也不太难
Day7 2018.7.5
一年计划的第一个星期就这么过去了...
后面几天不知道再干什么...
早上把SDOI2017R1D1的T2做了一下 只会10分...
于是搜题解 LCT
连splay都不大会的我不知道哪里来的自信决定半天搞定LCT
于是就gg了
下午去了趟图书馆 回来感觉想睡觉 于是就睡了一觉 然后再上课 一下午就这么过去了...
最后一天似乎是效率最低的一天
现在是20:15 终于开始做题
放弃LCT之后决定把动态规划训练一下 毕竟要有一个会一点点的东西 什么都不会太尴尬了...
bzoj 3628 [JLOI2014]天天酷跑
20:18 开题
20:36 终于看懂了题意
21:20 想了一个dp的做法 感觉会超时 看了题解之后发现跟我的坐法几乎一样 改成记忆化搜索就可以过了
22:00 一直感觉网上的题解有问题 然后构造了一个数据 成功×掉了网上仅存的3篇题解
23:00 自己写了一个做法 然后没调完
Day8 2018.7.6
bzoj 3628 [JLOI2014]天天酷跑
07:57 接着调
08:06 事实证明 如果要正确的做法 就会超时4个点 用错误的做法才可以过...
