noip模拟26
2022/6/7 23:23:00
本文主要是介绍noip模拟26,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
T1. LCIS
数组开小 100pts->60pts
蓝书原题,决策集合最优化\(O(n^2)\)
我用的树(状数组)套树(装数组) 与 值域优化对冲,导致达不到\(O(n ^ 2 (logn) ^2)\)的复杂度,lyin试图卡掉以失败告终
最坏复杂度\(O(n^2 logn )\),好多人\(O(n^4)\)跑得飞快
T2.物流运输
写的状压dp MLE 0pts
T3.tree
二分扰动值,给白边加上一个权值,从而使得扰动后的最小生成树满足条件
T4.建造游乐园
貌似是zr原题,
求欧拉图的个数
首先不考虑连通性,欧拉图个数 \(g_i = 2 ^{\binom{i-1}{2}}\),
由于对任意一个无向图,度数综合均为偶数,所以可以先生成\(i-1\)大小的任意图,将奇度点与\(i\)相连,便构成了一个欧拉图,不难发现这是一个双射
考虑连通性
\(f_i = g_i - (\text{不连通子图})\)
考虑\(i\)所在的连通块大小为\(j\)
\(\text{不连通子图} = \sum_{j=1} ^{i-1}{f_j *g_{i-j} * \binom{i-1}{j}}\),保证\(i\)与其他位置没有联系即可
这篇关于noip模拟26的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)