20190128

T1  方块转换Transformations
错因:代码中方法的顺序打错了。
模拟各个方法中行与列的关系,在进行对比。
T2  城堡 The Castle
还没改出来。
建图+深搜+细节(!)
T3  两只塔姆沃斯牛(The Tamworth Two)
模拟牛和农民的路线,用一个较大的值来判断他是否抓得住牛。注意一个小细节:旋转也占一分钟。
T4  骑马修栅栏
欧拉路径。
总结:速度太慢了,第四题还没有打时间就到了,第二题耗时最久但只得了零分,要注意取舍和对时间的把握。

2019寒假集训1.28

T1

模拟,模拟#1—>#5的情况,进行判断,由于数据小,直接暴力,嗯。

T2

。。。。不会,还在请教大佬。。。。。

T3

因为地图为10*10,所以可以简单粗暴的进行模拟。要注意的就是题目中提到的一些情况,顺时针旋转90°和对相遇的判断。

T4

这题不理解可以在纸上画图,首先应找奇点,若有多个几点,使用编号最小的那个。每次寻找编号最小的栅栏进行访问就行了。值得一提的是在最后输出时,要倒序输出,因为用的是递归。

2019寒假集训Day4

1.方块转换

纯模拟,可以用goto,方便.

2.城堡

不会.

3.塔姆沃斯牛

纯模拟,但是有一种很坑的情况....

. . . .  . . . . . .
. ******** .
. ******** .
. ******** .
. ******** .
. ******** .
. ******** .
C******** .
. ******** .
F. . . . . . . . .

嗯,循环超时 or 递归爆栈...

4.骑马修栅栏

欧拉回路 ?

会一笔画就好.

20190128

T1方块转换
模拟。
错因:1读入炸了;2有个地方字母打错。
难点主要在于#1和#3的两种旋转,列表观察之后可以发现以下规律:
(c为旋转后的图案,a为原图,字符串从下标0开始)
#1 c[i][j]=a[n-j-1][i];
#3 c[i][j]=a[j][n-i-1];
要注意的事:如果有多种可用的转换方法,请选择序号最小的那个。

 

T2城堡
BFS。
这道题细节特别多。以下讲一下我的做法。读入后,先处理墙的位置,注意要从南面(数字最大)开始处理,将墙的位置对应的数组下标赋为-1。(填充颜色为绿色表示下标,蓝色表示格点。)

然后就是宽搜,在搜索时存储每一个格子所在房间(即联通块)的大小,并给这些房间编号并新开一个数组存储编号,为下面寻找要推掉的墙做准备,此时已算出城堡的房间数目和最大的房间的大小。(填充颜色为绿色表示下标,蓝色表示格点,黑色和红色为墙(即所在a[i][j]为-1)。)

之后寻找要推掉的墙,上面存储编号的数组就起作用了,在寻找的过程中,打破上图中红色的那面墙,表面上将两边的数值加起来是18,但实际上两边是在同一个房间里的,打破此墙最大的房间面积仍为9,所以要判断墙两边的所在房间的编号是否相同,如果相同,就应该跳过。因为有多解时选最靠西的,仍然有多解时选最靠南的,所以要从右往左,从上到下循环。

T3两只塔姆沃斯牛
模拟。
错因:读入炸了。
按照题意操作,可以定义一个变量来存储当前人或牛的朝向,注意不要超出边界。至于怎么判定John无法抓住牛,可以定一个很大的数,如果时间超出了这个数还没有抓住,那么便可判定John无法抓住牛。

 

T4骑马修栅栏
DFS。一说欧拉路。错因:不会打。
用邻接矩阵存图,寻找是否存在奇点,若存在奇点,则从编号小的奇点开始DFS,否则从1号点开始DFS,以保证输出的是多组解中题目要求的那一组解。核心代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int x)//x为当前搜索到的点
{
    for(int i=1;i<=n;i++)
    {
        if(a[x][i]>0)
        {
            a[x][i]--;
            a[i][x]--;//无向图删边要删两次
            dfs(i);
        }
    }
    s[++l]=an;//s为栈,输出时逆序输出
}

最后说一句:读入一整行字符,一定要直接scanf("%s",s);不要一个一个读,我已经被这样坑过三四次了,这次少说也丢了一百多分。

2019寒假集训day3

T1混合牛奶
刚开始让人误以为是多重背包问题,但事实并非如此,还更简单一下。
用贪心的思想即可,快速排序把价格便宜的牛奶排在前面。
为什么说不是多重背包呢,因为这里的牛奶可以一升一升买。

