本周ACM总结以及最近ACM心得小结重头戏来了

68 阅读 0 评论 45 点赞

我是靠谱客的博主踏实故事，最近开发中收集的这篇文章主要介绍本周ACM总结以及最近ACM心得小结重头戏来了，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

总算交上作业了，亲爱的博客一周未见总算要来写我亲爱的博客了~

还是和往常一样先说点这周看到的印象深点的例题或者给过我小灵感小启发的题

先从开始简单点的 并查集和环说起：

我在看题解是看到说，并查集很重要的一个用处就是判环，如果有题中需要判环那就要考虑一下并查集啦，和别的相比算是最简单的办法了吧

原理很简单，输边输点的同时加边加点，如果加到一个点的父亲节点和另一个点的父亲节点相同，那么就可以判定出现了一个环。

删边删点类问题：

P3535 POI2012

P1197 JSOI2008星球大战

P3535 [POI2012]TOU-Tour de Byteotia

是因为我的惯性思维还是因为我看的题太少，一看见删边我就很乖乖听话的想着把图构造完然后怎么根据要求删边（内心cos：删啥呀，你又不会删），肯定是看的题太少了还没把这个思维刻到脑子里

一遇到删边问题基本都要用逆向思维反向加边，逆序做，经过这次博客写出来我下次应该能立刻反应出来了吧（看的这几个题还没有不能这样解决的呢），因为我发现，只要我写进我博客里的东西我一般都忘得很慢而且印象比较深

所以说博客不仅是对自身的总结，也是帮助促进学习记忆加深得一种手段

比如第2个题即先假设给的k个星球全都被炸，求出此时的联通块个数，就是经过k次打击的联通块个数。然后再加上最后一个被炸的星球，就求出了经过k-1次打击的联通块个数。以此类推，最后把所有点都加进去，就求出了经过0次打击后的连通块个数

再比如第2个题目要求删边，那就反过来从没有边开始加，符合条件就加，不符合条件就不加（也就是删除这条边）并且answer++,最后answer就是答案

还有下面这道题，同时考察了删边和成环的问题（但是我深刻记得当时看这个题的时候没想起来最小生成树，这看完题意不就赤裸裸的出来了么）很简单，就只需要0.001的思维而已，为我当时的愚笨浅记一下至少下次一定能想到

P2820 局域网

本题要求去掉边最大使图不能形成环，还是没想起来不就是求个最小生成树么，一看题解我才悟了

思维转换一下就是让剩下的边最小就是求最小生成树呗，用边的总长度减去最小生成树就是要删除的最大边了

带权并查集

这类题一般都有个惯用的套路，每当和最优解或者最值牵扯到关系时，那么必不可少的一步就是对sort对权值排序然后根据顺序依次处理边就能保证得到的答案是最值

就举一个对我来说典型又值得做的题

P1196 NOI2002

这个题可真是......题意读着简单题解看的有点小绕（我承认我看了很长时间才看会然后自己打的时候答案一直错错错，没办法比着题解又比着做了一遍然后又改改改才勉强过了）

本题所求的不止是两船是否有关系，还要求两船之间有什么关系也就是求两船之间的距离，又得件多个数组，fa[i]记录船的祖先也就是船之间是否联系，a[i]记录编号是i的船到fa[i]之间的距离（也就是距离这一列船头的距离），num[i]记录编号为i的船所在的那一列的船的总数。

我认为这个题用到的最重要的思想就是前缀和吧，求ab两船的距离的好方法也就是用b船距离船头的距离-a船距离船头的距离，假设用fa[i]表示飞船i到其所在队列队头的距离，然后飞船i和飞船j之间的飞船数量即为它们到队头的距离之差减一，就是abs(a[i]-a[j])-1。（以后在遇到这种一维的求两点距离的问题基本就要想到前缀和）

上代码

