考试总结(1.22)

果然,这次考试又是垫底

失败原因:

¤没有认真的审题,我们考了一道老的不能再老的题目虫食算,虽然我隔了很久没有敲了,但思路还是记得的,在我的不懈奋斗下,终于写出来了,但是!我没有认真看题我还有什么可说你的能?!100分就这么飞走了,下次一定要看清楚题目!!!

¤第一次知道在emacs中,他有些关键词的使用是不会给你报错的!!在这次考试中,我用end成功的敲开了CE的大门,虽然这题按我的正常水平也只有那么10pts,但是也比爆零好呀 !!

¤没有大局观念!!这是你一直以来的错误,审题不细,看题不清,做题不完,知识漏洞,这都是你考倒数的原因!加油,下次千万别这样了

题目分析:

1.黑白棋游戏

我们考的是这个题目的简化版,它只让你求最少需要移动的次数

思路:

不是很懂,大佬都说要(状压+BFS)

2.乌龟棋

我的天哪,竟然是一道我做过的背包题!!

关键是我一点印象都没有,还听信了昨天大佬说的都是搜索题的假话!!

结果以10pts结束了这道题

思路:

这题如果用背包的话是挺简单的

总共有四种走法,相应的我们就开一个四维数组用来记录每种走法的步数

我们可以记录每种走法的次数,再来一个四重循环进行背包

最后就只要输出就可以啦

这其实就是一个背包的版子题,只不过需要我们对数据进行处理&分析,并推出其是四维

3.CF-177-A

由于这题找不到合适的链接,而且题目有比较短,我就直接复制粘贴到博客上啦

题目:

3 CF-177-A
3.1 题目描述
• 满足以下条件的字符串:
1. 包含恰好 k 个不同字符
2. 长度为 n
3. 相邻两个字符不同
• 如果存在多个,请输出字典序最小的
• n ≤ 10 6 , k ≤ 26
3.2 输入格式
一行两个数 n, k 。
3.3 输出格式
一个长度为 n 的字符串。

就是这样啦
思路:

我一看到这个题目我有点惊讶,如此简单的一个题,但是事实是即使再简单我也没有A掉

80tps

主要是有2中情况没有考虑到

1.k=1,n=1;

2.虽然题目没有说,但是测评中竟然也有错误的项,及就是输出-1

4.虫食算

这道题真的超级经典!!我至少做过2~3次,一次是搜索入门,那是候的搜索太low了,只能打个60pts,但是后来学剪枝也做了,再到后来要NOIP联赛了,搜索专题中又有她

但是!!

我又错了,

原因竟是

我多打了一个空格

我已经无话可说了

思路:

按照进制要求从后往前一一匹配

枚举每个字母所代表的n进制数内的数字

值得注意的是,为了剪枝需要,你需要每进一位就要满足当前的式子

好的,就这样

 

其实主要是那些我不会的题目

而且网上有找不到题解,没办法,只能强迫自己去看那些大佬的代码,自己领悟~~~~(>_<)~~~~)(要死了)

考试的5.6.我就先pass了,因为实在接受不了

其实这次第六题特别神奇,竟然只需要一个freopen就可以满分了,动都没动的我掩面哭泣~~~~(>_<)~~~~

直接上第7题

7.最大团

题目:

7
最大团
7.1
题目描述
• 给定一个图 tt = (V, E)
• 求一个点集 S ,使得对于任意 x ≠ y ∈ S ,x 和 y 都有一条边
• |V | ≤ 50
7.2 输入格式
第一行两个数,n, m 分别表示图的点数、边数。 接下
来 m 行,每行两个整数 x, y 表示一条边 x ↔ y 。
7.3 输出格式
输出最大团的大小以及最大团的数目。

大概就是这样了

因为这次考是时间不够,所以我根本就没来得及去看这道题目,直到刚刚,我才有机会去了解一下题目大意

GQL告诉我这是一个完全图,我很开心,因为我学过,但是!!!我一点也不记得了,所以在这里的话我主要是讲一讲大佬代码的思路,然后我就

借鉴一下!!

思路:

首先,我们用邻接链表的形式储存,用一个tot记录当前所找到的最大团中包含多少个元素,然后就用DFS去枚举寻找

在寻找同时我们要记录有多少个最大团,并在最大团内元素更新时,记录数清1

那么我们这么来判断一个最大团呢,这里用的是一个特别简单粗暴的方法,每次找一个点,我们就将他与之前找过的点去进行比较,如果都能匹配上,那么就可以算到最大团内

最后,我们就只要输出tot和记录数就可以了,虽然我觉得这个思路很对,但是只有80pts,maybe是超时了吧

8.TC-572-D1L2 

不出意外的,我这题又没有看

其实仔细思考的话,这一题打暴力是很容易的,就类似于虫食算一样,一个一个进行匹配

在看了大佬GQL的代码后,感觉整个世界都明亮了

思路:

1.我们要想好这么处理这些数据,于是我们可以用减法,对每一位上于原数相匹配数做减法

最后确定数的时候就只需要检验这些数是否已为0

2.我们所要进行枚举的就是我们的数每一位上的值,然后根据这个值去对应题目所给数字中相应位数,如果该位上的数字会使所给数字与所求数字相同数字超过要求,那么就不符合题意,而判断的条件就是看被剪的数是否为负,其实这也是一个剪枝,在DFS的过程中就将其减去

3.我们还有注意记录解的个数,分为唯一解,多解和无解

虽然我并不会正解,但是这个方法挺适合我的,放在这次考试中还是有70多分

注意:

前导零的存在是合理的,不需要进行特判,我们GQL大佬就是因为特判丢的分

9.弱弱的说一句,我实在是不想看了,能力范围所不及啊

 

原文地址:https://www.cnblogs.com/KSTT/p/10305709.html