Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
TCO19 SRM 744 Div1 解题记录
? 解题记录 ?
? Topcoder ?
? 贪心 ?
2019-02-26 08:15:15
358
0
0
rockdu
? 解题记录 ?
? Topcoder ?
? 贪心 ?
### Easy ModularQuadrant 题意：一个无限大的矩形，$(r,c)位置的元素=max(r,c)\ mod 3$，查询一个子矩形内所有元素的和。 题解：格子内的值相当于到原点的切比雪夫距离模$3$。考虑把查询改成4个前缀矩形查询。一定分为一个正方形区域拼上一串长条。直接$O(1)$计算就好了。 ### Medium UniformingMatrix 题意：一个$n\times m$，"01"矩形。每一次可以选择一个格子，把同行同列的格子除了它本身全部翻转。问可不可以操作成全"1"。$n,m\le 100$ 题解：哇，思维僵化做不起了。注意到实际上行和列可以分开考虑。我们进行行列操作，只要行列操作个数的奇偶性相同就可以成功操作。 考虑先进行列操作，必须操作成对于一行来说都全是"0"或"1"才可以用行操作来进行。直接模拟就完了。 复杂度$O(nm)$ ### Hard CoverTreePaths 题意：给你一棵$N$个点的树。你要在每个点放置一些物品，使得对于每一个点$u$满足到根的路径上的物品总数$\le d_u$，其中$d_u$对于每个点给定。 其次每一个点放置物品的代价还不同，$c_u$为放一个物品在$u$的代价。 问满足条件的最小花费。$n\le 10^5$ 题解：直接考虑贪心，考虑如果每一个点都用祖先上最便宜的点来满足一定是可以有解的，但是不够优，因为会浪费很多物品。 那就很简单了，直接从根向下来贪心，每一次先看看还需要再放几个物品，然后全部放在最便宜的祖先上。 可以做到线性。 不知道对不对……
上一篇:
TCO19 SRM 743 Div1 解题记录
下一篇:
TCO19 SRM 746 Div1 解题记录
0
赞
358 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册