T2回文质数
有一个比较复杂算法,耗时956ms(不稳定):
对于数据范围1——1e9
我们知道,回文的密度要比质数要小,所以我们可以先判断回文。
我们可以想到,一个数如果既是回文又是质数,那么它的个位仅可能是1,3,5,7,9.这时枚举的i可以2个2个加。
它的最高位也只能是1,3,5,7,9.所以对于向20001的数字可以直接跳转到30001.
虽然看似时间复杂度小了很多,但是那些优化判断也是需要时间的,优化作用不是很好,这时怎么办呢?
最后我们发现,1e8之后已经没有符合条件的数字了,这时我们可以把枚举范围缩小到1e8,或者采用On算法:打表。数字并不多,可以事先求出。

T3最短网络
最小生成树,比较明显的一道题;
推荐使用Prim算法,因为这里邻接矩阵已经事先给出,不用自己转化。

T4兽径管理
依然考最小生成树算法
Prim算法不推荐使用,不好优化
这里讲Kruskal算法
暴力做法:每次加一条边都sort一次,后做最小生成树,部分数据超时。
有没有更快的做法?
我们发现,我们可以给每一条边标记它的加边时间,然后一次sort的同时把时间也带上,这样我们可以通过标记来判断符不符合时间,这样以来只需sort一次。

20190127

语文是基础学科。

——ZDQ

T1 混合牛奶

贪心思想。

考试时花了好几分钟弄懂题目的意思。

以价格为第一关键字来排序,再从前到后地取每个人的牛奶,直到取满为止。
T2 回文质数

考点如题。只会埃氏筛的我就直接打表了。

不过考完再回头看看题目,我在考试时的思路是先判断质数再判断回文,但其实先判断回文再判断质数,速度会更快。所以,当一种方法无法解决问题时,可以多思考一些别的方法。

将各数位分离即可判断回文。
T3 最短网络

最小生成树。无需赘述了。
T4 兽径管理

仍然是最小生成树。

错误原因:不知道,我直接重新打了。

利用结构体来存储每条边的数据,为了不多次排序浪费时间,就需要将边的序号也存入结构体。将边按照边的权值排序,然后在最小生成树的过程中判断此时此边是否存在即可。

2019寒假集训1.27

T1

贪心,将输入后的数据按价格排列,从低到高。在排列价格时注意一下价格对应的牛奶量就差不多了,最后模拟一下买牛奶的过程就行了。

T2

用函数来判断回文和素数,应先判断构成回文,再判断是否是指数会快一点。

T3

由于在做题时并没有想过Ac,而是朝着部分分做题的。并不是很清楚。。。。。

T4

这题题目信息特别多。其中提到“兽径”是可以保留的,所以在判断一个点是否能到达其他所有的点时,不行要记录下来。还有一个就是重路的问题,进行比较即可。

2019寒假集训day2

T1破碎的项链
模拟题
要点:
1.破环为链:由于题目给的字符串是环状的,所以要复制两倍的长度。
2.对于w可以当作任意颜色的珠子,这里不详细说明
3.破环为链的过程中有个细节:因为要复制两倍长度,可能会有整串都是rrr的情况,这里可能会误以为是6.

T2双重回文数
要懂得判断进制和回文(先判断进制后判断回文)

T3等差数列
难点:
1.双重平方数
2.等差数列的数字如何找,会不会陷入无穷的无底洞呢?
3.输出顺序问题;
4.上界;
一一来解决他们,对于1,双重平方数可以用二重循环全部求出,为了防止重复问题,可以把他们全部加入哈希表,再利用这个表桶排序,这样可以不仅可以得到双重平方数的数组,还可以得到一张表;
对于2我们可以通过两个回文平方数相减得到一些差值,然后通过这些差值往上加,看看有没有符合条件的回文平方数(判断是否为回文平方数,在1中已经求出一张哈希表,可以在O1时间内迅速判断)。(因为等差数列必须包含回文平方数,所以这么做一定有效果)
对于3,首先用结构体来存储答案,再利用STL中的sort进行双关键字排序;
对于4,因为平方数可能会出事,2*250^2超过十万,固哈希表要定到二十万。

T4回家
1.要把字母转化为数字,最后转化为图,需注意:A和a是两个不同的地点;
2.本题对时间复杂度要求不高,可以采用Floyd算法(无向图),代码复杂度较小;