#include<bits/stdc++.h>
using namespace std;
int fa[30001];
int a[30001],num[30001];
int x,y,i,j,n,tt,ans;
char s;
int find(int x){
if(fa[x]==n)return fa[x];
a[x]+=a[fa[x]];//更新
return fa[x]=find(fa[x]);}
int main(){
cin>>tt;
for(i=1;i<=30000;++i){
fa[i]=i;
a[i]=0;
num[i]=1;}
while(tt--){
cin>>s>>x>>y;
int fx=find(x);
int fy=find(y);
if(s=='M'){
a[fx]+=num[fy];
fa[fx]=fy;
num[fy]+=num[fx];
num[fx]=0;}
if(s=='C'){
if(fx!=fy)cout<<"-1"<<endl;
else cout<<abs(a[x]-a[y])-1<<endl; }}
return 0;}

P2658 汽车拉力比赛

啊这，这也能往并查集上套？？

题意是一个二维数组然后求使两点之间能联通的最小差，看见这题的第一反应以及之后的反应就是怎么找从一个点到另一个点的路径使这个最大差最小，然后我觉得也就是我比较熟悉的搜索可以解决吧，毕竟和迷宫差不多，找路，但是这也是并查集例题啊，并查集在哪呢，咋用并查集解决呢，可真是想不通了（我太弱了qwq）然后看题解还是看题解，我滴，这也能想到，神了

没想到还能借用二分查找从整个图的最小差到整个图的最大差，然后合并差小于等于mid的两点，最后看路标之间是否连通（所以还是想怎么合并两点找祖先呗，我怎么就没想起来这样合并呢，看来还是没怎么掌握并查集的精髓之处吧，更何况没人告诉我用并查集的时候）

ps：最后查连通块的数量可以遍历找有几个点的父亲结点是自己就行了

那个表格里的题感觉开始的和后来的难度差可真大啊，开始题和题解都看得还比较轻松，当看到中间偏下的位置时，可真...难，后面几个有的连题目都快读不懂了，几乎没有一个是能把一个题的全部方法和思维考虑全的，总有障碍点，

后边有好几个难题都是不止用了并查集或拓扑排序，并查集和拓扑排序只看作是其中某个步骤或得到某个中间数值的工具，还要和别的算法结合起来，说实话我不看题解真的写不出来也想不起来，凭自己想的写出来之后答案基本都不怎么沾边，每个都要看一大会所以看透的也不是特别多，就先不一一阐述这些了，接下来的心得体会才是重头戏

先简单说一说这周打比赛和做题遇到的一点问题和错误总结：

1.尽量优化自己的代码，提高代码的效率，减少运行时间
① 这周打比赛时，有个div4级别的，第三个题应该也能做出来，前两个很简单，第三个也还行，当我兴奋的做出来第三个之后（虽然我是用三重循环做的我感觉可能会超时），结果还真超时了，但是不用三重循环好像没有更好的方法了，然后我问了一个做出来的人他说他也是用三重循环做的就过了，在三重循环里有个和剪枝类似的操作可以减少时间我也写了，但是还是不过。我就想既然都是三重循环，那应该就是我的细节没有优化吧。于是我把cincout改成scanfprintf，或者加上ios那一句加快cin速度，就这样我试了将近一个小时，就是超时（因为我不舍的放弃这个虽然超时但是做对的题）最后，我就试着放弃的心态把定义在外面的m，n等字母放到主函数里面，就，，，，过了，我，，震惊。
②还有在做洛谷题的时候我看别人题解都会用到快读写一个快读函数，我从来没用过因为我做的这些不用也能过，然后今天做了一个题就超时过不去，加个快读就过了
所以关键时刻还是有用的

2.细心
这周犯二犯了一个错就是因为我习惯数组上来用a命名，然后不小心有个变量和结构体都是用的a命名，但是这写重它没有报错!所以运行时就是不输出，以为是哪里步骤不行，仔细看了一下才看出来命名命重了，唉还是要细心太马虎了。

