LOFTER for ipad —— 让兴趣,更有趣

点击下载 关闭

LOFTER-网易轻博

NOIP

2040浏览    299参与
Algorithm.
哈哈…笑死我了………… 以及我...

哈哈…笑死我了…………

以及我认识到一个问题,NOIP更名为CSP后,是不是会跟那个绘画软件抢tag。。。

哈哈…笑死我了…………

以及我认识到一个问题,NOIP更名为CSP后,是不是会跟那个绘画软件抢tag。。。

neilchao
404 Not Found

线段树

占位先,作为一个线段树都能写炸的蒟蒻一定要些点东西
 没错我来写这个线段树的笔记了

# lofter支持markdown 吗?

lofter上好像不支持md,那就没有更丰富的展现了(?)

线段树能区间修改,区间求最小值
 对于单点修改,区间求和的出门左转“树状数组”(树状数组那么好写谁还写线段树)

代码

#define MAX 50010

#define lson (id<<1) //id*2

#define rson (id<<1|1)

int tree[MAX * 4], a[MAX];

inline void build...

占位先,作为一个线段树都能写炸的蒟蒻一定要些点东西
 没错我来写这个线段树的笔记了

# lofter支持markdown 吗?

lofter上好像不支持md,那就没有更丰富的展现了(?)

线段树能区间修改,区间求最小值
 对于单点修改,区间求和的出门左转“树状数组”(树状数组那么好写谁还写线段树)

代码

#define MAX 50010

#define lson (id<<1) //id*2

#define rson (id<<1|1)

int tree[MAX * 4], a[MAX];

inline void build(int l, int r, int id){

if(l == r){

tree[id]= a[l];

return;

}

else{

int mid =(l + r)/2;

build(l, mid, lson);

build(mid + 1, r, rson);

tree[id]= min(tree[lson], tree[rson]);

}

}

inline int qnery(int l, int r, int id, int ql, int qr){

if(ql <= l && qr <= qr){

return tree[id];

}

int mid =(l + r) / 2;

int res = 0x3f3f3f3f;

if(mid >= ql){

res = qnery(l, mid, lson, ql, qr);

}

if(mid <= qr){

res = min(res, qnery(mid + 1, r, rson, ql, qr));

}

return res;

}


oofoof

并查集(求有多少个团伙)

【基本概念】

并查集通过一个一维数组来实现,其本质是维护一个森林。刚开始的时候,森林的每个点都是孤立的,每个人都是自己的王,也可以理解为每个点就是一颗只有一个结点的树,之后通过一些条件,逐渐将这些树合并成一棵大树。

其实合并的过程就是一个“认爹的过程”。在这个过程中,要遵守“靠左”原则和”擒贼先擒王“原则(这里靠左或者靠右都并无大碍,但一旦选择一个原则,便要一直遵循)

在每次判断两个结点是否以及在同一棵树上的时候(一棵树其实就是一个集合),也要注意必须求其根源,中间父结点是不能说明问题的,必须找到其祖宗(树的根结点),判断两个结点的祖宗是否是同一个根结点才行。


【问题描述】

第一...

【基本概念】

并查集通过一个一维数组来实现,其本质是维护一个森林。刚开始的时候,森林的每个点都是孤立的,每个人都是自己的王,也可以理解为每个点就是一颗只有一个结点的树,之后通过一些条件,逐渐将这些树合并成一棵大树。

其实合并的过程就是一个“认爹的过程”。在这个过程中,要遵守“靠左”原则和”擒贼先擒王“原则(这里靠左或者靠右都并无大碍,但一旦选择一个原则,便要一直遵循)

在每次判断两个结点是否以及在同一棵树上的时候(一棵树其实就是一个集合),也要注意必须求其根源,中间父结点是不能说明问题的,必须找到其祖宗(树的根结点),判断两个结点的祖宗是否是同一个根结点才行。


【问题描述】

第一行两个数:n,m。其中n表示强盗的个数,m表示警方搜集到的线索。

接下来m行,每行两个整数a,b表示a强盗和b强盗是同伙。

问一共有多少个团伙?


【样例输入】

10 9

1 2

3 4

5 2

4 6

2 6

8 7

9 7

1 6

2 4


【样例输出】

3


【程序代码】

#include <bits/stdc++.h>

using namespace std;

int pre[100];


int find(int x) { //寻找x的父节点

    if(x!=pre[x])

        pre[x]=find(pre[x]);

    return pre[x];

}


