细节的重要性

注:补上一次基地校活动博客

细节的重要性

生活中处处有细节,有了完美的细节才有完美的整体。一个机器少了一颗螺丝钉,可能会使整个机器无法运转;一道菜多放了盐,本来的美味就会瞬间消失;一个细菌没有完全杀死,疾病就有可能再次复发。细节是多么重要,联系到生活的方方面面。当然,之前讲的都是理论上的,今天我才真正地体会到细节的重要性。

一次信息模拟赛,我辛辛苦苦打了一百多行的代码,犹如一条长龙,见不到尾,却得到了没有分数的回报。我当时又气愤又伤心,一口咬定是测试数据有问题。最后十分无奈的我,只好向老师倾诉这件事情。老师笑道:“你啊,就是一个急性子,测试数据是没有问题的。那位是李学长,信息奥赛多次获奖,你可以向他求助。”我硬着头皮来到李学长身边,向他说明我的遭遇,当时我都快哭出来了。

“你应该感谢老天这不是真正的省赛,”李学长说,“没事,我帮你看一看哪里有问题。”话音刚落,他打开了我的代码。“哇,你的代码真长。但是正解代码长度仅仅只有36行。你要注意代码的简洁,好让别人有耐心看,同时也方便自己,不容易出错。但是不要过于追求简洁影响到了答案,运行速度或者运行空间,这样很明显是不公平的交易。”这是李学长给我的第一个指导。

由于我的核心代码在主函数里,所以学长比较关注下方的语句。他大概浏览了一遍,发现我定义的变量五花八门,让人难以理解。所以他看几个句子,都要问我这个语句是什么意思,这个变量的作用又是什么。最后他终于理清了我的思路,并提醒我说:“写程序,变量要见名知意,最好用一些单词缩写,方便别人理解。”这是第二个指导。

李学长帮我删去了一些没有用只会占空间的句子,并进行一遍又一遍的调试,他发现我的思路和正解差不多,删去一些废句子以后,基本上是与正解一模一样。到底是哪儿有问题呢?学长眼睛有些红,一遍又一遍看我的主函数,从浏览到精度。最后他断定错误不在主函数里。所以他又去次要的函数找错误。学长看代码,而且还是别人的代码,比我做题还认真,我为自己之前的抱怨感到十分羞愧。我心里很清楚,理解别人的代码是很痛苦的,不仅要理清别人的想法,还要融入自己的思维。“找到了!唉,你这个粗心鬼。”李学长突然激动大叫,他指着屏幕上的“zhizhen1”这个变量,这个是有问题的,应该是“zhizhen2”。改完以后,拿到电脑上一测,0分秒变100分。如果比赛我加上这100分,可以从第26名变成第4名。学长指着我的脑袋以教育的口吻说:“多做一题不如多注意细节。这是信息奥赛,你的每一步都有可能让你坠入深渊。细节很重要,这种低级的错误下次别犯了。”这是最后的指导。

今天学长讲了三个注意事项:1.代码要尽量简洁,但不能因为简洁改变了做题思路;2.变量要见名知意;3.细节很重要。其中关于第3点我的印象最深。为什么呢?因为从0分秒变100分,这是省一和省三的区别!细节很重要,今天是真正接受了惨痛的教训。细节真的很重要。

2018CZ夏令营总结

常州的绿化是真的好看,常州高级中学也是很漂亮的。

原本想放更大更清晰的图上来的,但是最多只能放2MB,将就着看吧。


【正儿八经的总结】

第二次来到常州,去了另一所中学,也体验到了一些不一样的东西。

正如出发前yk说的,这边的题确实是比较考思维的,虽然也会考到没有学过的算法,但是有学过的算法都不一定能AC,还是会有些挫败感的。

而且,很多时候,看着很难的题目,往往正解都比较简单,而那些看着简单的题目,只能拿下部分分,优化却是出奇的难,一把辛酸泪啊。

上午打套题,下午听题解和一些算法。不过往往听不太懂,修行尚浅,也不能怪我吧。

