Educational Codeforces Round 9

时间:2022-09-16 11:25:33

Educational Codeforces Round 9

Longest Subsequence

题目描述:给出一个序列,从中抽出若干个数,使它们的公倍数小于等于\(m\),问最多能抽出多少个数,并输出方案与公倍数。

solution
枚举每一个数,将它的倍数的答案加一,最大值就是答案。

时间复杂度:\(O(nlogn)\)

Thief in a Shop

题目描述:给出\(n\)中物品与它们的价值,每种物品都有无限个,问从中拿出\(m\)个,价值有可能是什么,输出所有的价值。

solution
快速幂+FFT
要注意的是这里只是判断是否有这一价值,所以每一次要把大于零的位置改为一,否则会爆long long
每一次FFT时取当前的最大长度,这样可以减少一个\(logn\)的复杂度。
我终于都看到FFT的龟速。

时间复杂度:\(O(10^3mlogm)\)

Educational Codeforces Round 9的更多相关文章

  1. [Educational Codeforces Round 16]E. Generate a String

    [Educational Codeforces Round 16]E. Generate a String 试题描述 zscoder wants to generate an input file f ...

  2. [Educational Codeforces Round 16]D. Two Arithmetic Progressions

    [Educational Codeforces Round 16]D. Two Arithmetic Progressions 试题描述 You are given two arithmetic pr ...

  3. [Educational Codeforces Round 16]C. Magic Odd Square

    [Educational Codeforces Round 16]C. Magic Odd Square 试题描述 Find an n × n matrix with different number ...

  4. [Educational Codeforces Round 16]B. Optimal Point on a Line

    [Educational Codeforces Round 16]B. Optimal Point on a Line 试题描述 You are given n points on a line wi ...

  5. [Educational Codeforces Round 16]A. King Moves

    [Educational Codeforces Round 16]A. King Moves 试题描述 The only king stands on the standard chess board ...

  6. Educational Codeforces Round 6 C. Pearls in a Row

    Educational Codeforces Round 6 C. Pearls in a Row 题意:一个3e5范围的序列:要你分成最多数量的子序列,其中子序列必须是只有两个数相同, 其余的数只能 ...

  7. Educational Codeforces Round 37

    Educational Codeforces Round 37 这场有点炸,题目比较水,但只做了3题QAQ.还是实力不够啊! 写下题解算了--(写的比较粗糙,细节或者bug可以私聊2333) A. W ...

  8. Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic Ship

    Problem   Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic Ship Time Limit: 2000 mSec P ...

  9. Educational Codeforces Round 60 (Rated for Div. 2) - D. Magic Gems(动态规划+矩阵快速幂)

    Problem   Educational Codeforces Round 60 (Rated for Div. 2) - D. Magic Gems Time Limit: 3000 mSec P ...

随机推荐

  1. 为什么这些java接口没有抽象方法?浅谈Java标记接口

    在jdk的源码中,存在这样的一些接口,他们不包含任何的(抽象)方法,但是却广泛的存在. 这种接口我们称之为Mark Interface,也就是标记接口. 这些接口呢,我们不用来实现任何的方法,他们的作 ...

  2. java mkdir()和mkdirs()的区别

    boolean mkdir()    创建此抽象路径名指定的目录.   boolean mkdirs()    创建此抽象路径名指定的目录,包括创建必需但不存在的父目录. 也就是说,mkdir只能创建 ...

  3. http://blog.csdn.net/chenriwei2/article/details/38047119

    SSP或者说是空间金字塔匹配(spatial pyramid matching or SPM)是BoW的一个扩展,它把一张图片划分为从不同的分辨率级别然后聚合这些不同分辨率的图像,在深度学习之前SPM ...

  4. MSSQL OPTION语句详解

    一些联合表查询语句,这些表里都建立有索引.在没有加 option ( force order ) 前,整个查询费时40多秒,但 单独表 查询基本不到1秒.查看查询计划后发现查询过程是从table n开 ...

  5. Spring Boot 内嵌Tomcat的端口号的修改

    操作非常的简单,不过如果从来没有操作过,也是需要查找一下资料的,所以,在此我简单的记录一下自己的操作步骤以备后用! 1:我的Eclipse版本,不同的开发工具可能有所差异,不过大同小异 2:如何进入对 ...

  6. MVC三和,你能辨别它?

    上次我们聊的时间MVC,而之前我们学习过三层.那么我们不禁就要问,他们说的是一回事吗.他们有什么联系吗? 三层架构(3-tier application)通常意义上的三层架构就是将整个业务应用划分为: ...

  7. 如何下载github项目中的部分文件(文件夹)

    https://minhaskamal.github.io/DownGit/#/home 将你要下载的链接放进去即可.

  8. iOS中 UITextView文本视图 技术分享

    UITextView: 文本视图相比与UITextField直观的区别就是UITextView可以输入多行文字并且可以滚动显示浏览全文. UITextField的用处多,UITextView的用法也不 ...

  9. [Swift]LeetCode937. 重新排列日志文件 | Reorder Log Files

    You have an array of logs.  Each log is a space delimited string of words. For each log, the first w ...

  10. DevExpress ChartControl ViewType.Line

    源码地址:https://files.cnblogs.com/files/lanyubaicl/ChartControl.Line.7z public partial class Form1 : Fo ...