void merge(int x,int y) { //合并两个子集

    if(find(x)!=find(y)) {

        pre[find(y)]=find(x);

        }

}


int main() {

    int u,v,p,q;

    int ans;


    cin>>u>>v; //顶点数、边数

    for(int i=1; i<=u; i++) //初始时每个节点的父节点都是自己

        pre[i]=i;


    for(int i=0; i<v; i++) {

        cin>>p>>q; //边的两个顶点序号

        merge(p,q);

    }


    for(int i=1; i<=u; i++) {

        if(find(i)==i)

            ans++; //计算连通子图个数,也就是得出几个团伙 

    }


    cout<<ans<<endl;


    return 0;

 }


oofoof

线段树代码中 k<<1|1 的说明

【程序代码】

#include<bits/stdc++.h>

using namespace std;

int main() {

    int k;

    cin>>k;

    cout<<(k<<1|1);        //2k+1


return 0;

}


【程序代码】

#include<bits/stdc++.h>

using namespace std;

int main() {

    int k;

    cin>>k;

    cout<<(k<<1|1);        //2k+1

    

return 0;

}


ST.Koala

我想学

Garsia-Wachs

为什么网上找到的题解都是不详细讲这个算法的?

我想学

Garsia-Wachs

为什么网上找到的题解都是不详细讲这个算法的?

ST.Koala

我想出一道交互题。有没有dalao会出交互题,能不能教教我。

我想出一道交互题。有没有dalao会出交互题,能不能教教我。

帅小子F

为什么这里好像都没有人的样子啊

        我上一次在这里发东西已经是很久以前的事了(至少一周之前),为什么现在最新发布还是我啊。

        我上一次在这里发东西已经是很久以前的事了(至少一周之前),为什么现在最新发布还是我啊。

帅小子F

hello

        hello,有人一起学信息竞赛的吗?

        hello,有人一起学信息竞赛的吗?

海鲜蘑菇泡面

不知道该不该继续坚持了。。。
什么也听不懂,求着老师又讲了一遍仍然不懂
身边的大佬们看题就能撸代码而我还要分析题目想要干嘛(是的我连题都不懂)
有时候理解了老师的代码也自己写不了
很绝望看着身边比自己小的比自己厉害很多。。。

不知道该不该继续坚持了。。。
什么也听不懂,求着老师又讲了一遍仍然不懂
身边的大佬们看题就能撸代码而我还要分析题目想要干嘛(是的我连题都不懂)
有时候理解了老师的代码也自己写不了
很绝望看着身边比自己小的比自己厉害很多。。。

ERROR:

[CCF BASIC]Eg 2.31

//2.31

#include<iostream>

#include<cmath>

#include<iomanip>

using namespace std;

int main(){

double a,b,c,n;

cin>>a>>b>>c>>n;

cout<<setprecision(15)<<pow(a,n)+pow(b,n)+pow(c,n);

return 0;

}


//2.31

#include<iostream>

#include<cmath>

#include<iomanip>

using namespace std;

int main(){

double a,b,c,n;

cin>>a>>b>>c>>n;

cout<<setprecision(15)<<pow(a,n)+pow(b,n)+pow(c,n);

return 0;

}


ERROR:
soulwinter
soulwinter
soulwinter
邻座有只喵

2017/11/12 OI

退役啦。


大目标省一无缘,不知道能否保住省二,俗话说的好,学了半天信竞,却还是没能get到算法的真谛,考场上还是只会打暴力。

练了半天动态规划、二分、暴力DFS枚举、拓欧、高精、tarjan都没用上,太辣鸡了,智商感人。

虽然依然很想骂出题老师。什么鬼啊,D1T1不考代码,考大瞪眼法……


想想一年前,一切的一切开始于被老师划去了“趣味”两字的趣味算法课。

回忆回忆那课,还真是挺神奇的,想来之后也没人再体会到这么“水”的课了。都干过什么呢,比如:

  • 肖然从身旁拽过一把椅子,滑到叶芝蘅旁边:“给我讲讲孙济时的八卦吧!……继续讲继续讲!……”

  • 叶芝...

退役啦。

 

大目标省一无缘,不知道能否保住省二,俗话说的好,学了半天信竞,却还是没能get到算法的真谛,考场上还是只会打暴力。

练了半天动态规划、二分、暴力DFS枚举、拓欧、高精、tarjan都没用上,太辣鸡了,智商感人。

虽然依然很想骂出题老师。什么鬼啊,D1T1不考代码,考大瞪眼法……

 

想想一年前,一切的一切开始于被老师划去了“趣味”两字的趣味算法课。