不过也还是有一些收获的,像对搜索,贪心有更深一步的了解,贪心,和搜索也可以考得很难,像什么双向宽搜,A*算法(可能现在也还不是很懂)。然后曹文老师讲的那两天,连通图和树,是我听得最明白的了,加深了对树和图的基本认识,也学会了最近公共祖先LCA。省选那一期的下午,基本也没听了,在酒店随便看看,就学习了平衡树treap,set,和map的用法。

那么,总的来说,这十几天下来,收获还是不少的。

嗯,路漫漫其修远兮,吾将上下而求索。

继续阅读2018CZ夏令营总结

【2018常州】SCZ夏令营 总结

芳树无人花自落,春山一路鸟空啼

芬芳馥郁的秋叶摇曳在风中,用它动人的歌声为我们送行。蓦然回头看去,这是一次眼界大开的集训,收获满满的集训。

「课程」

江苏省常州高级中学的管理比较开放,不会过分计较迟到、旷课、零食之类的问题。优秀的人不应该有这些坏习惯。每天上午打原创套题,下午听讲座。内容偏难,更考验思维能力,并没有对代码量和算法掌握有很高的要求。有的题目看起来非常复杂,但是正解也不算繁杂,理解后发现还是可以修改出来的。

讲课的都是牛犇的大佬(其中有一位学长,颜值超级高),速度快,理解难。比如多重背包问题,我还不会,就直接讲了关于它的斜率优化之类的。特别到了后一周,前排听课的都是很厉害的人,有时候甚至不知道他们在讨论什么。真的全程几乎听不懂。但是即使其他人都没去,我还是选择每天都坚持听课。

「成绩」

首先常高的评测机有些神奇的限定。longlong不能用%lld,行末不能过滤空格比较,有些函数会报错。但这些都不是我经常垫底的理由(呜呜呜)。很幸运有一天能AC了一道题得到5元。

比较糟糕的是后一周题目不难可是我经常考得不好,可能是因为我对于推规律这一方面不是很行。遇到一个题目的时候,我总是会纠结暴力和正解,明明想到的解法的思路是错的可是都没有办法一下子否定,然后在那边梳理错误的思路;或者想到了正解可犹豫不定,担心是错的然后模模糊糊打不出来。我觉得我的解题思路是要把所有的搜索枚举分拿到,问题是有的题我连暴力都不是很会。所以有的题我打部分分就会花一个多小时的时间。

「收获」

这次集训有一些收获。图论上我知道了Floyd,Dijkstra,SPFA的区别和复杂度。但是我不会打Dijkstra以及堆优化,考试的时候就专心用SPFA了。另外我了解一些神奇的数据结构:堆,栈,队列,动态数据,二合一结构体,以及基本的操作。然后动态数组可以优化SPFA做更大的数据。扩展欧几里得我可以推式子但是不会算法实现。倍增求LCA知道原理,但是不会存树,也没打过题目。理解强联通分量Tarjan思路和实现。拆分含义。DP是个很玄学的东西,我至今无法分别它的分类,区间DP,状压DP,树上DP……但是题解的DP还是蛮好理解的。

还有就是打题的时候要静下心思考,这样一些代码实现上的错误好修改,省去查错很多时间。以及要宽容待人。

插一句,即使是常高也不乏小学生佬,成绩前列,深深佩服。

「体验」

酒店还是很不错的,只是中途有些小意外,厕所漏水,突然断电,中途换房间。另外常州花费还是挺高的。特别是饭馆菜价比肉价贵,怀疑浙江是畜牧区。这里的景色还是很美的,而且常州银丝面很好吃,常高学校环境很优雅。

另外还有位来自新疆的学长,感觉他很厉害。我不懂树的重心的定义他给我画了张图然后我就明白了,之后我参考了他很多问题。期待遇到更多这样友善的人。

「总结」

“努力,我要努力,我要变成万人迷”

蒟蒻水平还是欠缺,难的题目要争取打对暴力,简单的题目不能丢分。学习算法是一个有趣的过程,能在SCZ集训是幸运的。加油!

「 END」

感谢 Yk,Chh,Cjy,Csz,Cxj,Shy,Zl 同行的陪伴和帮助,与蒟蒻进步。

Aug.23th

【2018常州】集训总结

By shy

——这是生命中的一天,

平静而神往,

这是生命中的一天,

美丽而安详。


第二次邂逅常州,在SCZ度过的,是一个不一样的暑假。