重头戏来了

自学acm以来的收获和总结:

1.学习习惯的改变以及自律:
学acm之前我似乎还从未接触过这样的事，当时感觉就是为一件事下定决心而且在接下来的这段日子里注定是条不归路，不能回头，只能坚持下去（不得不说费老为了让我们补上这门课真是花了好大的力气，老师确实辛苦了，上就得坚持，不能旁听，我能感受到费老是真的想锻炼我们的能力想让我们有很大的突破想让我们成为更好的人）
以前的学习方式都是只学习上课讲的东西或者最多往后预习一节，就好像无事可干了，而现在，自从选了acm之后我再也没觉得有过空闲的时候了，而是每天都学不完的感觉。
其次，以前也从来没有过几乎全靠课下去练习学习某个东西，几乎就是靠自学（我学钢琴的时候可能和这有点类似也是每天回家写完作业再练几小时的琴一直到睡觉，不然曲子也不可能熟能生巧的也不会有后面参加总决赛拿奖的时候，但我感觉比acm简单多了），虽然老师引导很重要但课下不学是肯定不行，同时也提高了我的自学能力，开始看博客的时候可费劲了也看不懂也看不下去，好枯燥好无聊，但现在至少跟开始的感觉完全不一样了，当我看的时候，我可以坐下来在这认真研究分析，虽然题目变难了但是感觉比刚开始看的时候更能理解透了。
2.知识的学以致用.举一反三:
学到了知识就肯定有能用到的地方，而且不能学1是1，要扩展到他的应用，他的拓展，他的变形等等。洛谷上的每个题，看似是离我们很遥远的只能在做题时遇到的奇葩题，但是仔细想一想，这都是从生活中演变过来的实实在在的题诶，迷宫里面的游戏问题，你敢说用不到这些思想？最短路径问题，难道和平常导航出一条最优路无关？代码是死的思想是活的，不同的语言之间的思想都是通用的。
      几乎每个算法都会有一套模板，但是比着模板就真的会做题吗，不，还要考虑很多情况，要在原模板的基础上变形再变形，只背模板，不思考不动脑，是不可能真正学会的
3.经常总结、自我反省:
写博客是个好习惯，感谢费老让我养成了总结和记录的习惯，我写过之后一般印象都比较深，所以我现在很喜欢平常看题或者做题时不论是受到小启发还是大启发或者恍然大悟的时候，都想在博客总结时简单记录一下，下次遇到类似问题时我就会想到我曾经遇见过还写过
       还有一个好处就是能清楚知道我这周干了什么，学了什么，学到多少，能清楚把握自己所收获的东西
4.顾好当下，贪心别贪:
      既然当时选择了acm现在就先好好学着这个，顾好眼前，对未来想的再多，最切实的前提也是先顾好现在，才会有以后的成就。而且现在也没有什么精力去学别的，学一个抓好一个就是了。在生活中遇到选择时，不要想怎么兼顾，应该想如何选择能做到最优解，这样才能有最小的损失。
5.学会思维转变:
我记得从小学一个切苹果出来五角星的课文就开始讲逆向思维了，到现在又有多少人能做到呢，总是循规蹈矩不懂得创新，我也是这样。而且总是有一种惯性思维约束着我的发挥，就几乎不会反过来思考一下，在平常洛谷做算法题时就有好多次就需要逆向思维或者稍微转变一下把求这个转变成求另一个东西，我应该特别缺少这种思想，离我最近的就是这周刚看的并查集里面一说到删边，就要反过来加边，如果开始没人告诉我要我自己想，那我一定费劲脑子想什么把一个边去掉，这种思想应该也是现在大多数人缺少的吧。

总之，学acm是真的能学到很多东西，我也不后悔我当初选择了它，相信能继续锻炼我的能力，我也要继续坚持下去。换句话说，明天继续!