Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
TCO19 SRM 746 Div1 解题记录
? 解题记录 ?
? Topcoder ?
? 构造 ?
2019-02-25 17:21:51
341
0
0
rockdu
? 解题记录 ?
? Topcoder ?
? 构造 ?
### Easy ChangeDistances 题意：给定一个$n$个点的无向图$G$，要构造一个$n$个点的新无向图$H$满足对于任意点对$u,v$，在$G$中$dis(u,v)$不等于$H$中$dis(u,v)$。$n\le 50$ 题解：直接输出补图即可。 考虑证明： 在$G$中对于任意点$u$，对每个其它点$v$，若没有直接连边那么$v\in A$，否则$v\in B$。 那么显然$\forall v\in B, dis(u,v)=1$且$\forall v\in A, dis(u,v)\neq 1$ 考虑$H$中的$A'$以及$B'$，一定有$A'=B,B'=A$。 那么$dis(u,v)=1$的状态一定取反，必定不等。 得证 ### Medium FindStringHard 题意：你要构造一个长度小于等于$100$的串使得它的不回文子串恰好有$n$个。$n\le 1000$ 题解：考虑用$abababab$串。 一个$ababab$串，设有$k$个$ab$，那么有$k^2$个不回文串。 我们在分界处取反为$babababa$对整体答案没有影响。 就可以过了吧。 ### Hard SpaceProbes 题意：三维空间中你有两个卫星，一个卫星只能沿着一条直线移动，一条直线用两个点表示，为$x_i,y_i,z_i,i\in [0,3]$。每一次可以测量两个卫星连线的中点，有一颗行星在坐标$x_4,y_4,z_4$处，问你测量点离行星距离最近是多少。 题解：考虑一下中点一定有什么性质。画一画感觉中点应该都落在一个平面上，但是不会证。 要被亲爱的高中数学老师$jfy$吊打了。 首先一定可以找到一个平面让它平行于两条不相交直线。 然后感性理解一定落在"中平面"。 求出这个平面，用点到平面的距离算就行。 既然不会证让我们走近题解，就地感受： https://www.topcoder.com/blog/single-round-match-746-editorials/
上一篇:
TCO19 SRM 744 Div1 解题记录
下一篇:
TCO19 SRM 747 Div1 解题记录
0
赞
341 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册