20180713NOIP模拟赛
2024-10-07 18:18:40
20180713NOIP模拟赛
T1:动物园 zoo.cpp 2s
- 【题目描述】
给定一张图,点有点权,求每个点到其他所有点中所有点的权值最小值之和。 - 【思路】
\(50pts\)做法:对于每个点跑一遍\(spfa\),对于每一遍\(spfa\)累加一下里面的答案,复杂度为\(O(nm)\)
\(100pts\)做法:考虑如何更简便的计算答案,我们发现对于路径必然处于原图的最大生成树上,边权取两端点点权的最小值,从大到小枚举树边,每次添加一条边,对于答案的贡献就是\(ans += siz[fx] * siz[fy] * e[i].w\),最后令\(ans\)乘2即可,复杂度为\(O(mlogm)。\)
T2:线段计数 segment.cpp 2s
- 【题目描述】
给定一些覆盖线段,支持删除第k次操作,求线段覆盖情况。 - 【思路】
\(30pts:\)模拟
\(100pts:\)树状数组,首先离散化,用两个树状数组,一个维护区间左端,一个维护区间右端,查询时用树状数组2中小于等于当前右端点的个数减去在树状
数组 1 中查询严格小于当前左端点的个数,复杂度\(O(nlogn)\)。
T3:填数游戏
- 【题目描述】
给定空矩阵和一些已经填了的数,只能天1或-1,求有多少种方案可以使得对于每个数的每一行或每一列乘积为-1\(?\) - 【思路】
30pts做法:dfs枚举。
10pts做法:当n+m为奇数时为0.
由于注意到$ k < max(n,m)$,则必然有一行或一列是完全空的假设空的是一行,除了这行其他行随便填,满足其他行的乘积都是-1,然后用这一行来收尾。显然其他行都满足后,这一行只有 1种填法。
70pts做法:由上面可得,用乘法原理直接计数。
100pts做法:设p为当前没有填的格子数,答案为\(2^p-1\).
最新文章
- Matlab2015基本语句语法04
- 关于int类型的赋值语句正确的有
- 我在 CSDN 的小窝
- 关于git不区分文件名大小写的处理
- Win7下使用Telnet命令
- POJ 1496
- git-daemon的快捷搭建
- JavaScript语言基础知识1
- Opencv 图像叠加 添加水印
- cookies和re
- Head First设计模式之原型模式
- python-时间模块,random、os、sys、shutil、json和pickle模块
- 跨浏览器的javascript事件的封装
- es6基础(7)--函数扩展
- centos网络配置(手动设置,自动获取)的2种方法3
- flex布局中transform出错
- Fedora 安装oracle11g 之最简洁方式
- 解决Eclipse中新建jsp文件总是以ISO8859-1编码问题
- 【week6】用户数
- Flask实战第65天:帖子按照发布时间和评论数量等排序
热门文章
- 【leetcode】977. Squares of a Sorted Array
- 【原理】RabbitMQ架构图
- Oracle删除修改字段
- 质数密度+思维——cf1174D
- AcWing 202. 最幸运的数字 (欧拉定理)打卡
- java.io.IOException: Could not find resource SqlMapConfig.xml
- 教你一些IDE中比较骚的操作技巧!
- 关于Visual Leak Detector的配置与使用 (测试vector 引起的内存泄漏问题)
- leetcode.字符串.409最长回文串-Java
- POJ 3259 Wormholes Bellman题解