【暑假集训模拟DAY1】搜索&枚举

前言

最困难的题目往往只需要最朴素的方法---搜索

赛时崩溃...因为只写了两道题的部分分,甚至怀疑爆零,还好看到大家基本都是30pts

得分:40pts

题解

T1 hzw的粉丝

按照题目说是最简单的一道题,但也只会爆搜,而且在实现的时候出了很多bug(还莫名其妙50pts->20pts) 

字符串的字典序排序出了点问题。。。发现char类型只能用strcmp比较大小,string只能用>=<比较大小

sscanf,sprintf忘记用法。。。

PS: sscanf(s,"%d",&n); sprintf(s,"%d",n);

正解:小数据直接打表,大数据固输,因为 k<=1e9大数据直接是hzwer+数字后缀

T2华容道

题解:BFS裸题(谁说的)

考场直接放弃。大概是5进制HASH记录状态的BFS,但是现在还不太完全明白

T3聚会

中位数操作不难想,但是在走到指定位置的操作上一直不会处理,最终写了个错误的贪心

正解:通过中位数先找到一个终点,然后以该点为起点拓展出一个大小为n的连通块,然后全排列 n! 枚举每个点放到连通块里的哪一个位置

T4真相

(真相了)

考场放弃。原本一眼觉得是我不会做的样子的带权并查集,但是居然真的也是搜索

正解:没有“$"操作的时候,直接线性搜索;有”$"操作的时候,先假设所有“$"话都为假算出一个tot,再枚举哪一个"$"为真的情况下对答案的贡献a[i],最后统计答案时tot+a[i]==i说明i句话为真可行

真是神题

后话

真是破防了

原文地址:https://www.cnblogs.com/conprour/p/15120360.html