与常州一中严格的规定不同的是,SCZ的管理比较宽松,

例如手机随便带(然并卵),上课随便迟到,以及随便逃课(还好没人管)。关键是,AC还奖钱!(好像不关我们什么事)

但是最大的不同在于,SCZ的题和林厚从的题风格截然不同:

林厚从的题都有一种说不出的恶心,专考一些码量极大的数据结构,考的范围还很广,连卡常数都出来了。

SCZ的题注重于思维,码量不大(不过50行),每天都会有一两道“水”题,但是不仔细想,不将思路变通,想做出来还真有点难。

(举个例子,SCZ的题目不是很强调时限,如果std的时间接近0.5秒,甚至会给我们开2秒时限;不像林厚从那儿整天压时限,以机子跑得快为理由直接压成0.5秒,还拿水题出卡常,直接读入1千万个数,连读入优化都不堪重负)

所以说,在SCZ的日子比起常州一中那是怎样的一种惬意啊。

不过也有几桩不好。比如评测的教师机用不了%lld,这还好,关键是好几次评测时用的全文比较,没有过滤文末空格回车,害的我被坑了好几次,从此我养成每次输出都换行的好习惯。

而且下午的讲课依旧不是很懂,讲的内容实在可怕。不过曹文老师讲的不错,内容也都消化了。


那么我学了什么呢:

  1. 死磕正解(雾)
  2. 如何在提高组找水题
  3. 图算法:
    • 习惯了使用动态数组版邻接表代替链式前向星
    • tarjan算法求强联通分量、割点和桥(思路会了,暂时没碰到过题目)
  4. 树:
    • 用无向图的方法存树
    • 倍增求LCA(最近公共祖先)
  5. DP
    • 第一次在比赛中推出区间DP
    • 发现计数问题大多都是DP(然并卵)

SCZ的每一天都是充实的,每一道题目对我来说都充满了挑战,它们磨练着我的思维。这话很套路,但的确如此。

有时也会有意想不到的收获,最后一天做省选的题目,我竟然AC了第一题。那是一道扫雷的题目,我恰好在书上看到过类似的题目,于是我推了两个终于推出了这题。尽管只有40行代码,但是没有那道题目的其实,我真的很难想到这种解法。所以,多看书,多写题目实践,也是很重要的。我靠这道题赚了120,真是开心~

充实的每一天使我快乐,但是快乐终究是短暂的,我们依旧要迎来新的学期,新的挑战。


——我看见天空那么奇幻,

我感觉大地那么温暖,

我听见天使在向我召唤,

我知道这一次我不用再等待. . .

SCZ_CZ

集训十五天
发现一个问题
我就开始几天和中间几天认真了点!其他时间都在玩qwqqqq
太没毅力了……
不过没办法!人就是这样!能咋办!
崩的彻底不过我心态非常好~
回学校学习啦~
准备准备9.1的入学考emm

Endl.

2018常州培训心得

在常州的十天培训,我收益颇多。不仅学到了新的知识,还意识到了自己只是茫茫学生中最不起眼的那个……

day1

我们学习了搜索的优化。总的来说尚可,但仍有地方听得不太明白,需再研究。

day2-day3

我们学习了树的运用。讲课的老师是江熠玲老师,这个老师讲课真的很好,一般学生不会的她都会讲解一下,且讲得特详细。她讲课那些天的内容我都理解得不错,不过还是需要去多加复习。

day4-day5

依旧是江熠玲老师讲课,我们学了背包问题及其运用。

day6-day8

我们学习了有关图论的相关知识及运用,对此我掌握非常不好。对于那些基础的知识半知半解,对于prim算法、dijkstra、SPFA我只知道其大致的思路但不会打代码……对于tarjan,唉……

day9

我不幸的发烧了,在酒店里卧床不起。学的是动态规划的优化,据说很难。

day10

学的是二分倍增分治。能说什么呢。教我们的是一位水平很高的老师,但这不代表听得懂他的课。总的来说,一节课什么都没学会。

关于这些天的比赛:

总的来说都还算正常发挥。觉得自己有些漏洞还是需要补补:

  1. 细节还是不够注意;
  2. 审题还是不够认真;
  3. 解题还是get不到正解;
  4. 层次还是有待提升。

