ErikTse Runtime

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

[ABC234]D - Prefix K-th Max(set)

题目传送门:D - Prefix K-th Max (atcoder.jp) 题目大意 给定一个大小为N的排列,从第K个数字开始,每次求从开始到该数字为止的序列中的第K大的数字。 思路 如果是一个月前,我将会不知所措。但是最近atcoder出了好几个multiset和set的题目,于是不难想到用set这个神奇的数据结构。 因为set的插入和查询复杂度均为O(logN),所以可以很轻松地完成这道题。 […]

2022年3月29日 0条评论 580点热度 1人点赞 Eriktse 阅读全文
中等

[洛谷P2678][NOIP2015 提高组] 跳石头(二分 + 贪心)

题目链接:P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目大意就不说了,请看原题。 这道题我在很久之前就A了,昨天朋友问起发现自己还写错了几次,实在惭愧,今天记录一下这个思路。 思路 首先,如果已知撤走的石头,想要求最短距离,是不容易的,但是如果已知最短距离,求“一定要至少撤走多少个石头”可以通过遍历一遍,O(N)的复杂度算出 […]

2022年3月29日 0条评论 573点热度 0人点赞 Eriktse 阅读全文
中等

[ABC245]E - Wrapping Chocolate(multiset + 贪心)

题目链接:E - Wrapping Chocolate (atcoder.jp) 题目大意 有N个矩形巧克力,M个矩形盒子,一个盒子只能放最多一块巧克力,且巧克力的长和宽不能旋转,问能否装下。 思路 输入巧克力和盒子的数据,将巧克力的type设为1,盒子为0,将他们存在同一个数组里,数组大小为N + M。 将所有矩形(包括巧克力和盒子)按照宽度排降序,规则是宽更大的在左边,如果宽相同,则盒子在前, […]

2022年3月27日 0条评论 596点热度 0人点赞 Eriktse 阅读全文
技术分享

Devcpp5.4.0离线稳定版分享

在学习竞赛的过程中,环境搭建是一个比较头疼的事情,但是其实我们不需要那么复杂的操作,devcpp对于算法竞赛的学习已经足够了。 这里分享的devcpp5.4.0是离线且稳定的版本,无需安装,无需搭建环境,解压就可以直接使用。 下载地址:http://eriktse.kuaiyunds.com/eriktse/devcpp5.4.0.7z

2022年3月27日 0条评论 687点热度 0人点赞 Eriktse 阅读全文
中等

[ABC245]C - Choose Elements(DP)

题目传送门:C - Choose Elements (atcoder.jp) 题目大意 给定长度为N的整数序列 A 和 B ,能否构造出一个序列X,使得Xi = Ai or Bi,且| Xi - X(i-1) | <= K。 思路 这里用dp的思路,dp[i][0]表示能够从起点构造到第i位,并使Xi = Ai,dp[i][1]则表示Xi = Bi。 状态转移方程就是转移一下“到起点的连通性 […]

2022年3月27日 0条评论 547点热度 0人点赞 Eriktse 阅读全文
简单

[洛谷P2088] 果汁店的难题(贪心 + 模拟)

题目传送门:P2088 果汁店的难题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这是今天的一道练习题,我一看普及+/提高感觉蛮难的,其实想一下也还好。主要是数据非常小,复杂度是O(N ^ 2)。 题目大意请看原题。 思路 我们用used来表示某种水果被用在一个榨汁机里,具体在哪个榨汁机不重要。 cnt表示当前有多少个榨汁机里面是有东西的。 先将整个序列离线,然后遍历。如果水 […]

2022年3月25日 0条评论 509点热度 0人点赞 Eriktse 阅读全文
中等

[codeforces 729]C. Road to Cinema(前缀和 + 离线处理 + 二分)

题目链接:Problem - 729C - Codeforces 题目大意 现在俺在坐标为0的租车场要去一个电影院看电影,电影院在S点(一维数轴),电影T时刻开场。 我这里有很多车,每辆车有一个价格Ci和油箱容量Vi。 路上有K个加油站,每个加油站可以免费把油加满,车辆在起点时油箱是满的。 在路上有两种驾驶模式: 模式1:每1单位油走1公里,耗时2时间(正常模式) 模式2:每2单位油走1公里,耗时 […]

2022年3月25日 0条评论 553点热度 0人点赞 Eriktse 阅读全文
中等

[洛谷P2136]拉近距离(负权带环图SPFA)

题目传送门:P2136 拉近距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 在之前有写过spfa做的题《[NOIP2009]最优贸易(分层图论 + SPFA最长路) – ErikTse Runtime》,不过那道题比较复杂,本题是一道纯模板题。 思路 直接spfa,有几个点需要注意。 这里是单向图,根据题意,需要对d[1][N]和d[N][1]取小。 注意判环,方法是如果一 […]

2022年3月23日 0条评论 557点热度 0人点赞 Eriktse 阅读全文
中等

[AtCoder Beginner Contest 244]F - Shortest Good Path(DP + 图论)

题目传送门:F - Shortest Good Path (atcoder.jp) 啊shit,这题没做出来啊。这个dp状态属实想不到,之前写了好几次dfs都T了,看了题解才明白,用bfs好多了。 dfs无法保证第一个拓展到的点是长度最短的,但是bfs可以,然后下一次就不会拓展已经拓展了的点。于是bfs的复杂度比dfs低了很多。 题目大意 有一个N个点,M条无向边,现在有2^N条线路,分别是0 ~ […]

2022年3月21日 0条评论 612点热度 0人点赞 Eriktse 阅读全文
简单

[AtCoder Beginner Contest 244]E - King Bombee(DP动态规划)

题目传送门:E - King Bombee (atcoder.jp) 没错,就是一个纯纯的DP,难在状态表示。 一开始我也以为是图论,但是观察到特点:取模、数据范围、奇偶性、求方案数。这些可都是DP的显著特征啊,于是考虑使用dp。 题目描述请看原题,自己翻译一下。 思路 这题难就难在表示状态,我们用dp[i][j][k]表示第i个点,在时间j(时间就是在序列中的位置),走过x的次数为奇数或偶数(1 […]

2022年3月20日 0条评论 682点热度 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(主席树)
[POJ3695]Rectangles(容斥原理 + 离线 + 玄学) [牛客竞赛]生活在树上(图论 + 树) [USACO 2006 Nov S]Bad Hair Day(单调栈) [ABC245]E - Wrapping Chocolate(multiset + 贪心)
最近评论
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号