当前位置：网站首页>【8.7】代码源 - 【抽卡】【LCM与GCD】

【8.7】代码源 - 【抽卡】【LCM与GCD】

2022-08-08 16:28:00 【ZhgDgE】

#968. 抽卡

题意：

在这里插入图片描述
题解：UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) 部分题目题解

思路：考虑 DP 。先排一下序，然后定义 d p ( i , j ) dp(i,j) dp(i,j) 表示后 i i i 个字符串选择 j j j 个拼起来的最小字典序。 d p ( i , j ) = min ⁡ ( d p ( i + 1 , j ) , s i + d p ( i + 1 , j − 1 ) ) dp(i,j)=\min(dp(i+1,j),s_i+dp(i+1,j-1)) dp(i,j)=min(dp(i+1,j),si​+dp(i+1,j−1)) ，注意边界条件。

有两点要说的：

  1. 我们要按照 a + b < b + a a+b<b+a a+b<b+a 的方式排序，而不是 a < b a<b a<b 的方式。比如按照后者排序为 b , b a b,ba b,ba ，但是拼起来就不是字典序最小的。我们按照前者排序，就能保证 一个子集的最小字典序拼接方式的字符串 等于 这些字符串按照排序后的下标从左到右拼起来的字符串。
  2. 至于为什么倒着 DP ，大概是因为前面 i − 1 i-1 i−1 个字符串的最小字典序，和当前字符串拼起来，不一定是前 i i i 个字符串的最小字典序。不是很懂。

AC代码：http://oj.daimayuan.top/submission/325124

#953. LCM与GCD

题意：

在这里插入图片描述
思路：又是一个推公式题。等价于 x ⋅ a gcd ⁡ ( a , b ) ⋅ b gcd ⁡ ( a , b ) − y = k gcd ⁡ ( a , b ) x\cdot \frac a{\gcd(a,b)}\cdot \frac b{\gcd(a,b)}-y=\frac k {\gcd(a,b)} x⋅gcd(a,b)a​⋅gcd(a,b)b​−y=gcd(a,b)k​ ，容易知道 gcd ⁡ ( a , b ) \gcd(a,b) gcd(a,b) 一定是 k k k 的因子，根号枚举因子即可。

对于一个枚举的因子，我们再推公式： a gcd ⁡ ( a , b ) ⋅ b gcd ⁡ ( a , b ) = k gcd ⁡ ( a , b ) + y x = M \frac a{\gcd(a,b)}\cdot \frac b{\gcd(a,b)}=\frac{\frac k {\gcd(a,b)}+y}x=M gcd(a,b)a​⋅gcd(a,b)b​=xgcd(a,b)k​+y​=M ，问题转化为有多少对数互质且乘积为 M M M 。根号枚举计算质因子种类即可。

AC代码：http://oj.daimayuan.top/submission/325163

原网站

版权声明
本文为[ZhgDgE]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_51948235/article/details/126217884

边栏推荐

猜你喜欢

随机推荐