有些小学生,初一学生真是太恐怖,每天都能进前十。且越到后面比赛就越难,有一些学生竟然还能上300甚至AC,真是山外有山,人外有人。突然想起似乎有人提醒过我们:长江后浪推前浪,千万不要被拍死在沙滩上了……

学好信息学的路途尚远,我只能更加努力……

-End-

changzhou_practice

头一次听说信息奥赛要来常州培训,这让我意识到,信息奥赛是一门很重要的学科,并不是一种业余的事情。而且这一次培训让我深受感悟,不仅学到了许多知识,还让我明白了许多道理。

常州第1天

常州第一天是将深搜的优化和剪枝,我虽然学过深搜,但是这堂课我还是听得十分糊涂,即使我已经很认真了,第一次考试前二十名都没有我的名字。这个时候,身为井底之蛙的我应该意识到什么了。我一直以为我的信息学实力很强,其实这根本就是一个谬论。当来到一个更加宽广的世界,山外有山人外人有,高手非常多,在信息考试的第一天,在渺茫的排名中,我的排名要往下拉很久在可以看到,虽然这对我的打击很大,但我必须意识到:我必须更加地努力,而不是满足于现状。

常州第2~5天

这四天都是江熠玲老师讲课,我觉得这位老师讲课质量十分出色,她在讲课的时候,每讲一道题,都会预留时间给我们思考,讲题的时候语速比较慢,这样方便我们理解。背包问题和堆的性质我听得不错,但是比较难的题目还是不可以理解,希望在暑假的最后几天可以抽出时间去好好消化一下那些内容。

常州第6~8天

这三天是讲图论的,对于图论的内容是很难的,毕竟一开始从来没有接触过这些东西。一整堂课下来讲的内容都是压缩的,解压的过程还得自己来。

常州第9~10天

这两天讲的内容是最难的,讲课的老师获得的奖项也是最多的,但这并不代表我能听得更好,越是学历高的老师,讲的内容就更加高深,让我摸不着头脑,有许多不会的数学公式,以及一些名称奇怪的算法。这些东西不是一个月就能解决的,还是先解决其他的吧。

对于考试

我没有考过300分以上的(不包括300)。信息学是一门十分严谨而又高深,同时十分抽象的一门学科,所以做题目错误率极高。有些题目我已经想好思路,并且证明这是对的做法,但是动手亲自实践时总会犯一些小毛病:比如变量名打错,错的十分隐蔽。或者是多此一举,多加了一些没有用处反而有害的东西。小错误先不说,还有很多完全没有思路,连暴力骗分都做不到题目,竟然还是有许多常州的学生打出来了。实力的差距,就要把它化为前进的动力才对,而不是满足于现状,或者自暴自弃。

总结

这次常州培训来得十分有意义,虽然有许多知识并没有完全掌握,甚至是完全听不懂,但是时间的消磨一定可以解决它们的。我还明白:人不能高傲自大,外面的世界很宽阔难道真的没有人比你更厉害吗?最后,我对信息学的态度要有所改进,我应该要像语数英那样去对待它,它并不是一门业余的学科,它是十分专业的。

【2018常州】8-21 Day14

By shy

——这是多么美好的一天,

阳光明媚 大地无边,

我却毫无意义。

一道清晰的光柱,

无话可说 无处不在,

就像粒尘土. . . . . .


1. ​​深渊(abyss)

题意:有n个物品,每个物品有一个价值v[i],选择尽可能多的物品使价值之和为 m 的倍数,输出这个最大值。1<=n, m<=5000,1<=v[i]<=100000 (1<=i<=n)。

解法:

首先我们发现,令价值之和为m的倍数,等价于价值之和模m≡0

那么我们实际上可以在求解时一边取余,这样所有的价值之和模m的余数都不会超过m,这样缩小了状态数,我们就可以用一个接近于背包的DP求解:

无后效性分析:取第i+1个物品时,价值之和只与在前i个物品中取到的价值之和有关与物品选取的顺序无关

设f[i][j]表示前i个取到的价值和%m余j的情况下,能取到最大价值和,

转移则为 f[i][j]=max(f[i-1][j],f[i-1][(j-v[i])%m]+v[i]);

