最后一周训练:
· 入门题能对:T1没问题
· 普及-题能对:T2就没问题
· 普及/提高-(普及 和 提高-)能对:对标T3和T4
· 普及+/提高能对:部分年份的T4
考场注意事项:
· 不要爆零(freopen格式,文件夹不要建错)
freopen("code.in", "r", stdin);
freopen("code.out", "w", stdout);
fclose(stdin);
fclose(stdout);
不要忘记删测试语句,建议用cerr语句(和cout用法一样)来测试
提交代码前,检测3遍freopen有没有写错
提交文件的时候,保证一定有cpp源文件
· 大数据一定要验证
Excel公式:=IF(A1=C1,1,0) 右下角往下拖,如果为1则此行正确,若为0则此行错误
· 心态保持稳定(遇到难题很正常,深呼吸,慢慢想)
做题时:
· 第一步,看数据范围,注意long long,注意时间复杂度。T3T4需要你根据数据范围先猜测算法
· 第二步,写代码的时候,问问自己这个算法的时间复杂度会不会超时。T3T4再根据题目特征确定算法
题目特征
T3T4骗分粪决
骗分路径
深搜骗分的通用技巧
DFS优化的技巧
1. 可行性剪枝:当前状态已经不可能达到目标 -> 立刻return
2.最优性剪枝:当前解已经不必最优解好 -> 立刻return
3.记忆化(搜索 -> DP的桥梁)
当你发现DFS的参数组合**(a, b, c)**会重复出现时,加一个数组记录是否会重复出现,如果重复了直接返回结果
4.搜索顺序优化
优先搜大的/优先搜小的:按题目直觉,先搜更可能有解的分支,更早触发剪枝
优先搜必须要搜的位置:比如先把广搜扩散的所有起点放入队列