ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
DP
中等

【牛客】生蚝接柿子(单调队列dp)

链接:G-生蚝接柿子_"夜莺杯"武汉理工大学第四届新生程序设计竞赛 (nowcoder.com) 去年新生赛的一道题。 现在补一下。 分析 不难定义出状态dp[i][j]表示,到从下往上第i个柿子的时候,此时左手在j位置可以接到的最多柿子个数。 状态的转移也比较简单,dp[i][j] -> dp[i + 1][L ~ R],其中L, R是可以j到达的最远的位置。 当然从i - 1转移到i也可以,只 […]

2022年11月6日 0条评论 121点热度 0人点赞 Eriktse 阅读全文
中等

CCPC2021威海站部分题解 A D E G J M

比赛传送门:Dashboard - The 2021 CCPC Weihai Onsite - Codeforces A. Goodbye, Ziyin!(签到 + 树) 签到题。 给定一颗无根树(没有指定根的,意味着任何一点都可以为根),问有多少个点作为根可以使得整棵树为一颗二叉树。 对于签到的树题,一般都不需要建树,只需要记录度数。我们想一下二叉树的特征:根的度数\(\le 2\),其余点的度 […]

2022年10月9日 0条评论 176点热度 1人点赞 Eriktse 阅读全文
简单

[洛谷]P1521 求逆序对(DP)

题目传送门:P1521 求逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 / Thought 用dp[i]j[j]表示选取[1, i]的数组,且有j个逆序对的排列方案数。 dp[i]可以从dp[i - 1]转移过来,假设现在的数字是i,那么对于dp[i - 1]的所有状态,i可以插入到i个位置中去,如果插入到第1个位置,那么逆序对会增加i - 1个,如果插入第2个位 […]

2022年9月24日 0条评论 98点热度 0人点赞 Eriktse 阅读全文
中等

第46届ICPC国际大学生程序设计竞赛亚洲区域赛(上海)补题D E G I

题目传送门:第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛(上海) D Strange_Fractions(解方程,数论) 解方程,设\(t = \frac{b}{a}\),将方程两边同时乘\(t\)可以得到\(qt^2 - pt + q = 0\),通过小学二年级学的一元二次方程求根公式可知:当\(p^2 - 4q^2 \ge 0\)时方程有解。由求根公式可以得到\(t = \frac […]

2022年9月22日 0条评论 174点热度 1人点赞 Eriktse 阅读全文
中等

2022ICPC亚洲网络选拔赛L.LCS-like Problem(DP + 字符串)

可以在PTA补题。 题目大意 / Problem 给定两个字符串s和t,求一个s的子串s'使得s'和t的最大公共子串长度不超过1,问s'的最大长度。 子串可以不连续。 思路 / Thought 先把字符转换成[0, 25]的数字方便处理。 根据题意判断应该是个DP。由于是一个和位置和字符有关的dp,状态可以设为\(dp[i][j]\),表示到s的第i个位置为止,最后一个敏感字符(定义为存在于t中的 […]

2022年9月20日 0条评论 257点热度 1人点赞 Eriktse 阅读全文
中等

[AtCoder Beginner Contest 265]E - Warp(dp + set)

题目传送门:E - Warp (atcoder.jp) 题意 / Problem 在二维平面中,从原点(0, 0)出发,进行N次移动,每次移动可以选择3个方向,分别是从\((x, y)\)移动到\((x + A, y + B)、(x + C, y + D)、(x + E, y + F)\),只在整数点上运动。 有M个障碍点是不能走的。问N次移动后一共可以有多少种运动轨迹。 思路 / Thought […]

2022年8月24日 0条评论 163点热度 0人点赞 Eriktse 阅读全文
中等

[牛客竞赛]209809.乐团派对(线性DP)

题目传送门:乐团派对 (nowcoder.com) 思路 / Thought 首先对能力值数组进行排序,因为选人的时候顺序没要求,升序的话方便考虑,如果i可以组成乐队的话,比i小的肯定可以组成。 定义dp[i]表示到i为止可以组成的最大合法乐团数量。 接下来就可以写状态转移方程 第i个人,要么分到前面的乐队,要么分到后面的乐队。 但是第N个只能分到前面的乐队,所以输出的答案应该是dp[N - a[ […]

2022年8月23日 0条评论 108点热度 0人点赞 Eriktse 阅读全文
困难

[HDUOJ7191]Count Set(图论 + 排列组合 + NTT + 堆优化 + DP)

题目传送门:Problem - 7191 (hdu.edu.cn) 题目 / Problem 给定一个[1, n]的排列p和一个数字K,求[1, n]的子集T的个数。 子集T的大小为K,对于集合T中的任意一个元素x,p[x]不在该集合中。 思路 / Thought 排列的题很容易想到将i与p[i]连接起来,一定能组成若干个环,这里要求对于T中任意一个元素x,p[x]不能在T中,也就是说在若干个环中 […]

2022年8月12日 0条评论 190点热度 0人点赞 Eriktse 阅读全文
中等

[AtCoder Beginner Contest 263]F - Tournament(DFS记忆化搜索 + DP)

题目传送门:F - Tournament (atcoder.jp) 题意 / Problem 有\(2^N\)个人,从\(1 ~ N\)进行编号,进行N轮操作,每轮操作将第\(2i-1\)和第\(2i\)个人进行对战,每次对战都有一个人胜出,失败的人淘汰。 编号为i的人如果赢了j次,那么就可以获得\(C[i][j]\)的奖励。求所有人获得的最大的奖励之和。 思路 / Thought 显然是一颗完美 […]

2022年8月10日 0条评论 210点热度 0人点赞 Eriktse 阅读全文
中等

[AtCoder Beginner Contest 263]E - Sugoroku 3(期望DP)

题目传送门:E - Sugoroku 3 (atcoder.jp) 题目大意 / Problem 有N个点(位置),其中从1到N - 1个点上各有一个骰子,在第i个点上可以投掷第i个骰子,假设在x位置上投到y,下一步就走到y上。保证下一个位置不会大于N。 问从位置1到位置N的步数期望,对998244353。 思路 / Thought 之前有写过期望的题《[LightOJ]Race to 1 Aga […]

2022年8月7日 0条评论 205点热度 0人点赞 Eriktse 阅读全文
123

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

最新 热点 随机
最新 热点 随机
Git学习笔记[1]:基础指令和连接到Github hx的数列(数论) [Codeforces *2000]D. Doremy's Pegging Game(组合数学) [第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(昆明)]M.Stone Games(主席树)
[Codeforces *2100]D. Carry Bit(位运算 + 组合计数) [USACO 2006 Nov S]Bad Hair Day(单调栈) [POJ3695]Rectangles(容斥原理 + 离线 + 玄学) P2697 宝石串(前缀和 + 思维)
最近评论
MartinHou 发布于 3 个月前(10月27日) wwwwwwwE神
嫩爹 发布于 3 个月前(10月17日) 我的bfs呢
采集一直 发布于 4 个月前(09月27日) 虽然不太理解,但是我想通了,因为如果删除导致的合并会使得不能全部删除完,那么我肯定不会让它们合并(连...
采集一直 发布于 4 个月前(09月27日) 我感觉你这个线段树写的有问题,万一删除后合并的话,有效1会变化的,可能会减一
hesy 发布于 4 个月前(09月21日) 谢谢,帮助到了我
文章归档
  • 2022年12月
  • 2022年11月
  • 2022年10月
  • 2022年9月
  • 2022年8月
  • 2022年7月
  • 2022年6月
  • 2022年5月
  • 2022年4月
  • 2022年3月
  • 2022年2月
Search for Something!

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号