注意j-v[i]若为负要变成模意义下的正数

但是这个转移方程有几点很麻烦的问题:

  1. 要有一个前提条件,就是转移之前的的状态(即f[i-1][(j-v[i])%m])是合法的(有被转移到过)。
  2. 另外,j-v[i]为负的处理也得注意,
  3. 而且方程转移的顺序也让人难以捉摸。

那么,针对这些问题,有个简单的办法:记忆化搜索

先打出暴搜框架(因为无后效性,所以可以把结果作为返回值【便于记忆化】),复杂度为O(2^N):


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int v[5005];
ll dfs(int i,int j){
//正在选择第i个,已经选择的物品价值之和%m为j
    if(i>n){
        //物品选完了
        if(j==0){
                //物品价值之和是m的倍数,返回0
            return 0;
        }
        return -INT_MAX;
                //否则返回一个大负数,表示无解
    }
    ll res=dfs(i+1,j);
        //不选第i个的情况
    res=max(res,(dfs(i+1,(j+v[i])%m)+v[i]));
        //选第i个的情况
    return res;
}
int main(){
    cout<<dfs(1,0)<<endl;
        //从第1个开始选择,初始价值为0
    return 0;
}

因为暴搜过程中存在重复调用导致复杂度升高,而重复调用的返回值相同(这就是记忆化搜索中无后效性的必要性),所以我们记忆化的过程只需要一个二维数组f[i][j],存储每次调用的答案(数组每一维对应一个形参):


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int v[5005];
ll f[5005][5005];
ll dfs(int i,int j){
//正在选择第i个,已经选择的物品价值之和%m为j
    if(i>n){
        //物品选完了
        if(j==0){
                //物品价值之和是m的倍数,返回0
            return 0;
        }
        return -INT_MAX;
                //否则返回一个大负数,表示无解
    }
    if(f[i][j]!=-1) return f[i][j];
        //如果有记录结果,直接使用记录的结果
    ll res=dfs(i+1,j);
        //不选第i个的情况
    res=max(res,(dfs(i+1,(j+v[i])%m)+v[i]));
        //选第i个的情况
    return f[i][j]=res;
        //回溯时记录结果
}
int main(){
    memset(f,-1,sizeof(f));
        //数组清为-1,表示没有调用过(没有记录过结果)
    cout<<dfs(1,0)<<endl;
        //从第1个开始选择,初始价值为0
    return 0;
}

由于每一种参数最多被调用2次,所以复杂度为O(NM)【也就是DP的复杂度】,可以通过本题。

这样打有什么好处呢:

  • 可以从暴搜过渡到记忆化,思考比较容易(实在不行就交暴搜)
  • 可以解决之前提到的三个问题
    1. (合法状态):我们从第1个物品、价值为0开始搜索,遍历的状态必定是通过合法状态转移的;
    2. (j为负的处理):j只会增加,所以不会为负
    3. (方程转移的顺序):搜索的顺序就是转移的顺序

PS:700ms,好险(不过DP也差不了多少)


——天空升起紫色的烟花,

眼前是一片辉煌。

我迎着风向前狂奔,

这速度能不能抛开忧伤?

继续阅读【2018常州】8-21 Day14

2018CZ夏令营Day14

这是集训的倒数第二天了,明明水的一匹,却炸了。

不要问我为什么,我也不知道为什么······


T1:【深渊】

题意:不想讲有n个数,每个数都有一个价值v,取若干个数使他们的和是m的倍数又尽可能的大。

先吐槽一下,给的题解有点偏差,真是害死人,改半天改不出来。

正解动规。

f[i][j]表示前i个取到的价值和再%m余j的情况下,能取到最大价值和。

每个物品只有两种状态,取或不取。不取的话,就等于上个物品%m余j的最大价值和,所以:

f[i][(j+v[i])%m]=f[i-1][(j+v[i])%m];

如果取的话,就等于本身(也就是不取的情况)和上一个物品再%m余j的情况下,加上v[i]。注意第二维j+v[i]可能会超过m,所以要取余。

if(h[i-1][j])  f[i][(j+v[i])%m]=max(f[i-1][j]+v[i],f[i][(j+v[i])%m]),h[i][(j+v[i])%m]=1;

