Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
TCO19 SRM 743 Div1 解题记录
? 解题记录 ?
? Topcoder ?
? 贪心 ?
? 动态规划 ?
2019-02-26 11:24:38
340
0
0
rockdu
? 解题记录 ?
? Topcoder ?
? 贪心 ?
? 动态规划 ?
### Easy MaximizingGCD 题意：给你$2n$个数，问把他们两两配对求和形成的$n$个数$gcd$最大是多少。$n\le 30,a\le 10^9$ 题解：直接枚举$2n$个数的和的所有约数$d$，是否可以作为答案即可。验证方法是对原数组都模一个$d$，看一看可不可以拼成$n$个$d$。$O(n\sqrt{na})$ ### Medium ExpectedSum 题意：有一个长度为$n$的$int$数组$a$，有$p_i\%$的概率在$a_i$前加一个负号，问全局最大连续子段和的期望是多少。 $n,a_i\le 50$ 题解：$f(i,j,k)$表示到$i$最大子段和为$j$，最大后缀和为$k$的概率。$O(n^3a^2_i)$ ### Hard PermuteTheArray 题意：给你一个长度为$n$的数组$A$，你要找到这个数组的一个排列$P$，满足$m$个条件，形如$P_{x_i}+P_{y_i}=d_i(mod\ 2),d_i\in[0,1]$。请判断是否有解，如果有解那么输出字典序最小的。 题解：考虑每一个位置的关系构成一张图，显然这张图给出的信息很全面，对于任意一个连通块，我们考虑设一个点的奇偶性我们就可以推导出其他点的奇偶性，若中途出现冲突一定无解。否则我们可以得到两个点集$A,B$，它们的奇偶性相反。 剩下的考虑贪心，看一下奇数和偶数哪一个小，用一个$DP$判一下是否可行，因为一个位置奇偶性固定必定让另一些位置的奇偶性固定。总复杂度$O(n^3)$
上一篇:
TCO19 SRM 742 Div1 解题记录
下一篇:
TCO19 SRM 744 Div1 解题记录
0
赞
340 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册