noip模拟26[肾炎黄·酱累黄·换莫黄]
noip模拟26[肾炎黄·酱累黄·换莫黄]
noip模拟26solutions
这个题我做的确实是得心应手，为啥呢，因为前两次考试太难了
T1非常的简单，只不过我忘记了一个定理，
T2就是一个小小的线段树，虽然吧我曾经说过我再也不写树状数组了，但是我看见最长上升子序列就兴奋了
码了个树状数组就溜走了，用时仅为10min，60pts，组合拳
T3我就是nb
T1神炎皇
这个就是一个小小的推式子，让我给你推一推
a+b|a∗b,设d=gcd(a,b),x=a/d,y=b/d,所以x和y互质
我们有k∗(x+y)|x∗y∗d2<====>(x+y)|x∗y∗d
因为x，y互质所以（x+y）| d,设(x+y)=k
k∗d<=n并且k|d并且k<d，所以这样的d一共有nk2个
这种x与y互质，x+y为定值，你发现x与x+y也是互质的，所以每一个k对应的x+y都有ϕ(k)
k的范围是n−−√
那么接下来的事就只剩下线性筛了;
T2降雷皇
这个题真的是简单极了，我也没想到会有这么简单的题，打了个60分的组合拳就走了
最后发现这个用线段树维护一下就好了
毕竟是动态开点，而且这个电阻值只有1e5，完全不需要离散化，
对于每一种长度也就是最长上升子序列的长度建立一个线段树，
线段树的下标是电阻值，因为你查询的时候是按照电阻值来查询的
线段树中维护的权值即为方案数，这样遍历一遍这个序列，O(nlogn)就可以解决方案数了
最后直接输出最长长度的线段树的所有权值加和,说白了就是根节点的sum
T3幻魔皇
这整一棵树都充斥这非波那契数列，真的就直接倒就好了
其实还有更简单的O(n2)做法还比我的简单，比我的快
去看别人的博客吧，我这个非常难理解，
主要思路就是，首先枚举每一层，每一层的黑色节点和白色节点的类型都是一样的
黑色节点直接枚举左右儿子就行，白色节点就是直接用自己连接自己子树中的白色节点
注意黑色子树中有一个不符合规律的，就是这个黑色节点的白儿子，把这个拎出来单独算
·
分类: noip模拟测试
好文要顶 关注我 收藏该文 
fengwu2005
关注 - 6
粉丝 - 21
+加关注
1
0
« 上一篇： noip模拟25[random·string·queen]
posted @ 2021-07-28 20:09 fengwu2005 阅读(80) 评论(1) 编辑 收藏 举报
评论列表
回复 引用
#1楼 2021-07-28 20:33 -OMA-
%%%
支持(1) 反对(0)
刷新评论刷新页面返回顶部
发表评论
编辑预览
自动补全
退出 订阅评论 我的博客
[Ctrl+Enter快捷键提交]
【推荐】大型组态、工控、仿真、CAD\GIS 50万行VC++源码免费下载!
【推荐】阿里云云大使特惠：新用户购ECS服务器1核2G最低价87元/年
【推荐】投资训练营：一杯咖啡的价格，教你学会投资，增加被动收入
【推荐】加州大学伯克利分校高管教育：大数据与数学科学-在线课程
【推荐】和开发者在一起：华为开发者社区，入驻博客园科技品牌专区
编辑推荐：
· 我给鸿星尔克写了一个720°看鞋展厅
· 带团队后的日常（三）
· 你为什么不想向上汇报？
· 传统.NET 4.x应用容器化体验（4）
· CSS 世界中的方位与顺序
最新新闻：
· 在团购之后，抖音终于进军外卖了
· “教主”俞敏洪和他的四个风暴漩涡
· 谁都无法独善其身 芯片短缺影响到苹果、特斯拉
· 二季度财报亮眼，但特斯拉为什么开始“省钱”了？
· 我想买蔚来，我的腰说：不行
» 更多新闻...
公告
昵称： fengwu2005
园龄： 2年
粉丝： 21
关注： 6
+加关注
| <2021年7月> | ||||||
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|---|---|---|---|---|---|
| 27 | 28 | 29 | 30 | 1 | 2 | 3 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
随笔分类 (33)
noip模拟测试(25)
STL(2)
题解(6)
随笔档案 (50)
2021年7月(18)
2021年6月(17)
2021年5月(2)
2021年4月(3)
2021年3月(1)
2021年2月(2)
2020年10月(1)
2019年8月(1)
2019年7月(5)
hzoi比我小一届比我nb的大佬
史迪史
YinMX
hzoi同届的大佬们
大佬（AFO）
WindZR
Varuxn
OMA
zxb 人称笨B
LiBoyi
Max
sB
XieCoYu
JYFHYX
zero4338
zxs
XIN
XIN队
推荐排行榜
1. 线段树进阶学习笔记———动态开点、权值、线段树合并(4)
2. 多边形游戏——区间dp(4)
3. 回文词——线性dp(4)
4. 整数划分——区间dp（石子合并）(3)
5. 高精度算法总结(已完结)(3)
Copyright © 2021 fengwu2005
Powered by .NET 5.0 on Kubernetes