h数组则是维护某个状态是否到达过。如果你当前这个状态需要有上一个状态转移,而上一个状态却不曾到达过,也是不可行的。

最后要输出的便是前n个数%m=0的最大价值和了,也就是f[n][0];

感谢烨神尽一个小时的教导,还帮我调代码。


T2:【勇士】

这是我来到常州这么多天遇到的最最最最最水的一题,没有之一。

就是给你n个数,找到最大的数,并找一下最大的数值有几个。

简!单!不!简!单!

不需要任何算法,你自己爱怎么来怎么来,反正我没有用到快排,直接在读入时,如果这个数大于maxx,maxx=当前这个数,g(计数器)清为1。如果等于,g++。

注意每个数的范围,此题需要long long。


T3:【战斗】

题意:好复杂不想讲

其实最后的正解也就是贪心。

每次把所有的数从小到大排,然后对于最大的数,只能和前面的数连,也就是从前a[n]个数都要减一,而最后一个数变成零,重复此步骤知道所有的数都变成零。如果大于零的数不够减了,那便是矛盾的。

嗯,就这样。考场上我写的代码也很接近了,少个排序断送满分。


T4:【堕落】

不是很会,也不是很想去理解 。送你们题解:

看到x坐标范围较小,考虑将一个矩形拆成若干个以行单位的线段,最多1000*1000条,然后双关键字排序,统计每一行的线段覆盖。

继续阅读2018CZ夏令营Day14

【2018常州】 8.21 Day14 心得

风华是一指流砂,苍老是一段年华

传送门 Day14 T1 深渊

他们并不知道,赐予他们食物的,并非上帝,而是深渊中的魔鬼

50分:暴力+部分分优化

枚举所有可能的情况。当m=2时如果答案满足直接输出,不满足减去最小的奇数。最后为了防超时大数据的搜索从最大值开始依次递减最小值找到答案立刻输出。

100分:DP

无论是二维还是一维,时间复杂度都差不多。从头开始枚举所有点可以累积的各个因数的值。为了防止被乱累积,达不到也就是没有值的点不计入。

for(i=1;i<=n;i++)
{memset(books,0,sizeof(books));
for(j=0;j<m;j++){
if(book[j]!=0){b[(j+a[i])%m]=max(c[j]+a[i],b[(j+a[i])%m]);
books[(j+a[i])%m]=1;}}
for(j=0;j<m;j++){c[j]=b[j];if(books[j]==1){book[j]=1;}}}

传送门 Day14 T2 勇士

几天后,在街上乞讨的他,在报亭口的报纸上看到黑帮全体成员离奇死亡的消息。
一声低沉的嘶吼,打断了他的回忆......

题意简单。找出一串序列中最大的值有多少个。

然而因为昨天没休息好(借口),我大意地看错题意了,连自己所理解的思路都是错的

Good Relax ≠  Good Result

传送门 Day14 T3 战斗

“我们已经迷失方向了,这么走下去可不是办法。”

100分:每个人都是一样的,枚举所有情况没有意义。每次抓连边最多的点拿起来连,连完后排序一遍再连即可,最后看看可不可以连完。

50分:由于害怕反复排序会超时,在每次操作完之后并没有重新排序

传送门 Day14 T4 堕落

那夜,她亲眼见到她的伙伴的面容变得发青,变得狰狞——“不是上帝让这个世界变成这样子,让这个世界堕落的,是我们自己。”

30分:建立一个100*100的方格,然后涂色

40分:在此基础上对只有一个矩形的点特判,直接长*宽计算面积即可

100分:由于横轴宽度小,枚举每一列。把每个矩形拆成h*1的若干个矩形,按照端点排序,然后累计。

这就是今天的题目。符合题面上安慰人心的话“普及组信心赛”和备注“AK了不要大声喧哗以及批判出题人。”

但是我只有110分。我不应该

I.看错题意 II.害怕超时而选择错误的打法 III.没有休息充分

下午只有我去听课,讲的是前几天没讲完的网络流提高。虽然什么都没听懂,但是就凭今天这个讲题学长的颜值以及最后十分钟的开车Worth the time!

 

最后一天,无论考好与坏,都用真诚的心去努力。加油

Aug.21th