20210902PM
2021/9/2 23:11:25
本文主要是介绍20210902PM,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
--- | 预期 | 实际 | delta |
---|---|---|---|
A | 70 | 100 | +30 |
B | 100 | 100 | 0 |
C | 100 | 100 | 0 |
D | 100 | 100 | 0 |
E | 100 | 0 | -100 |
F | 100 | 0 | -100 |
G | 100 | 100 | 0 |
H | 70 | 30 | -40 |
总计 | 740 | 530 | -210 |
A 回文日期
由年份可确定整个串,再判定是否合法以及是否在[L,R]内即可
江湖传言可以打表
B GCD
rt
C 校门外的树
数据太小,模拟即可
D 蛇形方阵2
太菜只能模拟一条蛇了,注意越界了退回来。
E 单点修改区间查询
树状数组板子,线段树也可,就是码量相对感人,可惜了我少一个\n直接爆零
F 溶液模拟器
用栈存下所有P指令,注意top等于0时Z指令无效化
下次一定要看清楚输出啊...少输出一个值错失100pts
G 转圈游戏
题意:求\((m*10^{k}+x)\mod n\)
- 其实本来以为是高精取模,毕竟\(10^{k}\)多半爆long long,但是k<=\(10^{9}\),高精也解决不了,因此我们要从另外的角度解决
- 由于取模操作里的四则运算除了除都可以搬出来,所以可以化为分别求m,x,\(10^{k}\)对n取模,因此可以转成快速幂求解
H 生日
初见想到的是01背包,但是数据范围里总金额m<=\(2^{31}-1\),按正常dp来写肯定时空都顶不住,然而这道题并不需要具体的买了多少件这类数据,可以转为判定方案的合法性
- 一遍dfs是O(\(2^{n}\)) 要炸,效仿双向搜索的思想,将所有礼物分成前n/2件与后n/2件分别dfs得到各自可以实现的金额,再将二者组合看看是否能得到m
- 具体实现而言,第一遍前半部分的dfs将可行金额存下来,第二遍对于现有金额val,查询m-val是否存在
- 其中有一个注意点,初见我是用set来存可行金额的,但众所周知set是由红黑树实现的,修改和查询时间复杂度\(O(\log n)\),总时间复杂度$ O(2^{n/2}*\log_{2}(n/2)) $,TLE的干脆利落
- 隔壁巨佬
用一顿饭的时间得出用哈希表的解法,可以O(1)查询,双哈希选的值要注意,实在不行三哈希。
到此本题结束。
这篇关于20210902PM的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南