回忆回忆那课,还真是挺神奇的,想来之后也没人再体会到这么“水”的课了。都干过什么呢,比如:

  • 肖然从身旁拽过一把椅子,滑到叶芝蘅旁边:“给我讲讲孙济时的八卦吧!……继续讲继续讲!……”

  • 叶芝蘅表示自己录了学长团团舞,大家表示好奇,纷纷凑到电脑旁边看起了优酷……

  • 从学段开始到学段结束,中间桌子上的书、零食越堆越多,问:“老师,您怎么都不收拾桌子的?”“不影响啊,摆的也不邋遢,为什么要收拾呢多浪费时间”……(居然找到了同样的观点。)

  • 拿着桌上的黄飞红花生:“可以吃吗?”“嗯你吃吧。”“不怕我上个课吃完吗?”“怕啊,可是老师上课不能吃东西……没事你吃吧。”

不过也有正经编程的时候,还记得我生日那天,课堂内容正好是用MATLAB编曲,于是便编了一首生日快乐歌放出来。而很多作业,虽然也有纠结于for循环套for循环的时候,然而一般我好似都在下课几十分钟甚至一小时前干完……亏的之前没有白和爸爸搞乐高、尝试学习SmallBasic语言。(现在看来,那算个毛算法。)

所以在课程结束的时候,肖然抓着我讲了一番排序,并强势安利,来信息学竞赛俱乐部吧。

还转发了登峰杯的邀请,问题是我都不会编程啊。

……哦。

结果没想到,到了第二学段末,报信息通用课的时候,由于不想换老师,竟然一脑抽接受了肖然的邀请,当时还道只是上个课。

 

寒假,D105,三四个人的教室里,在边听课、边随意乱窜、甚至可以随便吃桌子上零食的情况下,竟然用不到两个星期把其他19届一学期的内容学完,从C++入门到深搜。

然而毕竟入门太快,缺少练习和消化,很多代码没有真正理解掌握,加上不够勤奋刷题,于是在接下来一个学期的课里只能尽力追赶。

就是,一说写题,还会在编译器前坐个十几分钟,思路断篇,代码写错,调试两个小时出错不断的那种。

有时候,课上发给微信给“场外援助”,说这道题编不出来好像不太好意思回家,可怜巴巴地请求帮忙人工debug。和朋友、父亲的聊天记录里充满了“我好弱啊,做了一个小时这道题还没过,他们都过了”“我为啥又死循环了”“今天肖然测试又爆零了,什么逻辑思维能力都不存在的,如果我最后确实什么成绩都没有,看起来还投入这么多,岂不是很搞笑”等等。即使到学期末,也有坐在电脑前一个上午没拽出一道题的经历,大概真的是我智商不足……

我可能是在学习怎么写BUG和死循环吧。

好在是,还算尽力地写了作业,也算是花了比别人多几倍的时间跟下来了。虽然像什么拓扑、在线更新MST都是依靠标程,慢慢一句一句对出来的。

终于,在学期末的时候,和肖然在学校遛了将近一个小时。记得他一直在鼓励说我和其他人的能力没有多大的差距,期望我继续努力,倒是很吃惊。甚至,我们还聊到了高二整个的大体方向和以后的专业方向。真的感谢肖然老师在那时候鼓励我坚持,也真的感谢他没有觉得我投入不够或者智商余额不足而放弃我,否则怕不是要后悔好多啊。

最后学期总评的时候,看到98的分数和第2的排名,激动地说不出话来。

 

然而,高二第一学段的冲刺才算是真正参与到了竞赛当中。

初赛的时候,有那么几个晚上,竟然专心致志地刷了一晚上的题或背知识点。

复赛之前三周,加课、刷题和模拟赛成了常态,交织在每一天的生活中,每天不做个几道题都仿佛对人生的辜负。

确实累啊。

不但要用飞一般地速度写完课内作业,而且还要用剩下尽可能多的时间沉浸在AC、TLE、WA和RE中。每天固定在一努力写题就熬夜、一熬夜第二天就神情恍惚的无限循环中。

心态爆炸无数次,模拟赛爆零爆十,死磕dp仅仅是从5变到了20,脑子昏昏沉沉把简单循环变量写错,数组下标错得离谱……会想自己怎么这么辣鸡,会撑着一个字一个字地敲代码,会沉默地悄悄弃疗一会,也会在飞快的敲击键盘中重新坐起来,也会在晚上走在校园里的时候人脑模拟。有时候,无限谈论着信息竞赛、时不时的绝望也会影响到身边的人,也一直很懊恼很抱歉……

也难怪考完后,真的什么都不想干了,只想智障一会。

 

我大概是竞赛中最不像搞竞赛的一个吧。舞蹈节、舞蹈团等艺术活动一点没落,书院内阁、招新活动也刷脸频繁,以及,还有了个展……我敬佩的学姐学长们,他们在105日复一日地埋头学习,在每个静悄悄的深夜做实验、刷题。既能一个人消磨寂静,又能在一起不失风度地讲着段子、小小地打闹一番,差点一副岁月静好的样子。

高一时,对竞赛没有很清晰的概念,只是觉得搞竞赛的人很厉害,只是觉得学习竞赛能多学点,挺好的。而身边参加竞赛的人,有不少一部分是“跟风”。

直到考完NOIP,才知道,这才是竞赛啊。

真的是需要花很大精力认真投入的东西,需要自己沉下心来慢慢投入和享受。你要满腔热血地去爱,也要学会沉稳下来自我折磨。当然,也需要那么一点点的高智商,没有便只能用更多几倍的努力去弥补。

所以它才变得这么有魅力,所以搞竞赛的人都在很投入地去付出、去不断挑战自己。

想起这学段开始的时候,肖然对一个来面试的学妹说:“你要想清楚啊,竞赛要很费精力的,可能会耗掉很多时间的……”

我在旁边嘴角一抽,那您去年怎么跟我说的是:“不难不难,来吧,他们也没讲多少,和你之前用MATLAB学的都差不多的……”

哼,骗人的。

 

虽说没有方成段子手那么6,也有些专属于OIer的笑点难以忘却。

会记得MST是Minimum Spanning Tree而不是the Most Small Tree,gcd的真实本质是马克思主义,最大子矩阵的暴力可以先枚举四点再判断是否为矩形,坑爹的输出判定如“YE5”和“N0”,我觉得应该早日讲线段树时其实是觉得应该早日退坑,传说中越是nb越是要去厕所,金牌选手dan晓晗,拉不拉的尴尬动规选择……

会记得洛谷上十几遍的大红大紫变成满面春风的喜悦,指尖连续敲击在键盘上的行云流水,各种环境里抱着电脑得天下的满足,以及考试里哪点小聪明换来的几十分……

 

看过hzwer关于的博客,里面说:“我们做竞赛的时候就是一种惺惺相惜的感觉,就觉得你考得不好我真的很惋惜,这题没做出来我真的替你感到很难过,是这么一种感觉,而不是我高你几分我有一种优越感,就是我们那边竞赛选手我们没有一种竞争的感觉,就是大家都好像是在和题目去竞争不是和人去竞争。”

我觉得说的在理,在一起竞赛的朋友们,是真的会为了对方分数低或者调不出来哪道题感到惋惜,对方考得好也真的会为他由衷地开心,平时约着交流题目、互相帮忙查错,在课上课下聊天互评,大抵如此吧。

在这里也有幸见识到了大神的风范,希望两位初三大神们继续努力,真心祝他们能干成一番大事。

 

不管怎么说,职业生涯也算是告一段落了。

近来一直在思考以后的问题,从自招到以后的相关专业,只是说不定,没准大学就选了计算机专业,又回到电脑前码代码了呢。尚且认真学习,求个选择的余地吧。

作为一个投入远远不及神犇的省四选手,本不应该矫情这么多,却依然忍不住记下了OI的一些历程,很神奇了。我真的辣鸡,最终没实现省一的目标,也后悔当初为什么没有多刷点题多用点功,为什么考场上脑子这么不灵光。

不过,肖然的推送最后一句写得好:“没有对生活的绝望,就没有对生活的热爱。生活不是考试,人生不是赛场,祝愿你们早日摆脱这世界的荒谬。”最最值得回味的部分,往往是过程,是那些故事,尽管一点也不客观唯物。确实一点也不够优秀,可生活的的确确不只是有竞赛和学习。

毕竟成长。

也毕竟找到了点什么。

 

无比感谢肖然老师满分的讲课、鼓励以及耐心辅导的种种,感谢D105和D104里的时光,感谢NOIP时忍受我折磨的ljy和yzh,感谢队友们的帮助,祝以后的学弟学妹们RP++!

hehe0__0
hehe0__0
hehe0__0
hehe0__0

LOFTER

让兴趣,更有趣

简单随性的记录
丰富多彩的内容
让生活更加充实

下载移动端
关注最新消息